Making data structures persistent
Making a change in an ordinary data structure destroys the old version, leaving only the new one. This paper investigates the problem of realizing persistent data structures in the sense that all the versions in the history of the data structure are available for use. Two kind of persistence are identified: partial persistence in which only the newest version may be updated and fully persistence in which an update operation may apply to any version. The authors study the case of linked data structures for which they propose two paradigms for making them persistent. These techniques are used to devise persistent forms of binary search trees with efficient implementations of the access, insertion and deletion operations.
- A new data structure for representing sorted lists
- Amortized Computational Complexity
- An applicative random-access stack
- AVL-trees for localized search
- Binary Search Trees of Bounded Balance
- Decomposable searching problems I. Static-to-dynamic transformation
- Design and Analysis of a Data Structure for Representing Sorted Lists
- Filtering Search: A New Approach to Query-Answering
- Fractional cascading. I: A data structuring technique
- How to search in history
- scientific article; zbMATH DE number 3911764 (Why is no real title available?)
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 3716818 (Why is no real title available?)
- Maintaining order in a generalized linked list
- Making data structures persistent
- On the average number of rebalancing operations in weight-balanced trees
- Organization and maintenance of large ordered indexes
- Searching and storing similar lists
- Updating a balanced search tree in 0(1) rotations
- Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines
- A sweepline algorithm for Voronoi diagrams
- Making data structures persistent
- Space reduction and an extension for a hidden line elimination algorithm
- Unifications, deunifications, and their complexity
- Worst-case data structures for the priority queue with attrition
- A parallel algorithm for finding a blocking flow in an acyclic network
- Visibility with a moving point of view
- Speeding up dynamic transitive closure for bounded degree graphs
- A constant update time finger search tree
- Orthogonal queries in segments
- The space-optimal version of a known rectangle enclosure reporting algorithm
- Indexing moving points
- Parallel local search algorithms for high school timetabling problems
- A space efficient variant of path copying for partially persistent sorted sets
- Translating a regular grid over a point set
- Parallel algorithms for arrangements
- Sweep methods for parallel computational geometry
- Algorithms for generalized halfspace range searching and other intersection searching problems
- Queries on Voronoi diagrams on moving points
- Faster approximate diameter and distance oracles in planar graphs
- On the planar two-center problem and circular hulls
- Online machine learning techniques for Coq: a comparison
- String indexing for top-\(k\) close consecutive occurrences
- Finding pairwise intersections of rectangles in a query rectangle
- Fully persistent B-trees
- Efficient planar two-center algorithms
- Computing homotopic line simplification
- Efficient algorithms for the longest common subsequence in \(k\)-length substrings
- Two-dimensional packet classification and filter conflict resolution in the internet
- Extensions of self-improving sorters
- From MDD to BDD and arc consistency
- Approximating points by a piecewise linear function
- Sequential vector packing
- Nearest-neighbor searching under uncertainty. I
- Simple and efficient LZW-compressed multiple pattern matching
- Colored top-\(K\) range-aggregate queries
- Improved output-sensitive snap rounding
- Lower and upper bounds on obtaining history independence
- Exponentially decreasing number of operations in balanced trees
- Algorithms for three-dimensional dominance searching in linear space.
- Empty squares in arbitrary orientation among points
- Making data structures confluently persistent. (Extended abstract)
- Programming languages for interactive computing
- Data structures for range-aggregation over categories
- Cache-oblivious persistence
- Sparse dominance queries for many points in optimal time and space
- Efficient range searching for categorical and plain data
- Retroactive data structures
- Minmax regret 1-facility location on uncertain path networks
- Dynamic Planar Range Maxima Queries
- Efficient top-k queries for orthogonal ranges
- Range-Aggregate Queries Involving Geometric Aggregation Operations
- Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
- Efficient non-intersection queries on aggregated geometric data
- A partially persistent data structure for the set-union problem
- Versioning Tree Structures by Path-Merging
- Confluently Persistent Tries for Efficient Version Control
- Indexing Information for Data Forensics
- New Data Structures for IP Lookup and Conflict Detection
- Some Results for Elementary Operations
- Isocontour based Visualization of Time-varying Scalar Fields
- scientific article; zbMATH DE number 1375590 (Why is no real title available?)
- Fully persistent arrays. (Extended abstract)
- Fully persistent data structures for disjoint set union problems
- Optimal purely functional priority queues
- Using persistent data structures for adding range restrictions to searching problems
- A composite stabilizing data structure
- Persistent Views--A Mechanism for Managing Ageing Data
- Making data structures confluently persistent
- scientific article; zbMATH DE number 1471729 (Why is no real title available?)
- Simple Confluently Persistent Catenable Lists
- An efficient algorithm for the 1D total visibility-index problem and its parallelization
- New upper bounds for generalized intersection searching problems
- INTERSECTION PROBLEMS ON SEGMENTS UNDER BOUNDARY UPDATES WITH APPLICATION TO PERSISTENT LISTS
- Computing the map of geometric minimal cuts
- Spiderman graph: visibility in urban regions
- Partially persistent B-trees with constant worst case update time
- Linear-space data structures for range minority query in arrays
- Simple confluently persistent catenable lists
- Lower bounds for monotonic list labeling
- Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)
- Further results on generalized intersection searching problems: Counting, reporting, and dynamization
- Extensions of self-improving sorters
- An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3
- \(k\)-best solutions of MSO problems on tree-decomposable graphs
- Nearly optimal separation between partially and fully retroactive data structures
- Approximate range queries for clustering
- Finding pairwise intersections of rectangles in a query rectangle
- Counting palindromes in substrings
- Dynamic Structures for Top-k Queries on Uncertain Data
- Semi-persistent Data Structures
- I/O-efficient point location using persistent B-trees
- Detecting regular visit patterns
- Partial updates
- Confluent persistence revisited
- Fully persistent B-trees
- Optimal finger search trees in the pointer machine
- Algorithms for generalized halfspace range searching and other intersection searching problems
- scientific article; zbMATH DE number 7765406 (Why is no real title available?)
This page was built for publication: Making data structures persistent
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1117690)