J. M. Hellerstein, E. Koutsoupias, and C. H. Papadimitriou.
On the Analysis of Indexing Schemes.
In Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART
Symposium on Principles of Database Systems, pages 249--256,
Tucson, Arizona, 12--15 May 1997.
Abstract
We consider the problem of indexing general database workloads (combinations of data sets and sets of potential queries). We define a framework for measuring the efficiency of an indexing scheme for a workload based on two characterizations: storage redundancy (how many times each item in the data set is stored), and access overhead (how many times more blocks than necessary does a query retrieve). Using this framework we present some initial results, showing upper and lower bounds and trade-offs between them in the case of multi-dimensional range queries and set queries.Bib
@string{PODS97 = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART
Symposium on Principles of Database Systems}}
@InProceedings{HKP97,
author = {J. M. Hellerstein and E. Koutsoupias and C. H. Papadimitriou},
title = {On the analysis of indexing schemes},
booktitle = PODS97,
pages = {249--256},
address= {Tucson, Arizona},
month = {12--15 } # may,
year = 1997
}