New data structures for orthogonal range queries

Consider a set of $N$ records corresponding to points in $k$-dimensional space ($k \geqq 2$). This article introduces one new data structure which uses memory $O(N\log ^{k - 1} N)$ for supporting orthogonal range queries with worst-case complexity $O(\log ^{k - 1} N)$ and several modifications of th...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1985-02, Vol.14 (1), p.232-253
Main Author: WILLARD, D. E
Format: Article
Language:English
Subjects:
Aggregates
Algorithms
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Expected values
Information systems. Data bases
Memory organisation. Data processing
Queries
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider a set of $N$ records corresponding to points in $k$-dimensional space ($k \geqq 2$). This article introduces one new data structure which uses memory $O(N\log ^{k - 1} N)$ for supporting orthogonal range queries with worst-case complexity $O(\log ^{k - 1} N)$ and several modifications of this proposal for a dynamic environment. These results are especially useful when $k = 2$.
ISSN:0097-5397
1095-7111
DOI:10.1137/0214019