Selectivity Estimation in Spatial Databases.

@inproceedings{DBLP:conf/sigmod/AcharyaPR99,
  author    = {Swarup Acharya and
               Viswanath Poosala and
               Sridhar Ramaswamy},
  editor    = {Alex Delis and
               Christos Faloutsos and
               Shahram Ghandeharizadeh},
  title     = {Selectivity Estimation in Spatial Databases},
  booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference
               on Management of Data, June 1-3, 1999, Philadelphia, Pennsylvania,
               USA},
  publisher = {ACM Press},
  year      = {1999},
  isbn      = {1-58113-084-8},
  pages     = {13-24},
  ee        = {http://doi.acm.org/10.1145/304182.304184, db/conf/sigmod/AcharyaPR99.html},
  crossref  = {DBLP:conf/sigmod/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1999 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.

ACM SIGMOD DiSC

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/DISC001 or /cdrom

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[Ant92]

Gennady Antoshenkov: Random Sampling from Pseudo-Ranked B+ Trees. VLDB 1992: 375-382 BibTeX

[Aok97]

Paul M. Aoki: Generalizing ``Search'' in Generalized Search Trees (Extended Abstract). ICDE 1998: 380-389 BibTeX

[APR99]

...

[ARC93]

Environmental Systems Research Institute: Understanding GIS - The ARC/INFO Method, 3rd Ed. GeoInformation International / John Wiley 1995, ISBN 1-899761-04-7,0-470-24987-0
BibTeX

[BF95]

Alberto Belussi, Christos Faloutsos: Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB 1995: 299-310 BibTeX

[BKSS90]

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX

[CR94]

Chung-Min Chen, Nick Roussopoulos: Adaptive Selectivity Estimation Using Query Feedback. SIGMOD Conference 1994: 161-172 BibTeX

[DeW94]

David J. DeWitt, Navin Kabra, Jun Luo, Jignesh M. Patel, Jie-Bing Yu: Client-Server Paradise. VLDB 1994: 558-569 BibTeX

[GG82]

Erol Gelenbe, Danièle Gardy: The Size of Projections of Relations Satisfying a Functional Dependency. VLDB 1982: 325-333 BibTeX

[GRSS97]

Stéphane Grumbach, Philippe Rigaux, Michel Scholl, Luc Segoufin: DEDALE, A Spatial Constraint Database. DBPL 1997: 38-59 BibTeX

[Gut85]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[HNSS95]

Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Lynne Stokes: Sampling-Based Estimation of the Number of Distinct Values of an Attribute. VLDB 1995: 311-322 BibTeX

[Int97]

...

[KMS97]

Sanjeev Khanna, S. Muthukrishnan, Steven Skiena: Efficient Array Partitioning. ICALP 1997: 616-626 BibTeX

[Koo80]

Robert Kooi: The Optimization of Queries in Relational Databases. Ph.D. thesis, Case Western Reserve University 1980
BibTeX

[LNS90]

Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider: Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990: 1-11 BibTeX

[Map98]

...

[MPS99]

S. Muthukrishnan, Viswanath Poosala, Torsten Suel: On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications. ICDT 1999: 236-256 BibTeX

[PI97]

Viswanath Poosala, Yannis E. Ioannidis: Selectivity Estimation Without the Attribute Value Independence Assumption. VLDB 1997: 486-495 BibTeX

[PIHS96]

Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, Eugene J. Shekita: Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conference 1996: 294-305 BibTeX

[Poo97]

Viswanath Poosala: Histogram-Based Estimation Techniques in Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1997
BibTeX

[PSC84]

Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276 BibTeX

[SAC+79]

Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX

[Sam89a]

...

[Sam89b]

Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX

[SFGM93]

Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11 BibTeX

[SRF87]

Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX

[tig92]

...

[TS96]

Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171 BibTeX

[Ube94]

Michael Ubell: The Montage Extensible DataBlade Achitecture. SIGMOD Conference 1994: 482 BibTeX

[Zip49]

George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949
BibTeX

Referenced by

1. Dimitrios Gunopulos, George Kollios, Vassilis J. Tsotras, Carlotta Domeniconi: Approximating Multi-Dimensional Aggregate Range Queries over Real Attributes. SIGMOD Conference 2000: 463-474
2. Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, Jeffrey Scott Vitter: A Unified Approach for Indexed and Non-Indexed Spatial Joins. EDBT 2000: 413-429
3. Viswanath Poosala, Venkatesh Ganti, Yannis E. Ioannidis: Approximate Query Answering using Histograms. IEEE Data Eng. Bull. 22(4): 5-14(1999)
4. Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, Sridhar Ramaswamy: Join Synopses for Approximate Query Answering. SIGMOD Conference 1999: 275-286