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

DOI10.4230/LIPICS.ESA.2017.2zbMATH Open1442.68245OpenAlexW2759561597MaRDI QIDQ5111685FDOQ5111685

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

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

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)

Cites Work

• The buffer tree: A technique for designing batched external data structures
• Algorithms and data structures for external memory
• Lower bounds for orthogonal range searching: I. The reporting case
• Computational models for parallel computers
• Title not available (Why is that?)
• Lower bounds for sorted geometric queries in the I/O model
• Title not available (Why is that?)
• Orthogonal range reporting, query lower bounds, optimal structures in 3-d, and higher-dimensional improvements
• Title not available (Why is that?)
• On a model of indexability and its bounds for range queries
• External-memory algorithms for processing line segments in geographic information systems
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Fast permuting on disk arrays
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Orthogonal Range Reporting in Three and Higher Dimensions
• Ordered and unordered top-\(K\) range reporting in large data sets
• Permuting Information in Idealized Two-Level Storage
• Title not available (Why is that?)
• I/O-efficient range minima queries
• Title not available (Why is that?)
• Algorithms – ESA 2004

Cited In (4)

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

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)