language: en

On the Analysis of Indexing Schemes

Joseph M. Hellerstein
Division of Computer Science UC Berkeley,
Berkeley, CA 94720
jmh@cs.berkeley.edu
Elias Koutsoupias
Department of Computer Science UCLA,
Los Angeles, CA 90095
elias@cs.ucla.edu
Christos H. Papadimitriou
Division of Computer Science UC Berkeley,
Berkeley, CA 94720
christos@cs.berkeley.edu

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.

1 Introduction