Abstract
D-Cube is a disk-based and distributed algorithm designed to find dense subtensors (group anomalies) in massive, multi-aspect datasets. It handles "tera-scale" data (up to 2.6TB) that is far too large for memory, outperforming state-of-the-art in-memory methods by being up to 7x faster and using up to 1,561x less memory while maintaining rigorous accuracy guarantees.
Introduction
In the world of "Big Data," many interesting phenomena—from credit card fraud and botnets to network intrusions—manifest as group anomalies. When multi-aspect data (e.g., User x IP x Timestamp x Action) is modeled as a tensor, these anomalies appear as dense subtensors: small blocks where a subset of entities interact with each other with unusually high frequency.
The primary challenge is scale. Previous state-of-the-art algorithms like M-Zoom or CrossSpot assume the data fits in main memory (RAM). However, real-world tensors from social media or web logs often reach terabytes or petabytes. When data exceeds RAM, these algorithms either crash or become agonizingly slow due to "disk thrashing." D-Cube addresses this "tera-scale" gap, finding dense needles in massive haystacks that do not fit on a single disk.
Methods: The D-Cube Algorithm
D-Cube is a search-based method that iteratively prunes "sparse" attribute values to isolate a dense core. Its key innovations include:
- Out-of-Core Processing: Unlike previous methods requiring random access, D-Cube relies on sequential disk scans, which are significantly faster than random I/O.
- Mass-Threshold Pruning ($\theta$): Standard greedy algorithms remove one attribute value at a time. D-Cube uses a parameter $\theta$ to remove multiple low-mass attribute values in a single scan, drastically reducing iterations without sacrificing theoretical approximation guarantees.
- Distributed Architecture: Implemented on MapReduce (Hadoop), D-Cube scales across multiple machines by parallelizing the computation of attribute-value masses and tuple filtering.
- Flexibility: It supports various density metrics, including Arithmetic Average Mass and "Suspiciousness" (Poisson-based).
Experimental Evaluation
The researchers evaluated D-Cube on 11 diverse real-world datasets, including rating data (Yelp, Netflix), Wikipedia revision history, and network traffic (DARPA, AirForce). Synthetic tensors were used to test scalability up to 10^11 tuples (2.6 TB).
Key Results
- Efficiency: D-Cube handled 1,000x larger data (2.6TB) than competitors, which suffered from Out-of-Memory (O.O.M.) errors at much smaller scales.
- Memory Savings: It required up to 1,561x less memory than state-of-the-art in-memory methods.
- Speed: It achieved up to a 7x speedup over M-Zoom on datasets where both could run, largely due to superior cache locality from sequential scanning.
- Accuracy: In network intrusion tasks, D-Cube achieved an AUROC of 0.930 to 0.987, outperforming tensor decomposition methods (CPD).
Discussion and Insights
One of the most significant findings is that sequential disk access can actually trump RAM-based random access for large-scale tensor mining. D-Cube’s memory requirement depends only on the number of distinct attribute values, not the total number of interactions (tuples), allowing it to process trillions of interactions with just a few gigabytes of RAM.
While highly effective, D-Cube currently requires the sets of distinct attribute values to fit in memory. Future work may address dimensions with billions of unique entities (e.g., every URL on the web) or extend the algorithm to a streaming context for real-time anomaly detection.
Summary updated