2026-04-18T07:58:20Zhttps://recercat.cat/oai/request

oai:recercat.cat:10230/714102025-10-10T19:28:02Zcom_2072_6col_2072_452952

BWBEV: a bitwise query processing algorithm for approximate prefix search Moura, Edleno S. de Ferreira, Berg da Silva, Altigran Baeza Yates, Ricardo Bit-parallelism Autocomplete Trie Error tolerance 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. 2025-10-07T06:10:51Z 2025-10-07T06:10:51Z 2024 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion de Moura ES, Ferreira B, da Silva A, Baeza-Yates R. BWBEV: a bitwise query processing algorithm for approximate prefix search. Journal of the Brazilian Computer Society. 2024 Oct 27;30(1):527-41. DOI: 10.5753/jbcs.2024.4236 1678-4804 http://hdl.handle.net/10230/71410 http://dx.doi.org/10.5753/jbcs.2024.4236 http://hdl.handle.net/10230/71410 eng Journal of the Brazilian Computer Society. 2024 Oct 27;30(1):527-41 Copyright (c) 2024 Edleno S. de Moura, Berg Ferreira, Altigran da Silva, Ricardo Baeza-Yates. This work is licensed under a Creative Commons Attribution 4.0 International License. http://creativecommons.org/licenses/by/4.0/ info:eu-repo/semantics/openAccess application/pdf application/pdf Sociedade Brasileira de Computação