Given a graph and an integer k, the goal of group closeness maximization is to find, among all possible sets of k vertices (called seed sets), a set that has the highest group closeness centrality. Existing techniques for this NP-hard problem strive to quickly find a seed set with a high, but not necessarily the highest centrality. We propose PRESTO, a new solution that can efficiently provide both approximate and exact answers to the group closeness maximization problem. PRESTO continuously calculates the centrality of different seed sets until a time limit is reached or it identifies a seed set with the highest possible centrality. It prioritizes seed sets to quickly find ones that are highly central and thus can be used as accurate approximate answers to the problem. Furthermore, PRESTO can proactively discard large groups of seed sets that cannot have the highest centrality, thereby drastically speeding up the discovery of approximate and exact answers. In our evaluations, compared to other state-of-the-art solutions, PRESTO finds seed sets that have up to 39% higher centrality.

Subgraph discovery in a data graph (finding subsets of vertices and edges satisfying a user-specified criteria) is an essential and general graph analytics operation with a wide spectrum of applications. We present Nuri, a general subgraph discovery system that allows users to succinctly specify subgraphs of interest and criteria for ranking them. Given such specifications, Nuri efficiently finds the k most relevant subgraphs. It prioritizes (i.e., expands earlier than others) subgraphs that are more likely to expand into the desired subgraphs (prioritized subgraph expansion) and proactively discards irrelevant subgraphs from which the desired subgraphs cannot be constructed (pruning). Nuri can also efficiently store and retrieve a large number of subgraphs on disk without being limited by the size of main memory. We demonstrate using both real and synthetic datasets that Nuri only on a single core outperforms the closest alternative distributed system running on 40 cores by more than 2 orders of magnitude for clique discovery and 1 order of magnitude for subgraph isomorphism and pattern mining.

Many of today's applications can benefit from the discovery of the most central entities in real-world networks. This paper presents a new technique that efficiently finds the k most central entities in terms of closeness centrality. Instead of computing the centrality of each entity independently, our technique shares intermediate results between centrality computations. Since the cost of each centrality computation may vary substantially depending on the choice of the previous computation, our technique schedules centrality computations in a manner that minimizes the estimated completion time. This technique also updates, with negligible overhead, an upper bound on the centrality of every entity. Using this information, our technique proactively skips entities that cannot belong to the final answer. This paper presents evaluation results for actual networks to demonstrate the benefits of our technique.

Trajectory compression algorithms enable efficient transmission, storage, and processing of trajectory data by eliminating redundant information. While a large number of compression algorithms have been developed, there is no comprehensive and convenient benchmarking system for evaluating these algorithms. We will demonstrate TrajMetrix, our system that meets the above need. We will show how TrajMetrix can be used to gain insights into the benefits and drawbacks of various compression algorithms given different compression requirements.

The world is full of evolving networks, many of which can be represented by a series of large graphs. Neither the current graph processing systems nor database systems can efficiently store and query these graphs due to their lack of support for managing multiple graphs and lack of essential graph querying capabilities. We propose to demonstrate our system, G*, that meets the new challenges of managing multiple graphs and supporting fundamental graph querying capabilities. G* can store graphs on a large number of servers while compressing these graphs based on their commonalities. G* also allows users to easily express queries on graphs and efficiently executes these queries by sharing computations across graphs. During our demonstrations, conference attendees will run various analytic queries on large, practical data sets. These demonstrations will highlight the convenience and performance benefits of G* over existing database and graph processing systems, the effectiveness of sharing in graph data storage and processing, as well as G*'s scalability.

The massive volumes of trajectory data generated by inexpensive GPS devices have led to difficulties in processing, querying, transmitting and storing such data. To overcome these difficulties, a number of algorithms for compressing trajectory data have been proposed. These algorithms try to reduce the size of trajectory data, while preserving the quality of the information. We present results from a comprehensive empirical evaluation of many compression algorithms including Douglas-Peucker Algorithm, Bellman's Algorithm, STTrace Algorithm and Opening Window Algorithms. Our empirical study uses different types of real-world data such as pedestrian, vehicle and multimodal trajectories. The algorithms are compared using several criteria including execution times and the errors caused by compressing spatio-temporal information, across numerous real-world datasets and various error metrics.

iFlow is a replication-based system that can achieve both fast and reliable processing of high volume data streams on the Internet scale. iFlow uses a low degree of replication in conjunction with detouring techniques to overcome network congestion and outages. Computation over iFlow can be expressed as a graph of operators. To cope with varying system conditions these operators continually migrate in a manner that improves performance and availability at the same time.

