Fast kNN Search in Weighted Hamming Space With Multiple Tables.

Area of Science:

• Computer Science
• Data Science
• Machine Learning

Background:

• Approximate Nearest Neighbor (ANN) search is crucial for big data, often using hashing for efficiency.
• Standard Hamming distance in hashing overlooks bit-level importance, impacting search accuracy.
• Existing weighted Hamming space methods rely on slow linear scans, unsuitable for large datasets.

Purpose of the Study:

• To develop an efficient and accurate k-Nearest Neighbor (kNN) search method in weighted Hamming space.
• To address the limitations of linear scans in existing weighted Hamming space ranking methods.
• To improve the performance of ANN search for big data applications.

Main Methods:

• Proposed Weighted Hamming space with Multiple Tables (WHMT) approach.
• Incorporated bit-level weight distribution into multi-index building.
• Developed an exact kNN search strategy without exhaustive linear scan.

Main Results:

• WHMT achieves optimal candidate set selection for exact kNN search in weighted Hamming space.
• The method avoids time-consuming exhaustive linear scans.
• Experimental results demonstrated a speedup of up to 69.8 times compared to linear scan baselines without accuracy loss.

Conclusions:

• WHMT offers a significant speedup for exact kNN search in weighted Hamming space.
• The proposed method enhances search accuracy by considering bit-level weights effectively.
• WHMT is a viable solution for efficient and accurate ANN search in large-scale datasets.