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.

  • (no subject)

    Didn't sleep well. Long day of work. Dinner with akiva at hanamichi.

  • (no subject)

    K was going to do a thing for her dad's birthday, but scheduling kept slipping and slipping so I guess we're going to try doing it tomorrow instead.

  • (no subject)

    Had a pleasant lunch with paul and gabe back from working-at-facebook times. Discussed the important issues of the day, by which I mean video games…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded