On a model of indexability and its bounds for range queries

DOI10.1145/505241.505244zbMath1323.68252OpenAlexW2167184472MaRDI QIDQ3196634

Joseph M. Hellerstein, Daniel P. Miranker, Vasilis Samoladas, Elias Koutsoupias, Christos H. Papadimitriou

Publication date: 30 October 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/505241.505244

zbMATH Keywords

databaseindexlower boundsredundancyindexabilitymultidimensional range query

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (6)

I/O-efficient 2-d orthogonal range skyline and attrition priority queues ⋮ Optimal external memory planar point enclosure ⋮ Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines ⋮ Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions ⋮ Permuting and Batched Geometric Lower Bounds in the I/O Model ⋮ IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS

This page was built for publication: On a model of indexability and its bounds for range queries