Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries

V. Samoladas, D. P. Miranker
Abstract
In this paper, we derive a lower-bounds theorem for arbitrary indexing problems. We use a model for indexing data stored in external memory proposed by Hellerstein, Koutsoupias and Papadimitriou. In that model, indexing is quantified by two parameters: storage redundancy and access overhead. There is a tradeoff between these two parameters, in the sense that for some problems it is not possible for both of these to be low.
We apply our theorem to the particular problem of $d$-dimensional range queries. We first resolve the open problem of for a tight lower bound for 2-dimensional range queries and extend our lower bound to $d$-dimensional range queries. We then show, how, the construction in our lower-bounds proof may be exploited to derive an index whose asymptotic complexity matches our lower bounds.
full-text.pdf

@inproceedings{ samoladas98lower,
author = "Vasilis Samoladas and Daniel P. Miranker",
title = "A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries",
pages = "44--51",
year = "1998",
url = "citeseer.ist.psu.edu/samoladas98lower.html" }