Space-efficient online computation of quantile summaries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Space-efficient online computation of quantile summaries

Full text

Pdf (233 KB)

Source

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

Santa Barbara, California, United States

Pages: 58 - 66

Year of Publication: 2001

ISBN:1-58113-332-4

Also published in ...

Authors

Michael Greenwald	Computer & Information Science Department, University of Pennsylvania, 200 South 33rd Street, Philadelphia, PA
Sanjeev Khanna	Computer & Information Science Department, University of Pennsylvania, 200 South 33rd Street, Philadelphia, PA

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 111, Citation Count: 87

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

ABSTRACT

An ∈-approximate quantile summary of a sequence of N elements is a data structure that can answer quantile queries about the sequence to within a precision of ∈N.

We present a new online algorithm for computing∈-approximate quantile summaries of very large data sequences. The algorithm has a worst-case space requirement of &Ogr;(1÷∈ log(∈N)). This improves upon the previous best result of &Ogr;(1÷∈ log²(∈N)). Moreover, in contrast to earlier deterministic algorithms, our algorithm does not require a priori knowledge of the length of the input sequence.

Finally, the actual space bounds obtained on experimental data are significantly better than the worst case guarantees of our algorithm as well as the observed space requirements of earlier algorithms.

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	Rakesh Agrawal and Arun Swami. A one-pass space-efficient algorithm for finding quantiles. Proc. 7th Int. Conf. Management of Data, COMAD, 28-30 December 1995.
	2	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
	3	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
	4	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
	5	Michael Greenwald, Practical algorithms for self scaling histograms or better than average data collection, Performance Evaluation, 27-28, p.19-40, Oct. 1996 [doi>10.1016/0166-5316(96)00043-0]
	6	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]
	7	I. Pohl. A minimum storage algorithm for computing the median. IBM Research Report RC 2701, November 1969.
	8	Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Approximate medians and other quantiles in one pass and with limited memory, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.426-435, June 01-04, 1998, Seattle, Washington, United States
	9	Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Random sampling techniques for space efficient online computation of order statistics of large datasets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.251-262, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	10	J. I. Munro and M.S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, vol. 12: 315-323; 1980.
	11	M.S. Paterson. Progress in selection. Technical Report, University ofWarwick, Coventry, UK, 1997.
	12	Viswanath Poosala, Venkatesh Ganti, and Yannis E. Ioannidis. Approximate query answering using histograms. Bulletin of the IEEE Technical Committee on Data Engineering, 22(4):6-15, December 1999.
	13	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

