Approximate medians and other quantiles in one pass and with limited memory

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate medians and other quantiles in one pass and with limited memory

Full text

Pdf (1.25 MB)

Source

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

Seattle, Washington, United States

Pages: 426 - 435

Year of Publication: 1998

ISBN:0-89791-995-5

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

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 53, Citation Count: 66

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/276304.276342 What is a DOI?

ABSTRACT

We present new algorithms for computing approximate quantiles of large datasets in a single pass. The approximation guarantees are explicit, and apply for arbitrary value distributions and arrival distributions of the dataset. The main memory requirements are smaller than those reported earlier by an order of magnitude. We also discuss methods that couple the approximation algorithms with random sampling to further reduce memory requirements. With sampling, the approximation guarantees are explicit but probabilistic, i.e. they apply with respect to a (user controlled) confidence parameter. We present the algorithms, their theoretical analysis and simulation results on different datasets.

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	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]
	2	Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	3	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
	4	"DB2 MVS:", To be completed.
	5	"Informix", To be completed.
	6	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
	7	M. Blum, R. W. Floyd, V. R. Pratt, R. L. Rivest, and R. E. Tarjan, "Time Bounds for Selection", in J. Cornput. Syst. Sci., vol. 7, pp. 448-461, 1973.
	8	M. R. Paterson, "Progress in Selection", Deptt. of Computer Science, University of Warwick, Coventry, UK, 1997.
	9	D. Dor, Selection Algorithms, PhD thesis, Tel-Aviv University, 1995.
	10	Dorit Dor , Uri Zwick, Selecting the median, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.28-37, January 22-24, 1995, San Francisco, California, United States
	11	D. Dot and U. Zwick, "Finding the anth Largest Element", Combinatorica, vol. 16, pp. 41-58, 1996.
	12	D. Dor and U. Zwick, "Median Selection Requires (2 q-e)n Comparisons", Technical Report 312/96, Department of Computer Science, Tel-Aviv University, Apr. 1996.
	13	F. F. Yao, ON LOWER BOUNDS FOR SELECTION PROBLEMS, Massachusetts Institute of Technology, Cambridge, MA, 1974
	14	I. Pohl, "A Minimum Storage Algorithm for Computing the Median", Technical Report IBM Research Report RC 2701 (# 12713), IBM T J Watson Center, Nov. 1969.
	15	J. I. Munro and M. S. Paterson, "Selection and Sorting with Limited Storage", Theoretical Computer Science, vol. 12, pp. 315-323, 1980.
	16	Raj Jain , Imrich Chlamtac, The P2 algorithm for dynamic calculation of quantiles and histograms without storing observations, Communications of the ACM, v.28 n.10, p.1076-1085, Oct. 1985 [doi>10.1145/4372.4378]
	17	R. Agrawal and A. Swami, "A One-Pass Space-Efficient Algorithm for Finding Quantiles", in Proc. 7th Intl. Conf. Management of Data (COMAD-95), Pune, India, 1995.
	18	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
	19	W. Hoeffding, "Probability Inequalities for Sum8 of Bounded Random Variables", American Statistical Association Jornal, pp. 13-30, Mar. 1963.

CITED BY 66

	Fei Chen , Diane Lambert , José C. Pinheiro, Incremental quantile estimation for massive tracking, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.516-522, August 20-23, 2000, Boston, Massachusetts, United States
	Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy, Tracking join and self-join sizes in limited storage, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.10-20, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	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
	Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.909-910, January 17-19, 1999, Baltimore, Maryland, United States
	Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, ACM SIGMOD Record, v.30 n.2, p.58-66, June 2001
	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
	Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining data streams under block evolution, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002
	Hua-Huai Chern , Hsien-Kuei Hwang , Tsung-Hsi Tsai, An asymptotic theory for Cauchy---Euler differential equations with applications to the analysis of algorithms, Journal of Algorithms, v.44 n.1, p.177-225, July 2002
	Sanguthevar Rajasekaran, Sorting and selection on parallel disk models, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Random sampling techniques for space efficient online computation of order statistics of large datasets, ACM SIGMOD Record, v.28 n.2, p.251-262, June 1999
	Ashraf Aboulnaga , Surajit Chaudhuri, Self-tuning histograms: building histograms without looking at data, ACM SIGMOD Record, v.28 n.2, p.181-192, June 1999
	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
	M. Otey , S. Parthasarathy , A. Ghoting , G. Li , S. Narravula , D. Panda, Towards NIC-based intrusion detection, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	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
	Edith Cohen , Haim Kaplan, Spatially-decaying aggregation over a network: model and algorithms, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Classifying Matrices Separating Rows and Columns, IEEE Transactions on Parallel and Distributed Systems, v.15 n.7, p.654-665, July 2004
	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
	Theodore Johnson, Data warehousing, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Graham Cormode , Theodore Johnson , Flip Korn , S. Muthukrishnan , Oliver Spatscheck , Divesh Srivastava, Holistic UDAFs at streaming speeds, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 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
	Graham Cormode , Minos Garofalakis , S. Muthukrishnan , Rajeev Rastogi, Holistic aggregates in a networked world: distributed tracking of approximate quantiles, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	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
	Michael B. Greenwald , Sanjeev Khanna, Power-conserving computation of order-statistics over sensor networks, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	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
	Graham Cormode , S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, v.55 n.1, p.58-75, April 2005
	Boulat A. Bash , John W. Byers , Jeffrey Considine, Approximately uniform random sampling in sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada
	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
	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
	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
	Sudipto Guha , Nick Koudas , Kyuseok Shim, Approximation and streaming algorithms for histogram construction problems, ACM Transactions on Database Systems (TODS), v.31 n.1, p.396-438, March 2006
	Surajit Chaudhuri , Vivek Narasayya, Automating Statistics Management for Query Optimizers, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.7-20, January 2001
	Eric Anderson , Mahesh Kallahalla , Mustafa Uysal , Ram Swaminathan, Buttress: A Toolkit for Flexible and High Fidelity I/O Benchmarking, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
	Karl Schnaitter , Joshua Spiegel , Neoklis Polyzotis, Depth estimation for ranking query optimization, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	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
	Srikanta Tirthapura , Bojian Xu , Costas Busch, Sketching asynchronous streams over a sliding window, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Goetz Graefe, Implementing sorting in database systems, ACM Computing Surveys (CSUR), v.38 n.3, p.10-es, 2006
	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
	Edith Cohen , Haim Kaplan, Spatially-decaying aggregation over a network, Journal of Computer and System Sciences, v.73 n.3, p.265-288, May, 2007
	Yannis Kotidis, Extending the data warehouse for service provisioning data, Data & Knowledge Engineering, v.59 n.3, p.700-724, December 2006
	Yury Bakshi , David A. Hoeflin, Quantile estimation: a minimalist approach, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	Nagender Bandi , Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Fast data stream algorithms using associative memories, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Damianos Chatziantoniou, Using grouping variables to express complex decision support queries, Data & Knowledge Engineering, v.61 n.1, p.114-136, April, 2007
	Yossi Matias , Daniel Urieli, Optimal workload-based weighted wavelet synopses, Theoretical Computer Science, v.371 n.3, p.227-246, March, 2007
	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
	Feng Tian , David J. DeWitt, Tuple routing strategies for distributed eddies, Proceedings of the 29th international conference on Very large data bases, p.333-344, 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
	Tsai-Hung Fan , Dennis K. J. Lin , Kuang-Fu Cheng, Regression analysis for massive datasets, Data & Knowledge Engineering, v.61 n.3, p.554-562, June, 2007
	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
	Bertram Ludäscher , Pratik Mukhopadhyay , Yannis Papakonstantinou, A transducer-based XML query processor, Proceedings of the 28th international conference on Very Large Data Bases, p.227-238, August 20-23, 2002, Hong Kong, China
	Yossi Matias , Jeffrey Scott Vitter , Min Wang, Dynamic Maintenance of Wavelet-Based Histograms, Proceedings of the 26th International Conference on Very Large Data Bases, p.101-110, September 10-14, 2000
	Yannis Kotidis, A Data Warehousing Architecture for Enabling Service Provisioning Process, Proceedings of the 27th International Conference on Very Large Data Bases, p.481-490, September 11-14, 2001
	Haixun Wang , Carlo Zaniolo, Using SQL to Build New Aggregates and Extenders for Object- Relational Systems, Proceedings of the 26th International Conference on Very Large Data Bases, p.166-175, September 10-14, 2000
	Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
	Lixin Fu , Sanguthevar Rajasekaran, Evaluating holistic aggregators efficiently for very large datasets, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.2, p.148-161, May 2004
	Sankardas Roy , Mauro Conti , Sanjeev Setia , Sushil Jajodia, Securely computing an approximate median in wireless sensor networks, Proceedings of the 4th international conference on Security and privacy in communication netowrks, September 22-25, 2008, Istanbul, Turkey
	Balachander Krishnamurthy , Phillipa Gill , Martin Arlitt, A few chirps about twitter, Proceedings of the first workshop on Online social networks, August 18-18, 2008, Seattle, WA, USA
	Eric Anderson, Capture, conversion, and analysis of an intense NFS workload, Proccedings of the 7th conference on File and stroage technologies, p.139-152, February 24-27, 2009, San Francisco, California
	Karl Schnaitter , Joshua Spiegel , Neoklis Polyzotis, Depth estimation for ranking query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.2, p.521-542, April 2009
	Kenneth A. Ross , John Cieslewicz, Optimal splitters for database partitioning with size bounds, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
	Ying Hu , Seema Sundara , Jagannathan Srinivasan, Estimating aggregates in time-constrained approximate queries in Oracle, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Nadeem Akhtar , Faraz Khan , Mohammed A Qadeer, Information processing using data stream management system on Jamdroid, Proceedings of the International Conference on Advances in Computing, Communication and Control, January 23-24, 2009, Mumbai, India
	Sankardas Roy , Mauro Conti , Sanjeev Setia , Sushil Jajodia, Secure median computation in wireless sensor networks, Ad Hoc Networks, v.7 n.8, p.1448-1462, November, 2009
	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