This comment points out several mathematical errors in the proof of Therorem 3, and gives the correct expression of B3.

We study the problem of identifying discriminative features in Big Data arising from heterogeneous sensors. We highlight the heterogeneity in sensor data from engineering applications and the challenges involved in automatically extracting only the most interesting features from large datasets. We formulate this problem as that of classification of multivariate time series and design shapelet-based algorithms for this task. We design a novel approach, called Shapelet Forests (SF), which combines shapelet extraction with feature selection. We evaluate our proposed method with other approaches for mining shapelets from multivariate time series using data from real-world engineering applications. Quantitative analysis of the experiments shows that SF performs better than the baseline approaches and achieves high classification accuracy. In addition, the method enables identification of noisy sensors from multivariate data and discounts their use for classification.

In this poster, we present a novel approach to study and reveal network protocol information from radio activities instrumentation in wireless sensor network. Recent studies have analyzed radio activities; however, most of these studies focus on estimating energy consumption, since radio chip usually dominates the energy consumption of nodes. In our work, we analyze radio activities with a different purpose, which aims to reveal network protocols and application workloads by an analysis of fine-grained low level radio activities on the nodes. We design a feature called Radio Awake Length Counter and use it to classify and reveal network activity. Results from experiments on a real world testbed indicate that our approach can achieve up to 97% accuracy to identify the routing protocols, average 85% accuracy to distinguish application workloads.

This paper considers a stochastic optimization approach for job scheduling and server management in large-scale, geographically distributed data centers. Randomly arriving jobs are routed to a choice of servers. The number of active servers depends on server activation decisions that are updated at a slow time scale, and the service rates of the servers are controlled by power scaling decisions that are made at a faster time scale. We develop a two-time-scale decision strategy that offers provable power cost and delay guarantees. The performance and robustness of the approach is illustrated through simulations.

Efficient reasoning in large knowledge bases is an important problem for AI systems. Hand-optimization of reasoning becomes impractical as KBs grow, and impossible as knowledge is automatically added via knowledge capture or machine learning. This paper describes a method for automatic extraction of axioms for efficient inference over large knowledge bases, given a set of query types and information about the types of facts in the KB currently as well as what might be learned. We use the highly right skewed distribution of predicate connectivity in large knowledge bases to prune intractable regions of the search space. We show the efficacy of these techniques via experiments using queries from a learning by reading system. Results show that these methods lead to an order of magnitude improvement in time with minimal loss in coverage.

Commonsense reasoning at scale is a core problem for cognitive systems. In this paper, we discuss two ways in which heuristic graph traversal methods can be used to generate plausible inference chains. First, we discuss how Cyc’s predicate-type hierarchy can be used to get reasonable answers to queries. Second, we explain how connection graph-based techniques can be used to identify script-like structures. Finally, we demonstrate through experiments that these methods lead to significant improvement in accuracy for both Q/A and script construction.

While a massive amount of time series can now be collected in many physical systems, it is a challenge to build an analytic model that can correctly profile the data because those time series usually exhibit various behaviors. In this paper we propose an integrated method to address the heterogeneity issue in modeling big time series data. We first extracts relevant features to summarize the underlying dynamics of those series. We present both linear and nonlinear feature extraction techniques, as well as a procedure to determine the right extraction method for individual time series. Given extracted features, our method further models the trajectory pattern of time series in the feature space. Both a regression based and a density based method are presented to profile different types of feature trajectories. Experimental results in a real power plant illustrate that our feature extraction and trajectory model are effective to profile various time series. Our method has been used to successfully detect anomalies in the system.

