Here's a story that illustrates how I'd like this to work, at least with regard to the encoding and the searching:
Alice tells Trent of a list of identities that she'd like to meet in real life, one of them is Bob, whom she's seen online, but never in real life. Trent agrees to send her a notification when one of them is nearby. At that point, they can chat online and mutually decide if they'd like to meet up or not.
Trent runs the public location database. He's a well-meaning do-no-harm kind of corporation, but deep down, neither Alice nor Bob nor anyone else in their right mind really trust him with all their location data. Even a company that is never evil could have its share of bad seeds and pitfalls, like a lurking serial-killer on the payroll or a secret court order.
Periodically, Alice encodes her location and uploads it to Trent. Bob also has an account with Trent and does the same. Both happen to be in midtown Manhattan this afternoon...
How can Trent tell Alice that Bob's within two city blocks (and vice-versa), knowing as little as possible of their whereabouts, if possible not much other than "Planet Earth", and couldn't tell you even if they had to.