Existing Big data analytics platforms, such as Hadoop, lack support for user activity monitoring. Several diagnostic tools such as Ganglia, Ambari, and Cloudera Manager are available to monitor health of a cluster, however, they do not provide algorithms to detect security threats or perform user activity monitoring. Hence, there is a need to develop a scalable system that can detect malicious user activities, especially in real-time, so that appropriate actions can be taken against the user. At eBay, we developed such a system named Eagle, which collects audit logs from Hadoop clusters and applications running on them, analyzes users behavior, generates profiles per user of the system, and predicts anomalous user activities based on their prior profiles. Eagle is a highly scalable system, capable of monitoring multiple eBay clusters in real-time. It includes machine-learning algorithms that create user profiles based on the user's history of activities. As far as we know, this is the first activity monitoring system on the Hadoop-ecosystem for the detection of intrusion-related activities using behavior-based profiles of users. When a user performs any operation in the cluster, Eagle matches current user action against his prior activity pattern and raises alarm if it suspects anomalous action. We investigate two machine-learning algorithms: density estimation, and principal component analysis (PCA). In this paper, we introduce the Eagle system, discuss the algorithms in detail, and show performance results. We demonstrate that the sensitivity of the density estimation algorithm is 93%, however the sensitivity of our system increases by 4.94% (on average) to 98% (approximately) by using an ensemble of the two algorithms during anomaly detection.

The sheer growth in data volume and Hadoop cluster size make it a significant challenge to diagnose and locate problems in a production-level cluster environment efficiently and within a short period of time. Often times, the distributed monitoring systems are not capable of detecting a problem well in advance when a large-scale Hadoop cluster starts to deteriorate i n performance or becomes unavailable. Thus, inc o m i n g workloads, scheduled between the time when cluster starts to deteriorate and the time when the problem is identified, suffer from longer execution times. As a result, both reliability and throughput of the cluster reduce significantly. In this paper, we address this problem by proposing a system called Astro, which consists of a predictive model and an extension to the Hadoop scheduler. The predictive model in Astro takes into account a rich set of cluster behavioral information that are collected by monitoring processes and model them using machine learning algorithms to predict future behavior of the cluster. The Astro predictive model detects anomalies in the cluster and also identifies a ranked set of metrics that have contributed the most towards the problem. The Astro scheduler uses the prediction outcome and the list of metrics to decide whether it needs to move and reduce workloads from the problematic cluster nodes or to prevent additional workload allocations to them, in order to improve both throughput and reliability of the cluster. The results demonstrate that the Astro scheduler improves usage of cluster compute resources significantly by 64.23% compared to traditional Hadoop. Furthermore, the runtime of the benchmark application reduced by 26.68% during the time of anomaly, thus improving the cluster throughput.

MOTIVATION: We investigate the problem of exact repeat detection on large genomic sequences. Most existing approaches based on suffix trees and suffix arrays (SAs) are limited either to small sequences or those that are memory resident. We introduce RepMaestro, a software that adapts existing in-memory-enhanced SA algorithms to enable them to scale efficiently to large sequences that are disk resident. Supermaximal repeats, maximal unique matches (MuMs) and pairwise branching tandem repeats have been used to demonstrate the practicality of our approach; the first such study to use an enhanced SA to detect these repeats in large genome sequences. RESULTS: The detection of supermaximal repeats was observed to be up to two times faster than Vmatch, but more importantly, was shown to scale efficiently to large genome sequences that Vmatch could not process due to memory constraints (4 GB). Similar results were observed for the detection of MuMs, with RepMaestro shown to scale well and also perform up to six times faster than Vmatch. For tandem repeats, RepMaestro was found to be slower but could nonetheless scale to large disk-resident sequences. These results are a significant advance in the quest of scalable repeat detection. Software availability: RepMaestro is available at http://www.naskitis.com.

SUMMARY: The shorter and vastly more numerous reads produced by second-generation sequencing technologies require new tools that can assemble massive numbers of reads in reasonable time. Existing short-read assembly tools can be classified into two categories: greedy extension-based and graph-based. While the graph-based approaches are generally superior in terms of assembly quality, the computer resources required for building and storing a huge graph are very high. In this article, we present Taipan, an assembly algorithm which can be viewed as a hybrid of these two approaches. Taipan uses greedy extensions for contig construction but at each step realizes enough of the corresponding read graph to make better decisions as to how assembly should continue. We show that this approach can achieve an assembly quality at least as good as the graph-based approaches used in the popular Edena and Velvet assembly tools using a moderate amount of computing resources.

MOTIVATION: Second-generation sequencing technologies produce a massive amount of short reads in a single experiment. However, sequencing errors can cause major problems when using this approach for de novo sequencing applications. Moreover, existing error correction methods have been designed and optimized for shotgun sequencing. Therefore, there is an urgent need for the design of fast and accurate computational methods and tools for error correction of large amounts of short read data. RESULTS: We present SHREC, a new algorithm for correcting errors in short-read data that uses a generalized suffix trie on the read data as the underlying data structure. Our results show that the method can identify erroneous reads with sensitivity and specificity of over 99% and 96% for simulated data with error rates of up to 3% as well as for real data. Furthermore, it achieves an error correction accuracy of over 80% for simulated data and over 88% for real data. These results are clearly superior to previously published approaches. SHREC is available as an efficient open-source Java implementation that allows processing of 10 million of short reads on a standard workstation.

The suffix tree (or equivalently, the enhanced suffix array) provides efficient solutions to many problems involving pattern matching and pattern discovery in large strings, such as those arising in computational biology. Here we address the problem of arranging a suffix array on disk so that querying is fast in practice. We show that the combination of a small trie and a suffix array-like blocked data structure allows queries to be answered as much as three times faster than the best alternative disk-based suffix array arrangement. Construction of our data structure requires only modest processing time on top of that required to build the suffix tree, and requires negligible extra memory.

Duplicate and near-duplicate digital image matching is beneficial for image search in terms of collection management, digital content protection, and search efficiency. In this paper, we introduce SICO, a novel system for near-duplicate image detection during web search. It accurately detects near-duplicates in the answers returned by commercial image search engines in real-time. We show that SICO - which utilizes PCA-SIFT local descriptors and adapts near-duplicate text document detection techniques - is both effective and efficient. On a standard desktop personal computer, SICO identifies clusters of near-duplicate images with 93% accuracy in under 30 seconds, for an average of 622 returned images for each query.