Liu, Jiaqian;
Dai, Haipeng;
Xia, Rui;
Li, Meng;
Basat, Ran Ben;
Li, Rui;
Chen, Guihai;
(2022)
DUET: A Generic Framework for Finding Special Quadratic Elements in Data Streams.
In:
Proceedings of the ACM Web Conference 2022.
(pp. pp. 2989-2997).
ACM
Preview |
Text
DUET.pdf - Other Download (3MB) | Preview |
Abstract
Finding special items, like heavy hitters, top-k, and persistent items, has always been a hot issue in data stream processing for web analysis. While data streams nowadays are usually high-dimensional, most prior works focus on special items according to a certain primary dimension and yield little insight into the correlations between dimensions. Therefore, we propose to find special quadratic elements to reveal close correlations. Based on the items mentioned above, we extend our problem to three applications related to heavy hitters, top-k, and persistent items, and design a generic framework DUET to process them. Besides, we analyze the error bound of our algorithm and conduct extensive experiments on four data sets. Our experimental results show that DUET can achieve 3.5 times higher throughput and three orders of magnitude lower average relative error compared with cutting-edge algorithms.
| Type: | Proceedings paper |
|---|---|
| Title: | DUET: A Generic Framework for Finding Special Quadratic Elements in Data Streams |
| Event: | WWW '22: The ACM Web Conference 2022 |
| ISBN-13: | 9781450390965 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1145/3485447.3512019 |
| Publisher version: | https://doi.org/10.1145/3485447.3512019 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| Keywords: | data stream mining, sketch, data structure |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10152895 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
