Grid-Based Indexing and Search Algorithms for Large-Scale and High-Dimensional Data

• Main Authors: Chuanfu Yang, Zhiyang Li, Wenyu Qu, Zhaobin Liu, Heng Qi
• Format: Conference Proceeding
• Language: English
• Subjects: Approximate Nearest Neighbor Search; Clustering algorithms; High-dimensional data; Indexing; Large-scale Data; Nearest neighbor searches; Partitioning algorithms; Quantization (signal)
• ISSN: 2375-527X
• DOI: 10.1109/ISPAN-FCST-ISCC.2017.85

The rapid development of Internet has resulted in massive information overloading recently. These information is usually represented by high-dimensional feature vectors in many related applications such as recognition, classification and retrieval. These applications usually need efficient indexing and search methods for such large-scale and high-dimensional database, which typically is a challenging task. Some efforts have been made and solved this problem to some extent. However, most of them are implemented in a single machine, which is not suitable to handle large-scale database.In this paper, we present a novel data index structure and nearest neighbor search algorithm implemented on Apache Spark. We impose a grid on the database and index data by non-empty grid cells. This grid-based index structure is simple and easy to be implemented in parallel. Moreover, we propose to build a scalable KNN graph on the grids, which increase the efficiency of this index structure by a low cost in parallel implementation. Finally, experiments are conducted in both public databases and synthetic databases, showing that the proposed methods achieve overall high performance in both efficiency and accuracy.