CITED BY 87

	Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast incremental maintenance of approximate histograms, ACM Transactions on Database Systems (TODS), v.27 n.3, p.261-298, September 2002
	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
	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
	Minos Garofalakis , Amit Kumar, Correlating XML data streams using tree-edit distance embeddings, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.143-154, June 09-11, 2003, San Diego, California
	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
	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
	Haixun Wang , Wei Fan , Philip S. Yu , Jiawei Han, Mining concept-drifting data streams using ensemble classifiers, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001
	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
	Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Approximate join processing over data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Phillip B. Gibbons , Srikanta Tirthapura, Distributed streams algorithms for sliding windows, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	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
	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
	Amitabha Bagchi , Amitabh Chaudhary , David Eppstein , Michael T. Goodrich, Deterministic sampling and range counting in geometric data streams, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	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
	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
	Nisheeth Shrivastava , Chiranjeeb Buragohain , Divyakant Agrawal , Subhash Suri, Medians and beyond: new aggregation techniques for sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA
	Sreenivas Gollapudi , D. Sivakumar, Framework and algorithms for trend analysis in massive temporal data sets, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	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
	Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Semantic Approximation of Data Stream Joins, IEEE Transactions on Knowledge and Data Engineering, v.17 n.1, p.44-59, January 2005
	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
	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
	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
	Minos Garofalakis , Amit Kumar, XML stream processing using tree-edit distance embeddings, ACM Transactions on Database Systems (TODS), v.30 n.1, p.279-332, March 2005
	Timothy M. Chan , Eric Y. Chen, Multi-pass geometric algorithms, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	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
	Theodore Johnson , S. Muthukrishnan , Irina Rozenbaum, Sampling algorithms in a stream operator, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Graham Cormode , Minos Garofalakis, Sketching streams through the net: distributed approximate query tracking, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	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
	Rohit Ananthakrishna , Abhinandan Das , Johannes Gehrke , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Efficient Approximation of Correlated Sums on Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.569-572, March 2003
	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
	Wei Fan, Systematic data selection to mine concept-drifting data streams, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	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
	Jiawei Han , Yixin Chen , Guozhu Dong , Jian Pei , Benjamin W. Wah , Jianyong Wang , Y. Dora Cai, Stream Cube: An Architecture for Multi-Dimensional Analysis of Data Streams, Distributed and Parallel Databases, v.18 n.2, p.173-197, September 2005
	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
	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
	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
	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
	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
	S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005
	Haixun Wang , Jian Yin , Jian Pei , Philip S. Yu , Jeffrey Xu Yu, Suppressing model overfitting in mining concept-drifting data streams, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	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
	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
	Xuemin Lin , Qing Zhang , Yidong Yuan , Qing Liu, Error minimization in approximate range aggregates, Data & Knowledge Engineering, v.62 n.1, p.156-176, July, 2007
	Yury Bakshi , David A. Hoeflin, Quantile estimation: a minimalist approach, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	Zhang Longbo , Li Zhanhuai , Zhao Yiqiang , Yu Min , Zhang Yang, A priority random sampling algorithm for time-based sliding windows over weighted streaming data, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	Wee Hyong Tok , Stéphane Bressan , Mong-Li Lee, A stratified approach to progressive approximate joins, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	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
	Wei Fan, StreamMiner: a classifier ensemble-based engine to mine concept-drifting data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.1257-1260, August 31-September 03, 2004, Toronto, Canada
	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
	Yixin Chen , Guozhu Dong , Jiawei Han , Benjamin W. Wah , Jianyong Wang, Multi-dimensional regression analysis of time-series data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.323-334, August 20-23, 2002, Hong Kong, China
	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
	Amitabha Bagchi , Amitabh Chaudhary , David Eppstein , Michael T. Goodrich, Deterministic sampling and range counting in geometric data streams, ACM Transactions on Algorithms (TALG), v.3 n.2, p.16-es, May 2007
	T. S. Jayram , Andrew McGregor , S. Muthukrishnan , Erik Vee, Estimating statistical aggregates on probabilistic data streams, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Amit Chakrabarti , Graham Cormode , Andrew McGregor, Robust lower bounds for communication and stream computation, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Surajit Chaudhuri , Gautam Das , Vivek Narasayya, Optimized stratified sampling for approximate query processing, ACM Transactions on Database Systems (TODS), v.32 n.2, p.9-es, June 2007
	Rob Pike , Sean Dorward , Robert Griesemer , Sean Quinlan, Interpreting the data: Parallel analysis with Sawzall, Scientific Programming, v.13 n.4, p.277-298, October 2005
	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
	Minos N. Garofalakis , Phillip B. Gibbon, Approximate Query Processing: Taming the TeraBytes, Proceedings of the 27th International Conference on Very Large Data Bases, p.725, September 11-14, 2001
	Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Tracking set-expression cardinalities over continuous update streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.354-369, December 2004
	Yixin Chen , Guozhu Dong , Jiawei Han , Jian Pei , Benjamin W. Wah , Jianyong Wang, Regression Cubes with Lossless Compression and Aggregation, IEEE Transactions on Knowledge and Data Engineering, v.18 n.12, p.1585-1599, December 2006
	Graham Cormode , Minos Garofalakis, Approximate continuous querying over distributed streams, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-39, June 2008
	Piotr Indyk , Andrew McGregor, Declaring independence via the sketching of sketches, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.737-745, January 20-22, 2008, San Francisco, California
	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
	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
	Graham Cormode , Marios Hadjieleftheriou, Finding frequent items in data streams, Proceedings of the VLDB Endowment, v.1 n.2, August 2008
	Yufei Tao , Xiaokui Xiao, Efficient temporal counting with bounded error, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1271-1292, August 2008
	Sudipto Das , Divyakant Agrawal , Amr El Abbadi, CAM conscious integrated answering of frequent elements and top-k queries over data streams, Proceedings of the 4th international workshop on Data management on new hardware, June 13-13, 2008, Vancouver, Canada
	Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Multi-query optimization for sketch-based estimation, Information Systems, v.34 n.2, p.209-230, April, 2009
	T. S. Jayram , Andrew McGregor , S. Muthukrishnan , Erik Vee, Estimating statistical aggregates on probabilistic data streams, ACM Transactions on Database Systems (TODS), v.33 n.4, p.1-30, November 2008
	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
	Ke Yi , Qin Zhang, Optimal tracking of distributed heavy hitters and quantiles, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Dan Jurca , Rolf Stadler, Computing histograms of local variables for real-time monitoring using aggregation trees, Proceedings of the 11th IFIP/IEEE international conference on Symposium on Integrated Network Management, p.367-374, June 01-05, 2009, New York, NY, USA
	Ke Yi , Feifei Li , Graham Cormode , Marios Hadjieleftheriou , George Kollios , Divesh Srivastava, Small synopses for group-by query verification on outsourced data streams, ACM Transactions on Database Systems (TODS), v.34 n.3, p.1-42, August 2009
	Dengcheng He , Yongluan Zhou , Lidan Shou , Gang Chen, Cluster based rank query over multidimensional data streams, Proceeding of the 18th ACM conference on Information and knowledge management, November 02-06, 2009, Hong Kong, China