Fast Nearest-Neighbor Search Algorithms Based on High-Multidimensional Data
Fast Nearest-Neighbor Search Algorithms Based on High-Multidimensional Data
- 인문사회과학기술융합학회
- 예술인문사회융합멀티미디어논문지
- 3권 1호
-
2013.0617 - 24 (8 pages)
- 0
Similarity search in multimedia databases requires an efficient support of nearest-neighbor search on a large set of high-dimensional points as a basic operation for query processing. As recent theoretical results show, state of the art approaches to nearest-neighbor search are not efficient in higher dimensions. In our new approach, we therefore pre-compute the result of any nearest-neighbor search which corresponds to a computation of the voronoi cell of each data point. In the second step, we store the voronoi cells in an index structure efficient for high-dimensional data spaces. As a result, nearest neighbor search corresponds to a simple point query on the index structure. Although our technique is based on a precipitation of the solution space, it is dynamic, i.e. it supports insertions of new data points. An extensive experimental evaluation of our tech-unique demonstrates the high efficiency for uniformly distributed as well as real data. We obtained a significant reduction of the search time compared to nearest neighbor search in the X-tree.
1. Introduction
2. Related Work
3. Implementation
4. Conclusion
References
(0)
(0)