I/O-efficient point location using persistent B-trees

DOI10.1145/996546.996549MaRDI QIDQ5463442zbMATH OpenOpenAlexFDO

Authors Lars Arge, Andrew Danner, Sha-Mayn Teh

Publication date 4 August 2005

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL http://www.acm.org/jea/2003/ArgeIO/

zbMATH Keywords

algorithmsB-treesI/O efficientpersistencepoint location

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• I/O-efficient dynamic planar point location
• scientific article; zbMATH DE number 1305387
• Planar point location for large data sets
• Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os
• External memory planar point location with logarithmic updates

Cites work

• A new data structure for representing sorted lists
• A new point-location algorithm and its practical efficiency: comparison with existing algorithms
• A space-optimal solution of general region location
• Efficient bulk operations on dynamic \(R\)-trees
• External-memory algorithms for processing line segments in geographic information systems
• scientific article; zbMATH DE number 3653523 (Why is no real title available?)
• scientific article; zbMATH DE number 1182923 (Why is no real title available?)
• scientific article; zbMATH DE number 1947384 (Why is no real title available?)
• scientific article; zbMATH DE number 1792106 (Why is no real title available?)
• I/O-efficient dynamic planar point location (extended abstract)
• Making data structures persistent
• Optimal Search in Planar Subdivisions
• Organization and maintenance of large ordered indexes
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• The buffer tree: A technique for designing batched external data structures

Cited in

(18)

• Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os
• I/O-efficient dynamic planar point location
• Fully persistent B-trees
• How to pack directed acyclic graphs into small blocks
• The complexity of flow on fat terrains and its i/o-efficient computation
• Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions
• scientific article; zbMATH DE number 1305387 (Why is no real title available?)
• Orthogonal point location and rectangle stabbing queries in 3-d
• Dynamic Planar Point Location in External Memory.
• I/O-efficient path traversal in succinct planar graphs
• I/O-Efficient Point Location in a Set of Rectangles
• Planar point location for large data sets
• Fully persistent B-trees
• External memory planar point location with logarithmic updates
• External memory fully persistent search trees
• Partial order multiway search
• Buffered partially-persistent external-memory search trees
• Optimal external memory planar point enclosure

Describes a project that uses

Uses Software

• TPIE

This page was built for publication: I/O-efficient point location using persistent B-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5463442)