| Title | Indexing in k-Nearest Neighbor Graph by Hash-Based Hill-Climbing |
| Publication Type | Conference Paper |
| Year of Publication | 2019 |
| Authors | Rattaphun, Munlika, Prayoonwong, Amorntip, Chiu, Chih- Yi |
| Conference Name | 2019 16th International Conference on Machine Vision Applications (MVA) |
| Keywords | Acceleration, approximate nearest neighbor search, approximation theory, Binary codes, Clustering algorithms, Euclidean distance, file organisation, GIST1M datasets, graph theory, hash-based hill-climbing, hashing, hashing-based seed generation, hill-climbing, Indexes, indexing, Inverted index, k-nearest neighbor graph, Measurement, Metrics, nearest neighbor graph, nearest neighbor search, nearest neighbour methods, principal component analysis, pubcrawl, query assignment process, query processing, search problems, SIFT1M datasets, Upper bound, vector quantization |
| Abstract | A main issue in approximate nearest neighbor search is to achieve an excellent tradeoff between search accuracy and computation cost. In this paper, we address this issue by leveraging k-nearest neighbor graph and hill-climbing to accelerate vector quantization in the query assignment process. A modified hill-climbing algorithm is proposed to traverse k-nearest neighbor graph to find closest centroids for a query, rather than calculating the query distances to all centroids. Instead of using random seeds in the original hill-climbing algorithm, we generate high-quality seeds based on the hashing technique. It can boost the query assignment efficiency due to a better start-up in hill-climbing. We evaluate the experiment on the benchmarks of SIFT1M and GIST1M datasets, and show the proposed hashing-based seed generation effectively improves the search performance. |
| DOI | 10.23919/MVA.2019.8758021 |
| Citation Key | rattaphun_indexing_2019 |
Indexing in k-Nearest Neighbor Graph by Hash-Based Hill-Climbing