# A data structure for orthogonal range queries

@article{Lueker1978ADS, title={A data structure for orthogonal range queries}, author={George S. Lueker}, journal={19th Annual Symposium on Foundations of Computer Science (sfcs 1978)}, year={1978}, pages={28-34} }

Given a set of points in a d-dimensional space, an orthogonal range query is a request for the number of points in a specified d-dimensional box. [...] Key Method Next we briefly discuss decision tree bounds on the complexity of orthogonal range queries. We show that a decision tree of height O(dn log n) (Where the implied constant does not depend on d or n) can be constructed to process n operations in d dimensions. This suggests that the standard decision tree model will not provide a useful method for… Expand

#### Topics from this paper

#### 228 Citations

A Data Structure for Dynamic Range Queries

- Computer Science
- Inf. Process. Lett.
- 1982

A dynamic data structure and algorithm which enable one to insert and delete points and to perform orthogonal range queries and is faster than the best previous algorithm by a factor of log n. Expand

New data structures for orthogonal range searching

- Mathematics, Computer Science
- Proceedings 41st Annual Symposium on Foundations of Computer Science
- 2000

New general techniques for static orthogonal range searching problems in two and higher dimensions are presented and query time O(log n) using space O(n log n) is achieved. Expand

Compact and succinct data structures for multidimensional orthogonal range searching

- Computer Science, Mathematics
- Inf. Comput.
- 2020

Compact and succinct representations of a d-dimensional point set for any constant d ≥ 3 supporting orthogonal range searching are introduced and the algorithm runs fast in practical database search. Expand

Priority Range Trees

- Mathematics, Computer Science
- ISAAC
- 2010

A data structure, called a priority range tree, which accommodates fast orthogonal range reporting queries on prioritized points, which is motivated by the Weber–Fechner Law, which states that humans perceive and interpret data on a logarithmic scale. Expand

A Lower Bound on the Complexity of Orthogonal Range Queries

- Mathematics, Computer Science
- JACM
- 1981

It is shown here that fi(n(logn) ~) is a lower bound on the inherent worst case time reqmred to process a sequence of n intermixed insemons, deleuons, and range queries, which imphes that the Lueker and Wdlard data structures are in some sense optimal. Expand

A Succinct Data Structure for Multidimensional Orthogonal Range Searching

- Mathematics, Computer Science
- 2017 Data Compression Conference (DCC)
- 2017

A succinct representations of a d-dimensional point setsupporting orthogonal range searching under two circumstances is introduced and a succinct representation of the point set which requires dn lg U + o( n lg n) bits is proposed while supporting these queries in the same time complexity as that in rank space. Expand

Untangled monotonic chains and adaptive range search

- Computer Science
- Theor. Comput. Sci.
- 2011

This work presents the first adaptive data structure for two-dimensional orthogonal range search, and presents a novel algorithm of independent interest to decompose a point set into a minimum number of untangled, same-direction monotonic chains in O(kn + n log n) time. Expand

Space efficient dynamic orthogonal range reporting

- Computer Science
- SCG
- 2005

This paper presents new space e cient dynamic data structures for orthogonal range reporting and presents a dynamic data structure for d -dimensional range reporting with search time O, update time O (log d n ), and space O (n log d .2+e n ) for any e > 0. Expand

Odds-On Trees

- Computer Science, Mathematics
- ArXiv
- 2010

A data structure called the odds-on tree is described, of size O(n^\epsilon) that can be used as a filter that quickly computes P(q) for some query values q in R^d and relies on S for the remaining queries. Expand

Path Queries in Weighted Trees

- Mathematics, Computer Science
- ISAAC
- 2011

A linear space data structure is presented that answers path reporting queries in $O(\lg \sigma + occ \lg\lgg\sigma)$ time, which are the first data structures that answer path reporting queries under the word RAM model. Expand

#### References

SHOWING 1-10 OF 19 REFERENCES

A survey of algorithms and data structures for range searching

- Computer Science
- 1978

A set of “loGical structures” is described and ‘then their implementation in primary and secondary memories is discussed, and a set of algorithms for efficiently answering range queries are surveyed. Expand

Partial-Match Retrieval Algorithms

- Computer Science
- SIAM J. Comput.
- 1976

A new class of combinatorial designs (called associative block designs) provides better hash functions with a greatly reduced worst-case number of lists examined, yet with optimal average behavior maintained. Expand

Multidimensional binary search trees used for associative searching

- Mathematics, Computer Science
- CACM
- 1975

The multidimensional binary search tree (or <italic>k-d tree) as a data structure for storage of information to be retrieved by associative searches is developed and it is shown to be quite efficient in its storage requirements. Expand

Divide-and-conquer in multidimensional space

- Mathematics, Computer Science
- STOC '76
- 1976

A divide-and-conquer technique in multidimensional space is investigated which decomposes a geometric problem into two problems on N/2 points in k dimensions plus a single problem in k−1 dimension to obtain an algorithm for finding the two closest of N points in 0(N log N) time in any dimension. Expand

Binary search trees of bounded balance

- Mathematics, Computer Science
- STOC
- 1972

A new class of binary search trees, called trees of bounded balance, is introduced. These trees are easy to maintain in their form despite insertions and deletions of nodes, and the search time is… Expand

A Problem in Multivariate Statistics: Algorithm, Data Structure and Applications.

- Computer Science
- 1978

A multidimensional divide-and-conquer technique is employed that gives rise to a compact data structure for geometric and statistical search problems and a large number of important statistical quantities are computed much faster than was previously possible. Expand

Multidimensional Searching Problems

- Mathematics, Computer Science
- SIAM J. Comput.
- 1976

Classic binary search is extended to multidimensional search problems. This extension yields efficient algorithms for a number of tasks such as a secondary searching problem of Knuth, region location… Expand

AN ALGORITHM FOR THE ORGANIZATION OF INFORMATION

- Computer Science
- 1963

The organization of information placed in the points of an automatic computer is discussed and the role of memory, storage and retrieval in this regard is discussed. Expand

Note Added August

- Note Added August
- 1978

Private Communication, August 1978. Jon Bentley and Jerome Friedman, "Algorithms and Data Structures for Range Searching,

- Proceedings of the Computer Science
- 1978