-
Metric Skip Lists
2003-12-09 10:39 in /tech/nips
From yesterday, metric skip lists are the data structure presented for approximate nearest neighbor searching. I wanted to estimate the space required for this data structure a little more precisely. The scaling was O(n log n). Specifically, in the case considered, there are 16 pointers for each octave of distance for each point assuming the data fits on a 2-d manifold in some sense. 16 = 4^2.
So, if n = 1 000 000 ~ 2^20, we require 16 * 20 * 1000000 * 4 bytes = 1.3GB.
If n = 10 000 000 ~ 2^23, we need 16 * 23 * 10 000 000 * 4 = 15 GB.
So, this doesn't actually seem so useful.
Leave a comment
Please use plain text only. No HTML tags are allowed.
Comments are closed for this story.
Trackbacks are closed for this story.