Jason (jcreed) wrote,

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 log2 search time if you use the moderately clever version, and log time (with worse constants) if you use the strenuously clever version.
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded