16175912
Online latent variable detection in sensor networks
Sensor networks attract increasing interest, for a broad range of applications. Given a sensor network, one key issue becomes how to utilize it efficiently and effectively. In particular, how can we detect the underlying correlations (latent variables) among many co-evolving sensor measurements? Can we do it incrementally? We present a system that can (1) collect the measurements from the real wireless sensors; (2) process them in real-time; and (3) determine the correlations (latent variables) among the sensor streams on the fly.
803846
Selectivity estimation for predictive spatio-temporal queries
We propose a cost model for selectivity estimation of predictive spatio-temporal window queries. Initially, we focus on uniform data proposing formulae that capture both points and rectangles, and any type of object/query mobility combination (i.e., dynamic objects, dynamic queries or both). Then, we apply the model to nonuniform datasets by introducing spatio-temporal histograms, which in addition to the spatial, also consider the velocity distributions during partitioning. The advantages of our techniques are (i) high accuracy (1-2 orders of magnitude lower error than previous techniques), (ii) ability to handle all query types, and (iii) efficient handling of updates.
2957894
InteMon: intelligent system monitoring on large clusters
InteMon is a prototype monitoring and mining system for large clusters. Currently, it monitors over 100 hosts of a prototype data center at CMU. It uses the SNMP protocol and it stores the monitoring data in an mySQL database. Then, it allows for visualization of the time-series data using a JSP web-based frontend interface for users.What sets it apart from other cluster monitoring systems is its ability to automatically analyze the monitoring data in real time and alert the users for potential anomalies. It uses state of the art stream mining methods, it has a sophisticated definition of anomalies (broken correlations among input streams), and it can also pinpoint the reason of the anomaly. InteMon has a user-friendly GUI, it allows the users to perform interactive mining tasks, and it is fully operational.
4473626
Relevance search and anomaly detection in bipartite graphs
Many real applications can be modeled using bipartite graphs, such as users vs. files in a P2P system, traders vs. stocks in a financial trading system, conferences vs. authors in a scientific publication network, and so on. We introduce two operations on bipartite graphs: 1) identifying similar nodes (relevance search), and 2) finding nodes connecting irrelevant nodes (anomaly detection). And we propose algorithms to compute the relevance score for each node using random walk with restarts and graph partitioning; we also propose algorithms to identify anomalies, using relevance scores. We evaluate the quality of relevance search based on semantics of the datasets, and we also measure the performance of the anomaly detection algorithm with manually injected anomalies. Both effectiveness and efficiency of the methods are confirmed by experiments on several real datasets.
7374346
Beyond streams and graphs: dynamic tensor analysis
How do we find patterns in author-keyword associations, evolving over time? Or in Data Cubes, with product-branch-customer sales information? Matrix decompositions, like principal component analysis (PCA) and variants, are invaluable tools for mining, dimensionality reduction, feature selection, rule identification in numerous settings like streaming data, text, graphs, social networks and many more. However, they have only two orders, like author and keyword, in the above example.We propose to envision such higher order data as tensors,and tap the vast literature on the topic. However, these methods do not necessarily scale up, let alone operate on semi-infinite streams. Thus, we introduce the dynamic tensor analysis (DTA) method, and its variants. DTA provides a compact summary for high-order and high-dimensional data, and it also reveals the hidden correlations. Algorithmically, we designed DTA very carefully so that it is (a) scalable, (b) space efficient (it does not need to store the past) and (c) fully automatic with no need for user defined parameters. Moreover, we propose STA, a streaming tensor analysis method, which provides a fast, streaming approximation to DTA.We implemented all our methods, and applied them in two real settings, namely, anomaly detection and multi-way latent semantic indexing. We used two real, large datasets, one on network flow data (100GB over 1 month) and one from DBLP (200MB over 25 years). Our experiments show that our methods are fast, accurate and that they find interesting patterns and outliers on the real datasets.
16117277
Hiding in the Crowd: Privacy Preservation on Evolving Streams through Correlation Tracking
We address the problem of preserving privacy in streams, which has received surprisingly limited attention. For static data, a well-studied and widely used approach is based on random perturbation of the data values. However, streams pose additional challenges. First, analysis of the data has to be performed incrementally, using limited processing time and buffer space, making batch approaches unsuitable. Second, the characteristics of streams evolve over time. Consequently, approaches based on global analysis of the data are not adequate. We show that it is possible to efficiently and effectively track the correlation and autocorrelation structure of multivariate streams and leverage it to add noise which maximally preserves privacy, in the sense that it is very hard to remove. Our techniques achieve much better results than previous static, global approaches, while requiring limited processing time and memory. We provide both a mathematical analysis and experimental evaluation on real data to validate the correctness, efficiency, and effectiveness of our algorithms.
2724281
A semi-local paradigm for wavelet denoising
Wavelet denoising methods have been proven useful for many one- and two-dimensional problems. Most existing methods can in principle be carried over to three-dimensional problems, such as the denoising of volumetric positron emission tomography (PET) images, but they may not be sufficiently flexible in allowing some regions of an image to be denoised more aggressively than others. In this paper, we propose a semi-local paradigm for wavelet denoising. The semi-local paradigm involves the division of an image into suitable blocks, which are then individually denoised. To denoise the blocks, we use our modification of the generalized cross validation (GCV) technique of Jansen and Bultheel to choose thresholding parameters; we also present risk estimators to guide some of the other choices involved in the implementation. Experiments with phantom PET images show that the semi-local paradigm provides superior denoising compared to standard application of the GCV technique. An asymptotic analysis demonstrates that, under some regularity conditions, semi-local denoising is asymptotically consistent on the logarithmic scale. The paper concludes with a discussion on the nature of semi-local denoising and some topics for future research.
5921528
PRISMATICA: toward ambient intelligence in public transport environments
On-line surveillance to improve safety and security is a major requirement for the management of public transport networks and other public places. The surveillance task is a complex one involving people, management procedures, and technology. This work describes an architecture that takes into account the distributed nature of the detection processes and the need to allow for different types of devices and actuators. This was part of a major European initiative on intelligent transport systems. Because of the dominant nature of closed circuit television in surveillance, This work describes in detail a computer-vision module used in the system and its particular ability to detect situations of interest in busy conditions. The system components have been implemented, integrated, and tested in real metropolitan railway environments and are considered to be the first step toward providing ambient intelligence in such complex scenarios. Results are presented that not only deal with detection performance, but also on the perception of people who used the system on its effectiveness and potential impact.
18262141
Algorithmic Design Using Object-Z for Twig XML Queries Evaluation
Web technologies based on XML, e.g. Semantic Web and Web Services, facilitate Web automation and universally accessible content. One of the key factors for the success of XML-based technologies is of finding an efficient query evaluation algorithm for XML-based data models. An XML twig query is a complex selection predicate on both structure and content of a labelled XML document. Several novel twig query evaluation algorithms have been proposed recently. However, these algorithms are difficult to understand and hence implement due to high complexity. In this work, we present an algorithmic design for XML queries evaluation system using Object-Z. An Object-Z specification is developed to give a concise and logical description of the XML data model and the twig queries. It makes the twig query evaluation straight-forward, and allows different evaluation algorithms to be constructed easily and independently.
42715872
A Data Mining Based Intrusion Detection Model
Intrusion Detection Systems (IDSs) have become a critical part of security systems. The goal of an intrusion detection system is to block intrusion effectively and accurately. However, the performance of IDS is not satisfying. In this paper, we study the issue of building a data mining based intrusion detection model to raise the detection performance. The key ideas are to use data mining techniques to discover consistent and useful patterns for intrusion and use the set of patterns to recognize intrusion. By applying statistics inference theory to this model, the patterns mined from a set of test data are effective to detect the attacks in the same category, and therefore can detect most novel attacks that are variants of known attacks.
5987473
Formal semantics and verification for feature modeling
Research on features has received much attention in the domain engineering community. Feature modeling plays an important role in the design and implementation of complex software systems. However, the presentation and analysis of feature models are still largely informal. There is also an increasing need for methods and tools that can support automated feature model analysis. This paper presents a formal engineering approach to the specification and verification of feature models. A formal semantics for the feature modeling language is defined using first-order logic. It provides a precise and rigorous formal interpretation for the graphical notation. In addition, further validation of the semantics using the Z/EVES theorem prover is presented. Finally, we demonstrate that the consistency of a feature model and its configurations can be automatically verified by encoding the semantics into the Alloy Analyzer. A case study of the Key Word in Context (KWIC) index systems feature model is presented to illustrate the verification process.