Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/6F3048FE-2E7A-4970-9A8E-86E4250BF91C | ||
| Year | 1998 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| Bibliographic Citation | 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 . | ||
| Appears in Collections |
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.
Copyright © DIAS 2013
