A lower bound theorem for indexing schemes and its application to multidimensional range queriesA lower bound theorem for indexing schemes and its application to multidimensional range queries Πλήρης Δημοσίευση σε Συνέδριο Conference Full Paper 2015-10-171998enIndexing schemes were proposed by Hellerstein, Koutsoupias and Fapadlmitriou [7] to model data indexing on external memory, Using indexing schemes, the complexity of indexing is qunntified 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 poseiblc 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 &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.http://creativecommons.org/licenses/by/4.0/ Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems Samoladas Vasilis Σαμολαδας Βασιλης Miranker, Daniel P