DIMACS TR: 2003-31

What's New: Finding Significant Differences in Network Data Streams



Authors: Graham Cormode and S. Muthukrishnan

ABSTRACT

Monitoring and analyzing network traffic usage patterns is vital for managing IP Networks. An important problem is to provide network managers with information about changes in traffic, informing them about "what's new". Specifically, we focus on the challenge of finding significant differences in traffic: over time, between interfaces and between routers. We introduce the idea of a "deltoid": an item that has a large difference, whether the difference is absolute, relative or variational.

We design algorithms for finding the most significant deltoids in high speed data, and prove that they use small space, small time per update, and are guaranteed to find significant deltoids with pre-specified accuracy. In experimental evaluation, our algorithms perform well and recover almost all deltoids. This is the first work to provide solutions capable of working with one pass, at network traffic speeds.

Paper available at ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-31.ps.gz

DIMACS Home Page