Google's Dremel was one of the first systems that combined a set of architectural principles that have become a common practice in today's cloud-native analytics tools, including disaggregated storage and compute, in situ analysis, and columnar storage for semistructured data. In this paper, we discuss how these ideas evolved in the past decade and became the foundation for Google BigQuery.

Participatory sensing services based on mobile phones constitute an important growing area of mobile computing. Most services start small and hence are initially sparsely deployed. Unless a mobile service adds value while sparsely deployed, it may not survive conditions of sparse deployment. The paper offers a generic solution to this problem and illustrates this solution in the context ofGreenGPS; a navigation service that allows drivers to find the most fuel-efficient routes customized for their vehicles between arbitrary end-points. Specifically, when the participatory sensing service is sparsely deployed, we demonstrate a general framework for generalization from sparse collected data to produce models extending beyond the current data coverage. This generalization allows the mobile service to offer value under broader conditions. GreenGPS uses our developed participatory sensing infrastructure and generalization algorithms to perform inexpensive data collection, aggregation, and modeling in an end-to-end automated fashion. The models are subsequently used by our backend engine to predict customized fuel-efficient routes for both members and non-members of the service. GreenGPS is offered as a mobile phone application and can be easily deployed and used by individuals. A preliminary study of our green navigation idea was performed in[1], however, the effort was focused on a proof-of-concept implementation that involved substantial offline and manual processing. In contrast, the results and conclusions in the current paper are based on a more advanced and accurate model and extensive data from a real-world phone-based implementation and deployment, which enables reliable and automatic end-to-end data collection and route recommendation. The system further benefits from lower cost and easier deployment. To evaluate the green navigation service efficiency, we conducted a user subject study consisting of 22 users driving different vehicles over the course of several months in Urbana-Champaign, IL. The experimental results using the collected data suggest that fuel savings of 21.5 over the fastest, 11.2 percent over the shortest, and 8.4 percent over the Garmin eco routes can be achieved by following GreenGPS green routes. The study confirms that our navigation service can survive conditions of sparse deployment and at the same time achieve accurate fuel predictions and lead to significant fuel savings.

This article presents a tool for uncovering bugs due to interactive complexity in networked sensing applications. Such bugs are not localized to one component that is faulty, but rather result from complex and unexpected interactions between multiple often individually nonfaulty components. Moreover, the manifestations of these bugs are often not repeatable, making them particularly hard to find, as the particular sequence of events that invokes the bug may not be easy to reconstruct. Because of the distributed nature of failure scenarios, our tool looks for sequences of events that may be responsible for faulty behavior, as opposed to localized bugs such as a bad pointer in a module. We identified several challenges in applying discriminative sequence mining for root cause analysis when the system fails to perform as expected and presented our solutions to those challenges. We also present two alternative schemes, namely, two-stage mining and the progressive discriminative sequence mining to address the scalability challenge. An extensible framework is developed where a front-end collects runtime data logs of the system being debugged and an offline back-end uses frequent discriminative pattern mining to uncover likely causes of failure. We provided several case studies where we applied our tool successfully to troubleshoot the cause of the problem. We uncovered a kernel-level race condition bug in the LiteOS operating system and a protocol design bug in the directed diffusion protocol. We also presented a case study of debugging a multichannel MAC protocol that was found to exhibit corner cases of poor performance (worse than single-channel MAC). The tool helped to uncover event sequences that lead to a highly degraded mode of operation. Fixing the problem significantly improved the performance of the protocol. We also evaluated the extensions presented in this article. Finally, we provided a detailed analysis of tool overhead in terms of memory requirements and impact on the running application.

This paper presents a novel multicopy routing protocol for disruption-tolerant networks whose objective is to minimize energy expended on communication. The protocol is designed for disaster-response applications, where power and infrastructure resources are disrupted. Unlike other delay-tolerant networks, energy is a vital resource in post disaster scenarios to ensure availability of (disruption-tolerant) communication until infrastructure is restored. Our approach exploits naturally recurrent mobility and contact patterns in the network, formed by rescue workers, volunteers, survivors, and their (possibly stranded) vehicles to reduce the number of message copies needed to attain an adequate delivery ratio in the face of disconnection and intermittent connectivity. A new notion of intercontact routing is proposed that allows estimating route delays and delivery probabilities, identifying more reliable routes and controlling message replication and forwarding accordingly. In addition, we augment the protocol with a differentiated message delivery service that enables the network to function even in an extremely low energy condition. We simulate the scheme using a mobility model that reflects recurrence inspired by disaster scenarios and compare our results to previous DTN routing techniques. The evaluation shows that the new approach reduces the resource overhead per message over previous approaches while maintaining a comparable delivery ratio at the expense of a small (bounded) increase in latency.

