On Random Sampling over Joins.

@inproceedings{DBLP:conf/sigmod/ChaudhuriMN99,
  author    = {Surajit Chaudhuri and
               Rajeev Motwani and
               Vivek R. Narasayya},
  editor    = {Alex Delis and
               Christos Faloutsos and
               Shahram Ghandeharizadeh},
  title     = {On Random Sampling over Joins},
  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     = {263-274},
  ee        = {http://doi.acm.org/10.1145/304182.304206, db/conf/sigmod/ChaudhuriMN99.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

[1]

Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: Random Sampling for Histogram Construction: How much is enough? SIGMOD Conference 1998: 436-447

[2]

Sumit Ganguly, Phillip B. Gibbons, Yossi Matias, Abraham Silberschatz: Bifocal Sampling for Skew-Resistant Join Size Estimation. SIGMOD Conference 1996: 271-281

[3]

Peter J. Haas, Jeffrey F. Naughton, Arun N. Swami: On the Relative Cost of Sampling for Join Selectivity Estimation. PODS 1994: 14-24

[4]

Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang: Online Aggregation. SIGMOD Conference 1997: 171-182

[5]

Wen-Chi Hou, Gultekin Özsoyoglu, Erdogan Dogdu: Error-Constraint COUNT Query Evaluation in Relational Databases. SIGMOD Conference 1991: 278-287

[6]

Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri: Efficient Sampling Strategies for Relational Database Operations. Theor. Comput. Sci. 116(1&2): 195-226(1993)

[7]

Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press 1995, ISBN 0-521-47465-5

[8]

Jeffrey F. Naughton, S. Seshadri: On Estimating the Size of Projections. ICDT 1990: 499-513

[9]

Frank Olken, Doron Rotem: Simple Random Sampling from Relational Databases. VLDB 1986: 160-169

[10]

...

[11]

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

[12]

Jeffrey Scott Vitter: Random Sampling with a Reservoir. ACM Trans. Math. Softw. 11(1): 37-57(1985)

[13]

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