Name
Abstract | ||
|---|---|---|
We propose path-merging as a refinement of techniques used to make linked data structures partially persistent. Path-merging supports bursts of operations between any two adjacent versions in contrast to only one operation in the original variant. The superiority of the method is shown both theoretically and experimentally. Details of the technique are explained for the case of binary search trees. Path-merging is particularly useful for the implementation of scan-line algorithms where many update operations on the sweep status structure have to be performed at the same event points. Examples are algorithms for planar point location, for answering intersection queries for sets of horizontal line segments, and for detecting conflicts in sets of 1-dim IP packet filters.Subject Classifications: E.1 [Data]: Data Structures --- trees; E.2 [Data]: Data Storage Representations --- linked representations; F.2.2 [Analysis of Algorithms and Problem Complexity] Nonnumerical Algorithms and Problems --- Geometrical problems and computations. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-69311-6_13 | FAW |
Keywords | Field | DocType |
versioning tree structures,nonnumerical algorithms,adjacent version,1-dim ip packet filter,data structures,data storage representations,binary search tree,problem complexity,event point,subject classifications,data structure,tree structure,linked data,point location,data storage | Data structure,Point location,Computer science,Analysis of algorithms,Linked data,Algorithm,Theoretical computer science,Tree structure,Horizontal line test,Binary search tree,Computation | Conference |
Volume | ISSN | Citations |
5059 | 0302-9743 | 2 |
PageRank | References | Authors |
0.37 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Khaireel A. Mohamed | 1 | 6 | 2.83 |
| Tobias Langner | 2 | 126 | 7.98 |
| Th. Ottmann | 3 | 468 | 124.40 |