At CPSWeek 2011, the authors presented a demonstration of Apollo, a fact-finder for participatory sensing that ranks archived human-centric and sensor data by credibility. The current demonstration significantly extends our previous work by allowing Apollo to operate on live streaming data; in this case, live Twitter feeds. As the role of humans as sensors increases in emerging sensing applications, a principled approach becomes necessary to address the problem of ascertaining the veracity of sources and observations made by them. Participatory and social sensing applications may use potentially unreliable or unverified sources, such as a phone-based sensing application that grows virally in a large un-vetted population, a disaster-response application, where conflicting damage assessment reports may come from large numbers of different volunteers, or a military application, where friendly observers at a remote location may make hard-to-verify claims about local events. Apollo analyzes noisy data that increasingly plagues human-centric sensing to determine which items of information are more likely to be true.

This paper develops a navigation service, called GreenGPS, that uses participatory sensing data to map fuel consumption on city streets, allowing drivers to find the most fuel efficient routes for their vehicles between arbitrary end-points. The service exploits measurements of vehicular fuel consumption sensors, available via the OBD-II interface standardized in all vehicles sold in the US since 1996. The interface gives access to most gauges and engine instrumentation. The most fuel-efficient route does not always coincide with the shortest or fastest routes, and may be a function of vehicle type. Our experimental study shows that a participatory sensing system can influence routing decisions of individual users and also answers two questions related to the viability of the new service. First, can it survive conditions of sparse deployment? Second, how much fuel can it save? A challenge in participatory sensing is to generalize from sparse sampling of high-dimensional spaces to produce compact descriptions of complex phenomena. We illustrate this by developing models that can predict fuel consumption of a set of sixteen different cars on the streets of the city of Urbana-Champaign. We provide experimental results from data collection suggesting that a 1% average prediction error is attainable and that an average 10% savings in fuel can be achieved by choosing the right route.

Many participatory sensing applications use data collected by participants to construct a public model of a system or phenomenon. For example, a health application might compute a model relating exercise and diet to amount of weight loss. While the ultimately computed model could be public, the individual input and output data traces used to construct it may be private data of participants (e.g., their individual food intake, lifestyle choices, and resulting weight). This paper proposes and experimentally studies a technique that attempts to keep such input and output data traces private, while allowing accurate model construction. This is significantly different from perturbation-based techniques in that no noise is added. The main contribution of the paper is to show a certain data transformation at the client side that helps keeping the client data private while not introducing any additional error to model construction. We particularly focus on linear regression models which are widely used in participatory sensing applications. We use the data set from a map-based participatory sensing service to evaluate our scheme. The service in question is a green navigation service that constructs regression models from participant data to predict the fuel consumption of vehicles on road segments. We evaluate our proposed mechanism by providing empirical evidence that: i) an individual data trace is generally hard to reconstruct with any reasonable accuracy, and ii) the regression model constructed using the transformed traces has a much smaller error than one based on additive data-perturbation schemes.

Various sensor types, e.g., temperature, humidity, and acoustic, sense physical phenomena in different ways, and thus, are expected to have different sensing models. Even for the same sensor type, the sensing model may need to be changed in different environments. Designing and testing a different coverage protocol for each sensing model is indeed a costly task. To address this challenging task, we propose a new probabilistic coverage protocol (denoted by PCP) that could employ different sensing models. We show that PCP works with the common disk sensing model as well as probabilistic sensing models, with minimal changes. We analyze the complexity of PCP and prove its correctness. In addition, we conduct an extensive simulation study of large-scale sensor networks to rigorously evaluate PCP and compare it against other deterministic and probabilistic protocols in the literature. Our simulation demonstrates that PCP is robust, and it can function correctly in presence of random node failures, inaccuracies in node locations, and imperfect time synchronization of nodes. Our comparisons with other protocols indicate that PCP outperforms them in several aspects, including number of activated sensors, total energy consumed, and network lifetime.

