Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window
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 suffi...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2011-09-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/4/3/200/ |
| _version_ | 1819095270264143872 |
|---|---|
| author | Ho-Leung Chan Tak-Wah Lam Hing-Fung Ting Lap-Kei Lee |
| author_facet | Ho-Leung Chan Tak-Wah Lam Hing-Fung Ting Lap-Kei Lee |
| author_sort | Ho-Leung Chan |
| collection | DOAJ |
| description | 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/ε log W log (εB/ log W) min {log W, 1/ε} log |U|)- space data structure that can approximate the frequent items within an ε 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/ε log W log (εB/ logW) log log W) space. |
| first_indexed | 2024-12-21T23:40:38Z |
| format | Article |
| id | doaj.art-835403ea6bed46d6be06530a45606d18 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-12-21T23:40:38Z |
| publishDate | 2011-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-835403ea6bed46d6be06530a45606d182022-12-21T18:46:14ZengMDPI AGAlgorithms1999-48932011-09-014320022210.3390/a4030200Approximating Frequent Items in Asynchronous Data Stream over a Sliding WindowHo-Leung ChanTak-Wah LamHing-Fung TingLap-Kei LeeIn 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/ε log W log (εB/ log W) min {log W, 1/ε} log |U|)- space data structure that can approximate the frequent items within an ε 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/ε log W log (εB/ logW) log log W) space.http://www.mdpi.com/1999-4893/4/3/200/asynchronous data streamsfrequent itemssliding windowspace complexity |
| spellingShingle | Ho-Leung Chan Tak-Wah Lam Hing-Fung Ting Lap-Kei Lee Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window Algorithms asynchronous data streams frequent items sliding window space complexity |
| title | Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window |
| title_full | Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window |
| title_fullStr | Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window |
| title_full_unstemmed | Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window |
| title_short | Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window |
| title_sort | approximating frequent items in asynchronous data stream over a sliding window |
| topic | asynchronous data streams frequent items sliding window space complexity |
| url | http://www.mdpi.com/1999-4893/4/3/200/ |
| work_keys_str_mv | AT holeungchan approximatingfrequentitemsinasynchronousdatastreamoveraslidingwindow AT takwahlam approximatingfrequentitemsinasynchronousdatastreamoveraslidingwindow AT hingfungting approximatingfrequentitemsinasynchronousdatastreamoveraslidingwindow AT lapkeilee approximatingfrequentitemsinasynchronousdatastreamoveraslidingwindow |