Αναζήτηση

Πλοήγηση

• Κοινότητες
• Συγγραφείς
• Έτος
• Τίτλοι
• Θέματα

Ο Χώρος μου

• Είσοδος

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

Samoladas Vasilis, Miranker, Daniel P

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

---

Περίληψη

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.

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

Υπηρεσίες