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