A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries.
Vasilis Samoladas, Daniel P. Miranker:
A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries.
PODS 1998: 44-51@inproceedings{DBLP:conf/pods/SamoladasM98,
author = {Vasilis Samoladas and
Daniel P. Miranker},
title = {A Lower Bound Theorem for Indexing Schemes and Its Application
to Multidimensional Range Queries},
booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-996-3},
pages = {44-51},
ee = {http://doi.acm.org/10.1145/275487.275493, db/conf/pods/SamoladasM98.html},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Indexing schemes were proposed by Hellerstein, Koutsoupias and
Papadimitriou to model data indexing on external memory. Using
indexing schemes, the complexity of indexing is quantified 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 possible 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 a
tight lower bound for 2-dimensional range queries and extend our lower
bound to d-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.
Copyright © 1998 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
BibTeX
Printed Edition
Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington.
ACM Press 1998, ISBN 0-89791-996-3
Contents BibTeX
[Index Terms]
[Full Text in PDF Format, 934 KB]
References
- [1]
- ...
- [2]
- ...
- [3]
- ...
- [4]
- ...
- [5]
- Christos Faloutsos, Ibrahim Kamel:
Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension.
PODS 1994: 4-13 BibTeX
- [6]
- ...
- [7]
- Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou:
On the Analysis of Indexing Schemes.
PODS 1997: 249-256 BibTeX
- [8]
- Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer:
Generalized Search Trees for Database Systems.
VLDB 1995: 562-573 BibTeX
- [9]
- Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter:
Indexing for Data Models with Constraints and Classes.
PODS 1993: 233-243 BibTeX
- [10]
- Elias Koutsoupias, David Scot Taylor:
Tight Bounds for 2-Dimensional Indexing Schemes.
PODS 1998: 52-58 BibTeX
- [11]
- ...
- [12]
- Mark H. Nodine, Michael T. Goodrich, Jeffrey Scott Vitter:
Blocking for External Graph Searching.
PODS 1993: 222-232 BibTeX
- [13]
- Sridhar Ramaswamy, Paris C. Kanellakis:
OODB Indexing by Class-Division.
SIGMOD Conference 1995: 139-150 BibTeX
- [14]
- Sridhar Ramaswamy, Sairam Subramanian:
Path Caching: A Technique for Optimal External Searching.
PODS 1994: 25-35 BibTeX
- [15]
- Sunita Sarawagi, Michael Stonebraker:
Efficient Organization of Large Multidimensional Arrays.
ICDE 1994: 328-336 BibTeX
- [16]
- ...
- [17]
- ...
- [18]
- Mihalis Yannakakis:
Perspectives on Database Theory.
FOCS 1995: 224-246 BibTeX
- [19]
- Yihong Zhao, Prasad Deshpande, Jeffrey F. Naughton:
An Array-Based Algorithm for Simultaneous Multidimensional Aggregates.
SIGMOD Conference 1997: 159-170 BibTeX
Referenced by
- H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava:
Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse.
SIGMOD Conference 1999: 37-48
- Lars Arge, Vasilis Samoladas, Jeffrey Scott Vitter:
On Two-Dimensional Indexability and Optimal Range Search Indexing.
PODS 1999: 346-357
- Kothuri Venkata Ravi Kanth, Ambuj K. Singh:
Optimal Dynamic Range Searching in Non-replicating Index Structures.
ICDT 1999: 257-276
- Joseph M. Hellerstein, Lisa Hellerstein, George Kollios:
On the Generation of 2-Dimensional Index Workloads.
ICDT 1999: 113-130
- Elias Koutsoupias, David Scot Taylor:
Tight Bounds for 2-Dimensional Indexing Schemes.
PODS 1998: 52-58
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:18 2009