Counting Distinct Objects over Sliding Windows

Publication Type:
Conference Proceeding
Citation:
Conferences in Research and Practice in Information Technology Series, 2010, 104 pp. 75 - 84
Issue Date:
2010-12-01
Metrics:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005474OK.pdf363.24 kB
Adobe PDF
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: