Mobile crowd sensing (MCS) has emerged as a promising sensing paradigm with the widespread adoption of smartphones. However, one of the key bottlenecks in MCS lies in the high sensing cost imposed on mobile users. To alleviate this burden, sparse sensing strategies are often employed, where data is collected from a limited number of locations and the remaining data is inferred by exploiting spatio-temporal correlations. Compared with vector-based inference approaches, matrix completion techniques can better capture two-dimensional correlations in the sensing data, thereby achieving higher recovery accuracy. Nevertheless, their performance degrades significantly when the actual sensing rate is low. In this paper, we propose a novel matrix-reshaping strategy that is applied prior to matrix completion to enhance recovery performance under sparse observations. We provide a theoretical analysis demonstrating that the reshaping process reduces the number of measurements required for successful matrix recovery. To validate our approach, we conduct extensive experiments using traditional matrix completion algorithms, deep learning models, and tensor completion methods on six real-world datasets. The results show that, to achieve the same level of recovery accuracy, our reshaped matrices consistently reduce the measurement overhead compared to their original ones.

Sparse network monitoring, a breakthrough technology for cost-effective network-wide monitoring, has garnered significant attention from researchers and network equipment providers. By measuring only a subset of paths and nodes, it leverages the network’s low-rank property to obtain comprehensive monitoring data. However, a previously unnoticed vulnerability called the"global diffusion vulnerability"poses a significant threat to sparse network monitoring. This vulnerability suggests that if a few measurement samples are tainted, the entire network monitoring data can become inaccurate, leading to potential network failures and adverse effects on routing and bandwidth allocation. This paper presents the first exploration of the"global diffusion vulnerability"to launch effective attacks on sparse network monitoring. Sparse monitoring often employs various imputation models to estimate unmeasured data and collects multiple perspectives of network-wide data over extended periods. The challenges in attacking sparse monitoring lie in designing perturbations that can impact all views of network-wide data over time, regardless of the specific imputation models, while remaining unobtrusive. To tackle these challenges, we propose ModelFreeUP, the first perturbation generation algorithm designed for sparse network monitoring. ModelFreeUP creates imputation model-free, universal, and unobtrusive perturbations that exert a significant influence on multiple perspectives of network-wide data over time. Our experiments demonstrate that ModelFreeUP effectively disrupts the sparse monitoring process, causing substantial deviations in the network-wide monitoring data at a relatively low attack cost. Furthermore, when the manipulated monitoring data is used for downstream routing tasks, it triggers 100% Maximum Link Utilization in the Abilene network, indicating network congestion or failure. By shedding light on these critical mismeasurement issues, our work emphasizes the need for robust countermeasures against adversarial attacks in the network monitoring domain.

Matrix completion is a method for imputing missing data, typically based on the assumption of a low-rank structure. However, in practice, various factors can obscure this structure, leading to a perceived high-rank nature. Recently, a few studies begin to address high-rank data completion, their methods rely on specific hypothesis distributions that are often impractical to validate in real-world scenarios. Therefore, in this paper, we tackle high-rank data completion without any hypothesis distribution. Firstly, we theoretically demonstrate that the Radial Basis Function (RBF) kernel feature mapping has the capability to transform general high-rank data into low-rank data in a higher-dimensional feature space. Secondly, combining with the adaptive row and column neighbor information, a novel graph-based high-rank matrix completion algorithm is developed. Thirdly, experiments on four real datasets across three domains demonstrate that the proposed method reduces reconstruction error by up to 63% compared to the second-best method at the same missing rate. Furthermore, to achieve similar accuracy, it requires up to 40% fewer samples. Our code is released at https://github.com/shiqinyeah/Graph-HRMC.git.

Sparse data gathering has become a promising solution for reducing measurement costs by leveraging the inherent sparsity of data. However, most existing approaches rely on low-dimensional models such as compressive sensing or matrix completion, which are limited in capturing complex high-dimensional structures. To overcome these limitations, we proposeTensorMon, a novel tensor-based sparse data gathering framework that introduces a cuboid sampling strategy to more effectively exploit multidimensional correlations. Unlike traditional entry-based or tube-based sampling, TensorMon introduces the innovative concept ofcuboid sampling. We further develop a lightweight sampling scheduling algorithm and a non-iterative inference algorithm to ensure efficient measurement planning and accurate reconstruction of unmeasured data. Theoretical analysis establishes a new performance bound for our sampling strategy, which is significantly lower than those in existing literature. To validate our theoretical findings, we conduct extensive experiments on four real-world datasets: two network monitoring datasets, a city-scale crowd flow dataset, and a road traffic speed dataset. Experimental results demonstrate that TensorMon achieves substantial reductions in measurement cost, delivers high inference accuracy, and ensures rapid data recovery, highlighting its effectiveness and practicality across diverse application scenarios.

