BWBEV: a bitwise query processing algorithm for approximate prefix search
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Moura, Edleno S. de
- dc.contributor.author Ferreira, Berg
- dc.contributor.author da Silva, Altigran
- dc.contributor.author Baeza Yates, Ricardo
- dc.date.accessioned 2025-10-07T06:10:51Z
- dc.date.available 2025-10-07T06:10:51Z
- dc.date.issued 2024
- dc.description.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.en
- dc.format.mimetype application/pdf
- dc.identifier.citation 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
- dc.identifier.doi http://dx.doi.org/10.5753/jbcs.2024.4236
- dc.identifier.issn 1678-4804
- dc.identifier.uri http://hdl.handle.net/10230/71410
- dc.language.iso eng
- dc.publisher Sociedade Brasileira de Computação
- dc.relation.ispartof Journal of the Brazilian Computer Society. 2024 Oct 27;30(1):527-41
- dc.rights 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.
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.rights.uri http://creativecommons.org/licenses/by/4.0/
- dc.subject.keyword Bit-parallelismen
- dc.subject.keyword Autocompleteen
- dc.subject.keyword Trieen
- dc.subject.keyword Error toleranceen
- dc.title BWBEV: a bitwise query processing algorithm for approximate prefix searchen
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/publishedVersion