Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/6F3048FE-2E7A-4970-9A8E-86E4250BF91C | - |
| Language | en | - |
| Extent | 8 pages | en |
| Title | A lower bound theorem for indexing schemes and its application to multidimensional range queries | en |
| Creator | Samoladas Vasilis | en |
| Creator | Σαμολαδας Βασιλης | el |
| Creator | Miranker, Daniel P | en |
| Content Summary | Indexing 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. | en |
| Type of Item | Πλήρης Δημοσίευση σε Συνέδριο | el |
| Type of Item | Conference Full Paper | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2015-10-17 | - |
| Date of Publication | 1998 | - |
| Bibliographic Citation | V. Samoladas, D. P. Miranker,"A lower bound theorem for indexing schemes and its application to multidimensional range queries," in the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems,1998, pp.44-51 . | en |
Copyright © DIAS 2013
