1. BWBEV: A Bitwise Query Processing Algorithm for Approximate Prefix Search.
- Author
-
de Moura, Edleno S., Ferreira, Berg, da Silva, Altigran, and Baeza-Yates, Ricardo
- Subjects
SEARCH algorithms ,SUFFIXES & prefixes (Grammar) - Abstract
We tackle the challenge of conducting an approximate prefix search within datasets of strings. We explore using a bit-parallelism technique to compute the edit distance between distinct strings and illustrate its adaptation for an approximate prefix search procedure referred to as BWBEV. This technique employs a unary representation of edit vectors alongside bitwise operations to efficiently update these vectors during the edit distance computation. We also show how to apply our new bit-parallelism technique strategy to online edit distance computation between strings without index structure. Our experiments with BWBEV applied to approximate prefix search for a query autocompletion task revealed a substantial acceleration of over 36% when contrasted against state-of-the-art methods. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF