{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T01:16:48Z","timestamp":1768699008222,"version":"3.49.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>\n            While traditional data-management systems focus on evaluating single, ad-hoc queries over static data sets in a centralized setting, several emerging applications require (possibly, continuous) answers to queries on\n            <jats:italic>dynamic<\/jats:italic>\n            data that is widely\n            <jats:italic>distributed<\/jats:italic>\n            and constantly updated. Furthermore, such query answers often need to discount data that is \"stale\", and operate solely on a\n            <jats:italic>sliding window<\/jats:italic>\n            of recent data arrivals (e.g., data updates occurring over the last 24 hours). Such\n            <jats:italic>distributed data streaming<\/jats:italic>\n            applications mandate novel algorithmic solutions that are both time- and space-efficient (to manage high-speed data streams), and also communication-efficient (to deal with physical data distribution). In this paper, we consider the problem of complex query answering over distributed, high-dimensional data streams in the sliding-window model. We introduce a novel sketching technique (termed\n            <jats:italic>ECM-sketch<\/jats:italic>\n            ) that allows effective summarization of streaming data over both time-based and count-based sliding windows with probabilistic accuracy guarantees. Our sketch structure enables point as well as inner-product queries, and can be employed to address a broad range of problems, such as maintaining frequency statistics, finding heavy hitters, and computing quantiles in the sliding-window model. Focusing on distributed environments, we demonstrate how ECM-sketches of individual, local streams can be composed to generate a (low-error) ECM-sketch summary of the order-preserving aggregation of all streams; furthermore, we show how ECM-sketches can be exploited for continuous monitoring of sliding-window queries over distributed streams. Our extensive experimental study with two real-life data sets validates our theoretical claims and verifies the effectiveness of our techniques. To the best of our knowledge, ours is the first work to address efficient, guaranteed-error complex query answering over distributed data streams in the sliding-window model.\n          <\/jats:p>","DOI":"10.14778\/2336664.2336672","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"992-1003","source":"Crossref","is-referenced-by-count":57,"title":["Sketch-based querying of distributed sliding-window data streams"],"prefix":"10.14778","volume":"5","author":[{"given":"Odysseas","family":"Papapetrou","sequence":"first","affiliation":[{"name":"Technical University of Crete"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minos","family":"Garofalakis","sequence":"additional","affiliation":[{"name":"Technical University of Crete"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonios","family":"Deligiannakis","sequence":"additional","affiliation":[{"name":"Technical University of Crete"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.844498"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1763424.1763480"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9506-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684566"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2005.01.006"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366106"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066161"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773182"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/08071795X"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398363"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2008.08.014"},{"key":"e_1_2_1_14_1","first-page":"541","volume-title":"VLDB","author":"Gibbons P. B.","year":"2001","unstructured":"P. B. Gibbons . Distinct sampling for highly-accurate answers to distinct values queries and event reports . In VLDB , pages 541 -- 550 , 2001 . P. B. Gibbons. Distinct sampling for highly-accurate answers to distinct values queries and event reports. In VLDB, pages 541--550, 2001."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/564870.564880"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375670"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2007.93"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.24"},{"key":"e_1_2_1_19_1","first-page":"699","volume-title":"LATIN","author":"Hung R. Y. S.","year":"2008","unstructured":"R. Y. S. Hung and H.-F. Ting . Finding heavy hitters over the sliding window of a weighted data stream . In LATIN , pages 699 -- 710 , 2008 . R. Y. S. Hung and H.-F. Ting. Finding heavy hitters over the sliding window of a weighted data stream. In LATIN, pages 699--710, 2008."},{"key":"e_1_2_1_20_1","volume-title":"SIGCOMM Workshop on Hot Topics in Networks (HotNets)","author":"Jain A.","year":"2004","unstructured":"A. Jain , J. M. Hellerstein , S. Ratnasamy , and D. Wetherall . A wakeup call for internet monitoring systems: The case for distributed triggers . In SIGCOMM Workshop on Hot Topics in Networks (HotNets) , 2004 . A. Jain, J. M. Hellerstein, S. Ratnasamy, and D. Wetherall. A wakeup call for internet monitoring systems: The case for distributed triggers. In SIGCOMM Workshop on Hot Topics in Networks (HotNets), 2004."},{"key":"e_1_2_1_21_1","unstructured":"D. Kotz T. Henderson I. Abyzov and J. Yeo. CRAWDAD trace set dartmouth\/campus\/snmp (v. 2004-11-09). http:\/\/crawdad.cs.dartmouth.edu\/dartmouth\/campus\/snmp.  D. Kotz T. Henderson I. Abyzov and J. Yeo. CRAWDAD trace set dartmouth\/campus\/snmp (v. 2004-11-09). http:\/\/crawdad.cs.dartmouth.edu\/dartmouth\/campus\/snmp."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645532.656169"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872825"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.2003.1214970"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142508"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146397"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0048-7"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2336664.2336672","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:45:52Z","timestamp":1672224352000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2336664.2336672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":27,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.14778\/2336664.2336672"],"URL":"https:\/\/doi.org\/10.14778\/2336664.2336672","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}