Making data structures persistent

DOI10.1016/0022-0000(89)90034-2zbMath0667.68026OpenAlexW4213048098WikidataQ30052803 ScholiaQ30052803MaRDI QIDQ1117690

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90034-2

zbMATH Keywords

binary search trees persistent data structures

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05) Algorithms in computer science (68W99)

Related Items (only showing first 100 items - show all)

Space-efficient functional offline-partially-persistent trees with applications to planar point location ⋮ Optimal window queries on line segments using the trapezoidal search DAG ⋮ Random access in persistent strings and segment selection ⋮ Zip-zip trees: making zip trees more balanced, biased, compact, or persistent ⋮ A Wait-free Queue with Polylogarithmic Step Complexity ⋮ Unnamed Item ⋮ Translating a regular grid over a point set ⋮ Online machine learning techniques for Coq: a comparison ⋮ Upper and lower bounds for fully retroactive graph problems ⋮ A constant update time finger search tree ⋮ Optimal external memory planar point enclosure ⋮ Sparse dominance queries for many points in optimal time and space ⋮ Minmax regret 1-facility location on uncertain path networks ⋮ Approximating points by a piecewise linear function ⋮ Simple confluently persistent catenable lists ⋮ Lower bounds for monotonic list labeling ⋮ Sequential vector packing ⋮ Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations ⋮ DATA STRUCTURES FOR RANGE-AGGREGATION OVER CATEGORIES ⋮ Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract) ⋮ Further results on generalized intersection searching problems: Counting, reporting, and dynamization ⋮ A sweepline algorithm for Voronoi diagrams ⋮ Orthogonal queries in segments ⋮ Dynamic state restoration using versioning exceptions ⋮ An Efficient Algorithm for the 1D Total Visibility-Index Problem and Its Parallelization ⋮ Parallel algorithms for arrangements ⋮ Sweep methods for parallel computational geometry ⋮ String indexing for top-\(k\) close consecutive occurrences ⋮ Making data structures persistent ⋮ Algorithms for generalized halfspace range searching and other intersection searching problems ⋮ A partially persistent data structure for the set-union problem ⋮ Finding pairwise intersections of rectangles in a query rectangle ⋮ Space reduction and an extension for a hidden line elimination algorithm ⋮ Queries on Voronoi diagrams on moving points ⋮ EERTREE: an efficient data structure for processing palindromes in strings ⋮ Efficient range searching for categorical and plain data ⋮ Nearest-neighbor searching under uncertainty. I ⋮ Parallel local search algorithms for high school timetabling problems ⋮ The space-optimal version of a known rectangle enclosure reporting algorithm ⋮ Indexing moving points ⋮ An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³ ⋮ Range queries on uncertain data ⋮ Confluently Persistent Tries for Efficient Version Control ⋮ Fully persistent B-trees ⋮ Dynamic fractional cascading ⋮ Optimal purely functional priority queues ⋮ Empty squares in arbitrary orientation among points ⋮ Unnamed Item ⋮ Simple and efficient LZW-compressed multiple pattern matching ⋮ Colored top-\(K\) range-aggregate queries ⋮ Unifications, deunifications, and their complexity ⋮ Dynamic Structures for Top-k Queries on Uncertain Data ⋮ Computing the map of geometric minimal cuts ⋮ Spiderman graph: visibility in urban regions ⋮ Using persistent data structures for adding range restrictions to searching problems ⋮ Efficient planar two-center algorithms ⋮ Linear-space data structures for range minority query in arrays ⋮ Counting Palindromes in Substrings ⋮ Multiple matching of parameterized patterns ⋮ Time-varying Reeb graphs for continuous space-time data ⋮ Maintaining dynamic sequences under equality tests in polylogarithmic time ⋮ New upper bounds for generalized intersection searching problems ⋮ Dynamic Planar Range Maxima Queries ⋮ A dynamic data structure for top-\(k\) queries on uncertain data ⋮ Computing homotopic line simplification ⋮ Data structures for halfplane proximity queries and incremental Voronoi diagrams ⋮ Efficient algorithms for the longest common subsequence in \(k\)-length substrings ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Improved output-sensitive snap rounding ⋮ Confluently persistent tries for efficient version control ⋮ Detecting regular visit patterns ⋮ Largest empty circle centered on a query line ⋮ Lower and upper bounds on obtaining history independence ⋮ Approximating nearest neighbor among triangles in convex position ⋮ Two-dimensional packet classification and filter conflict resolution in the internet ⋮ INTERSECTION PROBLEMS ON SEGMENTS UNDER BOUNDARY UPDATES WITH APPLICATION TO PERSISTENT LISTS ⋮ Unnamed Item ⋮ The partial visibility representation extension problem ⋮ Extensions of self-improving sorters ⋮ Optimal finger search trees in the pointer machine ⋮ Unnamed Item ⋮ Efficient Top-k Queries for Orthogonal Ranges ⋮ Range-Aggregate Queries Involving Geometric Aggregation Operations ⋮ I/O-efficient point location using persistent B-trees ⋮ Unnamed Item ⋮ Worst-case data structures for the priority queue with attrition ⋮ A parallel algorithm for finding a blocking flow in an acyclic network ⋮ New Data Structures for IP Lookup and Conflict Detection ⋮ Some Results for Elementary Operations ⋮ Unnamed Item ⋮ Isocontour based Visualization of Time-varying Scalar Fields ⋮ EFFICIENT NON-INTERSECTION QUERIES ON AGGREGATED GEOMETRIC DATA ⋮ Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines ⋮ From MDD to BDD and arc consistency ⋮ Approximate Range Queries for Clustering ⋮ Algorithms for generalized halfspace range searching and other intersection searching problems ⋮ Exponentially decreasing number of operations in balanced trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Programming Languages For Interactive Computing

Cites Work

This page was built for publication: Making data structures persistent