Sketches for size of join estimation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sketches for size of join estimation

Full text

Pdf (819 KB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 33 , Issue 3 (August 2008) table of contents

Article No. 15

Year of Publication: 2008

ISSN:0362-5915

Authors

Florin Rusu	University of Florida, Gainesville
Alin Dobra	University of Florida, Gainesville

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 56, Downloads (12 Months): 115, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1386118.1386121 What is a DOI?

ABSTRACT

Sketching techniques provide approximate answers to aggregate queries both for data-streaming and distributed computation. Small space summaries that have linearity properties are required for both types of applications. The prevalent method for analyzing sketches uses moment analysis and distribution-independent bounds based on moments. This method produces clean, easy to interpret, theoretical bounds that are especially useful for deriving asymptotic results. However, the theoretical bounds obscure fine details of the behavior of various sketches and they are mostly not indicative of which type of sketches should be used in practice. Moreover, no significant empirical comparison between various sketching techniques has been published, which makes the choice even harder. In this article we take a close look at the sketching techniques proposed in the literature from a statistical point of view with the goal of determining properties that indicate the actual behavior and producing tighter confidence bounds. Interestingly, the statistical analysis reveals that two of the techniques, Fast-AGMS and Count-Min, provide results that are in some cases orders of magnitude better than the corresponding theoretical predictions. We conduct an extensive empirical study that compares the different sketching techniques in order to corroborate the statistical analysis with the conclusions we draw from it. The study indicates the expected performance of various sketches, which is crucial if the techniques are to be used by practitioners. The overall conclusion of the study is that Fast-AGMS sketches are, for the full spectrum of problems, either the best, or close to the best, sketching technique. We apply the insights obtained from the statistical study and the experimental results to design effective algorithms for sketching interval data. We show how the two basic methods for sketching interval data, DMAP and fast range-summation, can be improved significantly with respect to the update time without a significant loss in accuracy. The gain in update time can be as large as two orders of magnitude, thus making the improved methods practical. The empirical study suggests that DMAP is preferable when update time is the critical requirement and fast range-summation is desirable for better accuracy.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Aduri, P. and Tirthapura, S. 2005. Range efficient computation of F0 over massive data streams. In Proceedings of the 21st IEEE ICDE International Conference on Data Engineering. IEEE Computer Society, 32--43.
	2	Alon, N., Gibbons, P. B., Matias, Y., and Szegedy, M. 2002. Tracking join and self-join sizes in limited storage. J. Comput. Syst. Sci. 64, 3, 719--747.
	3	Alon, N., Matias, Y., and Szegedy, M. 1996. The space complexity of approximating the frequency moments. In Proceedings of the 28th ACM Symposium on Theory of Computing. ACM, New York, 20--29.
	4	An, N., Yang, Z.-Y., and Sivasubramaniam, A. 2001. Selectivity estimation for spatial joins. In Proceedings of the 17th IEEE ICDE International Conference on Data Engineering. IEEE Computer Society, 368--375.
	5	Balanda, K. P. and MacGillivray, H. L. 1988. Kurtosis: A critical review. J. Amer. Statist. 42, 2, 111--119.
	6	Charikar, M., Chen, K., and Farach-Colton, M. 2002. Finding frequent items in data streams. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming. Springer, 693--703.
	7	Coles, S. 2001. An Introduction to Statistical Modeling of Extreme Values. Springer, Berlin, Germany.
	8	Cormode, G. and Garofalakis, M. 2005. Sketching streams through the net: distributed approximate query tracking. In Proceedings of the 31st International Conference on Very Large Data Bases. VLDB Endowment, 13--24.
	9	Cormode, G. and Muthukrishnan, S. 2005a. An improved data stream summary: the count-min sketch and its applications. J. Algor. 55, 1, 58--75.
	10	Cormode, G. and Muthukrishnan, S. 2005b. Summarizing and mining skewed data streams. In Proceedings of SIAM Conference on Data Mining. SIAM, Philadelphia, PA.
	11	CPS. 2006. http://www.census.gov/cps.
	12	Das, A., Gehrke, J., and Riedewald, M. 2004. Approximation techniques for spatial data. In Proceedings of the 23rd ACM SIGMOD International Conference on Management of Data (SIGMOD'04). ACM, New York, 695--706.
	13	Dobra, A., Garofalakis, M., Gehrke, J., and Rastogi, R. 2002. Processing complex aggregate queries over data streams. In Proceedings of the 21st ACM SIGMOD International Conference on Management of Data (SIGMOD'02). ACM, New York, 61--72.
	14	Estan, C. and Naughton, J. F. 2006. End-biased samples for join cardinality estimation. In Proceedings of the 22nd IEEE International Conference on Data Engineering. IEEE Computer Society, 20--31.
	15	Ganguly, S., Garofalakis, M., and Rastogi, R. 2004. Processing data-stream join aggregates using skimmed sketches. In Proceedings of the 9th International Conference on Extending Database Technology. Springer, 569--586.
	16	Ganguly, S., Kesh, D., and Saha, C. 2005. Practical algorithms for tracking database join sizes. In Proceedings of the 25th Conference on Foundations of Software Technology and Theoretical Computer Science. Springer, 297--309.
	17	Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., and Strauss, M. J. 2005. Domain-driven data synopses for dynamic quantiles. IEEE Transactions on Knowl. Data Engin. 17, 7, 927--938.
	18	Haas, P. J. and Hellerstein, J. M. 1999. Ripple joins for online aggregation. In Proceedings of the eighteenth ACM SIGMOD International Conference on Management of Data (SIGMOD'99). ACM Press, New York, 287--298.
	19	Kempe, D., Dobra, A., and Gehrke, J. 2003. Gossip-based computation of aggregate information. In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 482--491.
	20	MassDAL. 2006. http://www.cs.rutgers.edu/_muthu/massdal.html.
	21	Motwani, R. and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press, Cambridge, UK.
	22	Olive, D. J. 2005. A simple confidence interval for the median. Manuscript. www.math.siu.edu/olive/ppmedci.pdf.
	23	Pennecchi, F. and Callegaro, L. 2006. Between the mean and the median: The L_p estimator. Metrologia 43, 3, 213--219.
	24	Price, R. M. and Bonett, D. G. 2001. Estimating the variance of the sample median. J. Statist. Comput. Simul. 68, 3, 295--305.
	25	Rusu, F. and Dobra, A. 2007. Pseudorandom number generation for sketch-based estimations. ACM Trans. Datab. Syst. 32, 2, 11.
	26	Sachs, L. 1984. Applied Statistics—A Handbook of Techniques. Springer, Berlin, Germany.
	27	Shao, J. 1999. Mathematical Statistics. Springer, Berlin, Germany.
	28	Thorup, M. and Zhang, Y. 2004. Tabulation based 4-universal hashing with applications to second moment estimation. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. 615--624.