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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

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

Samoladas Vasilis, Miranker, Daniel P

Πλήρης Εγγραφή


URI: http://purl.tuc.gr/dl/dias/6F3048FE-2E7A-4970-9A8E-86E4250BF91C
Έτος 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 .
Εμφανίζεται στις Συλλογές

Περίληψη

Indexing schemes were proposed by Hellerstein, Koutsoupiasand Fapadlmitriou [7] to model data indexing on externalmemory, Using indexing schemes, the complexity of indexingis qunntified by two parameters: storage redundancyand access overhead, There is a tradeoff between these twoparameters, in the sense that for some problems it is notposeiblc for both of these to be low.In this paper we derive a lower-bounds theorem for arbitraryindexing schemes. We apply our theorem to theparticular problem of d-dimensional range queries. We firstresolve the open problem of [7] for a tight lower bound for2-dimensional range queries and extend our lower bound to&dimensional range queries. We then show, how, the constructionin our lower-bounds proof may be exploited to deriveindexing schemes for d-dimensional range queries, whoseasymptotic complexity matches our lower bounds.

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά