Computing set difference cardinalities is a critical task in database optimization, network management, and anomaly detection. Due to the limited computational and mem-ory resources, exactly calculating set difference cardinalities becomes impractical in real-world applications. To solve this issue, sketch methods such as Odd sketch, Tug-of-War sketch, and HyperLogLog sketch can be extended to provide approximate estimations of set difference cardinalities. They use a family of hash functions to compress all elements in a set into a compact data structure. Unfortunately, Odd sketch suffers from limited estimation range, while Tug-of-War sketch and HyperLogLog sketch unavoidably face the problems of large estimation errors and high computational costs. In this paper, we design a novel data structure of bit array GXBits to fast and accurately estimate set difference cardinalities in a large range. In GXBits, the prob-ability of each bit recording its corresponding elements follows a variant of geometric distributions and varies across different bits. We conduct extensive experiments on synthetic datasets and real-world datasets. Experimental results demonstrate that our method GXBits is more computationally and memory efficient, and significantly increases the estimation accuracy of existing methods by up to 221.3 times.

Kernel density estimation is a useful method for estimating the probability distribution of data. It is a challenge to achieve efficient kernel density estimation, especially for large-scale and high-dimension stream data. We proposerotation kernel, a novel kernel function for density estimation. The rotation kernel density can be fast estimated by a data structure namedRotation Kernel Density Sketch(RKDS). RKDS is a time- and memory-efficient method for kernel density estimation, even over data streams and distributed systems. RKDS is applicable for estimating density at specific points and also for representing data distribution. We provide theoretical analysis for rotation kernel and RKDS. Furthermore, we apply RKDS to outlier detection, concept drift detection, and personalized federated learning. Experiments show that our method improves time efficiency by up to$3\times 10^{3}$times compared with baselines. RKDS also provides comparable detecting precision and better delay on outlier detection and concept drift detection tasks.

Log messages provide a valuable source of runtime information for ensuring the safety and consistency of systems. Recently, many machine learning and deep learning methods have been proposed to automatically detect anomalous log messages, obviating the need for manual detection by experts. However, we find that in practice, the effectiveness of existing learning-based methods is severely affected by incomplete information and distribution shift. Specifically, each log message can actually be parsed into a fixed number of key information fields, while existing methods analyze log messages using only the log event information and ignore other useful information fields that can be critical to anomaly detection. Further, the distribution of real-world log messages changes continuously due to the dynamic nature of the runtime environment and thus, a detection model conventionally trained based on the unrealistic i.i.d. assumption may not provide the expected and consistent performance. In this paper, we present a robust and transferable anomaly detection framework RT-Log to address the above problems. To perform a comprehensive analysis of log messages, we introduce an adaptive relation modeling technique, which captures feature interactions among log information fields selectively and dynamically for effective and interpretable log representations. To establish its robustness and transferability, we propose a general environment generalization technique for learning the environment invariant representations that can generalize across different runtime environments. We evaluate the anomaly detection performance of RT-Log on large real-world datasets. Extensive experimental results demonstrate that RT-Log consistently outperforms state-of-the-art methods by a significant margin under different settings.

Many real-world datasets are given in the stream of entity-identifier pairs, and measuring data distribution on these datasets is fundamental for applications such as privacy protection. In this paper, we study the problem of computing the cumulative distribution for different cardinalities (i.e., the number of distinct entities owning the same identifier). However, previous sketch-based methods cost large memory space especially when there are a large number of identifiers, and sampling-based methods require much time for cardinality estimation. A recent work KHyperLogLog combines both sketch and sampling methods but it is wasteful to separately build a HyperLogLog sketch of large size for identifiers with small cardinalities. To address these challenges, we propose a memory-efficient method EV-HLL, which designs a shared structure to store all sampled identifiers and their entities and utilizes additional sketches to track value updates during the sampling procedure. Meanwhile, EV-HLL provides real-time unbiased estimations according to value changes whenever a new entity-identifier pair arrives. We evaluate the performance of EV-HLL and other state-of-the-arts on real-world available datasets. Experimental results demonstrate that comparing to other methods, EV-HLL effectively reduces their memory usage with the same estimation accuracy and has higher accuracy with the same memory usage.

