Web service administrators must ensure the stability of multiple systems by promptly detecting anomalies in Key Performance Indicators (KPIs). Achieving the goal of "train once, infer across scenarios" remains a fundamental challenge for time series anomaly detection models. Beyond improving zero-shot generalization, such models must also flexibly handle sequences of varying lengths during inference, ranging from one hour to one week, without retraining. Conventional approaches rely on sliding-window encoding and self-supervised learning, which restrict inference to fixed-length inputs. Large Language Models (LLMs) have demonstrated remarkable zero-shot capabilities across general domains. However, when applied to time series data, they face inherent limitations due to context length. To address this issue, we propose ViTs, a Vision-Language Model (VLM)-based framework that converts time series curves into visual representations. By rescaling time series images, temporal dependencies are preserved while maintaining a consistent input size, thereby enabling efficient processing of arbitrarily long sequences without context constraints. Training VLMs for this purpose introduces unique challenges, primarily due to the scarcity of aligned time series image-text data. To overcome this, we employ an evolutionary algorithm to automatically generate thousands of high-quality image-text pairs and design a three-stage training pipeline consisting of: (1) time series knowledge injection, (2) anomaly detection enhancement, and (3) anomaly reasoning refinement. Extensive experiments demonstrate that ViTs substantially enhance the ability of VLMs to understand and detect anomalies in time series data. All datasets and code will be publicly released at: https://anonymous.4open.science/r/ViTs-C484/.

As deep learning (DL) continues to advance, effective feature extraction from large-scale data remains crucial for enhancing model performance. To leverage the advantages of the frequency domain, such as concentrated signal energy, prominent data features, and rich detailed characteristics, this paper proposes a novel frequency-domain feature extraction method. However, existing frequency component selection algorithms often struggle to adapt to diverse tasks, tend to yield only locally optimal solutions, and require prolonged processing times. To overcome these limitations, we introduce the Adaptive Fast Frequency Selection (AFFS) algorithm, which seamlessly integrates a frequency component selection factor layer into DL models to identify globally optimal frequency combinations suited to various downstream tasks. We further analyze the relationship between selected frequency components and model performance, providing theoretical guarantees regarding optimality, robustness, and generalization error bounds. Moreover, a fast selection procedure is developed to exploit the empirically observed rapid convergence of the selection-factor ranking, significantly accelerating the selection process. Extensive experiments on five datasets, ten DL models, and two subsequent tasks demonstrate that AFFS achieves superior performance: even when the input data size is reduced to only 10% of the original frequency features, model classification accuracy improves by approximately 1%, while the early stopping mechanism shortens the selection process by about 80%.

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.

Tensor data is widely used in fields such as smart grids, cloud systems, and deep learning. As the scale of this data increases, storage and transmission costs rise significantly. Many tensor data exhibit low-rank structures, offering the potential for data compression through low-rank decomposition techniques. Tucker decomposition, a typical low-rank decomposition technique, achieves data compression and interpretability by capturing complex data correlations and representing the original tensor with a compact core tensor and factor matrices. However, the compression ratio provided by Tucker decomposition is often insufficient, particularly for large-scale tensors. To tackle this issue, we propose a robust low-rank tensor compression method that leverages Tucker decomposition with quantization and coding. Initially, we establish a robust Tucker decomposition framework that decomposes the low-rank tensor into a core tensor and factor matrices using well-designed Tucker rank-setting rules. This framework effectively handles noise and missing values. Subsequently, we conduct an in-depth analysis of the numerical characteristics of the core tensor and factor matrices within the Tucker decomposition framework. Based on their distinct characteristics, we design tailored quantization and coding schemes to compress the core tensor and factor matrices, respectively, thereby significantly improving the compression ratio of Tucker decomposition while maintaining high accu-racy. Through extensive experiments on four publicly available datasets (which can form 3 or 4 order tensors), we demonstrate that our approach can achieve compression ratios$4\times-10\times$higher than the best competitor, with recovery errors improved by 8% - 42%.

Sketch has been widely used in the field of large-scale data stream processing. However, common fixed-counter algorithms such as Count-Min Sketch have to allocate larger counters, which wastes a lot of memory due to the high skewness of real-world data streams. To reduce memory usage, we propose to dynamically adjust the counter size that matches the distribution of the data stream. We introduce BitMatcher, a fast global-adjusting algorithm that automatically adjusts the counter to the appropriate size to match the data stream. During stream processing, BitMatcher identifies items hashed into a bucket based on isolated fingerprints. If it overflows, BitMatcher changes the flag bits in the bucket and dynamically increases or shrinks the size of some counters in a fine-grained manner. BitMatcher can also relocate a cold item in the bucket with the idea of cuckoo hashing to preserve the potential hot item while achieving global load balancing. Through the above way of dealing with overflow caused by skewed data, BitMatcher precisely manipulates allocated bits and maximizes memory utilization. The experiments show that BitMatcher has high throughput and can outperform SOTA by up to 4 orders of magnitude in terms of accuracy. We also deployed BitMatcher on several platforms, showing its software and hardware scalability.

In large-scale online service systems, numerous Key Performance Indicators (KPIs), such as service response time and error rate, are gathered in a time-series format. KPI Anomaly Detection (KAD) is a critical data mining problem due to its widespread applications in real-world scenarios. However, KAD faces the challenges of dealing with KPI heterogeneity and noisy data. We propose KAD-Disformer, a KPI Anomaly Detection approach through Disentangled Transformer. KAD-Disformer pre-trains a model on existing accessible KPIs, and the pre-trained model can be effectively "fine-tuned" to unseen KPI using only a handful of samples from the unseen KPI. We propose a series of innovative designs, including disentangled projection for transformer, unsupervised few-shot fine-tuning (uTune), and denoising modules, each of which significantly contributes to the overall performance. Our extensive experiments demonstrate that KAD-Disformer surpasses the state-of-the-art universal anomaly detection model by 13% in F1-score and achieves comparable performance using only 1/8 of the finetuning samples saving about 25 hours. KAD-Disformer has been successfully deployed in the real-world cloud system serving millions of users, attesting to its feasibility and robustness. Our code is available at https://github.com/NetManAIOps/KAD-Disformer.

Time series Anomaly Detection (AD) plays a crucial role for web systems. Various web systems rely on time series data to monitor and identify anomalies in real time, as well as to initiate diagnosis and remediation procedures. Variational Autoencoders (VAEs) have gained popularity in recent decades due to their superior de-noising capabilities, which are useful for anomaly detection. However, our study reveals that VAE-based methods face challenges in capturing long-periodic heterogeneous patterns and detailed short-periodic trends simultaneously. To address these challenges, we propose Frequency-enhanced Conditional Variational Autoencoder (FCVAE), a novel unsupervised AD method for univariate time series. To ensure an accurate AD, FCVAE exploits an innovative approach to concurrently integrate both the global and local frequency features into the condition of Conditional Variational Autoencoder (CVAE) to significantly increase the accuracy of reconstructing the normal data. Together with a carefully designed "target attention" mechanism, our approach allows the model to pick the most useful information from the frequency domain for better short-periodic trend construction. Our FCVAE has been evaluated on public datasets and a large-scale cloud system, and the results demonstrate that it outperforms state-of-the-art methods. This confirms the practical applicability of our approach in addressing the limitations of current VAE-based anomaly detection models.

Network telemetry, characterized by its efficient push model and high-performance communication protocol (gRPC), offers a new avenue for collecting fine-grained real-time data. Despite its advantages, existing network telemetry systems lack a theoretical basis for setting measurement frequency, struggle to capture informative samples, and face challenges in setting a uniform frequency for multi-metric monitoring. We introduce FineMon, an innovative adaptive network telemetry scheme for precise, fine-grained, multi-metric data monitoring. FineMon leverages a novel Two-sided Frequency Adjustment (TFA) to dynamically adjust the measurement frequency on the Network Management System (NMS) and infrastructure sides. On the NMS side, we provide a theoretical basis for frequency determination, drawing on changes in the rank of multi-metric data to minimize monitoring overhead. On the infrastructure side, we adjust the frequency in real-time to capture significant data fluctuations. We propose a robust Enhanced-Subspace-based Tensor Completion (ESTC) to ensure accurate recovery of fine-grained data, even with noise or outliers. Through extensive experimentation with three real datasets, we demonstrate FineMon's superiority over existing schemes in reduced measurement overhead, enhanced accuracy, and effective capture of intricate temporal features.

