{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:24:24Z","timestamp":1758266664075,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642402722"},{"type":"electronic","value":"9783642402739"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40273-9_7","type":"book-chapter","created":{"date-parts":[[2013,8,10]],"date-time":"2013-08-10T01:20:34Z","timestamp":1376097634000},"page":"77-96","source":"Crossref","is-referenced-by-count":11,"title":["Frugal Streaming for Estimating Quantiles"],"prefix":"10.1007","author":[{"given":"Qiang","family":"Ma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Sandler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","unstructured":"Agrawal, R., Swami, A.: A one-pass space-efficient algorithm for finding quantiles. In: Proc. 7th Intl. Conf. Management of Data, COMAD 1995 (1995)"},{"key":"7_CR2","unstructured":"Alsabti, K., Ranka, S., Singh, V.: A one-pass algorithm for accurately estimating quantiles for disk-resident data. In: Proc. 23rd VLDB Conference, pp. 346\u2013355 (1997)"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1145\/1055558.1055598","volume-title":"Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2004","author":"A. Arasu","year":"2004","unstructured":"Arasu, A., Manku, G.S.: Approximate counts and quantiles over sliding windows. In: Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2004, pp. 286\u2013296. ACM, New York (2004)"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1145\/773153.773176","volume-title":"Proceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2003","author":"B. Babcock","year":"2003","unstructured":"Babcock, B., Datar, M., Motwani, R., O\u2019Callaghan, L.: Maintaining variance and k-medians over data stream windows. In: Proceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2003, pp. 234\u2013243. ACM, New York (2003)"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11767831_1","volume-title":"Privacy Enhancing Technologies","author":"G.D. Bissias","year":"2006","unstructured":"Bissias, G.D., Liberatore, M., Jensen, D., Levine, B.N.: Privacy vulnerabilities in encrypted HTTP streams. In: Danezis, G., Martin, D. (eds.) PET 2005. LNCS, vol.\u00a03856, pp. 1\u201311. Springer, Heidelberg (2006)"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1145\/1142351.1142389","volume-title":"Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2006","author":"G. Cormode","year":"2006","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 Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2006, pp. 263\u2013272. ACM, New York (2006)"},{"issue":"1","key":"7_CR7","doi-asserted-by":"publisher","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. Journal of Algorithms\u00a055(1), 58\u201375 (2005)","journal-title":"Journal of Algorithms"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Cranor, C., Johnson, T., Spataschek, O.: Gigascope: a stream database for network applications. In: SIGMOD, pp. 647\u2013651 (2003)","DOI":"10.1145\/872757.872838"},{"key":"7_CR9","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 28th International Conference on Very Large Data Bases, VLDB 2002, pp. 454\u2013465. VLDB Endowment (2002)","DOI":"10.1016\/B978-155860869-6\/50047-0"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1145\/376284.375670","volume":"30","author":"M. Greenwald","year":"2001","unstructured":"Greenwald, M., Khanna, S.: Space-efficient online computation of quantile summaries. SIGMOD Rec.\u00a030, 58\u201366 (2001)","journal-title":"SIGMOD Rec."},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"2044","DOI":"10.1137\/07069328X","volume":"38","author":"S. Guha","year":"2009","unstructured":"Guha, S., Mcgregor, A.: Stream order and order statistics: Quantile estimation in random-order streams. SIAM Journal on Computing\u00a038, 2044\u20132059 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR12","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1145\/1989323.1989401","volume-title":"Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD 2011","author":"Z. Huang","year":"2011","unstructured":"Huang, Z., Wang, L., Yi, K., Liu, Y.: Sampling based algorithms for quantile computation in sensor networks. In: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, pp. 745\u2013756. ACM, New York (2011)"},{"key":"7_CR13","first-page":"362","volume-title":"Proceedings of the 20th International Conference on Data Engineering, ICDE 2004","author":"X. Lin","year":"2004","unstructured":"Lin, X., Lu, H., Xu, J., Yu, J.X.: Continuously maintaining quantile summaries of the most recent n elements over a data stream. In: Proceedings of the 20th International Conference on Data Engineering, ICDE 2004, pp. 362\u2013374. IEEE Computer Society, Washington, DC (2004)"},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1145\/276305.276342","volume":"27","author":"G.S. Manku","year":"1998","unstructured":"Manku, G.S., Rajagopalan, S., Lindsay, B.G.: Approximate medians and other quantiles in one pass and with limited memory. SIGMOD Rec.\u00a027, 426\u2013435 (1998)","journal-title":"SIGMOD Rec."},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Mcgregor, A., Valiant, P.: The shifting sands algorithm. In: SODA (2012)","DOI":"10.1137\/1.9781611973099.39"},{"issue":"3","key":"7_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"J.I. Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. Theoretical Computer Science\u00a012(3), 315\u2013323 (1980)","journal-title":"Theoretical Computer Science"},{"key":"7_CR17","first-page":"239","volume-title":"Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, SenSys 2004","author":"N. Shrivastava","year":"2004","unstructured":"Shrivastava, N., Buragohain, C., Agrawal, D., Suri, S.: Medians and beyond: new aggregation techniques for sensor networks. In: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, SenSys 2004, pp. 239\u2013249. ACM, New York (2004)"}],"container-title":["Lecture Notes in Computer Science","Space-Efficient Data Structures, Streams, and Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40273-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T14:09:34Z","timestamp":1646316574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40273-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642402722","9783642402739"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40273-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}