Adding range restriction capability to dynamic data structures

DOI10.1145/3828.3839zbMath0629.68097OpenAlexW1979630448MaRDI QIDQ3766892

Publication date: 1985

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3828.3839

zbMATH Keywords

range queries empirical cumulative distribution function decomposable searching problems trees of bounded balance

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items

An algorithm for handling many relational calculus queries efficiently., Computing rectangle enclosures, Computing a poset from its realizer, A technique for adding range restrictions to generalized searching problems, Online timestamped text indexing, On-line updating of solutions to a class of matroid intersection problems, Dynamic Euclidean minimum spanning trees and extrema of binary functions, Straight-path queries in trajectory data, Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract), Further results on generalized intersection searching problems: Counting, reporting, and dynamization, On the representation of the search region in multi-objective optimization, General methods for adding range restrictions to decomposable searching problems, Approximate covering detection among content-based subscriptions using space filling curves, Maintaining range trees in secondary memory. Part I: Partitions, Maintaining range trees is secondary memory. Part II: Lower bounds, Efficient splitting and merging algorithms for order decomposable problems, Connected component and simple polygon intersection searching, Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems, Fast algorithms for collision and proximity problems involving moving geometric objects, Space efficient data structures for dynamic orthogonal range counting, Maximum matchings in geometric intersection graphs, Dynamic orthogonal range queries in OLAP., Unnamed Item, Near-optimal quantum algorithms for string problems, Dynamic fractional cascading, Dynamic deferred data structuring, Hidden surface removal for rectangles, Efficient dynamic algorithms for some geometric intersection problems, Using persistent data structures for adding range restrictions to searching problems, Divided $k-d$ trees, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, New upper bounds for generalized intersection searching problems, Hidden surface removal for $c$-oriented polyhedra, Dynamic output-sensitive hidden surface removal for $c$-oriented polyhedra, Connected dominating sets on dynamic geometric graphs, Kinetic spanners in $\mathbb R^{d}$, Unnamed Item, A deterministic skip list for $k$-dimensional range search, Maintaining multiple representations of dynamic data structures, Independent sets and hitting sets of bicolored rectangular families, Efficient algorithms for finding a longest common increasing subsequence, Efficient Top-k Queries for Orthogonal Ranges, Approximate colored range and point enclosure queries, A new approach to the dynamic maintenance of maximal points in a plane, Resolving SINR Queries in a Dynamic Setting, Data structures in real-time environment, An application of $m$-ary trees to the design of data structures for geometric searching problems, Dynamic Trees and Dynamic Point Location, A data structure for dynamic range queries, Efficient splitting and merging algorithms for order decomposable problems., OPTIMAL FACILITY LOCATION UNDER VARIOUS DISTANCE FUNCTIONS, Towards using computational methods for real-time negotiations in electronic commerce