Cache-oblivious range reporting with optimal queries requires superlinear space
type: Item
instance of: scholarly article
title: Cache-oblivious range reporting with optimal queries requires superlinear space
zbMATH Open document ID: 1215.68103
author: Peyman Afshani
author: Norbert Zeh
author: Chris H. Hamilton
published in: Discrete \& Computational Geometry
publication date: 2011-06-03T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 5903706
zbMATH Keywords: cache-obliviousness
zbMATH Keywords: lower bound
zbMATH Keywords: range reporting
MaRDI profile type: Publication
full work available at URL: s00454-011-9347-7
OpenAlex ID: W4239171964
cites work: On Dominance Reporting in 3D
cites work: Q4633824
cites work: A general approach for cache-oblivious range reporting and approximate range counting
cites work: Efficient searching with linear constraints
cites work: Cache-oblivious data structures for orthogonal range searching
cites work: Q3601535
cites work: Cache-oblivious planar orthogonal range searching and counting
cites work: Cache-oblivious R-trees
cites work: Organization and maintenance of large ordered indexes
cites work: On the limits of cache-obliviousness
cites work: Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
cites work: Q4945539
cites work: Efficient splitting and merging algorithms for order decomposable problems.
cites work: Algorithms for three-dimensional dominance searching in linear space.
cites work: Priority Search Trees
cites work: Q4228471
DOI: 10.1007/S00454-011-9347-7
description: scientific article; zbMATH DE number 5903706