Network distance measurement is crucial for evaluating network performance, attracting significant research attention. However, conducting measurements for the entire network is exceedingly expensive and time-consuming, making the reduction of network distance measurement costs a top priority. The tensor completion method efficiently reduces measurement costs by utilizing a small amount of measured data to estimate the entire network’s distance data. Unfortunately, current tensor completion methods still suffer from issues such as complex sample selection, high measurement overhead, slow recovery, and low inference accuracy. To address the aforementioned challenges, we present an online network-wide distance measurement scheme. In this approach, continuous distance data are structured into sliding-window-based tensors. Our method incorporates a lightweight sample selection algorithm with a lowest sampling bound and a rapid, accurate unmeasured data inference algorithm. We have conducted extensive experiments using four real network distance datasets and two citywide crowd flow datasets. The empirical evaluations demonstrate the effectiveness of our approach, particularly in reducing measurement costs and enhancing data recovery accuracy.

The surge in demand for latency-sensitive services has propelled network distance measurement to the forefront of networking research. Utilizing the low-rank structure of full network data, the tensor completion method can efficiently estimate network distance from partially sampled distance data measured from a small set of node pairs. However, its performance is affected by sampling algorithm limitations, including unreliability and high overhead in dynamic networks. To tackle these challenges, we propose tube-based sampling as an alternative to point-based sampling, utilizing a partition-based algorithm to incorporate randomness for improved reliability. Additionally, we introduce a Tube Length Identification Algorithm to dynamically adjust tube length based on network status, balancing scheduling overhead reduction with estimation accuracy. Experimental results on three real network distance datasets, compared against 13 baseline algorithms, demonstrate the high accuracy and low scheduling overhead of our approach.

In network distance measurement, how to estimate the whole network distance data from partially observed samples has attracted lots of attention because of its significance for network performance evaluation. Matrix completion becomes the most effective approach. However, the two-dimension matrix can only capture the spatial features in the network distance data while ignoring the temporal features. To conquer the problem, few recent studies begin to model the network distance data as a three-dimension tensor and propose tensor completion approaches for distance estimation. Although promising, existing tensor completion approaches still suffer the problem of low recovery accuracy and high measurement cost because they ignore the history priority information. To fully utilize both spatial and temporal features hidden in the distance data, this paper formulates a novel History Priority Enhanced Tensor Completion (HPETC) for distance estimation as a weighted tensor nuclear norm minimization problem where the weight is defined based on the history subspaces information. To solve the weighted tensor nuclear norm minimization problem, we firstly transform it into a factorization-based Frobenius norm minimization problem to avoid costly T-SVD computations, and then propose an iterative algorithm to solve the transformed problem. We further derive a theoretical sampling bound that is lower than the existing sampling bound, thus leads a lower measurement cost. We demonstrate the effectiveness of the proposed algorithm by conducting extensive experiments using two real network distance datasets. The result shows that the proposed algorithm can not only improve the estimation accuracy but also reduce the sampling complexity compared to the state-of-the-art approaches.

Traffic matrices (TMs) are essential for managing networks. Getting the whole TMs is difficult because of the high measurement cost. Several recent studies propose sparse measurement schemes to reduce the cost, which involve taking measurements on only a subset of origin and destination pairs (OD pairs) and inferring data for unmeasured OD pairs through matrix completion. However, existing sparse network measurement schemes suffer from the problems of high computation costs and low recovery quality. This paper investigates the coherence feature of real traffic flow data traces (Abilene and GÈANT). Both data sets are high coherence, with column coherence greater than row coherence. According to the coherence feature of both data sets, we propose our Redundant Row Subspace-based Matrix Completion (RRS-MC). RRS-MC involves several techniques. Firstly, we design an algorithm to identify subspace rows (OD pairs) from historical data. Secondly, based on the identified subspace rows, we design our sampling scheduling algorithm, which takes full measurement samples in subspace rows while taking partial measurement samples in the remaining rows. Moreover, we propose a redundant sampling rule prevent the recovery accuracy decrease caused by the subspace rows varying. Finally, we design a completion algorithm to recover the partially measured rows. We conduct extensive experiments. Results indicate that the proposed scheme is superior to the state-of-the-art sampling and completion scheme in computation costs and recovery accuracy.

