Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

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

Samoladas Vasilis, Miranker, Daniel P

Full record


URI: http://purl.tuc.gr/dl/dias/6F3048FE-2E7A-4970-9A8E-86E4250BF91C
Year 1998
Type of Item Conference Full Paper
License
Details
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

Summary

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.

Available Files

Services

Statistics