Permuting and batched geometric lower bounds in the I/O model

DOI10.4230/LIPICS.ESA.2017.2MaRDI QIDQ5111685zbMATH OpenOpenAlexFDO

Authors Peyman Afshani, Ingo van Duijn

Publication date 27 May 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/esa/esa2017.html#AfshaniD17

zbMATH Keywords

lower boundsI/O modelpermutingbatched geometric queries

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 1424315
• Lower bounds for sorted geometric queries in the I/O model
• The batched predecessor problem in external memory
• On the limits of cache-obliviousness
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems

Cites work

• scientific article; zbMATH DE number 1303612 (Why is no real title available?)
• scientific article; zbMATH DE number 1476487 (Why is no real title available?)
• scientific article; zbMATH DE number 1792106 (Why is no real title available?)
• scientific article; zbMATH DE number 910869 (Why is no real title available?)
• scientific article; zbMATH DE number 1424323 (Why is no real title available?)
• Algorithms and data structures for external memory
• Algorithms – ESA 2004
• Computational models for parallel computers
• External-memory algorithms for processing line segments in geographic information systems
• Fast permuting on disk arrays
• I/O-efficient range minima queries
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Lower bounds for orthogonal range searching: I. The reporting case
• Lower bounds for sorted geometric queries in the I/O model
• On a model of indexability and its bounds for range queries
• Ordered and unordered top-\(K\) range reporting in large data sets
• Orthogonal Range Reporting in Three and Higher Dimensions
• Orthogonal range reporting, query lower bounds, optimal structures in 3-d, and higher-dimensional improvements
• Permuting Information in Idealized Two-Level Storage
• 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

(4)

• Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems
• Lower bounds for sorted geometric queries in the I/O model
• Upper and lower I/O bounds for pebbling \(r\)-pyramids
• Computing the optimal IO sequences of a protocol in polynomial time

This page was built for publication: Permuting and batched geometric lower bounds in the I/O model

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