Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784

phone: +30 210 7275122
fax: +30 210 7275114

J. M. Hellerstein, E. Koutsoupias, D. P. Miranker, C. H. Papadimitriou, and V. Samoladas. On a model of indexability and its bounds for range queries. Journal of the ACM (JACM) 49(1):35--55, 2002.
Download: pdf ps


We develop a theoretical framework to characterize the hardness of indexing data sets on block-access memory devices like hard disks. We define an indexing workload by a data set and a set of potential queries. For a workload, we can construct an indexing scheme, which is a collection of fixed-sized subsets of the data. We identify two measures of efficiency for an indexing scheme on a workload: storage redundancy, r (how many times each item in the data set is stored), and access overhead, A (how many times more blocks than necessary does a query retrieve). For many interesting families of workloads, there exists a trade-off between storage redundancy and access overhead. Given a desired access overhead A, there is a minimum redundancy that any indexing scheme must exhibit. We prove a lower-bound theorem for deriving the minimum redundancy. By applying this theorem, we show interesting upper and lower bounds and trade-offs between A and r in the case of multidimensional range queries and set queries.


  author =	 {Joseph M. Hellerstein and Elias Koutsoupias and
                  Daniel P. Miranker and Christos H. Papadimitriou and
                  Vasilis Samoladas},
  title =	 {On a model of indexability and its bounds for range
  journal =	 {Journal of the ACM (JACM)},
  volume =	 {49},
  number =	 {1},
  year =	 {2002},
  issn =	 {0004-5411},
  pages =	 {35--55},
  doi =		 {http://doi.acm.org/10.1145/505241.505244},
  publisher =	 {ACM Press},