PADUA
Abstract
There are numerous applications (e.g., video surveillance, fraud detection, cybersecurity) in which we wish to identify unexplained sets of events. Most related past work has been domain-dependent (e.g., video surveillance, cybersecurity) and has focused on the valuable class of statistical anomalies in which statistically unusual events are considered. In contrast, suppose there is a set A of known activity models (both harmless and harmful) and a log L of time-stamped observations. We define a part L '⊆ L of the log to represent an unexplained situation when none of the known activity models can explain L ' with a score exceeding a user-specified threshold. We represent activities via probabilistic penalty graphs (PPGs) and show how a set of PPGs can be combined into one Super-PPG for which we define an index structure. Given a compute cluster of ( K + 1) nodes (one of which is a master node), we show how to split a Super-PPG into K subgraphs, each of which can be independently processed by a compute node. We provide algorithms for the individual compute nodes to ensure seamless handoffs that maximally leverage parallelism. PADUA is domain-independent and can be applied to many domains (perhaps with some specialization). We conducted detailed experiments with PADUA on two real-world datasets—the ITEA CANDELA video surveillance dataset and a network traffic dataset appropriate for cybersecurity applications. PADUA scales extremely well with the number of processors and significantly outperforms past work both in accuracy and time. Thus, PADUA represents the first parallel architecture and algorithm for identifying unexplained situations in observation data, offering both scalability and accuracy.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jul 15, 2014
- Source ID
- 10.1145/2633685
Entities
People
- Andrea Pugliese
- Antonino Rullo
- Antonio Picariello
- Cristian Molinaro
- V. S. Subrahmanian
- Vincenzo Moscato
Organizations
- Army Research Office
- Ministry of Education, Universities and Research
- University of Calabria
- University of Maryland
- University of Naples Federico II