A Functional Approach to Data Structures and Its Use in Multidimensional Searching
From MaRDI portal
Publication:4729345
DOI10.1137/0217026zbMath0679.68074OpenAlexW2085933841MaRDI QIDQ4729345
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217026
upper boundscomputational geometryfunctional programmingpointer machinerange searchintersection searchcomplexity of multidimensional searchinglinear-size data structuresrectangle problems
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computing methodologies and applications (68U99) Data structures (68P05) General topics in the theory of software (68N01)
Related Items
An algorithm for handling many relational calculus queries efficiently., Closest-pair queries and minimum-weight queries are equivalent for squares, Dynamic layers of maxima with applications to dominating queries, Efficient algorithms for the temporal precedence problem, Fast construction of wavelet trees, Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search, Finding Pairwise Intersections Inside a Query Range, Dynamic range majority data structures, Document listing on repetitive collections with guaranteed performance, On the difficulty of range searching, Discriminant analysis and density estimation on the finite d-dimensional grid, Longest common rollercoasters, Fractional cascading. II: Applications, EXTERNAL MEMORY ORTHOGONAL RANGE REPORTING WITH FAST UPDATES, Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing, Orthogonal queries in segments, Space-Efficient Frameworks for Top- k String Retrieval, Shortest paths among transient obstacles, A faster reduction of the dynamic time warping distance to the longest increasing subsequence length, Space Efficient Multi-dimensional Range Reporting, ROBUST NONPARAMETRIC SIMPLIFICATION OF POLYGONAL CHAINS, Indexing text using the Ziv--Lempel trie, Efficient range searching for categorical and plain data, Compressed property suffix trees, Space efficient data structures for dynamic orthogonal range counting, Space-efficient data-analysis queries on grids, Hamiltonian orthogeodesic alternating paths, Aggregate-MAX Top-k Nearest Neighbor Searching in the L1 Plane, Two-dimensional range successor in optimal time and almost linear space, An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3, Dynamic orthogonal range queries in OLAP., New algorithms on wavelet trees and applications to information retrieval, Elastic-degenerate string matching with 1 error, Unnamed Item, Unnamed Item, Biased range trees, Stronger Lempel-Ziv based compressed text indexing, Time-Optimal Top-$k$ Document Retrieval, Near-linear approximation algorithms for geometric hitting sets, Simplex Range Searching and Its Variants: A Review, Graph problems arising from parameter identification of discrete dynamical systems, Storing line segments in partition trees, Unnamed Item, Wavelet trees for all, On Dominance Reporting in 3D, Space efficient dynamic orthogonal range reporting, \(L_ 1\) shortest paths among polygonal obstacles in the plane, Rank and select revisited and extended, Filling gaps in the boundary of a polyhedron, Sequential and parallel algorithms for finding a maximum convex polygon, New upper bounds for generalized intersection searching problems, FAST ALGORITHMS FOR 3-D DOMINANCE REPORTING AND COUNTING, Finding pairwise intersections inside a query range, On the difficulty of range searching., Space-efficient construction of Lempel-Ziv compressed text indexes, OPTIMAL RANGE MAX DATACUBE FOR FIXED DIMENSIONS, A new framework for addressing temporal range queries and some preliminary results, Unnamed Item, A general approach for cache-oblivious range reporting and approximate range counting, A linear-space data structure for range-LCP queries in poly-logarithmic time, On the minimum total length of interval systems expressing all intervals, and range-restricted queries, Orthogonal range searching in linear and almost-linear space, Generalizing Geometric Graphs, The Level-Ancestor problem on pure pointer machines, Efficient Top-k Queries for Orthogonal Ranges, Selection from read-only memory with limited workspace, A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES, An algorithm for string matching with a sequence of don't cares, Approximate colored range and point enclosure queries, Resolving SINR Queries in a Dynamic Setting, Clustering, classification and image segmentation on the grid, Succinct and Implicit Data Structures for Computational Geometry, Orthogonal Range Searching for Text Indexing, Array Range Queries, Extending range queries and nearest neighbors, Chaining algorithms for multiple genome comparison, A new bound for map labeling with uniform circle pairs, The fine-grained complexity of multi-dimensional ordering properties, Unnamed Item, OPTIMAL FACILITY LOCATION UNDER VARIOUS DISTANCE FUNCTIONS, Fast and longest rollercoasters, A data structure for substring-substring LCS length queries
