Online Nearest Neighbor Search Using Hamming Weight Trees.

Area of Science:

• Computer Science
• Data Structures
• Algorithms

Background:

• Nearest Neighbor Search (NNS) is a fundamental problem in computational geometry and data mining.
• Existing NNS methods face challenges with large-scale and dynamic datasets, particularly those involving binary data.
• The need for efficient proximity queries on evolving binary datasets is growing in various applications.

Purpose of the Study:

• To propose a new data structure, the Hamming Weight Tree, for solving NNS on dynamic binary data.
• To develop search algorithms tailored for the Hamming Weight Tree supporting both Hamming and angular distances.
• To evaluate the performance of the proposed methods against state-of-the-art large-scale NNS solutions.

Main Methods:

• Developed the Hamming Weight Tree, a novel tree-based data structure for partitioning binary string feature spaces.
• The partitioning strategy leverages the Hamming weights of binary codes and their substrings.
• Proposed two search algorithms designed for the Hamming Weight Tree to handle Hamming and angular distance metrics.

Main Results:

• Empirical results demonstrate significant speedups in nearest neighbor search performance.
• The proposed Hamming Weight Tree and its associated algorithms outperform existing large-scale NNS solutions.
• The data structure is effective for dynamic binary datasets where data points are added incrementally.

Conclusions:

• The Hamming Weight Tree offers an efficient and scalable solution for nearest neighbor search on dynamic binary data.
• The proposed approach provides a substantial performance improvement over current methods for large-scale binary datasets.
• This work contributes a valuable tool for applications requiring rapid proximity queries on binary information.