Fast kNN graph construction

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 l...

Full description

Saved in:
Bibliographic Details
Main Author: Kassim Bin Mohamad Malaysia
Other Authors: Luo Siqiang
Format: Final Year Project
Language:English
Published: Nanyang Technological University 2024
Subjects:
Online Access:https://hdl.handle.net/10356/175305
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary: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.