Kleinberg's class was great again today. He blasted through explaining the results of this paper, which describes a way of probabilistically doing nearest-neighbor search that works well for medium-dimensional spaces (and degrades acceptably for high-dimensional spaces) but importantly works even on data that aren't nicely embeddable in an ambient (for example euclidean) space. Say, you've got a bunch of hosts on the internet and you know the latency between them pairwise. No ambient space, but the algorithm still works, with log² search time if you use the moderately clever version, and log time (with worse constants) if you use the strenuously clever version.