Robust PCA is a popular anomaly detection technique and has been widely used in many applications. Although Robust PCA is promising, it is usually designed in a two-order matrix form, which is inferior to the tensor that can capture multilinearity features of data. Moreover, the detection accuracy under Robust PCA further suffers due to its sensitivity to the rank parameter which is hard to set in practice and the limitation of PCA method in capturing the non-linear feature in the data. To address the issues, we propose a Robust Tensor Convolutional Autoencoder (RTCAE) where the autoencoder instead of SVD is exploited to recover the normal data from the corrupted measurement tensor data. However, directly exploiting deep autoencoder may suffer from the problem of high memory consumption and computation overhead due to the large number of parameters used in autoencoder. To make our anomaly detection lightweight, we further design a Light Convolutional Autoencoder (LightCAE) which contains a compressed autoencoder by exploiting tensor factorization to largely compress the parameters while significantly reducing the computation complexity. We conduct extensive experiments on three real data traces to compare the performance of our proposed schemes (RTCAE and lightCAE) with that of seven baseline algorithms. The experiment results demonstrate that our proposed RTCAE achieves the highest anomaly detection accuracy. Moreover, our LightCAE requires over 60 times smaller memory storage than that required in RTCAE while achieving the similar anomaly detection accuracy.

Distributed Deep Learning (DDL) is widely used to accelerate deep neural network training for various Web applications. In each iteration of DDL training, each worker synchronizes neural network gradients with other workers. This introduces communication overhead and degrades the scaling performance. In this paper, we propose a recursive model, OSF (Scaling Factor considering Overlap), for estimating the scaling performance of DDL training of neural network models, given the settings of the DDL system. OSF captures two main characteristics of DDL training: the overlap between computation and communication, and the tensor fusion for batching updates. Measurements on a real-world DDL system show that OSF obtains a low estimation error (ranging from 0.5% to 8.4% for different models). Using OSF, we identify the factors that degrade the scaling performance, and propose solutions to effectively mitigate their impacts. Specifically, the proposed adaptive tensor fusion improves the scaling performance by 32.2%∼ 150% compared to the constant tensor fusion buffer size.

Multi-set membership query is a fundamental issue for network functions such as packet processing and state machines monitoring. Given the rigid query speed and memory requirements, it would be promising if a multi-set query algorithm can be designed based on Bloom filter (BF), a space-efficient probabilistic data structure. However, existing efforts on multi-set query based on BF suffer from at least one of the following drawbacks: low query speed, low query accuracy, limitation in only supporting insertion and query operations, or limitation in the set size. To address the issues, we design a novel B h sequence-based Bloom filter (B h BF) for multi-set query, which supports four operations: insertion, query, deletion, and update. In B h BF, the set ID is encoded as a code in a B h sequence. Exploiting good properties of B h sequences, we can correctly decode the BF cells to obtain the set IDs even when the number of hash collisions is high, which brings high query accuracy. In B h BF, we propose two strategies to further speed up the query speed and increase the query accuracy. On the theoretical side, we analyze the false positive and classification failure rate of our B h BF. Our results from extensive experiments over two real datasets demonstrate that B h BF significantly advances state-of-the-art multi-set query algorithms.

