{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:43:08Z","timestamp":1758271388388,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["GRF-621413"],"award-info":[{"award-number":["GRF-621413"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Database queries can be broadly classified into two categories: reporting queries and aggregation queries. The former retrieves a collection of records from the database that match the query's conditions, while the latter returns an aggregate, such as count, sum, average, or max (min), of a particular attribute of these records. Aggregation queries are especially useful in business intelligence and data analysis applications where users are interested not in the actual records, but some statistics of them. They can also be executed much more efficiently than reporting queries, by embedding properly precomputed aggregates into an index.<\/jats:p>\n          <jats:p>However, reporting and aggregation queries provide only two extremes for exploring the data. Data analysts often need more insight into the data distribution than what those simple aggregates provide, and yet certainly do not want the sheer volume of data returned by reporting queries. In this article, we design indexing techniques that allow for extracting a statistical summary of all the records in the query. The summaries we support include frequent items, quantiles, and various sketches, all of which are of central importance in massive data analysis. Our indexes require linear space and extract a summary with the optimal or near-optimal query cost. We illustrate the efficiency and usefulness of our designs through extensive experiments and a system demonstration.<\/jats:p>","DOI":"10.1145\/2508702","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Indexing for summary queries"],"prefix":"10.1145","volume":"39","author":[{"given":"Ke","family":"Yi","sequence":"first","affiliation":[{"name":"Tsinghua University and Hong Kong University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Wang","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhewei","family":"Wei","sequence":"additional","affiliation":[{"name":"MADALGO and Aarhus University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,1,6]]},"reference":[{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Afshani P.","key":"e_1_2_1_1_1","unstructured":"P. Afshani , G. S. Brodal , and N. Zeh . 2011. Ordered and unordered top-k range reporting in large data sets . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. P. Afshani, G. S. Brodal, and N. Zeh. 2011. Ordered and unordered top-k range reporting in large data sets. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213562"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal and J. Erickson. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry. American Mathematical Society 1--56.  P. K. Agarwal and J. Erickson. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry. American Mathematical Society 1--56.","DOI":"10.1090\/conm\/223\/03131"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1813"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240481X"},{"key":"e_1_2_1_8_1","unstructured":"R. A. Baeza-Yates and G. H. Gonnet. 1991. Handbook of Algorithms and Data Structures. Addison-Wesley.   R. A. Baeza-Yates and G. H. Gonnet. 1991. Handbook of Algorithms and Data Structures. Addison-Wesley."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247504"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0050-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007602"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276343"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases.","author":"Cormode G.","key":"e_1_2_1_15_1","unstructured":"G. Cormode and M. Hadjieleftheriou . 2008. Finding frequent items in data streams . In Proceedings of the International Conference on Very Large Data Bases. G. Cormode and M. Hadjieleftheriou. 2008. Finding frequent items in data streams. In Proceedings of the International Conference on Very Large Data Bases."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Datar M.","key":"e_1_2_1_17_1","unstructured":"M. Datar , A. Gionis , P. Indyk , and R. Motwani . 2002. Maintaining stream statistics over sliding windows . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. M. Datar, A. Gionis, P. Indyk, and R. Motwani. 2002. Maintaining stream statistics over sliding windows. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375665"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases.","author":"Gilbert A. C.","key":"e_1_2_1_19_1","unstructured":"A. C. Gilbert , Y. Kotidis , S. Muthukrishnan , and M. J. Strauss . 2002. How to summarize the universe: Dynamic maintenance of quantiles . In Proceedings of the International Conference on Very Large Data Bases. A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss. 2002. How to summarize the universe: Dynamic maintenance of quantiles. In Proceedings of the International Conference on Very Large Data Bases."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989401"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412335"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"J\u00f8rgensen A.","key":"e_1_2_1_25_1","unstructured":"A. J\u00f8rgensen and K. Larsen . 2011. Range selection and median: Tight cell probe lower bounds and adaptive data structures . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. A. J\u00f8rgensen and K. Larsen. 2011. Range selection and median: Tight cell probe lower bounds and adaptive data structures. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms."},{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering.","author":"Lin X.","key":"e_1_2_1_26_1","unstructured":"X. Lin , Y. Yuan , Q. Zhang , and Y. Zhang . 2007. Selecting stars: The k most representative skyline operator . In Proceedings of the IEEE International Conference on Data Engineering. X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang. 2007. Selecting stars: The k most representative skyline operator. In Proceedings of the IEEE International Conference on Data Engineering."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213594"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_32_1","unstructured":"H. Samet. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann.   H. Samet. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.84"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering.","author":"Tao Y.","year":"2004","unstructured":"Y. Tao , G. Kollios , J. Considine , F. Li , and Papadias. 2004 . Spatio-temporal aggregation using sketches . In Proceedings of the IEEE International Conference on Data Engineering. Y. Tao, G. Kollios, J. Considine, F. Li, and Papadias. 2004. Spatio-temporal aggregation using sketches. In Proceedings of the IEEE International Conference on Data Engineering."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"volume-title":"Algorithms and Data Structures for External Memory","author":"Vitter J. S.","key":"e_1_2_1_37_1","unstructured":"J. S. Vitter . 2008. Algorithms and Data Structures for External Memory . Now Publishers . J. S. Vitter. 2008. Algorithms and Data Structures for External Memory. Now Publishers."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989299"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2508702","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2508702","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:52Z","timestamp":1750231732000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2508702"}},"subtitle":["Theory and practice"],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2508702"],"URL":"https:\/\/doi.org\/10.1145\/2508702","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2012-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}