Random sampling techniques for space efficient online computation of order statistics of large datasets

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Random sampling techniques for space efficient online computation of order statistics of large datasets

Full text

Pdf (1.50 MB)

Source

International Conference on Management of Data archive
Proceedings of the 1999 ACM SIGMOD international conference on Management of data table of contents

Philadelphia, Pennsylvania, United States

Pages: 251 - 262

Year of Publication: 1999

ISBN:1-58113-084-8

Also published in ...

Authors

Gurmeet Singh Manku	IBM Almaden Research Center
Sridhar Rajagopalan	IBM Almaden Research Center
Bruce G. Lindsay	IBM Almaden Research Center

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 71, Citation Count: 50

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/304182.304204 What is a DOI?

ABSTRACT

In a recent paper [MRL98], we had described a general framework for single pass approximate quantile finding algorithms. This framework included several known algorithms as special cases. We had identified a new algorithm, within the framework, which had a significantly smaller requirement for main memory than other known algorithms. In this paper, we address two issues left open in our earlier paper. First, all known and space efficient algorithms for approximate quantile finding require advance knowledge of the length of the input sequence. Many important database applications employing quantiles cannot provide this information. In this paper, we present a novel non-uniform random sampling scheme and an extension of our framework. Together, they form the basis of a new algorithm which computes approximate quantiles without knowing the input sequence length. Second, if the desired quantile is an extreme value (e.g., within the top 1% of the elements), the space requirements of currently known algorithms are overly pessimistic. We provide a simple algorithm which estimates extreme values using less space than required by the earlier more general technique for computing all quantiles. Our principal observation here is that random sampling is quantifiably better when estimating extreme values than is the case with the median.

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.

	ARS97	Khaled Alsabti , Sanjay Ranka , Vineet Singh, A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data, Proceedings of the 23rd International Conference on Very Large Data Bases, p.346-355, August 25-29, 1997
	AS95	R. Agrawal ~md A. Swami. A One-Pass Space- Efficient Algorithm for Finding Quantiles. In Proc. 7th lntl. Conf. Management of Data (COMAD-95), Pune, india, 1995.
	BFP+73	M. Blum, R. "W. Floyd, V. R. Pratt, R. L. Rivest, and R. E. TaJ:jan. Time Bounds for Selection. In J. Compui. Syst. Sci., volume 7, pages 448-461, t973.
	CMN98	Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Random sampling for histogram construction: how much is enough?, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.436-447, June 01-04, 1998, Seattle, Washington, United States
	CT91	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	DB2	DB2 MVS..
	DNS91	David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, Parallel sorting on a shared-nothing architecture using probabilistic splitting, Proceedings of the first international conference on Parallel and distributed information systems, p.280-291, December 1991, Miami, Florida, United States
	GM98	Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.331-342, June 01-04, 1998, Seattle, Washington, United States
	GM99	Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, External memory algorithms, American Mathematical Society, Boston, MA, 1999
	GMP97	Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast Incremental Maintenance of Approximate Histograms, Proceedings of the 23rd International Conference on Very Large Data Bases, p.466-475, August 25-29, 1997
	Hel97	J.M. Hellerstein. Online Processing Redux. Bulletin of the IEEE Computer Society, 1997.
	Hoe63	W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. American Statistical Association Jornal, pages 13-30, March 1963.
	Inf	Informix..
	MP80	J.I. Munro eald M. S. Paterson. Selection and Sorting with Limited Storage. Theoretical Computer Science, 12:315-323, 1980.
	MRL98	Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Approximate medians and other quantiles in one pass and with limited memory, ACM SIGMOD Record, v.27 n.2, p.426-435, June 1998
	Pat97	M.R. Paterson. Progress in Selection. Deptt. of Computer Science, University of \~arwick, Coventry, UK, 1997.
	PIHS96	Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada
	Poh69	I. Pohl. A Minimum Storage Algorithm for Computing the Median. Technical Report IBM Research Report RC 2701 (# 12713), IBM T J Watson Center, November 1969.
	SALP79	P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
	Vit85	Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
	Yao74	F. F. Yao, ON LOWER BOUNDS FOR SELECTION PROBLEMS, Massachusetts Institute of Technology, Cambridge, MA, 1974

CITED BY 50

	Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Processing complex aggregate queries over data streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Johannes Gehrke , Flip Korn , Divesh Srivastava, On computing correlated aggregates over continual data streams, ACM SIGMOD Record, v.30 n.2, p.13-24, June 2001
	Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, ACM SIGMOD Record, v.30 n.2, p.58-66, June 2001
	Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining data streams under block evolution, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002
	Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003
	Lin Qiao , Divyakant Agrawal , Amr El Abbadi, RHist: adaptive summarization over continuous data streams, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	Anupam Gupta , Francis X. Zane, Counting inversions in lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Fatemah A. Alqallaf , Kjell P. Konis , R. Douglas Martin , Ruben H. Zamar, Scalable robust covariance and correlation estimates for data mining, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
	Adam L. Buchsbaum , Raffaele Giancarlo , Jeffery R. Westbrook, On finding common neighborhoods in massive graphs, Theoretical Computer Science, v.299 n.1-3, p.707-718, 18 April 2003
	George Kollios , Dimitrios Gunopulos , Nick Koudas , Stefan Berchtold, Efficient Biased Sampling for Approximate Clustering and Outlier Detection in Large Data Sets, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1170-1187, September 2003
	Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece
	Xuemin Lin , Jian Xu , Qing Zhang , Hongjun Lu , Jeffrey Xu Yu , Xiaofang Zhou , Yidong Yuan, Approximate Processing of Massive Continuous Quantile Queries over High-Speed Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.18 n.5, p.683-698, May 2006
	Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	John Hershberger , Subhash Suri, Adaptive sampling for geometric problems over data streams, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003
	Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Subhash Suri , Csaba D. Tóth , Yunhong Zhou, Range counting over multidimensional data streams, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, One-Pass Wavelet Decompositions of Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.541-554, March 2003
	Arvind Arasu , Gurmeet Singh Manku, Approximate counts and quantiles over sliding windows, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Duplicate detection in click streams, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Richard Cole , Dennis Shasha , Xiaojian Zhao, Fast window correlations over uncooperative time series, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Naga K. Govindaraju , Nikunj Raghuvanshi , Dinesh Manocha, Fast and approximate stream mining of quantiles and frequencies using graphics processors, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Arvind Arasu , Brian Babcock , Shivnath Babu , Jon McAlister , Jennifer Widom, Characterizing memory requirements for queries over continuous data streams, ACM Transactions on Database Systems (TODS), v.29 n.1, p.162-194, March 2004
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Domain-Driven Data Synopses for Dynamic Quantiles, IEEE Transactions on Knowledge and Data Engineering, v.17 n.7, p.927-938, July 2005
	Themis Palpanas , Nick Koudas , Alberto Mendelzon, Using Datacube Aggregates for Approximate Querying and Deviation Detection, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1465-1477, November 2005
	Bernd Finkbeiner , Sriram Sankaranarayanan , Henny B. Sipma, Collecting Statistics Over Runtime Executions, Formal Methods in System Design, v.27 n.3, p.253-274, November 2005
	Sudipto Guha , Andrew McGregor, Approximate quantiles and the order of the stream, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Atish Das Sarma , Sreenivas Gollapudi , Rina Panigrahy, Estimating PageRank on graph streams, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Foto N. Afrati , Paraskevas V. Lekeas , Chen Li, Adaptive-sampling algorithms for answering aggregation queries on Web sites, Data & Knowledge Engineering, v.64 n.2, p.462-490, February, 2008
	James P. Mcdermott , G. Jogesh Babu , John C. Liechty , Dennis K. Lin, Data skeletons: simultaneous estimation of multiple quantiles for massive streaming datasets with applications to density estimation, Statistics and Computing, v.17 n.4, p.311-321, December 2007
	Xuemin Lin, Continuously maintaining order statistics over data streams: extended abstract, Proceedings of the eighteenth conference on Australasian database, p.7-10, January 30-February 02, 2007, Ballarat, Victoria, Australia
	Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, An integrated efficient solution for computing frequent and top-k elements in data streams, ACM Transactions on Database Systems (TODS), v.31 n.3, p.1095-1133, September 2006
	S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005
	Charu C. Aggarwal, On biased reservoir sampling in the presence of stream evolution, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Graham Cormode , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Space- and time-efficient deterministic algorithms for biased quantiles over data streams, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Qi Zhang , Wei Wang, An efficient algorithm for approximate biased quantile computation in data streams, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Amit Chakrabarti , T. S. Jayram , Mihai Pǎtraşcu, Tight lower bounds for selection in randomly ordered streams, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.720-729, January 20-22, 2008, San Francisco, California
	Yannis Ioannidis, The history of histograms (abridged), Proceedings of the 29th international conference on Very large data bases, p.19-30, September 09-12, 2003, Berlin, Germany
	Graham Cormode , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Finding hierarchical heavy hitters in data streams, Proceedings of the 29th international conference on Very large data bases, p.464-475, September 09-12, 2003, Berlin, Germany
	Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
	Yunyue Zhu , Dennis Shasha, StatStream: statistical monitoring of thousands of data streams in real time, Proceedings of the 28th international conference on Very Large Data Bases, p.358-369, August 20-23, 2002, Hong Kong, China
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, How to summarize the universe: dynamic maintenance of quantiles, Proceedings of the 28th international conference on Very Large Data Bases, p.454-465, August 20-23, 2002, Hong Kong, China
	Flip Korn , S. Muthukrishnan , Divesh Srivastava, Reverse nearest neighbor aggregates over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.814-825, August 20-23, 2002, Hong Kong, China
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin Strauss, Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.79-88, September 11-14, 2001
	Naixue Xiong , Laurence T. Yang , Yingshu Li, ODMCA: An adaptive data mining control algorithm in multicarrier networks, Computer Communications, v.32 n.3, p.560-567, February, 2009
	John Hershberger , Subhash Suri, Adaptive sampling for geometric problems over data streams, Computational Geometry: Theory and Applications, v.39 n.3, p.191-208, April, 2008
	Ming Hua , Jian Pei, Continuously monitoring top-k uncertain data streams: a probabilistic threshold method, Distributed and Parallel Databases, v.26 n.1, p.29-65, August 2009
	Alan Dix , Geoff Ellis, by chance enhancing interaction with large data sets through statistical sampling, Proceedings of the Working Conference on Advanced Visual Interfaces, May 22-24, 2002, Trento, Italy