Name
Abstract | ||
|---|---|---|
Colored range queries are a well-studied topic in computational geometry and database research that, in the past decade, have found exciting applications in information retrieval. In this paper, we give improved time and space bounds for three important one-dimensional colored range queries - colored range listing, colored range top-k queries and colored range counting - and, as a consequence, new bounds for various document retrieval problems on general collections of sequences. Colored range listing is the problem of preprocessing a sequence S[1,n] of colors so that, later, given an interval [i,i+@?-1], we list the different colors in S[i,i+@?-1]. Colored range top-k queries ask instead for k most frequent colors in the interval. Colored range counting asks for the number of different colors in the interval. We first describe a framework including almost all recent results on colored range listing and document listing, which suggests new combinations of data structures for these problems. For example, we give the first compressed data structure (using nH"k(S)+o(nlog@s) bits, for any k=o(log"@sn), where H"k(S) is the k-th order empirical entropy of S and @s the number of different colors in S) that answers colored range listing queries in constant time per returned result. We also give an efficient data structure for document listing whose size is bounded in terms of the k-th order entropy of the library of documents. We then show how (approximate) colored top-k queries can be reduced to (approximate) range-mode queries on subsequences, yielding the first efficient data structure for this problem. Finally, we show how modified wavelet trees can support colored range counting using nH"0(S)+O(n)+o(nH"0(S)) bits, and answer queries in O(log@?) time. As far as we know, this is the first data structure in which the query time depends only on @? and not on n. We also show how our data structure can be made dynamic. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2012.08.004 | String Processing and Information Retrieval |
Keywords | Field | DocType |
Colored range listing,range counting,efficient data structure,Colored range top-k query,Colored range query,range listing,different color,document retrieval,Colored range counting,document listing,data structure | Data structure,Colored,Information retrieval,Computer science,Computational geometry,Range query (data structures),Wavelet Tree,Logarithm,Document retrieval,Bounded function | Journal |
Volume | ISSN | ISBN |
483, | 0304-3975 | 3-642-16320-3 |
Citations | PageRank | References |
39 | 0.95 | 57 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Travis Gagie | 1 | 643 | 63.61 |
| Juha Kärkkäinen | 2 | 1354 | 95.20 |
| Gonzalo Navarro | 3 | 6088 | 345.16 |
| Simon J. Puglisi | 4 | 1132 | 75.14 |