Network coordinate systems can efficiently predict the round-trip time between any pair of nodes on the Internet. These systems map nodes onto a multi-dimensional coordinate space such that the round-trip time between two arbitrary nodes can be estimated by the distance between the corresponding pair of points in the coordinate space. In these systems, each node continuously updates its coordinates based on the latencies of new communications and the coordinates of other nodes. Node coordinates obtained in this manner, however, may be misled by erroneous information, such as extraordinary roundtrip times. Previous techniques attempt to overcome this problem by having nodes reject new information if it is inconsistent with the current coordinates. These techniques are still inappropriate if the coordinates are not sufficiently accurate. In this paper, we develop a new approach where each node preserves recent communication history. To update a node's coordinates more accurately, our approach re-evaluates the records in the node's history while ignoring inconsistent communication records and applying a higher weight to more reliable records. This approach thus can prevent node coordinates from being affected by erroneous information that was difficult to detect in the past. Through evaluations based on real network trace data, we demonstrate that our approach can reduce network latency prediction errors by 50% compared to previous approaches.

We propose to demonstrate iFlow, our replication-based system that supports both fast and reliable processing of data streams over the Internet. iFlow uses a low degree of replication in conjunction with detouring techniques to overcome network outages. iFlow also deploys replicas in a manner that improves performance and availability at the same time, and can cope with varying system conditions by continually migrating replicas. Based on a live network monitoring application, our demonstration will substantiate the strengths of iFlow. During the demonstration, various visual tools will provide graphical evidence of improvements with regards to availability, performance, and resource usage. To show iFlow's adaptivity, these tools will also allow us to control the demonstration situation including injecting different types of failures.

We present a replication-based approach that realizes both fast and highly-available stream processing over wide area networks. In our approach, multiple operator replicas send outputs to each downstream replica so that it can use whichever data arrives first. To further expedite the data flow, replicas run independently, possibly processing data in different orders. Despite this complication, our approach always delivers what non-replicated processing would produce without failures. We call this guarantee replication transparency. In this paper, we first discuss semantic issues for replication transparency and extend stream-processing primitives accordingly. Next, we develop an algorithm that manages replicas at geographically dispersed servers. This algorithm strives to achieve the best latency guarantee, relative to the cost of replication. Finally, we substantiate the utility of our work through experiments on PlanetLab servers as well as simulations based on real network traces.

Borealis-R is a replication-based system for both fast and

We present a collaborative, self-configuring high availability (HA) approach for stream processing that enables low-latency failure recovery while incurring small run-time overhead. Our approach relies on a novel fine-grained checkpointing model that allows query fragments at each server to be backed up at multiple other servers and recovered collectively (in parallel) when there is a failure. In this paper, we first address the problem of determining the appropriate query fragments at each server. We then discuss, for each fragment, which server to use as its backup as well as the proper checkpoint schedule. We also introduce and analyze operator-specific delta-checkpointing techniques to reduce the overall HA cost. Finally, we quantify the benefits of our approach using results from our prototype implementation and a detailed simulator.

Stream-processing systems are designed to support an emerging class of applications that require sophisticated and timely processing of high-volume data streams, often originating in distributed environments. Unlike traditional data-processing applications that require precise recovery for correctness, many stream-processing applications can tolerate and benefit from weaker recovery guarantees. In this paper, we study various recovery guarantees and pertinent recovery techniques that can meet the correctness and performance requirements of stream-processing applications. We discuss the design and algorithmic challenges associated with the proposed recovery techniques and describe how each can provide different guarantees with proper combinations of redundant processing, checkpointing, and remote logging. Using analysis and simulations, we quantify the cost of our recovery guarantees and examine the performance and applicability of the recovery techniques. We also analyze how the knowledge of query network properties can help decrease the cost of high availability.

Distributed and parallel computing environments are becoming cheap and commonplace. The availability of large numbers of CPU's makes it possible to process more data at higher speeds. Stream-processing systems are also becoming more important, as broad classes of applications require results in real-time. Since load can vary in unpredictable ways, exploiting the abundant processor cycles requires effective dynamic load distribution techniques. Although load distribution has been extensively studied for the traditional pull-based systems, it has not yet been fully studied in the context of push-based continuous query processing. In this paper, we present a correlation based load distribution algorithm that aims at avoiding overload and minimizing end-to-end latency by minimizing load variance and maximizing load correlation. While finding the optimal solution for such a problem is NP-hard, our greedy algorithm can find reasonable solutions in polynomial time. We present both a global algorithm for initial load distribution and a pair-wise algorithm for dynamic load migration.

Borealis is a distributed stream processing engine that is being developed at Brandeis University, Brown University, and MIT. Borealis inherits core stream processing functionality from Aurora and inter-node communication functionality from Medusa.We propose to demonstrate some of the key aspects of distributed operation in Borealis, using a multi-player network game as the underlying application. The demonstration will illustrate the dynamic resource management, query optimization and high availability mechanisms employed by Borealis, using visual performance-monitoring tools as well as the gaming experience.