Down the Rabbit Hole: Robust Proximity Search in Sublinear Space

Details Down the Rabbit Hole: Robust Proximity Search in Sublinear Space Down the Rabbit Hole: Robust Proximity Search in Sublinear Space

2011-11-12

arxiv.org/abs/1111.2942v1

Computer Science

Computational Geometry

Scientific paper

For a set of n points in $\Re^d$, and parameters k and {\epsilon}, we present a data structure that answers (1 + {\epsilon})-approximate k nearest neighbor queries in logarithmic time. Surprisingly, the space used by the data-structure is O(n/k), that is, the space used is sublinear in the input size if k is sufficiently large. Our approach provides a novel way to summarize geometric data, such that meaningful proximity queries on the data can be carried out using this sketch.

Affiliated with

Also associated with

No associations

Rating

Down the Rabbit Hole: Robust Proximity Search in Sublinear Space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Down the Rabbit Hole: Robust Proximity Search in Sublinear Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Down the Rabbit Hole: Robust Proximity Search in Sublinear Space will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-3298