NDLI: Sketches for size of join estimation

Content Provider	ACM Digital Library
Author	Rusu, Florin Dobra, Alin
Copyright Year	2008
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.
Starting Page	1
Ending Page	46
Page Count	46
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/1386118.1386121
Volume Number	33
Issue Number	3
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-09-03
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	AGMS sketches Count-Min sketches DMAP Fast-AGMS sketches Fast-Count sketches Size of join estimation Fast range-summation
Content Type	Text
Resource Type	Article
Subject	Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Statistical analysis of sketch estimators

Pseudo-random number generation for sketch-based estimations

New estimation algorithms for streaming data: Count-min can do more (extended version). http://www.cs.ualberta.ca/˜fandeng/ paper/cmm_full.pdf

Bifocal sampling for skew-resistant join size estimation

Optimal histograms for limiting worst-case error propagation in the size of join results

Self-spacial join selectivity estimation using fractal concepts

Size separation spatial join

Share a pie?: Privacy-Preserving Knowledge Base Export through Count-min Sketches

Comparing count sketches [1,2] and count min sketches [3].

Sketches for size of join estimation

Similar Documents

Statistical analysis of sketch estimators

Pseudo-random number generation for sketch-based estimations

New estimation algorithms for streaming data: Count-min can do more (extended version). http://www.cs.ualberta.ca/˜fandeng/ paper/cmm_full.pdf

Bifocal sampling for skew-resistant join size estimation

Optimal histograms for limiting worst-case error propagation in the size of join results

Self-spacial join selectivity estimation using fractal concepts

Size separation spatial join

Share a pie?: Privacy-Preserving Knowledge Base Export through Count-min Sketches

Comparing count sketches [1,2] and count min sketches [3].

Sketches for size of join estimation