Approximating frequent items in asynchronous data stream over a sliding window

DOI10.3390/A4030200MaRDI QIDQ1736485zbMATH OpenOpenAlexWikidataFDO

Authors Hing-Fung Ting, Lap-Kei Lee, Ho-Leung Chan, Tak-Wah Lam

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a4030200

zbMATH Keywords

asynchronous data streamsfrequent itemssliding windowspace complexity

Mathematics Subject Classification ID

Data structures (68P05) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Review text

Summary: 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 \textit{G. Cormode} [``Time-decaying aggregates in out-of-order streams, in: Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, PODS'08. New York, NY. 89--98 (2008; \url{doi:10.1145/1376916.1376930})], who gave an \(O\left(\frac{1}{\epsilon} \log W \log\left(\frac{\epsilon B}{\log W}\right) \min \left\{\log W, \frac{1}{\epsilon} \right\} \log | U|\right)\)-space data structure that can approximate the frequent items within an \(\epsilon\) 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\left(\frac{1}{\epsilon} \log W \log\left(\frac{\epsilon B}{\log W}\right) \log \log W\right)\) space.

Recommendations

• Approximating frequent items in asynchronous data stream over a sliding window
• Finding frequent items over sliding windows with constant update time
• An efficient algorithm for mining approximate frequent item over data streams
• A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window
• Sketching asynchronous data streams over sliding windows

Cites work

• A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window
• Approximating frequent items in asynchronous data stream over a sliding window
• Data streams: algorithms and applications.
• De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
• Finding frequent items over sliding windows with constant update time
• Finding repeated elements
• scientific article; zbMATH DE number 1947405 (Why is no real title available?)
• Maintaining significant stream statistics over sliding windows
• Maintaining Stream Statistics over Sliding Windows
• Sketching asynchronous streams over a sliding window
• Time-decaying sketches for robust aggregation of sensor data

Cited in

(4)

• Sketching asynchronous data streams over sliding windows
• The Frequent Items Problem in Online Streaming Under Various Performance Measures
• Approximating frequent items in asynchronous data stream over a sliding window
• The frequent items problem, under polynomial decay, in the streaming model

This page was built for publication: Approximating frequent items in asynchronous data stream over a sliding window

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736485)