Online monitoring user cardinalities in graph streams is fundamental for many applications such as anomaly detection. These graph streams may contain edge duplicates and have a large number of user-item pairs, which makes it infeasible to exactly compute user cardinalities due to limited computational and memory resources. Existing methods are designed to approximately estimate user cardinalities, but their accuracy highly depends on complex parameters and they cannot provide anytime-available estimation. To address these problems, we develop novel bit/register sharing algorithms, which use a bit/register array to build a compact sketch of all users’ connected items. Our algorithms exploit the dynamic properties of the bit/register arrays (e.g., the fraction of zero bits in the bit array) to significantly improve the estimation accuracy, and have low time complexity$O(1)$to update the estimations for a new user-item pair. In addition, our algorithms are simple and easy to use, without requirements to tune any parameter. Furthermore, we extend our methods to detect super spreaders with large cardinalities in real-time. We evaluate the performance of our methods on real-world datasets. The experimental results demonstrate that our methods are several times more accurate and faster than state-of-the-art methods using the same amount of memory.

Bipartite graphs widely exist in real-world scenarios and model binary relations like host-website, author-paper, and user-product. In bipartite graphs, a butterfly (i.e.,$2\times 2$bi-clique) is the smallest non-trivial cohesive structure and plays an important role in applications such as anomaly detection. Considerable efforts focus on counting butterflies in static bipartite graphs. However, they suffer from high time and space complexity when the bipartite graph of interest is given as a stream of edges. Although there are methods for approximately counting butterflies from bipartite graph streams, they suffer from either low accuracy or high time complexity. Therefore, it is still a challenge to accurately estimate butterfly counts from bipartite graph streams in a short time. To address this issue, we develop novel algorithms by exploiting the bipartite nature, which subtly integrates sampling and sketching techniques. We provide accurate estimators for butterfly counts and derive simple yet exact formulas for bounding their errors. We also conduct extensive experiments on a variety of real-world large bipartite graphs. Experimental results demonstrate that our algorithms are up to 20.0 times more accurate and up to 286.3 times faster than state-of-the-art methods under the same memory usage.

Many real-world datasets are given in the format of data streams, and processing these data streams is fundamental for many applications such as anomaly detection. In this paper, we study the problem of computing item frequencies, finding topk hot items, and detecting heavy changes. However, the widelyused sketches cost large memory usage and their performance is easily affected by the unbalanced distribution of data streams. To solve this issue, a novel method Cold Filter (CF) is proposed to split cold items and hot items, and use a separate structure to record the frequencies of hot items. Typically, CF has a small filter range and is only effective for filtering cold items with small frequencies. For some real-world applications, however, the cold items' frequencies may also be greater than hundreds or even tens of thousands. To solve the above challenges, we exploit the “LogLog” structure and develop a memory-efficient method LogLog Filter (LLF) to accurately estimate the above three metrics. LLF builds a register array where each register approximately counts the sum of item frequencies hashed into it. Our method remarkably enlarges the filter range of CF with fewer bits and only requires 4 bits to filter cold items with frequencies up to 224. We conduct extensive experiments on real-world and synthetic datasets, and the experimental results demonstrate the efficiency and effectiveness of our method.

Kernel density estimation method is a powerful tool and is widely used in many important real-world applications such as anomaly detection and statistical learning. Unfortunately, current kernel methods suffer from high computational or space costs when dealing with large-scale, high-dimensional datasets, especially when the datasets of interest are given in a stream fashion. Although there are sketch methods designed for kernel density estimation over data streams, they still suffer from high computational costs. To address this problem, in this paper, we propose a novel Rotation Kernel. The Rotation Kernel is based on a Rotation Hash method and is much faster to compute. To achieve memory-efficient kernel density estimation over data streams, we design a method, RKD-Sketch, which compresses high dimensional data streams into a small array of integer counters. We conduct extensive experiments on both synthetic and real-world datasets, and experimental results demonstrate that our RKD-Sketch saves up to 216 times computational resources and up to 104 times space resources than state-of-the-arts. Furthermore, we apply our Rotation Kernel in active learning. Results show that our method achieves up to 256 times speedup and saves up to 13 times space to achieve the same accuracy as the baseline methods.