Computing-as-a-service has been evolving steadily. Today, private clouds (e.g., Google's internal shared computing cluster) as well as public clouds (e.g., Amazon's web services (AWS), Microsoft's Azure) provide computing abstractions at various levels: bare virtual machines, specialized languages and runtimes (e.g., for massively-parallel data processing---MapReduce, Dryad), web services. For example, Amazon offers bare virtual machines as well as MapReduce clusters.

Recent advances in sensing and communication technologies enable us to collect round-the-clock monitoring data from a wide-array of distributed systems including data centers, manufacturing plants, transportation networks, automobiles, etc. Often this data is in the form of time series collected from multiple sensors (hardware as well as software based). Previously, we developed a time-invariant relationships based approach that uses Auto-Regressive models with eXogenous input (ARX) to model this data. A tool based on our approach has been effective for fault detection and capacity planning in distributed systems. In this paper, we first describe our experience in applying this tool in real-world settings. We also discuss the challenges in fault localization that we face when using our tool, and present two approaches - a spatial approach based on invariant graphs and a temporal approach based on expected broken invariant patterns - that we developed to address this problem.

How do reasoning systems that learn evolve over time? What are the properties of different learning strategies? Characterizing the evolution of these systems is important for understanding their limitations and gaining insights into the interplay between learning and reasoning. We describe an inverse ablation model for studying how large knowledge-based systems evolve: Create a small knowledge base by ablating a large KB, and simulate learning by incrementally re-adding facts, using different strategies to simulate types of learners. For each iteration, reasoning properties (including number of questions answered and run time) are collected, to explore how learning strategies and reasoning interact. We describe several experiments with the inverse ablation model, examining how two different learning strategies perform. Our results suggest that different concepts show different rates of growth, and that the density and distribution of facts that can be learned are important parameters for modulating the rate of learning.

In this work we focus on a stochastic optimization based approach to make distributed routing and server management decisions in the context of large-scale, geographically distributed data centers, which offers significant potential for exploring power cost reductions. Our approach considers such decisions at different time scales and offers provable power cost and delay characteristics. The utility of our approach and its robustness are also illustrated through simulation-based experiments under delay tolerant workloads.

Many applications are enabled by the ability to capture videos on a smartphone and to have these videos uploaded to an Internet-connected server. This capability requires the transfer of large volumes of data from the phone to the infrastructure. Smartphones have multiple wireless interfaces -- 3G/EDGE and WiFi -- for data transfer, but there is considerable variability in the availability and achievable data transfer rate for these networks. Moreover, the energy costs for transmitting a given amount of data on these wireless interfaces can differ by an order of magnitude. On the other hand, many of these applications are often naturally delay-tolerant, so that it is possible to delay data transfers until a lower-energy WiFi connection becomes available. In this paper, we present a principled approach for designing an optimal online algorithm for this energy-delay tradeoff using the Lyapunov optimization framework. Our algorithm, called SALSA, can automatically adapt to channel conditions and requires only local information to decide whether and when to defer a transmission. We evaluate SALSA using real-world traces as well as experiments using a prototype implementation on a modern smartphone. Our results show that SALSA can be tuned to achieve a broad spectrum of energy-delay tradeoffs, is closer to an empirically-determined optimal than any of the alternatives we compare it to, and, can save 10-40% of battery capacity for some workloads.

Various sensor network measurement studies have reported instances of transient faults in sensor readings. In this work, we seek to answer a simple question: How often are such faults observed in real deployments? We focus on three types of transient faults, caused by faulty sensor readings that appear abnormal. To understand the prevalence of such faults, we first explore and characterize four qualitatively different classes of fault detection methods. Rule-based methods leverage domain knowledge to develop heuristic rules for detecting and identifying faults. Estimation methods predict “normal” sensor behavior by leveraging sensor correlations, flagging anomalous sensor readings as faults. Time-series-analysis-based methods start with an a priori model for sensor readings. A sensor measurement is compared against its predicted value computed using time series forecasting to determine if it is faulty. Learning-based methods infer a model for the “normal” sensor readings using training data, and then statistically detect and identify classes of faults. We find that these four classes of methods sit at different points on the accuracy/robustness spectrum. Rule-based methods can be highly accurate, but their accuracy depends critically on the choice of parameters. Learning methods can be cumbersome to train, but can accurately detect and classify faults. Estimation methods are accurate, but cannot classify faults. Time-series-analysis-based methods are more effective for detecting short duration faults than long duration ones, and incur more false positives than the other methods. We apply these techniques to four real-world sensor datasets and find that the prevalence of faults as well as their type varies with datasets. All four methods are qualitatively consistent in identifying sensor faults, lending credence to our observations. Our work is a first step towards automated online fault detection and classification.

Load balancing in publish/subscribe (pub/sub) broker networks is challenging as the workload is multi-dimensional and content-dependent. In this paper we present the framework design of a middleware, called Shuffle, to achieve optimal load balancing in a pub/sub broker network. Shuffle features a suite of active workload management schemes within a single overlay topology on message parsing, matching, delivery, and forwarding, the four types of workload in a publish/subscribe service affected by two inputs-streaming events and stored subscriptions. Shuffle leverages its traffic randomization scheme and Chord, a DHT substrate, to build overlay trees for active workload aggregation and distribution, and we show the optimality property of the load balancing scheme upon any input traffic distribution on individual Shuffle aggregation trees. We also show the NP-hardness of the workload management problem when it has to be done among multiple correlated aggregation trees, and present a heuristic accordingly. Through extensive simulations we validated the design of Shuffle upon dynamic and heavy workload.

"Alice has a piece of valuable information which she is willing to sell to anyone who is interested in; she is too busy and wants to ask Bob, a professional broker, to sell that information for her; but Alice is in a dilemma where she cannot trust Bob with that information but Bob cannot help her find her customers without knowing that information." In this paper, we propose a security mechanism called information foiling to address new confidentiality problems arising in pub/sub overlay services [1]. Information foiling extends Rivest's "Chaffing and Winnowing" [2], and its basic idea is to carefully generate a set of fake messages to hide an authentic message. Information foiling requires no modification inside the broker network so that the routing/filtering capabilities of broker nodes remains intact. We formally present the information foiling mechanism in the context of publish/subscribe overlay services, and discuss its applicability in other Internet applications. For publish/subscribe applications, we propose a suite of optimal schemes for fake message generation in different scenarios. Real-world data are used in our evaluation to demonstrate the effectiveness of the proposed schemes.