Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/6F3048FE-2E7A-4970-9A8E-86E4250BF91C | - |
| Γλώσσα | en | - |
| Μέγεθος | 8 pages | en |
| Τίτλος | A lower bound theorem for indexing schemes and its application to multidimensional range queries | en |
| Δημιουργός | Samoladas Vasilis | en |
| Δημιουργός | Σαμολαδας Βασιλης | el |
| Δημιουργός | Miranker, Daniel P | en |
| Περίληψη | 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 |
| Τύπος | Πλήρης Δημοσίευση σε Συνέδριο | el |
| Τύπος | Conference Full Paper | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2015-10-17 | - |
| Ημερομηνία Δημοσίευσης | 1998 | - |
| Βιβλιογραφική Αναφορά | 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