As an efficient tool for approximate similarity computation and search, Locality Sensitive Hashing (LSH) has been widely used in many research areas including databases, data mining, information retrieval, and machine learning. Classical LSH methods typically require to perform hundreds or even thousands of hashing operations when computing the LSH sketch for each input item (e.g., a set or a vector); however, this complexity is still too expensive and even impractical for applications requiring processing data in real-time. To address this issue, several fast methods such as OPH and BCWS have been proposed to efficiently compute the LSH sketches; however, these methods may generate many sketches with empty bins, which may introduce large errors for similarity estimation and also limit their usage for fast similarity search. To solve this issue, we propose a novel densification method, i.e., BiDens. Compared with existing densification methods, our BiDens is more efficient to fill a sketch's empty bins with values of its non-empty bins in either the forward or backward directions. Furthermore, it also densifies empty bins to satisfy the densification principle (i.e., the LSH property). Theoretical analysis and experimental results on similarity estimation, fast similarity search, and kernel linearization using real-world datasets demonstrate that our BiDens is up to 106 times faster than state-of-the-art methods while achieving the same or even better accuracy.

Many real-world networks such as Twitter and YouTube are given as fully dynamic graph streams represented as sequences of edge insertions and deletions. (e.g., users can subscribe and unsubscribe to channels on YouTube). Existing similarity estimation methods such as MinHash and OPH are customized to static graphs. We observe that they are indeed sampling methods and exhibit a sampling bias when applied to fully dynamic graph streams, which results in large estimation errors. To solve this challenge, we develop a fast and accurate sketch method VOS. VOS processes each edge in the graph stream of interest with small time complexity O(1) and uses small memory space to build a compact sketch of the dynamic graph stream over time. Based on the sketch built on-the-fly, we develop a method to estimate user similarities over time. We conduct extensive experiments and the experimental results demonstrate the efficiency and efficacy of our method.

Recently, considerable efforts have been devoted to approximately computing the global and local (i.e., incident to each node) triangle counts of a large graph stream represented as a sequence of edges. Existing approximate triangle counting algorithms rely on sampling techniques to reduce the computational cost. However, their estimation errors are significantly determined by the covariance between sampled triangles. Moreover, little attention has been paid to developing parallel one-pass streaming algorithms that can be used to fast and approximately count triangles on a multi-core machine or a cluster of machines. To solve these problems, we develop a novel parallel method REPT to significantly reduce the covariance (even completely eliminate the covariance for some cases) between sampled triangles. We theoretically prove that REPT is more accurate than parallelizing existing triangle count estimation algorithms in a direct manner. In addition, we also conduct extensive experiments on a variety of real-world graphs, and the results demonstrate that our method REPT is several times more accurate than state-of-the-art methods.

Online monitoring user cardinalities (or degrees) in graph streams is fundamental for many applications. For example in a bipartite graph representing user-website visiting activities, user cardinalities (the number of distinct visited websites) are monitored to report network anomalies. These real-world graph streams may contain user-item duplicates and have a huge number of distinct user-item pairs, therefore, it is infeasible to exactly compute user cardinalities when memory and computation resources are limited. Existing methods are designed to approximately estimate user cardinalities, whose accuracy highly depends on parameters that are not easy to set. Moreover, these methods cannot provide anytime-available estimation, as the user cardinalities are computed at the end of the data stream. Realtime applications such as anomaly detection require that user cardinalities are estimated on the fly. To address these problems, we develop novel bit and register sharing algorithms, which use a bit array and a register array to build a compact sketch of all users' connected items respectively. Compared with previous bit and register sharing methods, our algorithms exploit the dynamic properties of the bit and register arrays (e.g., the fraction of zero bits in the bit array at each time) to significantly improve the estimation accuracy, and have low time complexity (O(1)) to update the estimations each time they observe a new useritem pair. In addition, our algorithms are simple and easy to use, without requirements to tune any parameter. We evaluate the performance of our methods on real-world datasets. The experimental results demonstrate that our methods are several times more accurate and faster than state-of-the-art methods using the same amount of memory.

Monitoring user behaviors over high speed links is important for applications such as network anomaly detection. Previous work focuses on monitoring anomalies such as extremely frequent users occurring in a short timeslot such as 1 minute. Little attention has been paid to detect users with stealthy behaviors (e.g., persistent, co-occurrence, anti-co-occurrence, and periodic behaviors) over a long period of time at the timeslot granularity. Due to limited computation and storage resources on routers, it is prohibitive to collect massive network traffic in a long period of time. We develop an end-to-end method for solving challenges in both long-term online traffic collection and offline user behavior analysis. We conduct extensive experiments on a variety of real-world traffic to evaluate the performance of detecting persistent, co-occurrence, anti-co-occurrence, and periodic behaviors, and the results demonstrate that our method significantly outperforms state-of-the-art methods.