The P2 algorithm for dynamic calculation of quantiles and histograms without storing observations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The P2 algorithm for dynamic calculation of quantiles and histograms without storing observations

Full text

Pdf (837 KB)

Source

Communications of the ACM archive
Volume 28 , Issue 10 (October 1985) table of contents

Pages: 1076 - 1085

Year of Publication: 1985

ISSN:0001-0782

Authors

Raj Jain	Digital Equipment Corporation, Hudson, MA
Imrich Chlamtac	Technion Israel Institute of Technology, Haifa, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 69, Citation Count: 24

Additional Information:

abstract references cited by index terms review 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/4372.4378 What is a DOI?

ABSTRACT

A heuristic algorithm is proposed for dynamic calculation of the median and other quantiles. The estimates are produced dynamically as the observations are generated. The observations are not stored; therefore, the algorithm has a very small and fixed storage requirement regardless of the number of observations. This makes it ideal for implementing in a quantile chip that can be used in industrial controllers and recorders. The algorithm is further extended to histogram plotting. The accuracy of the algorithm is analyzed.

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	Buchholz, W. File organization and addressing. IBM Syst. 1. 2, (196% 66-111.
	2	Knott, G.D. Hashing functions. Cornput. 1. 18. 3 (1975). 265-276.
	3	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	4	Pearson, ES.. and Hartley, H.O. Biometrikn, Tables for Stotisticinns. Cambridge University Press, Cambridge, 1972.
	5	Peterson, W.W. Addressing for random access storage. IBM I. Res. Develop. 1. 2 (Apr. 1957). 130-146.
	6	Van der Pool, J.A. Optimum storage allocation for initial loading of a file. IBM J. Res. Develop. 16 (Nov. 1972), 579-586.
	7	Jeffrey Scott Vitter, Implementations for coalesced hashing, Communications of the ACM, v.25 n.12, p.911-926, Dec 1982 [doi>10.1145/358728.358745]

CITED BY 24

	Demet C. Wood , Bruce W. Schmeiser, Overlapping batch quantiles, Proceedings of the 27th conference on Winter simulation, p.303-308, December 03-06, 1995, Arlington, Virginia, United States
	David A. Barrett , Benjamin G. Zorn, Using lifetime predictors to improve memory allocation performance, ACM SIGPLAN Notices, v.28 n.6, p.187-196, June 1993
	Benjamin Zorn , Dirk Grunwald, Evaluating models of memory allocation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.1, p.107-131, Jan. 1994
	Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, ACM SIGMOD Record, v.25 n.2, p.294-305, June 1996
	Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, ACM SIGMOD Record, v.30 n.2, p.58-66, June 2001
	E. Jack Chen , W. David Kelton, Simulation-based estimation of quantiles, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.428-434, December 05-08, 1999, Phoenix, Arizona, United States
	Krzysztof Pawlikowski, Steady-state simulation of queueing processes: survey of problems and solutions, ACM Computing Surveys (CSUR), v.22 n.2, p.123-170, June 1990
	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
	Edward Mascarenhas , Felipe Knop , Reuben Pasquini , Vernon Rego, Minimum cost adaptive synchronization: experiments with the ParaSol system, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.4, p.401-430, Oct. 1998
	Ramin Zabih , Raj Jain, A performance comparison of the window systems of two LISP machines (abstract), Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.458, February 1986, Cincinnati, Ohio, United States
	Jennifer E. McNeill , Gerald T. Mackulak , John W. Fowler, Factory capacity and throughput planning: indirect estimation of cycle time quantiles from discrete event simulation models using the Cornish-Fisher expansion, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
	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
	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
	Jennifer McNeill Bekki , Gerald T. Mackulak , John W. Fowler, Indirect cycle-time quantile estimation for non-FIFO dispatching policies, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	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
	Jennifer E. McNeill , John. W. Fowler , Gerald T. Mackulak , Barry L. Nelson, Cycle-time quantile estimation in manufacturing systems employing dispatching rules, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	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
	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
	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
	András Varga , Rudolf Hornig, An overview of the OMNeT++ simulation environment, Proceedings of the 1st international conference on Simulation tools and techniques for communications, networks and systems & workshops, March 03-07, 2008, Marseille, France
	D. Lüdtke , D. Tutsch, The modeling power of CINSim: Performance evaluation of interconnection networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.8, p.1274-1288, June, 2009
	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
	E. Jack Chen, Metamodels for Estimating Quantiles of Systems with One Controllable Parameter, Simulation, v.85 n.5, p.307-317, May 2009

INDEX TERMS

Classification:
G. Mathematics of Computing
G.3 PROBABILITY AND STATISTICS
Subjects: Statistical computing

I. Computing Methodologies
I.6 SIMULATION AND MODELING

J. Computer Applications
J.7 COMPUTERS IN OTHER SYSTEMS
Subjects: Real time

General Terms:
Algorithms, Measurement

REVIEW

"Leonard Francis Zettel, Jr. : Reviewer"

.abstract A heuristic algorithm is proposed for dynamic calculation of the median and other quantiles. . . . [T]he algorithm has a very small and fixed storage requirement regardless of the number of observations. . . . The algorithm is further more...

Collaborative Colleagues:

Raj Jain: colleagues

Imrich Chlamtac: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player