{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:37:33Z","timestamp":1760243853892,"version":"build-2065373602"},"reference-count":16,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2011,9,22]],"date-time":"2011-09-22T00:00:00Z","timestamp":1316649600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In an asynchronous data stream, the data items may be out of order with respect to their original timestamps. This paper studies the space complexity required by a data structure to maintain such a data stream so that it can approximate the set of frequent items over a sliding time window with sufficient accuracy. Prior to our work, the best solution is given by Cormode et al. [1], who gave an O (1\/\u03b5 log W log (\u03b5B\/ log W) min {log W, 1\/\u03b5} log |U|)- space data structure that can approximate the frequent items within an \u03b5 error bound, where W and B are parameters of the sliding window, and U is the set of all possible item names. We gave a more space-efficient data structure that only requires O (1\/\u03b5 log W log (\u03b5B\/ logW) log log W) space.<\/jats:p>","DOI":"10.3390\/a4030200","type":"journal-article","created":{"date-parts":[[2011,9,23]],"date-time":"2011-09-23T03:53:57Z","timestamp":1316750037000},"page":"200-222","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window"],"prefix":"10.3390","volume":"4","author":[{"given":"Hing-Fung","family":"Ting","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Hong Kong, Pokfulam, Hong Kong, China"}]},{"given":"Lap-Kei","family":"Lee","sequence":"additional","affiliation":[{"name":"MADALGO (Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation), Department of Computer Science, Aarhus University, Aarhus C DK-8000, Denmark"}]},{"given":"Ho-Leung","family":"Chan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Hong Kong, Pokfulam, Hong Kong, China"}]},{"given":"Tak-Wah","family":"Lam","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Hong Kong, Pokfulam, Hong Kong, China"}]}],"member":"1968","published-online":{"date-parts":[[2011,9,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cormode, G., Korn, F., and Tirthapura, S. (2008, January 9\u201311). Time-Decaying Aggregates in Out-of-Order Streams. Vancouver, Canada.","DOI":"10.1145\/1376916.1376930"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/762471.762473","article-title":"A simple algorithm for finding frequent elements in streams and bags","volume":"28","author":"Karp","year":"2003","journal-title":"ACM Trans. Database Syst."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Demaine, E., Lopez-Ortiz, A., and Munro, J. (2002, January 17\u201321). Frequency Estimation of Internet Packet Streams with Limited Space. Rome, Italy.","DOI":"10.1007\/3-540-45749-6_33"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S. (2005). Data Streams: Algorithms and Applications, Now Publisher Inc.","DOI":"10.1561\/9781933019604"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Babcock, B., Babu, S., Datar, M., Motwani, R., and Widom, J. (2002, January 3\u20135). Models and Issues in Data Stream Systems. Madison, WI, USA.","DOI":"10.1145\/543613.543615"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Arasu, A., and Manku, G. (2004, January 14\u201316). Approximate Counts and Quantiles over Sliding Windows. Paris, France.","DOI":"10.1145\/1055558.1055598"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Lee, L.K., and Ting, H.F. (2006, January June). A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows. Chicago, Illinois, USA.","DOI":"10.1145\/1142351.1142393"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Lee, L.K., and Ting, H.F. (2006, January 22\u201326). Maintaining Significant Stream Statistics over Sliding Windows. Miami, FL, USA.","DOI":"10.1145\/1109557.1109636"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1794","DOI":"10.1137\/S0097539701398363","article-title":"Maintaining stream statistics over sliding windows","volume":"31","author":"Datar","year":"2002","journal-title":"SIAMJ. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Tirthapura, S., Xu, B., and Busch, C. (2006, January 23\u201326). Sketching Asynchronous Streams over a Sliding Window. Denver, CO, USA.","DOI":"10.1145\/1146381.1146397"},{"key":"ref_11","unstructured":"Busch, C., and Tirthapua, S. (2007, January 22\u201324). A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window. Aachen, Germany."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1309","DOI":"10.1137\/08071795X","article-title":"Time-decaying sketches for robust aggregation of sensor data","volume":"39","author":"Cormode","year":"2009","journal-title":"SIAM J. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Chan, H.L., Lam, T.W., Lee, L.K., and Ting, H.F. (2009, January 10\u201311). Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window. Copenhagen, Denmark.","DOI":"10.1007\/978-3-642-12450-1_5"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0167-6423(82)90012-0","article-title":"Finding repeated elements","volume":"2","author":"Misra","year":"1982","journal-title":"Sci. Comput. Program."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., and Segev, G. (2009, January 5\u201312). De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results. Rhodes, Greece.","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/j.ipl.2009.01.027","article-title":"Finding frequent items over sliding windows with constant update time","volume":"110","author":"Hung","year":"2010","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/4\/3\/200\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:57:28Z","timestamp":1760219848000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/4\/3\/200"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,22]]},"references-count":16,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2011,9]]}},"alternative-id":["a4030200"],"URL":"https:\/\/doi.org\/10.3390\/a4030200","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2011,9,22]]}}}