Lightweight Fingerprints for Fast Approximate Keyword Matching Using Bitwise Operations
Keywords:Fingerprint, keyword matching, approximate matching, bitwise
AbstractWe aim to speed up approximate keyword matching with the use of a lightweight, fixed-size block of data for each string, called a fingerprint. These work in a similar way to hash values; however, they can be also used for matching with errors. They store information regarding symbol occurrences using individual bits, and they can be compared against each other with a constant number of bitwise operations. In this way, certain strings can be deduced to be at least within the distance k from each other (using Hamming or Levenshtein distance) without performing an explicit verification. We show experimentally that for a preprocessed collection of strings, fingerprints can provide substantial speedups for k = 1, namely over 2.5 times for the Hamming distance and over 30 times for the Levenshtein distance. Tests were conducted on synthetic and real-world English and URL data.
Download data is not yet available.
How to Cite
Cisłak, A., & Grabowski, S. (2019). Lightweight Fingerprints for Fast Approximate Keyword Matching Using Bitwise Operations. COMPUTING AND INFORMATICS, 38(2), 367–389. https://doi.org/10.31577/cai_2019_2_367