In this paper, we propose a new transport protocol for data collection in sensor networks that monitor physical phenomena. In a network with variable channel condition, this protocol adapts transmission reliability based on the importance of transmitted spatio-temporal data to the reconstruction of the phenomenon. Data whose omission generates a higher estimation error are transmitted more reliably. The protocol aggregates data from nodes to the base station and provides a constant expected estimation error while significantly reducing the energy consumption and bandwidth usage compared with other approaches to reliable communication. Moreover, our protocol is easy to implement on current motes. To the best of our knowledge, this is the first transport layer protocol, that incorporates predictive models, to be implemented on motes. We perform extensive experiments on MicaZ motes using LiteOS to compare the performance of our protocol against previous transport protocols and data suppression schemes. Our experimental results show that our protocol introduces a very small estimation error while saving orders of magnitude in consumed energy compared to reliable transport. In other cases, estimation error and energy consumption are simultaneously reduced by 50 - 85%.

This paper presents a novel multi-copy routing protocol for disruption-tolerant networks whose objective is to minimize energy expended on communication. The protocol is designed for disaster-response applications, where power and infrastructure resources are disrupted. Unlike other delay-tolerant networks, energy is a vital resource in post-disaster scenarios to ensure availability of (disruption-tolerant) communication until infrastructure is restored. Our approach exploits naturally recurrent mobility and contact patterns in the network, formed by rescue workers, volunteers, survivors, and their (possibly stranded) vehicles to reduce the number of message copies needed to attain an adequate delivery ratio in the face of disconnection and intermittent connectivity. A new notion of inter-contact routing is proposed that allows estimating route delays and delivery probabilities, identifying more reliable routes and controlling message replication and forwarding accordingly. We simulate the scheme using a mobility model that reflects recurrence inspired by disaster scenarios, and compare our results to previous DTN routing techniques. The evaluation shows that the new approach reduces the resource overhead per message over previous approaches while maintaining a comparable delivery ratio at the expense of a small (bounded) increase in latency.

This paper presents a tool for uncovering bugs due to interactive complexity in networked sensing applications. Such bugs are not localized to one component that is faulty, but rather result from complex and unexpected interactions between multiple often individually non-faulty components. Moreover, the manifestations of these bugs are often not repeatable, making them particularly hard to find, as the particular sequence of events that invokes the bug may not be easy to reconstruct. Because of the distributed nature of failure scenarios, our tool looks for sequences of events that may be responsible for faulty behavior, as opposed to localized bugs such as a bad pointer in a module. An extensible framework is developed where a front-end collects runtime data logs of the system being debugged and an offline back-end uses frequent discriminative pattern mining to uncover likely causes of failure. We provide a case study of debugging a recent multichannel MAC protocol that was found to exhibit corner cases of poor performance (worse than single channel MAC). The tool helped uncover event sequences that lead to a highly degraded mode of operation. Fixing the problem significantly improved the performance of the protocol.We also provide a detailed analysis of tool overhead in terms of memory requirements and impact on the running application.

We propose a new probabilistic coverage protocol (denoted by PCP) that considers probabilistic sensing models. PCP is fairly general and can be used with different sensing models. In particular, PCP requires the computation of a single parameter from the adopted sensing model, while everything else remains the same. We show how this parameter can be derived in general, and we actually do the calculations for two example sensing models: (i) the probabilistic exponential sensing model, and (ii) the commonly-used deterministic disk sensing model. The first model is chosen because it is conservative in terms of estimating sensing capacity, and it has been used before in another probabilistic coverage protocol, which enables us to conduct a fair comparison. Because it is conservative, the exponential sensing model can be used as a first approximation for many other sensing models. The second model is chosen to show that our protocol can easily function as a deterministic coverage protocol. In this case, we compare our protocol against two recent deterministic protocols that were shown to outperform others in the literature. Our comparisons indicate that our protocol outperforms all other protocols in several aspects, including number of activated sensors and total energy consumed. We also demonstrate the robustness of our protocol against random node failures, node location inaccuracy, and imperfect time synchronization.

Several previous works have experimentally shown that communication ranges of sensors are not regular disks. Rather, they follow probabilistic models. Yet, many current connectivity maintenance protocols assume the disk communication model for convenience and ease of analysis. In addition, current protocols do not provide any assessment of the quality of communication between nodes. In this paper, we take a first step in designing connectivity maintenance protocols for more realistic communication models. We propose a distributed connectivity maintenance protocol that explicitly accounts for the probabilistic nature of communication links and achieves a given target communication quality between nodes. Our protocol is simple to implement, and we demonstrate its robustness against random node failures, inaccuracy of node locations, and imperfect time synchronization of nodes using extensive simulations. We compare our protocol against others in the literature and show that it activates fewer number of nodes, consumes much less energy, and significantly prolongs the network lifetime.