Counting Distinct Objects over Sliding Windows

Zhang, W; Zhang, Y; Cheema, MA; Lin, X

Counting Distinct Objects over Sliding Windows

Zhang, W Zhang, Y

Cheema, MA Lin, X

Permalink

Publication Type:: Conference Proceeding
Citation:: Conferences in Research and Practice in Information Technology Series, 2010, 104 pp. 75 - 84
Issue Date:: 2010-12-01

Closed Access

	Filename	Description	Size
	2013005474OK.pdf		363.24 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, W	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Cheema, MA	en_US
dc.contributor.author	Lin, X	en_US
dc.date.issued	2010-12-01	en_US
dc.identifier.citation	Conferences in Research and Practice in Information Technology Series, 2010, 104 pp. 75 - 84	en_US
dc.identifier.issn	1445-1336	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28969
dc.description.abstract	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.	en_US
dc.relation.ispartof	Conferences in Research and Practice in Information Technology Series	en_US
dc.title	Counting Distinct Objects over Sliding Windows	en_US
dc.type	Conference Proceeding
utslib.citation.volume	104	en_US
utslib.for	0806 Information Systems	en_US
dc.location.activity	Brisbane, Australia	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US
pubs.volume	104	en_US

Abstract:

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:

http://hdl.handle.net/10453/28969