I/O Efficient Algorithm for c-Approximate Furthest Neighbor Search in High-Dimensional Space
- Publisher:
- Springer International Publishing
- Publication Type:
- Conference Proceeding
- Citation:
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2020, 12114 LNCS, pp. 221-236
- Issue Date:
- 2020-01-01
Closed Access
Filename | Description | Size | |||
---|---|---|---|---|---|
Liu2020_Chapter_IOEfficientAlgorithmForC-Appro (1).pdf | Accepted version | 785.92 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 2020, Springer Nature Switzerland AG. Furthest Neighbor search in high-dimensional space has been widely used in many applications such as recommendation systems. Because of the “curse of dimensionality” problem, c-approximate furthest neighbor (C-AFN) is a substitute as a trade-off between result accuracy and efficiency. However, most of the current techniques for external memory are only suitable for low-dimensional space. In this paper, we propose a novel algorithm called reverse incremental LSH based on Indyk’s LSH scheme to solve the problem with theoretical guarantee. Unlike the previous methods using hashing scheme, reverse incremental LSH (RI-LSH) is designed for external memory and can achieve a good performance on I/O cost. We provide rigorous theoretical analysis to prove that RI-LSH can return a-AFN result with a constant possibility. Our comprehensive experiment results show that, compared with other-AFN methods with theoretical guarantee, our algorithm can achieve better I/O efficiency.
Please use this identifier to cite or link to this item: