Optimizing BEVA with Two-Level Indexes
Indisponível
| Autor principal: | Ferreira, Van Den Berg da Gama |
|---|---|
| Outros Autores: | http://lattes.cnpq.br/9433225118102294 |
| Grau: | Dissertação |
| Idioma: | por |
| Publicado em: |
Universidade Federal do Amazonas
2020
|
| Assuntos: | |
| Acesso em linha: |
https://tede.ufam.edu.br/handle/tede/7840 |
| id |
oai:https:--tede.ufam.edu.br-handle-:tede-7840 |
|---|---|
| recordtype |
dspace |
| spelling |
oai:https:--tede.ufam.edu.br-handle-:tede-78402023-01-10T05:04:17Z Optimizing BEVA with Two-Level Indexes Otimizando o BEVA com índices de dois níveis Ferreira, Van Den Berg da Gama Moura, Edleno Silva de Moura http://lattes.cnpq.br/9433225118102294 http://lattes.cnpq.br/4737852130924504 Silva, Altigran Soares da http://lattes.cnpq.br/3405503472010994 Rosa, Thierson Couto http://lattes.cnpq.br/4414718560764818 CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Query processing Error-tolerant Autocompletion Two level Trie Programação de sistemas (Computação) Programas de computador - Precisão Indisponível Query autocompletion is an important component of modern search systems that suggests possible queries at each user keystroke to complete the query based on the prefix already typed in the search box. One of the most adopted and successful data structures for query autocompletion is the TRIE which is used to index the possible query suggestions. The TRIE is traversed based on the search prefix typed by the user in order to select suggestions that match the prefix. The use of TRIEs requires a large amount of extra memory for processing queries, which may increase the cost for processing queries and may limit the number of query suggestions indexed. In this work we propose optimized alternative implementations of BEVA algorithm, currently the state-of-the-art in the literature for autocompletion, in order to achieve a reduction in its memory consumption while keeping it efficient in query processing times. First, we propose a novel strategy to build the TRIE, named level-at-a-time (laat), and compare its performance to the way TRIEs are usually built, the key-ata-time (kaat). In the kaat strategy the index is built in depth-ward direction and in the laat strategy the index is built in breadth-ward direction. We implemented the proposed ideas and experimented them with several datasets, where we show that laat strategy allows a significant speedup in query processing of BEVA, being up to four times faster, with improvements achieved specially in queries with high number of errors, which are the most expensive ones. Second, we study the use of two-level indexing and prefix processing approaches for query autocompletion also in BEVA method. Two-level approaches combine the use of indexes with sequential search in order to reduce memory requirements in search systems. In our study, we insert in the TRIE only part of each query inserted, and the leaf nodes reference to a set of queries where a sequential search is performed. We experimented two alternative ways of selecting the portion of each key that remains indexed in the first level and compare their performance. The two-level approach has shown to significantly reduce the memory requirements for storing the index with just a small variation in query processing times 2020-07-22T15:27:57Z 2020-07-10 Dissertação FERREIRA, Van Den Berg. Optimizing BEVA with Two-Level Indexes. 2020. 89 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus, 2020. https://tede.ufam.edu.br/handle/tede/7840 por Acesso Aberto http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Universidade Federal do Amazonas Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática |
| institution |
TEDE - Universidade Federal do Amazonas |
| collection |
TEDE-UFAM |
| language |
por |
| topic |
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Query processing Error-tolerant Autocompletion Two level Trie Programação de sistemas (Computação) Programas de computador - Precisão |
| spellingShingle |
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Query processing Error-tolerant Autocompletion Two level Trie Programação de sistemas (Computação) Programas de computador - Precisão Ferreira, Van Den Berg da Gama Optimizing BEVA with Two-Level Indexes |
| topic_facet |
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Query processing Error-tolerant Autocompletion Two level Trie Programação de sistemas (Computação) Programas de computador - Precisão |
| description |
Indisponível |
| author_additional |
Moura, Edleno Silva de Moura |
| author_additionalStr |
Moura, Edleno Silva de Moura |
| format |
Dissertação |
| author |
Ferreira, Van Den Berg da Gama |
| author2 |
http://lattes.cnpq.br/9433225118102294 |
| author2Str |
http://lattes.cnpq.br/9433225118102294 |
| title |
Optimizing BEVA with Two-Level Indexes |
| title_short |
Optimizing BEVA with Two-Level Indexes |
| title_full |
Optimizing BEVA with Two-Level Indexes |
| title_fullStr |
Optimizing BEVA with Two-Level Indexes |
| title_full_unstemmed |
Optimizing BEVA with Two-Level Indexes |
| title_sort |
optimizing beva with two-level indexes |
| publisher |
Universidade Federal do Amazonas |
| publishDate |
2020 |
| url |
https://tede.ufam.edu.br/handle/tede/7840 |
| _version_ |
1831969881728221184 |
| score |
11.753735 |