{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:24:56Z","timestamp":1773887096513,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:p>\n            Stream frequency measurements are fundamental in many data stream applications such as financial data trackers, intrusion-detection systems, and network monitoring. Typically, recent data items are more relevant than old ones, a notion we can capture through a\n            <jats:italic>sliding window<\/jats:italic>\n            abstraction. This paper considers a generalized sliding window model that supports stream frequency queries over an interval given at\n            <jats:italic>query time.<\/jats:italic>\n            This enables drill-down queries, in which we can examine the behavior of the system in finer and finer granularities. For this model, we asymptotically improve the space bounds of existing work, reduce the update and query time to a constant, and provide deterministic solutions. When evaluated over real Internet packet traces, our fastest algorithm processes items 90--250 times faster, serves queries at least 730 times quicker and consumes at least 40% less space than the best known method.\n          <\/jats:p>","DOI":"10.14778\/3297753.3297762","type":"journal-article","created":{"date-parts":[[2019,2,27]],"date-time":"2019-02-27T14:57:56Z","timestamp":1551279476000},"page":"433-445","source":"Crossref","is-referenced-by-count":14,"title":["Stream frequency over interval queries"],"prefix":"10.14778","volume":"12","author":[{"given":"Ran Ben","family":"Basat","sequence":"first","affiliation":[{"name":"Harvard University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roy","family":"Friedman","sequence":"additional","affiliation":[{"name":"CS Technion"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rana","family":"Shahout","sequence":"additional","affiliation":[{"name":"CS Technion"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Open source code. https:\/\/github.com\/r4n4sh\/IFQ.  Open source code. https:\/\/github.com\/r4n4sh\/IFQ."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3131365.3131407"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055598"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154273.3154332"},{"key":"e_1_2_1_6_1","first-page":"23","article-title":"Volumetric hierarchical heavy hitters","volume":"13","author":"Basat R. B.","year":"2018","journal-title":"Network"},{"key":"e_1_2_1_7_1","unstructured":"R. Ben-Basat. Succinct approximate rank queries. CoRR\/1704.07710 2017.  R. Ben-Basat. Succinct approximate rank queries. CoRR\/1704.07710 2017."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524364"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057216"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3098822.3098832"},{"key":"e_1_2_1_11_1","unstructured":"R. Ben-Basat R. Friedman and R. Shahout. Stream frequency over interval queries. CoRR abs\/1804.10740 2018.  R. Ben-Basat R. Friedman and R. Shahout. Stream frequency over interval queries. CoRR abs\/1804.10740 2018."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862923"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0172-z"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1324172.1324174"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2013.05.007"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398363"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740658"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633056"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065211"},{"key":"e_1_2_1_22_1","unstructured":"P. Hick. CAIDA Anonymized Internet Trace equinix-chicago 2016.  P. Hick. CAIDA Anonymized Internet Trace equinix-chicago 2016."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.01.027"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956918"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009840925866"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142393"},{"key":"e_1_2_1_28_1","volume-title":"IEEE","author":"Lin X.","year":"2004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2008.11.001"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_27"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"J. Misra and D. Gries. Finding repeated elements. Technical report 1982.   J. Misra and D. Gries. Finding repeated elements. Technical report 1982.","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790265.2790281"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0380-7"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3297753.3297762","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:34:43Z","timestamp":1672220083000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3297753.3297762"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.14778\/3297753.3297762"],"URL":"https:\/\/doi.org\/10.14778\/3297753.3297762","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,12]]}}}