A data structure for dynamic range queries

DOI10.1016/0020-0190(82)90119-3zbMath0511.68080MaRDI QIDQ1838844

George S. Lueker, Dan E. Willard

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://escholarship.org/uc/item/9k40c7jc

zbMATH Keywords

data structures; searching; range queries; file organization; data base management; bounded balance trees

Mathematics Subject Classification ID

68P05: Data structures

68P20: Information storage and retrieval of data

Related Items

An application of $m$-ary trees to the design of data structures for geometric searching problems, Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Dynamic Euclidean minimum spanning trees and extrema of binary functions, A deterministic skip list for \(k\)-dimensional range search, An algorithm for handling many relational calculus queries efficiently., An optimal time and minimal space algorithm for rectangle intersection problems

Cites Work

• Unnamed Item
• Multidimensional divide-and-conquer
• Decomposable searching problems
• New Data Structures for Orthogonal Range Queries
• Adding range restriction capability to dynamic data structures
• Quintary trees
• A Lower Bound on the Complexity of Orthogonal Range Queries
• Binary Search Trees of Bounded Balance