University of Adelaide Library

Adelaide Research and Scholarship : Schools and Disciplines : School of Mathematical Sciences : Mathematical Sciences publications

Please use this identifier to cite or link to this item:

Times cited in Scopus
Times cited in Web of Science®
Type: Journal article
Title: Spatio-temporal compressive sensing and internet traffic matrices (extended version)
Author: Roughan, M.
Zhang, Y.
Willinger, W.
Qiu, L.
Citation: IEEE - ACM Transactions on Networking, 2012; 20(3):662-676
Publisher: IEEE-Inst Electrical Electronics Engineers Inc
Issue Date: 2012
ISSN: 1063-6692
Statement of
Matthew Roughan, Yin Zhang, Walter Willinger and Lili Qiu
Abstract: Despite advances in measurement technology, it is still challenging to reliably compile large-scale network datasets. For example, because of flaws in the measurement systems or difficulties posed by the measurement problem itself, missing, ambiguous, or indirect data are common. In the case where such data have spatio-temporal structure, it is natural to try to leverage this structure to deal with the challenges posed by the problematic nature of the data. Our work involving network datasets draws on ideas from the area of compressive sensing and matrix completion, where sparsity is exploited in estimating quantities of interest. However, the standard results on compressive sensing are: 1) reliant on conditions that generally do not hold for network datasets; and 2) do not allow us to exploit all we know about their spatio-temporal structure. In this paper, we overcome these limitations with an algorithm that has at its heart the same ideas espoused in compressive sensing, but adapted to the problem of network datasets. We show how this algorithm can be used in a variety of ways, in particular on traffic data, to solve problems such as simple interpolation of missing values, traffic matrix inference from link data, prediction, and anomaly detection. The elegance of the approach lies in the fact that it unifies all of these tasks and allows them to be performed even when as much as 98% of the data is missing.
Keywords: Compressed sensing; interpolation; prediction methods; tomography.
Rights: © 2011 IEEE
RMID: 0020120418
DOI: 10.1109/TNET.2011.2169424
Grant ID:
Appears in Collections:Mathematical Sciences publications
View citing articles in: Web of Science
Google Scholar

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2008 The University of Adelaide
CRICOS Provider Number 00123M
Service Charter | Copyright | Privacy | Disclaimer