A major factor that prevents the large scale deployment of Mobile Crowd Sensing (MCS) is its sensing and communication cost. Given the spatio-temporal correlation among the environment monitoring data, matrix completion (MC) can be exploited to only monitor a small part of locations and time, and infer the remaining data. Rather than only taking random measurements following the basic MC theory, to further reduce the cost of MCS while ensuring the quality of missing data inference, we propose an Active Sparse MCS (AS-MCS) scheme which includes a bipartite-graph-based sensing scheduling scheme to actively determine the sampling positions in each upcoming time slot, and a bipartite-graph-based matrix completion algorithm to robustly and accurately recover the un-sampled data in the presence of sensing and communications errors. We also incorporate the sensing cost into the bipartite-graph to facilitate low cost sample selection and consider the incentives for MCS. We have conducted extensive performance studies using the data sets from the monitoring of PM 2.5 air condition and road traffic speed, respectively. Our results demonstrate that our AS-MCS scheme can recover the missing data at very high accuracy with the sampling ratio only around $11%$, while the peer matrix completion algorithms with similar recovery performance requires up to 4-9 times the number of samples of ours for both the data sets.

Tensor completion can be applied to fill in the missing data, which is import for many data applications where the data are incomplete. To infer the missing data, existing tensor-completion algorithms generally assume that the tensor data have global low-rank structure and apply a single model to fit the overall observed data through the global optimization. However, there are different correlation levels among application data, thus the ranks of some sub-tensors can be even lower relative to that of the large tensor. Fitting a single model to all data will compromise the performance of data recovery. To increase the accuracy in missing data recovery, we propose to apply local tensor completion (Local-TC) to recover data from sub-tensors, with each containing data of higher correlations. Although promising, as the tensor data are only organized logically, it is difficult to determine the relationship among data. We propose to exploit locality-sensitive hash (LSH) to quickly find the data correlation and reorganize tensor data, based on which data entries with high correlations are put into the same sub-tensor. The experiment results demonstrate that Local-TC is very effective in increasing the recovery accuracy.

Sampling social graphs is critical for studying things like information diffusion. However, it is often necessary to laboriously obtain unbiased and well-connected datasets because existing survey algorithms are unable to generate well-connected samples, and current random-walk based unbiased sampling algorithms adopt rejection sampling, which heavily undermines performance. This paper proposes a novel random-walk based algorithm which implements Unbiased Sampling using Dummy Edges (USDE). It injects dummy edges between nodes, on which the walkers would otherwise experience excessive rejections before moving out from such nodes. We propose a rejection probability estimation algorithm to facilitate the construction of dummy edges and the computation of moving probabilities. Finally, we apply USDE in two real-life social media: Twitter and Sina Weibo. The results demonstrate that USDE generates well-connected samples, and outperforms existing approaches in terms of sampling efficiency and quality of samples.

A sketch is a probabilistic data structure that is used to record frequencies of items in a multi-set. Sketches have been applied in a variety of fields, such as data stream processing, natural language processing, distributed data sets etc. In this paper, we propose a new sketch, called Slim-Fat (SF) sketch, which has a much smaller memory footprint for query while supporting updates. The key idea behind our proposed SF-sketch is to maintain two separate sketches: a small sketch called Slimsubsketch and a large sketch called Fat-subsketch. The Slimsubsketch enables fast and accurate querying. The Fat-subsketch is used to assist the insertion and deletion from Slim-subsketch. We implemented and evaluated SF-sketch along with several prior sketches and compared them side by side. Our experimental results show that SF-sketch significantly outperforms the most commonly used CM-sketch in terms of accuracy. The full version is provided at arXiv.org [12].

Set queries are fundamental operations in computer systems and applications. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a Shifting Bloom Filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF based set data structures allocate additional memory to store auxiliary information. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.

Rogue Access Points (RAPs) pose serious security threats to local networks. An analytic model of prior probability distribution of Segmental TCP Jitter (STJ) is deduced from the mechanism of IEEE 802.11 MAC Distributed Coordinated Function (DCF) and used to differentiate the types of wire and WLAN connections which is the crucial step for RAPs detecting. STJ as the detecting metric can reflect more the characteristic of 802.11 MAC than ACK-Pair since it can eliminate the delay caused by packet transmission. The experiment on an operated network shows the average detection ratio of the algorithm with STJ is more than 92.8% and the average detection time is less than 1s with improvement of 20% and 60% over the detecting approach of ACK-Pair respectively. Farther more no WLAN training trace is needed in the detecting algorithm.