Name
Abstract | ||
|---|---|---|
We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set S \subseteq U, where U = \{0,1,\dots,2^w-1\}, which support various queries for integer intervals of U. For the query of reporting all integers in S contained within a query interval, we present an optimal data structure with linear space cost and with query time linear in the number of integers reported. This result holds in the unit cost RAM model with word size w and a standard instruction set. We also present a linear space data structure for approximate range counting. A range counting query for an interval returns the number of integers in S contained within the interval. For any constant &egr;0, our range counting data structure returns in constant time an approximate answer which is within a factor of at most 1+&egr; of the correct answer. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1145/380752.380842 | STOC |
Keywords | Field | DocType |
approximate range counting,optimal data structure,various query,query interval,dimensional range,optimal static range reporting,integer interval,static data structure,linear space data structure,query time,data structure return,linear space,count data,data structure,probabilistic methods | Integer,Discrete mathematics,Data structure,Combinatorics,Instruction set,Range searching,Linear space,Probabilistic method,e,Word (computer architecture),Mathematics | Conference |
ISBN | Citations | PageRank |
1-58113-349-9 | 30 | 1.08 |
References | Authors | |
19 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephen Alstrup | 1 | 657 | 42.60 |
| Gerth Stølting Brodal | 2 | 1399 | 86.30 |
| Theis Rauhe | 3 | 661 | 35.11 |