Space-time tradeoffs for orthogonal range queries
Pravin M. Vaidya · 1985
We investigate the question of (storage) space - (retrieval) time tradeoff for orthogonal range queries on a static database. Lower bounds on the product of retrieval time and storage space are obtained in the arithmetic and tree models.