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

Abstract EN

In high-dimensional spaces, accuracy and similarity search by low computing and storage costs are always difficult research topics, and there is a balance between efficiency and accuracy.

In this paper, we propose a new structure Similar-PBF-PHT to represent items of a set with high dimensions and retrieve accurate and similar items.

The Similar-PBF-PHT contains three parts: parallel bloom filters (PBFs), parallel hash tables (PHTs), and a bitmatrix.

Experiments show that the Similar-PBF-PHT is effective in membership query and K-nearest neighbors (K-NN) search.

With accurate querying, the Similar-PBF-PHT owns low hit false positive probability (FPP) and acceptable memory costs.

With K-NN querying, the average overall ratio and rank-i ratio of the Hamming distance are accurate and ratios of the Euclidean distance are acceptable.

It takes CPU time not I/O times to retrieve accurate and similar items and can deal with different data formats not only numerical values.