Approximating frequent items in asynchronous data stream over a sliding window
type: Item
instance of: scholarly article
title: Approximating frequent items in asynchronous data stream over a sliding window
zbMATH Open document ID: 1461.68260
author: Hing-Fung Ting
author: Lap-Kei Lee
author: Ho-Leung Chan
author: Tak-Wah Lam
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
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.
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68W27
zbMATH DE Number: 7042105
zbMATH Keywords: asynchronous data streams
zbMATH Keywords: frequent items
zbMATH Keywords: sliding window
zbMATH Keywords: space complexity
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a4030200
OpenAlex ID: W2027826195
Wikidata QID: Q58062912
cites work: Q4411371
cites work: Q3425115
cites work: Maintaining significant stream statistics over sliding windows
cites work: Maintaining Stream Statistics over Sliding Windows
cites work: Sketching asynchronous streams over a sliding window
cites work: A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window
cites work: Time-decaying Sketches for Robust Aggregation of Sensor Data
cites work: Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window
cites work: Finding repeated elements
cites work: De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
cites work: Finding frequent items over sliding windows with constant update time
DOI: 10.3390/A4030200
description: scientific article; zbMATH DE number 7042105