{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T14:52:38Z","timestamp":1784299958060,"version":"3.55.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,2,8]],"date-time":"2016-02-08T00:00:00Z","timestamp":1454889600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"European Research Council grant","award":["ERC-2014-CoG 647557"],"award-info":[{"award-number":["ERC-2014-CoG 647557"]}]},{"name":"Yahoo Faculty Research and Engagement Program"},{"name":"Royal Society Wolfson Research Merit Award"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s00778-016-0424-7","type":"journal-article","created":{"date-parts":[[2016,2,8]],"date-time":"2016-02-08T00:32:36Z","timestamp":1454891556000},"page":"449-472","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Quantiles over data streams: experimental comparisons, new analyses, and further improvements"],"prefix":"10.1007","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2823-4488","authenticated-orcid":false,"given":"Ge","family":"Luo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lu","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,2,8]]},"reference":[{"key":"424_CR1","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/2500128","volume":"38","author":"PK Agarwal","year":"2013","unstructured":"Agarwal, P.K., Cormode, G., Huang, Z., Phillips, J.M., Wei, Z., Yi, K.: Mergeable summaries. ACM Trans. Database Syst. 38, 26 (2013)","journal-title":"ACM Trans. Database Syst."},{"key":"424_CR2","doi-asserted-by":"publisher","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58(1), 137\u2013147 (1999). doi: 10.1006\/jcss.1997.1545 . http:\/\/www.sciencedirect.com\/science\/article\/B6WJ0-45JCBTJ-D\/2\/2a71f12f1f0112bc83447b9d48eba529","DOI":"10.1006\/jcss.1997.1545"},{"key":"424_CR3","doi-asserted-by":"crossref","unstructured":"Arasu, A., Manku, G.: Approximate counts and quantiles over sliding windows. In: Proceedings of the ACM Symposium on Principles of Database Systems (2004)","DOI":"10.1145\/1055558.1055598"},{"key":"424_CR4","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rievest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7, 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"424_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (2002)","DOI":"10.1007\/3-540-45465-9_59"},{"key":"424_CR6","doi-asserted-by":"crossref","unstructured":"Cormode, G., Hadjieleftheriou, M.: Finding frequent items in data streams. In: Proceedings of the International Conference on Very Large Data Bases (2008)","DOI":"10.14778\/1454159.1454225"},{"issue":"1","key":"424_CR7","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1), 58\u201375 (2005)","journal-title":"J. Algorithms"},{"key":"424_CR8","doi-asserted-by":"crossref","unstructured":"Cormode, G., Korn, F., Muthukrishnan, S., Johnson, T., Spatscheck, O., Srivastava, D.: Holistic UDAFs at streaming speeds. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 35\u201346 (2004)","DOI":"10.1145\/1007568.1007575"},{"key":"424_CR9","doi-asserted-by":"crossref","unstructured":"Cormode, G., Garofalakis, M., Muthukrishnan, S., Rastogi, R.: Holistic aggregates in a networked world: distributed tracking of approximate quantiles. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2005)","DOI":"10.1145\/1066157.1066161"},{"key":"424_CR10","doi-asserted-by":"crossref","unstructured":"Cormode, G., Korn, F., Muthukrishnan, S., Srivastava, D.: Space- and time-efficient deterministic algorithms for biased quantiles over data streams. In: Proceedings of the ACM Symposium on Principles of Database Systems (2006)","DOI":"10.1145\/1142351.1142389"},{"key":"424_CR11","unstructured":"Felber, D., Ostrovsky, R.: A randomized online quantile summary in O(1\/ $$\\varepsilon $$ \u03b5 log 1\/ $$\\varepsilon $$ \u03b5 ) words (2015). CoRR abs\/1503.01156, http:\/\/arxiv.org\/abs\/1503.01156"},{"key":"424_CR12","unstructured":"Ganguly, S., Majumder, A.: CR-precis: A deterministic summary structure for update data streams. In: ESCAPE (2007)"},{"key":"424_CR13","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Kotidis, Y., Muthukrishnan, S., Strauss, M.J.: How to summarize the universe: dynamic maintenance of quantiles. In: Proceedings of the International Conference on Very Large Data Bases (2002)","DOI":"10.1016\/B978-155860869-6\/50047-0"},{"key":"424_CR14","doi-asserted-by":"crossref","unstructured":"Govindaraju, N.K., Raghuvanshi, N., Manocha, D.: Fast and approximate stream mining of quantiles and frequencies using graphics processors. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2005)","DOI":"10.1145\/1066157.1066227"},{"key":"424_CR15","doi-asserted-by":"crossref","unstructured":"Greenwald, M., Khanna, S.: Space-efficient online computation of quantile summaries. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2001)","DOI":"10.1145\/376284.375670"},{"key":"424_CR16","doi-asserted-by":"crossref","unstructured":"Greenwald, M., Khanna, S.: Power conserving computation of order-statistics over sensor networks. In: Proceedings of the ACM Symposium on Principles of Database Systems (2004)","DOI":"10.1145\/1055558.1055597"},{"key":"424_CR17","doi-asserted-by":"crossref","unstructured":"Huang, Z., Wang, L., Yi, K., Liu, Y.: Sampling based algorithms for quantile computation in sensor networks. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2011)","DOI":"10.1145\/1989323.1989401"},{"key":"424_CR18","doi-asserted-by":"crossref","unstructured":"Hung, R.Y.S., Ting, H.F.: An $$\\varOmega (\\frac{1}{\\varepsilon }\\log \\frac{1}{\\varepsilon })$$ \u03a9 ( 1 \u03b5 log 1 \u03b5 ) space lower bound for finding $$\\varepsilon $$ \u03b5 -approximate quantiles in a data stream. In: FAW (2010)","DOI":"10.1007\/978-3-642-14553-7_11"},{"key":"424_CR19","volume-title":"M\u00e9canique analytique","author":"JL Lagrange","year":"1853","unstructured":"Lagrange, J.L.: M\u00e9canique analytique, vol. 1. Mallet-Bachelier, Paris (1853)"},{"key":"424_CR20","unstructured":"Li, C., Hay, M., Rastogi, V., Miklau, G., McGregor, A.: Optimizing histogram queries under differential privacy (2009). CoRR abs\/0912.4742, http:\/\/arxiv.org\/abs\/0912.4742"},{"key":"424_CR21","doi-asserted-by":"crossref","unstructured":"Manku, G.S., Rajagopalan, S., Lindsay, B.G.: Approximate medians and other quantiles in one pass and with limited memory. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (1998)","DOI":"10.1145\/276304.276342"},{"key":"424_CR22","doi-asserted-by":"crossref","unstructured":"Manku, G.S., Rajagopalan, S., Lindsay, B.G.: Random sampling techniques for space efficient online computation of order statistics of large datasets. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (1999)","DOI":"10.1145\/304182.304204"},{"key":"424_CR23","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. Theor. Comput. Sci. 12, 315\u2013323 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"424_CR24","first-page":"277","volume":"13","author":"R Pike","year":"2005","unstructured":"Pike, R., Dorward, S., Griesemer, R., Quinlan, S.: Interpreting the data: parallel analysis with sawzall. Dyn. Grids Worldw. Comput. 13(4), 277\u2013298 (2005)","journal-title":"Dyn. Grids Worldw. Comput."},{"key":"424_CR25","volume-title":"Linear Statistical Inference and its Applications","author":"CR Rao","year":"2009","unstructured":"Rao, C.R.: Linear Statistical Inference and its Applications, vol. 22. Wiley, New Jersey (2009)"},{"key":"424_CR26","doi-asserted-by":"crossref","unstructured":"Shrivastava, N., Buragohain, C., Agrawal, D., Suri, S.: Medians and beyond: new aggregation techniques for sensor networks. In: Proceedings of the ACM SenSys (2004)","DOI":"10.1145\/1031495.1031524"},{"key":"424_CR27","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1007\/s00454-006-1269-4","volume":"36","author":"S Suri","year":"2006","unstructured":"Suri, S., Toth, C., Zhou, Y.: Range counting over multidimensional data streams. Discrete Comput. Geom. 36, 633\u2013655 (2006)","journal-title":"Discrete Comput. Geom."},{"key":"424_CR28","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."},{"key":"424_CR29","doi-asserted-by":"crossref","unstructured":"Wang, L., Luo, G., Yi, K., Cormode, G.: Quantiles over data streams: an experimental study. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (2013)","DOI":"10.1145\/2463676.2465312"},{"issue":"1","key":"424_CR30","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/s00453-011-9584-4","volume":"65","author":"K Yi","year":"2013","unstructured":"Yi, K., Zhang, Q.: Optimal tracking of distributed heavy hitters and quantiles. Algorithmica 65(1), 206\u2013223 (2013)","journal-title":"Algorithmica"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-016-0424-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-016-0424-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-016-0424-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T06:16:49Z","timestamp":1567577809000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-016-0424-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,8]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["424"],"URL":"https:\/\/doi.org\/10.1007\/s00778-016-0424-7","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,8]]}}}