Counting Distinct Objects over Sliding Windows
- Publication Type:
- Conference Proceeding
- Conferences in Research and Practice in Information Technology Series, 2010, 104 pp. 75 - 84
- Issue Date:
Aggregation against distinct objects has been in-volved in many real applications with the presence of duplicates, including real-time monitoring mov-ing objects. In this paper, we investigate the prob-lem of counting distinct objects over sliding windows with arbitrary lengths. We present novel, time and space efficient, one scan algorithms to continuously maintain a sketch so that the counting can be ap-proximately conducted with a relative error guaran-tee ∈ in the presence of object duplicates. Efficient query algorithms have also been developed by ef-fectively utilizing the skyband property. Moreover, the proposed techniques may be immediately applied to the range counting aggregation and heavy hitter problem against distinct elements. A comprehensive performance study demonstrates that our algorithms can support real-time computation against high speed data streams. © 2010, Australian Computer Society, Inc.
Please use this identifier to cite or link to this item: