Accuracy Bounds For The Scaled Bitmap Data Structure

Sumeet Singh, Cristian Estan, George Varghese and Stefan Savage
CS2005-0819
March 22, 2005

This report describes the {\em scaled bitmap} data structure, that can accurately estimate the number of unique elements in a set (assuming the set has a continuously increasing number of elements). This data structure is particular motivated by the need toefficiently count the number of IP addresses, infected by a network worm during an epidemic.

How to view this document

• Display an overview of the document in one of the following formats.

• Display a selected page in one of the following formats (document has 5 pages).
• Display the whole document in one of the following formats.