Fast kNN graph construction - Kassim Bin Mohamad Malaysia (Nanyang Technological University, 2024)
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.