Spatial Join Selectivity Using Power Laws.

@inproceedings{DBLP:conf/sigmod/FaloutsosSTT00,
  author    = {Christos Faloutsos and
               Bernhard Seeger and
               Agma J. M. Traina and
               Caetano Traina Jr.},
  editor    = {Weidong Chen and
               Jeffrey F. Naughton and
               Philip A. Bernstein},
  title     = {Spatial Join Selectivity Using Power Laws},
  booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on
               Management of Data, May 16-18, 2000, Dallas, Texas, USA},
  publisher = {ACM},
  year      = {2000},
  isbn      = {1-58113-218-2},
  pages     = {177-188},
  ee        = {http://doi.acm.org/10.1145/342009.335412, db/conf/sigmod/FaloutsosSTT00.html},
  crossref  = {DBLP:conf/sigmod/2000},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

Online Edition

References

[APR+98]

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter: Scalable Sweeping-Based Spatial Join. VLDB 1998: 570-581

[BF95]

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

[BKS93]

Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246

[BSW99]

Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: The Bulk Index Join: A Generic Approach to Processing Non-Equijoins. ICDE 1999: 257

[CEN89]

...

[CHR84]

Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984)

[CMN99]

Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: On Random Sampling over Joins. SIGMOD Conference 1999: 263-274

[DNS91]

David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: An Evaluation of Non-Equijoin Algorithms. VLDB 1991: 443-452

[FJS97]

...

[FK94]

Christos Faloutsos, Ibrahim Kamel: Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension. PODS 1994: 4-13

[FRM94]

Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos: Fast Subsequence Matching in Time-Series Databases. SIGMOD Conference 1994: 419-429

[GÜN93]

Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59

[GÜT94]

Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)

[HKMRT96]

Kimmo Hätönen, Mika Klemettinen, Heikki Mannila, Pirjo Ronkainen, Hannu Toivonen: Knowledge Discovery from Telecommunication Network Alarm Databases. ICDE 1996: 115-122

[KS97]

Nick Koudas, Kenneth C. Sevcik: Size Separation Spatial Join. SIGMOD Conference 1997: 324-335

[KS98]

Nick Koudas, Kenneth C. Sevcik: High Dimensional Similarity Joins: Algorithms and Performance Evaluation. ICDE 1998: 466-475

[KW99]

Arnd Christian König, Gerhard Weikum: Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation. VLDB 1999: 423-434

[LR94]

Ming-Ling Lo, Chinya V. Ravishankar: Spatial Joins Using Seeded Trees. SIGMOD Conference 1994: 209-220

[MP99]

Nikos Mamoulis, Dimitris Papadias: Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999: 1-12

[MTV95]

Heikki Mannila, Hannu Toivonen, A. Inkeri Verkamo: Discovering Frequent Episodes in Sequences. KDD 1995: 210-215

[NH94]

Raymond T. Ng, Jiawei Han: Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994: 144-155

[ORE86]

Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336

[PD96]

Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270

[POO97]

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

[PMT99]

Dimitris Papadias, Nikos Mamoulis, Yannis Theodoridis: Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999: 44-55

[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

[SCO92]

...

[SIL96]

...

[SK96]

Kenneth C. Sevcik, Nick Koudas: Filter Trees for Managing Spatial Data over a Range of Size Granularities. VLDB 1996: 16-27

[SSA97]

Kyuseok Shim, Ramakrishnan Srikant, Rakesh Agrawal: High-Dimensional Similarity Joins. ICDE 1997: 301-311

[TP91]

...

[TS96]

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

[TSS98]

Yannis Theodoridis, Emmanuel Stefanakis, Timos K. Sellis: Cost Models for Join Queries in Spatial Databases. ICDE 1998: 476-483

[WKS+96]

Howard D. Wactlar, Takeo Kanade, Michael A. Smith, Scott M. Stevens: Intelligent Access to Digital Video: Informedia Project. IEEE Computer 29(5): 46-52(1996)

[VW99]

Jeffrey Scott Vitter, Min Wang: Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets. SIGMOD Conference 1999: 193-204