Fast Nearest-Neighbor Search Algorithms Based on High-Multidimensional Data
Fast Nearest-Neighbor Search Algorithms Based on High-Multidimensional Data
- Rosslin John Robles
- 인문사회과학기술융합학회
- 예술인문사회융합멀티미디어논문지
- 3권 1호
- 2013.06
- 17 - 24 (8 pages)
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