In network-wide monitoring, finding the large monitoring data entries is a fundamental network management function. However, the retrieval of large entries is extremely difficult and challenging as a result of incompleteness of network measurement data. Enlightened by tensor model’s strong capability of information representation and extraction, we model the network-wide monitoring data as a 3-way tensor. With tensor completion, the retrieval can be performed after recovering all missing entries. However, this not only incurs an extremely high cost when the tensor is large, but is also unnecessary. Instead, to quickly retrieve large entries at low cost, we transform the large entry retrieving problem to a cosine similarity searching problem, and propose two algorithms: 1) Quickly reordering the factor vectors based on Locality Sensitive Hashing (LSH) hash table so that vectors with small cosine distances are placed in the same hash bucket; 2) Quickly finding the similar vector of a queried one that the two together determine a large entry without incurring the high cost of recovering all entries through the dot products. In the process of LSH table building and similarity query, several novel techniques are proposed, including LSH table representation with the LSH forest, good hash table building to support the flexible search of cosine similarity, and bit-shifting-based quick similarity query. Our experimental studies on 4 real world datasets indicate that our technique is at least up to 60 times faster than the approach based on direct tensor completion.

Due to high network measurement cost, network-wide monitoring faces many challenges. For a network consisting of n nodes, the cost of one time network-wide monitoring will be O(n2). To reduce the monitoring cost, inspired by recent progress of matrix completion, a novel sparse network monitoring scheme is proposed to obtain network-wide monitoring data by sampling a few paths while inferring monitoring data of others. However, current sparse network monitoring schemes suffer from the problems of high measurement cost, high computation complexity in sampling scheduling, and long time to recover the un-sampled data. We propose a novel block matrix completion that can guarantee the quality of the un-sampled data inference by selecting as few as m = O(nr ln(r)) samples for a rank r N × T matrix with n = max{N,T}, which largely reduces the sampling complexity as compared to the existing algorithm for matrix completion. Based on block matrix completion, we further propose a light weight sampling scheduling algorithm to select measurement samples and a light weight data inference algorithm to quickly and accurately recover the un-sampled data. Extensive experiments on three real network monitoring data sets verify our theoretical claims and demonstrate the effectiveness of the proposed algorithms.

Network-wide monitoring is important for many network functions. Due to the need of sampling to reduce high measurement cost, system failure, and unavoidable data transmission loss, network monitoring systems suffer from the incompleteness of network monitoring data. Different from the traditional network monitoring data estimation problem which aims to infer all missing monitoring data entries with incomplete measurement data, we study a challenging problem of inferring the top-$k$largest monitoring data entries. The recent study shows it is promising to more accurately interpolate the missing data with a 3-D tensor compared to that based on a 2-D matrix. Taking full advantage of the multilinear structures, we apply tensor completion to first recover the missing data and then find the top-$k$data entries. To reduce the computational overhead, we propose a novel discrete tensor completion model which uses binary codes to represent the factor matrices. Based on the model, we further propose three novel techniques to speed up the whole top-$k$entry inference process: a discrete optimization algorithm to train the binary factor matrices, bit operations to facilitate quick missing data inference, and simplifying the finding of top-$k$largest entries with binary code partition. In our discrete tensor completion model, only one bit is needed to represent the entry in the factor matrices instead of a real value (32 bits) needed in traditional tensor completion model, thus the storage cost is reduced significantly. To quickly infer the top-$k$largest data entries when measurement data arrive sequentially, we also propose a sliding window based online algorithm using the discrete tensor completion model. Extensive experiments using five real data sets and one synthetic data set demonstrate that compared with the state of art tensor completion algorithms, our discrete tensor completion algorithm can achieve similar top-$k$entry inference accuracy using significantly smaller time and storage space.

Finding top- k elephant flows is a critical task in network measurement, with applications such as congestion control, anomaly detection, and traffic engineering. Traditional top- k flow detection problem focuses on using a small amount of memory to measure the total number of packets or bytes of each flow. Instead, we study a challenging problem of inferring the top- k elephant flows in a practical system with incomplete measurement data as a result of sub-sampling for scalability or data missing. The recent study shows it is promising to more accurately interpolate the missing data with a 3-D tensor compared to that based on a 2-D matrix. Taking full advantage of the multilinear structures, we apply tensor completion to first recover the missing data and then find the top- k elephant flows. To reduce the computational overhead, we propose a novel discrete tensor completion model which uses binary codes to represent the factor matrices. Based on the model, we further propose three novel techniques to speed up the whole top- k flow inference process: a discrete optimization algorithm to train the binary factor matrices, bit operations to facilitate quick missing data inference, and simplifying the finding of top- k elephant flows with binary code partition. In our discrete tensor completion model, only one bit is needed to represent the entry in the factor matrices instead of a real value (32 bits) needed in traditional tensor completion model, thus the storage cost is reduced significantly. Extensive experiments using two real traces demonstrate that compared with the state of art tensor completion algorithms, our discrete tensor completion algorithm can achieve similar data inference accuracy using significantly smaller time and storage space.