Pandora: An Efficient and Rapid Solution for Persistence-Based Tasks in High-Speed Data Streams
Proceedings of the ACM on Management of Data · 10.02.2025 · 3 (1) · 1-26
DOI: 10.1145/3709711 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 11.02.2025. Verfasst von Weihe Li. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 65 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
In data streams, persistence characterizes items that appear repeatedly across multiple non-overlapping time windows. Addressing persistence-based tasks, such as detecting highly persistent items and estimating persistence, is crucial for applications like recommendation systems and anomaly detection in high-velocity data streams. However, these tasks are challenging due to stringent requirements for rapid processing and limited memory resources. Existing methods often struggle with accuracy, especially given highly skewed data distributions and tight fastest memory budgets, where hash collisions are severe. In this paper, we introduce Pandora, a novel approximate data structure designed to tackle these challenges efficiently. Our approach incorporates the insight that items absent for extended periods are likely non-persistent, increasing their probability of eviction to accommodate potential persistent items more effectively. We validate this insight empirically and integrate it into our update strategy, providing better protection for persistent items. We formally analyze Pandora's error bounds to validate its theoretical soundness. Through extensive trace-driven tests, we demonstrate that Pandora achieves superior accuracy and processing speed compared to state-of-the-art methods across various persistence-based tasks. Additionally, we further accelerate Pandora's update speed using Single Instruction Multiple Data (SIMD) instructions, enhancing its efficiency in high-speed data stream environments. The code for our method is open-sourced.
Zitieren
APA
Li, W. (2025). Pandora: An Efficient and Rapid Solution for Persistence-Based Tasks in High-Speed Data Streams. Proceedings of the ACM on Management of Data, 3(1), 1-26. https://doi.org/10.1145/3709711
Vancouver
Li W. Pandora: An Efficient and Rapid Solution for Persistence-Based Tasks in High-Speed Data Streams. Proceedings of the ACM on Management of Data. 2025;3(1):1-26. doi:10.1145/3709711
BibTeX
@article{Li2025,
author = {Li, Weihe},
title = {Pandora: An Efficient and Rapid Solution for Persistence-Based Tasks in High-Speed Data Streams},
journal = {Proceedings of the ACM on Management of Data},
year = {2025},
volume = {3},
number = {1},
pages = {1--26},
doi = {10.1145/3709711}
}
EUVIMED