A Novel Accuracy and Similarity Search Structure Based on Parallel Bloom Filters

Area of Science:

• Computer Science
• Data Science
• Information Retrieval

Background:

• High-dimensional data presents challenges in balancing search accuracy with computational and storage efficiency.
• Existing methods often struggle to achieve both speed and precision in similarity searches.

Purpose of the Study:

• To propose a new data structure, Similar-PBF-PHT, for efficient representation and retrieval of similar items in high-dimensional spaces.
• To address the trade-off between efficiency and accuracy in similarity search.

Main Methods:

• The Similar-PBF-PHT structure combines parallel bloom filters (PBFs), parallel hash tables (PHTs), and a bitmatrix.
• The structure is designed for both membership queries and K-nearest neighbors (K-NN) search.

Main Results:

• The Similar-PBF-PHT demonstrates effectiveness in membership query and K-NN search.
• It achieves a low false positive probability (FPP) for accurate querying with acceptable memory usage.
• For K-NN search, it provides accurate Hamming distance ratios and acceptable Euclidean distance ratios.

Conclusions:

• The Similar-PBF-PHT structure offers an efficient solution for similarity search in high-dimensional data.
• It prioritizes CPU time over I/O, handles diverse data formats, and maintains accuracy and acceptable costs.