Approximation Techniques to Enable Dimensionality Reduction for Voronoi-based Nearest Neighbor Search

Utilizing spatial index structures on secondary memory for nearest neighbor search in high-dimensional data spaces has been the subject of much research. With the potential to host larger indexes in main memory, applications demanding a high query throughput stand to benefit from index structures tailored for that environment. “Index once, query at very high frequency” scenarios on semi-static data require particularly fast responses while allowing for more extensive precalculations. One such precalculation consists of indexing the solution space for nearest neighbor queries as used by the approximate Voronoi cell-based method. A major deficiency of this promising approach is the lack of a way to incorporate effective dimensionality reduction techniques. We propose methods to overcome the difficulties faced for normalized data and present a second reduction step that improves response times through limiting the dimensionality of the Voronoi cell approximations. In addition, we evaluate the suitability of our approach for main memory indexing where speedup factors of up to five can be observed for real world data sets.

Authors: Brochhaus C., Wichterich M., Seidl T.
Published in: In Ioannidis Y. et al. (Eds.): Advances in Database Technology - Proc. 10th International Conference on Extending Data Base Technology (EDBT 2006), Munich, Germany. Springer LNCS 3896
Publisher: Springer - Heidelberg,Germany
Sprache: EN
Jahr: 2006

(acceptance rate 16%)

Seiten: 204-221
ISBN: 9783540329602
Konferenz: EDBT
LNCS 3896
Typ: Tagungsbeiträge
Forschungsgebiet: Exploration of Multimedia Databases