Understanding data completeness in network monitoring systems

Flip Korn, Ruilin Liu, Hui Wang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

In many networks including Internet Service Providers, transportation monitoring systems and the electric grid, measurements from a set of objects are continuously taken over time and used for important decisions such as provisioning and pricing. It is therefore vital to understand the completeness and reliability of such data. Given the large volume of data generated by these systems, rather than enumerating the times and objects incurringmissing or spurious data, it is more effective to provide patterns (groups of tuples) concisely summarizing trends that may not otherwise be readily observable. In this paper, we define the Graph Tableau Discovery Problem where the measured tuples can be thought of as edges in a bipartite graph on an ordered attribute (time) and an unordered attribute (object identifiers). We define the problem of finding an optimal summary, show that it is NP-complete, and then provide a polynomial-time approximation algorithm with guarantees to find a good summary. Experiments on real and synthetic data demonstrate the effectiveness and efficiency of our approach.

Original languageEnglish
Title of host publicationProceedings - 12th IEEE International Conference on Data Mining, ICDM 2012
Pages359-368
Number of pages10
DOIs
StatePublished - 2012
Event12th IEEE International Conference on Data Mining, ICDM 2012 - Brussels, Belgium
Duration: 10 Dec 201213 Dec 2012

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Conference

Conference12th IEEE International Conference on Data Mining, ICDM 2012
Country/TerritoryBelgium
CityBrussels
Period10/12/1213/12/12

Fingerprint

Dive into the research topics of 'Understanding data completeness in network monitoring systems'. Together they form a unique fingerprint.

Cite this