DIMACS TR: 2003-31
What's New: Finding Significant Differences in Network
Authors: Graham Cormode and S. Muthukrishnan
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
DIMACS Home Page