A lower bound theorem for indexing schemes and its application to multidimensional range queries
Vasilis Samoladas, Daniel P. Miranker · 1998
Indexing schemes were proposed by Hellerstein, Koutsoupias and Papadimitriou [7] to model data indexing on external memory. Using indexing schemes, the complexity of 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. In this paper we derive a lower-bounds theorem for arbitrary indexing schemes. We apply our theorem to the particular problem of d-dimensional range queries. We first resolve the open problem of [7] 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 indexing schemes for d-dimensional range queries, whose asymptotic complexity matches our lower bounds. 1