A good search algorithm, then, needs a way to remember, on a per-npub basis, which relays are part of that npub's "public square."

If you go looking for someone, you start in the town square. If you can't find the fella in the square, you ask around, and people point you to this or that part of town where you might find the person.

It's six degrees of Kevin Bacon but for the internet. You don't need a direct link to everyone, you just need a large enough network that you can get to anyone else in six hops or less. And "large enough" isn't actually that large.

I bet one solution will be for search algorithms to live client-side. It needs to be attuned to each npub's network of connections, in order to more quickly find what that npub is probably looking for. There will be server-side algorithms as well, but those will probably solve a different problem.