title: A Novel Accuracy and Similarity Search Structure Based on Parallel Bloom Filters.
abstract: 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 andK-nearest neighbors (K-NN) search. With accurate querying, the Similar-PBF-PHT owns low hit false positive probability (FPP) and acceptable memory costs. WithK-NN querying, the average overall ratio and rank-iratio 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.
authors.affiliation: Faculty of Electric Power Engineering, Kunming University of Science and Technology, Kunming 650051, China.
authors.forename: Chunyan
authors.identifier: 0000-0001-8282-2697
authors.initials: C
authors.lastname: Shuai
authors.affiliation: Faculty of Electric Power Engineering, Kunming University of Science and Technology, Kunming 650051, China.
authors.forename: Hengcheng
authors.initials: H
authors.lastname: Yang
authors.affiliation: Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650051, China.
authors.forename: Xin
authors.identifier: 0000-0002-5861-8503
authors.initials: X
authors.lastname: Ouyang
authors.affiliation: Faculty of Electric Power Engineering, Kunming University of Science and Technology, Kunming 650051, China.
authors.forename: Siqi
authors.identifier: 0000-0003-2085-4938
authors.initials: S
authors.lastname: Li
authors.affiliation: Faculty of Transportation Engineering, Kunming University of Science and Technology, Kunming 650051, China.
authors.forename: Zheng
authors.initials: Z
authors.lastname: Chen
mesh_terms: D000465:Algorithms; D016208:Databases, Factual; D006801:Humans; D016247:Information Storage and Retrieval; D010363:Pattern Recognition, Automated