Analysis and Application of Adaptive Sampling James F. Lynch   View Paper (PDF)   Return to Sampling Abstract An estimation algorithm for a query is a probabilistic algorithm that computes an approximation for the size (number of tuples) of the query. The main question that is studied is which classes of logically definable queries have fast estimation algorithms. Evidence from descriptive complexity theory is provided that indicates not all such queries have fast estimation algorithms. However, it is shown that on classes of structures of bounded degree, all first-order queries have fast estimation algorithms. These estimation algorithms use a form of statistical sampling known as adaptive sampling. Several versions of adaptive sampling have been developed by other researchers. The original version has been surpassed in some ways by a newer version and a more specialized Monte-Carlo algorithm. An analysis of the average run time of the original version is given, and the different algorithms are compared. The analysis is used to compute what appears to be the best known upper bound on the efficiency of the original algorithm. Also, contrary to what seems to be a commonly held opinion, the two methods of adaptive sampling are incomparable. Which method is superior depends on the query being estimated and the criteria that are being applied. Lastly, adaptive sampling can be more efficient than the Monte-Carlo algorithm if knowledge about the maximum values of the data being sampled is available. References Note: References link to DBLP on the Web. [1] Serge Abiteboul , Kevin J. Compton , Victor Vianu : Queries Are Easier Than You Thought (Probably). PODS 1992 : 23-32 [2] ... [3] ... [4] ... [5] ... [6] Edith Cohen : Size-Estimation Framework with Applications to Transitive Closure and Reachability. JCSS 55(3) : 441-453(1997) [7] ... [8] ... [9] Markus Frick , Martin Grohe : Deciding First-Order Properties of Locally Tree-Decomposalbe Graphs. ICALP 1999 : 331-340 [10] ... [11] Peter J. Haas , Arun N. Swami : Sequential Sampling Procedures for Query Size Estimation. SIGMOD Conference 1992 : 341-350 [12] Torben Hagerup , Christine Rüb : A Guided Tour of Chernoff Bounds. IPL 33(6) : 305-308(1990) [13] ... [14] ... [15] ... [16] Richard J. Lipton , Jeffrey F. Naughton : Estimating the Size of Generalized Transitive Closures. VLDB 1989 : 165-171 [17] Richard J. Lipton , Jeffrey F. Naughton : Query Size Estimation by Adaptive Sampling. JCSS 51(1) : 18-25(1995) [18] ... [19] ... [20] ... BIBTEX @inproceedings{DBLP:conf/pods/Lynch00,   author    = {James F. Lynch},    title     = {Analysis and Application of Adaptive Sampling},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {260-267},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.