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

Simple record


URIhttp://purl.tuc.gr/dl/dias/6F3048FE-2E7A-4970-9A8E-86E4250BF91C-
Languageen-
Extent8 pagesen
TitleA lower bound theorem for indexing schemes and its application to multidimensional range queriesen
CreatorSamoladas Vasilisen
CreatorΣαμολαδας Βασιληςel
CreatorMiranker, Daniel Pen
Content SummaryIndexing schemes were proposed by Hellerstein, Koutsoupias and Fapadlmitriou [7] to model data indexing on external memory, Using indexing schemes, the complexity of indexing is qunntified by two parameters: storage redundancy and access overhead, There is a tradeoff between these two parameters, in the sense that for some problems it is not poseiblc for both of these to be low. In this paper we derive a lower-bounds theorem for arbitrary indexing schemes. We apply our theorem to the particular problem of d-dimensional range queries. We first resolve the open problem of [7] for a tight lower bound for 2-dimensional range queries and extend our lower bound to &dimensional range queries. We then show, how, the construction in our lower-bounds proof may be exploited to derive indexing schemes for d-dimensional range queries, whose asymptotic complexity matches our lower bounds.en
Type of ItemΠλήρης Δημοσίευση σε Συνέδριοel
Type of ItemConference Full Paperen
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2015-10-17-
Date of Publication1998-
Bibliographic CitationV. 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 .en

Available Files

Services

Statistics