Το έργο με τίτλο A lower bound theorem for indexing schemes and its application to multidimensional range queries από τον/τους δημιουργό/ούς Samoladas Vasilis, Miranker, Daniel P διατίθεται με την άδεια Creative Commons Αναφορά Δημιουργού 4.0 Διεθνές
Βιβλιογραφική Αναφορά
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.