The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Spatio-Temporal Compressive Sensing and Internet Traffic Matrices (Extended Version)
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Donoho, D. L. (2004) · Cited by 16,703
An Introduction To Compressive Sampling
Candes, E. J., & Wakin, M. B. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.914731 · Cited by 10,017
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Lee, D. D., & Seung, H. S. (2000) · neural information processing systems · Cited by 9,873
Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
Candes, E. J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.885507 · Cited by 6,839
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Recht, B., Fazel, M., & Parrilo, P. A. (2010) · SIAM Review · doi:10.1137/070697835 · Cited by 3,471
Diagnosing network-wide traffic anomalies
Lakhina, A., Crovella, M., & Diot, C. (2004) · Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/1015467.1015492 · Cited by 1,039
The nature of data center traffic: measurements & analysis
Kandula, S., Sengupta, S., Greenberg, A., Patel, P., & Chaiken, R. (2009) · Proceedings of the 9th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1644893.1644918 · Cited by 1,030
A storage model with self-similar input
Norros, I. (1994) · Queueing Systems · doi:10.1007/bf01158964 · Cited by 848
Network Tomography: Estimating Source-Destination Traffic Intensities from Link Data
Vardi, Y. (1996) · Journal of the American Statistical Association · doi:10.1080/01621459.1996.10476697 · Cited by 794
A signal analysis of network traffic anomalies
Barford, P., Kline, J., Plonka, D., & Ron, A. (2002) · Proceedings of the second ACM SIGCOMM Workshop on Internet measurment - IMW '02 · doi:10.1145/637201.637210 · Cited by 787
Optimizing OSPF/IS-IS weights in a changing world
Fortz, B., & Thorup, M. (2002) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2002.1003042 · Cited by 660
Fast accurate computation of large-scale IP traffic matrices from link loads
Zhang, Y., Roughan, M., Duffield, N., & Greenberg, A. (2003) · Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems · doi:10.1145/781027.781053 · Cited by 505
Self-citationTraffic matrix estimation: existing techniques and new directions
Medina, A., Taft, N., Salamatian, K., Bhattacharyya, S., & Diot, C. (2002) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/633025.633041 · Cited by 488
Structural analysis of network traffic flows
Lakhina, A., Papagiannaki, K., Crovella, M., Diot, C., Kolaczyk, E. D., & Taft, N. (2004) · Proceedings of the joint international conference on Measurement and modeling of computer systems · doi:10.1145/1005686.1005697 · Cited by 451
Deriving traffic demands for operational IP networks: methodology and experience
Feldmann, A., Greenberg, A., Lund, C., Reingold, N., Rexford, J., & True, F. (2001) · IEEE/ACM Transactions on Networking · doi:10.1109/90.929850 · Cited by 430
Sensitivity of PCA for traffic anomaly detection
Ringberg, H., Soule, A., Rexford, J., & Diot, C. (2007) · Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems · doi:10.1145/1254882.1254895 · Cited by 353
An information-theoretic approach to traffic matrix estimation
Zhang, Y., Roughan, M., Lund, C., & Donoho, D. (2003) · Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/863955.863990 · Cited by 303
Self-citationZhang⋆, Y., Ge, Z., Greenberg, A. G., & Roughan, M. (2005) · doi:10.5555/1251086.1251116 · Cited by 209
Self-citationSimplifying the synthesis of internet traffic matrices
Roughan, M. (2005) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1096536.1096551 · Cited by 199
Self-citationZhang, Y., Roughan, M., Lund, C., & Donoho, D. L. (2005) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2005.857115 · Cited by 185
Self-citationApplying PCA for Traffic Anomaly Detection: Problems and Solutions
Brauckhoff, D., Salamatian, K., & May, M. (2009) · IEEE INFOCOM 2009 · doi:10.1109/infcom.2009.5062248 · Cited by 179
Zhang, Y., Ge, Z., Greenberg, A. G., & Roughan, M. (2005) · ACM Internet Measurement Conference (IMC) · doi:10.1145/1330107.1330146 · Cited by 156
Self-citationModeling distances in large-scale networks by matrix factorization
Mao, Y. J., & Saul, L. K. (2004) · ACM Internet Measurement Conference (IMC) · doi:10.1145/1028788.1028827 · Cited by 153
Communication-Efficient Online Detection of Network-Wide Anomalies
Huang, L., Nguyen, X., Garofalakis, M., Hellerstein, J. M., Jordan, M. I., Joseph, A. D., & Taft, N. (2007) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2007.24 · Cited by 124
The many facets of internet topology and traffic
Alderson, D., Chang, H., Roughan, M., Uhlig, S., & Willinger, W. (2006) · Networks and Heterogeneous Media · doi:10.3934/nhm.2006.1.569 · Cited by 77
Self-citationAn empirical approach to modeling inter-AS traffic matrices
Chang, H., Jamin, S., Mao, Z. M., et al. (2005) · doi:10.5555/1251086.1251098 · Cited by 67
BasisDetect: a model-based network event detection framework
Eriksson, B., Barford, P., Bowden, R. A., Duffield, N. G., Sommers, J., & Roughan, M. (2010) · ACM Internet Measurement Conference (IMC) · doi:10.1145/1879141.1879200 · Cited by 33
Self-citation
Metadata
- Authors
- Roughan, M., Zhang, Y., Willinger, W., & Qiu, L.
- Venue
- IEEE/ACM Transactions on Networking
- Published
- 2012-06
- Volume
- 20
- Issue
- 3
- Pages
- 662-676
- ISSN
- 1063-6692 (ISSN-L)
- 1558-2566
- OpenAlex
- W2117368434
- Cited by
- 267
- References
- 30
- FWCI
- 3.87
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.