Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

A lower bound theorem for indexing schemes and its application to multidimensional range queries

Samoladas Vasilis, Miranker, Daniel P

Απλή Εγγραφή

URIhttp://purl.tuc.gr/dl/dias/6F3048FE-2E7A-4970-9A8E-86E4250BF91C-
Γλώσσαen-
Μέγεθος8 pagesen
ΤίτλοςA lower bound theorem for indexing schemes and its application to multidimensional range queriesen
ΔημιουργόςSamoladas Vasilisen
ΔημιουργόςΣαμολαδας Βασιληςel
ΔημιουργόςMiranker, Daniel Pen
Περίληψη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 Paperen
Άδεια Χρήσης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