New algorithms on wavelet trees and applications to information retrieval

详细信息	查看全文 | 推荐本文 |

• 作者：Travis Gagie^a ; ^{travis.gagie@gmail.com} ; Gonzalo Navarro^b ; ^{gnavarro@dcc.uchile.cl} ; Simon J. Puglisi^c ; ^d ; ^{simon.puglisi@rmit.edu.au}
• 关键词：Information retrieval ; Document retrieval ; Data structures ; 1D range queries ; Wavelet trees
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：6 April, 2012
• 卷：426-427
• 期：Complete
• 页码：25-41
• 文件大小：351 K

摘要

Wavelet trees are widely used in the representation of sequences, permutations, text collections, binary relations, discrete points, and other succinct data structures. We show, however, that this still falls short of exploiting all of the virtues of this versatile data structure. In particular we show how to use wavelet trees to solve fundamental algorithmic problems such as range quantile queries, range next value queries, and range intersection queries. We explore several applications of these queries in Information Retrieval, in particular document retrieval in hierarchical and temporal documents, and in the representation of inverted lists.