Fast kNN graph construction

• Main Author: Kassim Bin Mohamad Malaysia
• Other Authors: Luo Siqiang
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2024
• Subjects: Engineering
• Online Access: https://hdl.handle.net/10356/175305
• Institution: Nanyang Technological University

This Final Year Project (FYP) report delves into a new Approximate Nearest Neighbor (ANN) searching algorithm, The Dense Graph- Parallel Approximate Nearest Neighbor Search Over Graphs (DG-PANN). It is an innovative enhancement of Parallel Approximate Nearest Neighbor Search Over Graphs (PANN). By leveraging a density-based strategy, DG-PANN has significantly accelerated the graph construction timing and improved the search query speed while maintaining relatively high recall values. Through thorough benchmarking with datasets such as Mnist and SensIT, DG-PANN has provided a better efficiency in both the graph construction phase and search query phase as compared to the traditional PANN. The results have revealed that DG-PANN particularly excels in high-dimensional environments but its performance in lower-dimensional datasets, especially in the search query phase, leaves for more room for improvements. This report details DG-PANN’s design, implementation, result analysis, offering its strength and weaknesses and future improvements that broaden DG-PANN’s capabilities.