BROWSE
Detail
Conference Paper
Fast Parallel k-NN Search in High-Dimensional Spaces
Cited - time in 
Share 
Share
- Authors
- Hyun-Hwa Choi, Seung-Jo Bae, Kyu-Chul Lee
- Issue Date
- 2012-03
- Citation
- International Conference on Creative Content Technologies (CONTENT) 2012, pp.32-37
- Language
- English
- Type
- Conference Paper
- Abstract
- We are currently witnessing a rapid growth of image data, triggered by the popularity of the Internet and the huge amount of user-generated content from Web 2.0 applications. To address the demanding search needs caused by large-scale image collections, two major approaches for high-dimensional data in cluster systems have been proposed: Speeding up the search by using distributed index structures, and speeding up the search by scanning a Vector Approximation-file (VA-file) in parallel. We propose to combine both techniques to search for large k-nearest neighbors (k-NN) in a high-dimensional space. We develop a distributed index structure, called a Distributed Vector Approximation-tree (DVA-tree), with a two-level structure: the first level is a hybrid spill-tree consisting of minimum bounding spheres, the second level is VA-files. We also introduce a new approximate k-NN search algorithm on this structure and derive cost formulae for predicting the response time of the k-NN search. We then provide a detailed evaluation on large, high dimensional datasets. In an experimental evaluation, we show that our indexing scheme can handle approximate k-NN queries more efficiently for high-dimensional datasets.
- KSP Keywords
- Cluster system, Detailed evaluation, Distributed index structure, High dimensional datasets, High-dimensional space, Image collections, Image data, Indexing scheme, K-Nearest Neighbor(KNN), Large scale image, Level structure