25th International Conference on Database Systems for Advanced Applications

Sep. 24-27, 2020, Jeju, South Korea

Click following URL

http://dasfaa2020.sigongji.com

to visit DASFAA 2020 Online Event Site

Paper details

Title: I/O Efficient Algorithm for c-approximate Furthest Neighbor Search in High-dimensional Space

Authors: Wanqi Liu, Hanchen Wang, Ying Zhang, Lu Qin and Wenjie Zhang

Abstract: 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 c-AFN result with a constant possibility. Our comprehensive experiment results show that, compared with other c-AFN methods with theoretical guarantee, our algorithm can achieve better I/O efficiency.

Video file:

Slide file:

Sponsors