We propose moving from Software Defined Networks (SDN) to Software Managed Networks (SMN) where all information for managing the life cycle of a network (from deployment to operations to upgrades), across all layers (from Layer 1 through 7) is stored in a central repository. Crucially, a SMN also has a generalized control plane that, unlike SDN, controls all aspects of the cloud including traffic management (e.g., capacity planning) and reliability (e.g., incident routing) at both short (minutes) and large (years) time scales. Just as SDN allows better routing, a SMN improves visibility and enables cross-layer optimizations for faster response to failures and better network planning and operations. Implemented naively, SMN for planetary sc6ale networks requires orders of magnitude larger and more heterogeneous data (e.g., alerts, logs) than SDN. We address this using coarsening — mapping complex data to a more compact abstract representation that has approximately the same effect, and is more scalable, maintainable, and learnable. We show examples including Coarse Bandwidth Logs for capacity planning and Coarse Dependency Graphs for incident routing. Coarse Dependency Graphs improve an incident routing metric from 45% to 78% while for a distributed approach like Scouts the same metric was 22%. We end by discussing how to realize SMN, and suggest cross-layer optimizations and coarsenings for other operational and planning problems in networks.

Modern software projects have been increasingly using cloud services as important components. The cloud-based programming practice greatly simplifies software development by harvesting cloud benefits (e.g., high availability and elasticity). However, it imposes new challenges for software testing and analysis, due to opaqueness of cloud backends and monetary cost of invoking cloud services for continuous integration and deployment. As a result, cloud emulators are developed for offline development and testing, before online testing and deployment. This paper presents a systematic analysis of cloud emulators from the perspective of cloud-based software testing. Our goal is to (1) understand the discrepancies introduced by cloud emulation with regard to software quality assurance and deployment safety and (2) address inevitable gaps between emulated and real cloud services. The analysis results are concerning. Among 255 APIs of five cloud services from Azure and Amazon Web Services (AWS), we detected discrepant behavior between the emulated and real services in 94 (37 %) of the APIs. These discrepancies lead to inconsistent testing results, threatening deployment safety, introducing false alarms, and creating debuggability issues. The root causes are diverse, including accidental implementation defects and essential emulation challenges. We discuss potential solutions and develop a practical mitigation technique to address discrepancies of cloud emulators for software testing.

Large Language Models (LLMs) are increasingly being used to plan, reason, and execute tasks across diverse scenarios. In use cases like repeatable workflows and agentic settings, prompts are often reused with minor variations while having a similar structure for recurring tasks. This opens up opportunities for caching. However, exact prompt matching fails on such structurally similar prompts, while semantic caching may produce incorrect responses by ignoring critical differences. To address this, we introduce GenCache, a generative cache that produces variation-aware responses for structurally similar prompts. GenCache identifies reusable response patterns across similar prompt structures and synthesizes customized outputs for new requests. We show that GenCache achieves 83\% cache hit rate, while having minimal incorrect hits on datasets without prompt repetition. In agentic workflows, it improves cache hit rate by $\sim$20\% and reduces end-to-end execution latency by $\sim$34\% compared to standard prompt matching.

The rapid growth in the use of Large Language Models (LLMs) and AI Agents as part of software development and deployment is revolutionizing the information technology landscape. While code generation receives significant attention, a higher-impact application lies in using agents for the operational resilience of cloud services, which currently require significant human effort and domain knowledge. There is a growing interest in AI for IT Operations (AIOps), which aims to automate complex operational tasks, like fault localization and root cause analysis, reducing human intervention and customer impact. However, achieving the vision of autonomous and self-healing clouds through AIOps is hampered by the lack of standardized frameworks for building, evaluating, and improving AIOps agents. This vision paper lays the groundwork for such a framework by framing the requirements and then discussing design decisions that satisfy them. We also propose AIOpsLab, a prototype implementation leveraging agent-cloud-interface that orchestrates an application, injects real-time faults using chaos engineering, and interfaces with an agent to localize and resolve the faults. We report promising results and lay the groundwork to build a modular and robust framework for building, evaluating, and improving agents for autonomous clouds.

Debugging a failure usually requires reproducing it first. This can be hard for failures in production distributed systems, where bugs are exposed only by some unusual faulty events. While fault injection testing becomes popular, existing solutions are designed for bug finding. They are ineffective and inefficient to reproduce a specific failure during debugging.

Retry---the re-execution of a task on failure---is a common mechanism to enable resilient software systems. Yet, despite its commonality and long history, retry remains difficult to implement and test.

Concurrency bugs are difficult to detect, reproduce, and diagnose, as they manifest under rare timing conditions. Recently, active delay injection has proven efficient for exposing one such type of bug --- thread-safety violations --- with low overhead, high coverage, and minimal code analysis. However, how to efficiently apply active delay injection to broader classes of concurrency bugs is still an open question.

It is well known that valuable information is contained in the natural language components of software systems, like comments and manual, and such information can be used to improve system performance and reliability. Past research has attempted to extract such information through task-specific machine learning models and tool chains. Here, we investigate a general, one-model-fit-all solution through a state-of-the-art large language model (e.g., the GPT series). Our investigation covers three representative tasks: extracting locking rules from comments, synthesizing exception predicates from comments, and identifying performance-related configurations; it reveals challenges and opportunities in applying large language models to system maintenance tasks.

Database-backed applications are widely used. To effectively test these applications, one needs to design not only user inputs but also database states, which imposes unique challenges. First, valid database states have to satisfy complicated constraints determined by application semantics, and hence are difficult to synthesize. Second, the state space of a database is huge, as an application can contain tens to hundreds of tables with up to tens of fields per table. Making things worse, each test involving database operations takes significant time to run. Consequently, unhelpful database states and running tests on them can severely waste testing resources. We propose DBGRILLER, a tool that generates database states to facilitate thorough testing of database-backed applications. To effectively generate valid database states, DBGRILLER strategically injects minor mutation into existing database states and transforms part of the application-under-test into a stand-alone validity checker. To tackle the huge database state space and save testing time, DBGRILLER uses program analysis to identify a novel branch-projected DB view that can be used to filter out database states that are unlikely to increase the testing branch coverage. Our evaluation on 9 popular open-source database applications shows that DBGRILLER can effectively increase branch coverage of existing tests and expose previously unknown bugs.

Cloud providers use automated watchdogs or monitors to continuously observe service availability and to proactively report incidents when system performance degrades. Improper monitoring can lead to delays in the detection and mitigation of production incidents, which can be extremely expensive in terms of customer impacts and manual toil from engineering resources. Therefore, a systematic understanding of the pitfalls in current monitoring practices and how they can lead to production incidents is crucial for ensuring continuous reliability of cloud services.

Production incidents in today's large-scale cloud services can be extremely expensive in terms of customer impacts and engineering resources required to mitigate them. Despite continuous reliability efforts, cloud services still experience severe incidents due to various root-causes. Worse, many of these incidents last for a long period as existing techniques and practices fail to quickly detect and mitigate them. To better understand the problems, we carefully study hundreds of recent high severity incidents and their postmortems in Microsoft-Teams, a large-scale distributed cloud based service used by hundreds of millions of users. We answer: (a) why the incidents occurred and how they were resolved, (b) what the gaps were in current processes which caused delayed response, and (c) what automation could help make the services resilient. Finally, we uncover interesting insights by a novel multi-dimensional analysis that correlates different troubleshooting stages (detection, root-causing and mitigation), and provide guidance on how to tackle complex incidents through automation or testing at different granularity.

Crash localization, an important step in debugging crashes, is challenging when dealing with an extremely large number of diverse applications and platforms and underlying root causes. Large-scale error reporting systems, e.g., Windows Error Reporting (WER), commonly rely on manually developed rules and heuristics to localize blamed frames causing the crashes. As new applications and features are routinely introduced and existing applications are run under new environments, developing new rules and maintaining existing ones become extremely challenging.

Flaky tests, which can non-deterministically pass or fail on the same code, impose significant burden on developers by providing misleading signals during regression testing. Microsoft developers consider flaky tests as one of the top two reasons for slowing down software development. In order to debug the root-cause of a flaky behavior, a developer often needs to first reliably reproduce a failed execution. Unfortunately, this is non-trivial. For example, most of the flakiness in unit tests are caused by concurrency, and reproducing their failures requires specific thread interleaving. To address this challenge, we introduce FlakeRepro that helps developers reproduce a failed execution of a flaky test caused by concurrency. FlakeRepro combines static and dynamic analysis to quickly identify an interleaving that makes a flaky test fail with the same original error message. FlakeRepro is efficient: it can reproduce a failed execution after exploring few tens of interleavings. FlakeRepro integrates well with existing systems: it automatically instruments test binaries that can run on existing and unmodified test pipelines.

Synchronizations are fundamental to the correctness and performance of concurrent software. Unfortunately, correctly identifying all synchronizations has become extremely difficult in modern soft-ware systems due to the various types of synchronizations. Previous work either only infers specific type of synchronization by code analysis or relies on manual effort to annotate the synchronization. This paper proposes SherLock, a tool that uses unsupervised inference to identify synchronizations. SherLock leverages the fact that most synchronizations appear around the conflicting operations and form it into a linear system with a set of synchronization proper-ties and hypotheses. To collect enough observations, SherLock runs the unit tests a small number of times with feedback-based delay injection. We applied SherLock on 8 C# open-source applications. Without any prior knowledge, SherLock inferred 122 unique synchronizations, with few false positives. These inferred synchronizations cover a wide variety of types, including lock operations, fork-join operations, asynchronous operations, framework synchronization, and custom synchronization.

Runtime nondeterminism is a fact of life in modern database applications. Previous research has shown that nondeterminism can cause applications to intermittently crash, become unresponsive, or experience data corruption. We propose Adaptive Interventional Debugging (AID) for debugging such intermittent failures. AID combines existing statistical debugging, causal analysis, fault injection, and group testing techniques in a novel way to (1) pinpoint the root cause of an application's intermittent failure and (2) generate an explanation of how the root cause triggers the failure. AID works by first identifying a set of runtime behaviors (called predicates) that are strongly correlated to the failure. It then utilizes temporal properties of the predicates to (over)-approximate their causal relationships. Finally, it uses fault injection to execute a sequence of interventions on the predicates and discover their true causal relationships. This enables AID to identify the true root cause and its causal relationship to the failure. We theoretically analyze how fast AID can converge to the identification. We evaluate AID with six real-world applications that intermittently fail under specific inputs. In each case, AID was able to identify the root cause and explain how the root cause triggered the failure, much faster than group testing and more precisely than statistical debugging. We also evaluate AID with many synthetically generated applications with known root causes and confirm that the benefits also hold for them.

Cloud services have become the backbone of today's computing world. Runtime incidents, which adversely affect the expected service operations, are extremely costly in terms of user impacts and engineering efforts required to resolve them. Hence, such incidents are the target of much research effort. Unfortunately, there is limited understanding about cloud service incidents that actually happen during production runs: what cause them and how they are resolved.

In today’s agile world, developers often rely on continuous integration pipelines to help build and validate their changes by executing tests in an efficient manner. One of the significant factors that hinder developers’ productivity is flaky tests—tests that may pass and fail with the same version of code. Since flaky test failures are not deterministically reproducible, developers often have to spend hours only to discover that the occasional failures have nothing to do with their changes. However, ignoring failures of flaky tests can be dangerous, since those failures may represent real faults in the production code. Furthermore, identifying the root cause of flakiness is tedious and cumbersome, since they are often a consequence of unexpected and non-deterministic behavior due to various factors, such as concurrency and external dependencies.

App links, also known as mobile deep links, are URIs that point to specific pages in an app. App links are essential to many mobile experiences: Google and Bing use them to link search results directly to relevant pages in an app and apps use them for cross-app navigation. However, app links are hard to discover and, since they must be explicitly built into apps by developers, only exist for a small fraction of apps. To address these two problems, we propose Elix, an automated app link extractor. We define link extraction as a static information flow problem where a link, with its scheme and parameters, is synthesized by analyzing the data flow between subsequent pages in an app. As static analysis is prone to false positives, Elix adopts a novel, path-selective taint analysis that leverages symbolic execution to reason about path constraints and abandon infeasible paths. Elix can automatically and correctly discover links that are exposed by an app, and many others that are not explicitly exposed, thus increasing coverage of both link-enabled apps and link-enabled pages in an app. Elix also simplifies the scheme of extracted links by reducing complex types to a minimal set of primitive types. We have implemented Elix on Android and applied it to 1007 popular Android apps. Elix can extract 80-90% of an app's links, and above 80% of the extracted links are stable.

Concurrency bugs are hard to find, reproduce, and debug. They often escape rigorous in-house testing, but result in large-scale outages in production. Existing concurrency-bug detection techniques unfortunately cannot be part of industry's integrated build and test environment due to some open challenges: how to handle code developed by thousands of engineering teams that uses a wide variety of synchronization mechanisms, how to report little/no false positives, and how to avoid excessive testing resource consumption.

Accurate positioning in urban areas is important for personal navigation, geolocation apps, and ride-sharing. Smartphones localize themselves using GPS position estimates, and augment these with a variety of techniques including dead reckoning, map matching, and WiFi localization. However, GPS signals suffer significant impairment in urban canyons because of limited line-of-sight to satellites and signal reflections. In this paper, we focus on scalable and deployable techniques to reduce the impact of one specific impairment: reflected GPS signals from non-line-of-sight (NLOS) satellites. Specifically, we show how, using publicly available street-level imagery and off-the-shelf computer vision techniques, we can estimate the path inflation incurred by (the extra distance traveled by) a reflected signal from a satellite. Using these path inflation estimates we develop techniques to estimate the most likely actual position given a set of satellite readings at some position. Finally, we develop optimizations for fast position estimation on modern smartphones. Using extensive experiments in the downtown area of several large cities, we find that our techniques can reduce positioning error by up to 55% on average.

This paper presents GeoTrend; a system for scalable support of spatial trend discovery on recent microblogs, e.g., tweets and online reviews, that come in real time. GeoTrend is distinguished from existing techniques in three aspects: (1) It discovers trends in arbitrary spatial regions, e.g., city blocks. (2) It supports trending measures that effectively capture trending items under a variety of definitions that suit different applications. (3) It promotes recent microblogs as first-class citizens and optimizes its system components to digest a continuous flow of fast data in main-memory while removing old data efficiently. GeoTrend queries are top-k queries that discover the most trending k keywords that are posted within an arbitrary spatial region and during the last T time units. To support its queries efficiently, GeoTrend employs an in-memory spatial index that is able to efficiently digest incoming data and expire data that is beyond the last T time units. The index also materializes top-k keywords in different spatial regions so that incoming queries can be processed with low latency. In case of peak times, a main-memory optimization technique is employed to shed less important data, so that the system still sustains high query accuracy with limited memory resources. Experimental results based on real Twitter feed and Bing Mobile spatial search queries show the scalability of GeoTrend to support arrival rates of up to 50,000 microblog/second, average query latency of 3 milli-seconds, and at least 90+% query accuracy even under limited memory resources.

Context awareness is crucial for ubiquitous computing, and position is an important aspect of context. In an ideal world, every stationary object or entity in the built environment would be associated with position, so that applications can have precise spatial context about the environment surrounding a human. In this paper, we take a step towards this ideal: by analyzing images from Google Street View that cover different perspectives of a given object and triangulating the location of the object, our system, ALPS, can discover and localize common landmarks at the scale of a city accurately and with high coverage. ALPS contains several novel techniques that help improve the accuracy, coverage, and scalability of localization. Evaluations of ALPS on many cities in the United States show that it can localize storefronts with a coverage higher than 90% and a median error of 5 meters.

Services like Google Now on Tap and Bing Snapp enable new user experiences by understanding the semantics of contents that users consume in their apps. These systems send contents of currently displayed app pages to the cloud to identify relevant entities (e.g., a movie) appearing in the current page and show information related to such entities (e.g., local theaters playing the movie). These new experiences come with privacy concerns as they can send sensitive on-screen data (bank details, medical data, etc.) to the cloud. We propose a novel approach that efficiently extracts app content semantics on the device, without exfiltrating user data. Our solution consists of two phases: an offline, user-agnostic, in-cloud phase that automatically annotates apps' UI elements with stable semantics, and a lightweight on-device phase that assigns semantics to captured app contents on the fly, by matching the annotations. With this automatic approach we annotated 100+ food, dining, and music apps, with accuracy over 80%. Our system implementation for Android and Windows Phone---Appstract---incurs minimal runtime overhead. We built eight use cases on the Appstract framework.

We present new applications for cryptographic secret handshakes between mobile devices on top of Bluetooth Low-Energy (LE). Secret handshakes enable mutual authentication, with the property that the parties learn nothing about each other unless they have been both issued credentials by a group administrator. This property provides strong privacy guarantees that enable interesting applications. One of them is proximity-based discovery for private communities. We introduce MASHaBLE, a mobile application that enables participants to discover and interact with nearby users if and only if they belong to the same secret community. We use direct peer-to-peer communication over Bluetooth LE, rather than relying on a central server. We discuss the specifics of implementing secret handshakes over Bluetooth LE and present our prototype implementation.

Web deep links are instrumental to many fundamental user experiences such as navigating to one web page from another, bookmarking a page, or sharing it with others. Such experiences are not possible with individual pages inside mobile apps, since historically mobile apps did not have links equivalent to web deep links. Mobile deep links, introduced in recent years, still lack many important properties of web deep links. Unlike web links, mobile deep links need significant developer effort, cover a small number of predefined pages, and are defined statically to navigate to a page for a given link, but not to dynamically generate a link for a given page. We propose uLink, a novel deep linking mechanism that addresses these problems. uLink is implemented as an application library, which transparently tracks data- and UI-event-dependencies of app pages, and encodes the information in links to the pages; when a link is invoked, the information is utilized to recreate the target page quickly and accurately. uLink also employs techniques, based on static and dynamic analysis of the app, that can provide feedback to users about whether a link may break in the future due to, e.g., modifications of external resources such as a file the link depends on. We have implemented uLink on Android. Our evaluation with 34 (of 1000 most downloaded) Android apps shows that compared to existing mobile deep links, uLink requires minimal developer effort, achieves significantly higher coverage, and can provide accurate user feedback on a broken link.

Developers deploying web applications in the cloud often need to determine how changes such as service tiers or runtime loads may affect user-perceived page load time. We devise and evaluate a systematic methodology for exploring such "what-if" questions at the time a web application is deployed. Given a website, a web request, and “whatif” scenario, with a hypothetical configuration and runtime condition, our methodology, embedded in a system called WebPerf, can estimate a distribution of end-to-end response times for the request under the “what-if” scenario. WebPerf makes three contributions: (1) automated instrumentation of web sites written with increasingly popular task parallel libraries, to capture causal call dependencies of various computation and asynchronous I/O calls; (2) an algorithm to use the call dependencies, together with online- and offlineprofiled models of various I/O calls to estimate a distribution of end-to-end latency of the request; and (3) an algorithm to optimize modeling errors by deciding how many measurements to take within a limited time. We have implemented WebPerf for Microsoft Azure. Our experiments with five real websites and seven scenarios show that the median error of WebPerf’s estimation is within 7% for all applications and scenarios.

Microblogging services have become among the most popular services on the web in the last few years. This led to significant increase in data size, speed, and applications. This paper presentsVenus; a system that supports real-time spatial queries on microblogs.Venussupports its queries on a spatial boundary$R$and a temporal boundary$T$, from which only the top-$k$microblogs are returned in the query answer based on a spatio-temporal ranking function. Supporting such queries requiresVenusto digest hundreds of millions of real-time microblogs in main-memory with high rates, yet, it provides low query responses and efficient memory utilization. To this end,Venusemploys: (1) an efficient in-memory spatio-temporal index that digests high rates of incoming microblogs in real time, (2) a scalable query processor that prune the search space,$R$and$T$, effectively to provide low query latency on millions of items in real time, and (3) a group of memory optimization techniques that provide system administrators with different options to save significant memory resources while keeping the query accuracy almost perfect.Venusmemory optimization techniques make use of the local arrival rates of microblogs to smartly shed microblogs that are old enough not to contribute to any query answer. In addition,Venuscan adaptively, in real time, adjust its load shedding based on both the spatial distribution and the parameters of incoming query loads. AllVenuscomponents can accommodate different spatial and temporal ranking functions that are able to capture the importance of each dimension differently depending on the applications requirements. Extensive experimental results based on real Twitter data and actual locations of Bing search queries show thatVenussupports high arrival rates of up to 64 K microblogs/second and average query latency of 4 msec.

In a modern web application, a single high-level action like a mouse click triggers a flurry of asynchronous events on the client browser and remote web servers. We introduce Domino, a new tool which automatically captures and analyzes end-to-end, asynchronous causal relationship of events that span clients and servers. Using Domino, we found uncharacteristically long event chains in Bing Maps, discovered data races in the WinJS implementation of promises, and developed a new server-side scheduling algorithm for reducing the tail latency of server responses.

This paper presents experiences with eNav, a smartphone-based vehicular GPS navigation system that has an energy-saving location sensing mode capable of drastically reducing navigation energy needs. Traditional navigation systems sample the phone's GPS at a fixed rate (usually around 1Hz), regardless of factors such as current vehicle speed and distance from the next navigation waypoint. This practice results in a large energy consumption and unnecessarily reduces the attainable length of a navigation session, if the phone is left unplugged. The paper investigates two questions. First, would drivers be willing to sacrifice some of the affordances of modern navigation systems in order to prolong battery life? Second, how much energy could be saved using straightforward alternative localization mechanisms, applied to complement GPS for vehicular navigation? According to a survey we conducted of 500 drivers, as much as 91% of drivers said they would like to have a vehicular navigation application with an energy saving mode. To meet this need, eNav exploits on-board accelerometers for approximate location sensing when the vehicle is sufficiently far from the next navigation waypoint (or is stopped). A user test-study of eNav shows that it results in roughly the same user experience as standard GPS navigation systems, while reducing navigation energy consumption by almost 80%. We conclude that drivers find an energy-saving mode on phone-based vehicular navigation applications desirable, even at the expense of some loss of functionality, and that significant savings can be achieved using straightforward location sensing mechanisms that avoid frequent GPS sampling.

Advertising is the primary source of revenue for many mobile apps. One important goal of the ad delivery process is targeting users, based on criteria like users' geolocation, context, demographics, long-term behavior, etc. In this paper we report an in-depth study that broadly characterizes what targeting information mobile apps send to ad networks and how effectively, if at all, ad networks utilize the information for targeting users. Our study is based on a novel tool, called MadScope, that can (1) quickly harvest ads from a large collection of apps, (2) systematically probe an ad network to characterize its targeting mechanism, and (3) emulate user profiles of specific preferences and interests to study behavioral targeting. Our analysis of 500K ad requests from 150K Android apps and 101 ad networks indicates that apps do not yet exploit the full potential of targeting: even though ad controls provide APIs to send a lot of information to ad networks, much key targeting information is optional and is often not provided by app developers. We also use MadScope to systematically probe top 10 in-app ad networks to harvest over 1 million ads and find that while targeting is used by many of the top networks, there remain many instances where targeting information or behavioral profile does not have a statistically significant impact on how ads are chosen. We also contrast our findings with a recent study of targeted in-browser ads.

Mars demonstration exploits the microblogs location information to support a wide variety of important spatio-temporal queries on microblogs. Supported queries include range, nearest-neighbor, and aggregate queries. Mars works under a challenging environment where streams of microblogs are arriving with high arrival rates. Mars distinguishes itself with three novel contributions: (1) Efficient in-memory digestion/expiration techniques that can handle microblogs of high arrival rates up to 64,000 microblog/sec. This also includes highly accurate and efficient hopping-window based aggregation for incoming microblogs keywords. (2) Smart memory optimization and load shedding techniques that adjust in-memory contents based on the expected query load to trade off a significant storage savings with a slight and bounded accuracy loss. (3) Scalable real-time query processing, exploiting Zipf distributed microblogs data for efficient top-k aggregate query processing. In addition, Mars employs a scalable real-time nearest neighbor and range query processing module that employs various pruning techniques so that it serves heavy query workloads in real time. Mars is demonstrated using a stream of real tweets obtained from Twitter firehose with a production query workload obtained from Bing web search. We show that Mars serves incoming queries with an average latency of less than 4 msec and with 99% answer accuracy while saving up to 70% of storage overhead for different query loads.

This paper presents Mercury; a system for real-time support of top-k spatio-temporal queries on microblogs, where users are able to browse recent microblogs near their locations. With high arrival rates of microblogs, Mercury ensures real-time query response within a tight memory-constrained environment. Mercury bounds its search space to include only those microblogs that have arrived within certain spatial and temporal boundaries, in which only the top-k microblogs, according to a spatio-temporal ranking function, are returned in the search results. Mercury employs: (a) a scalable dynamic in-memory index structure that is capable of digesting all incoming microblogs, (b) an efficient query processor that exploits the in-memory index through spatio-temporal pruning techniques that reduce the number of visited microblogs to return the final answer, (c) an index size tuning module that dynamically finds and adjusts the minimum index size to ensure that incoming queries will be answered accurately, and (d) a load shedding technique that trades slight decrease in query accuracy for significant storage savings. Extensive experimental results based on a real-time Twitter Firehose feed and actual locations of Bing search queries show that Mercury supports high arrival rates of up to 64K microblogs/second and average query latency of 4 msec.

Mobile app ecosystems have experienced tremendous growth in the last six years. This has triggered research on dynamic analysis of performance, security, and correctness properties of the mobile apps in the ecosystem. Exploration of app execution using automated UI actions has emerged as an important tool for this research. However, existing research has largely developed analysis-specific UI automation techniques, wherein the logic for exploring app execution is intertwined with the logic for analyzing app properties. PUMA is a programmable framework that separates these two concerns. It contains a generic UI automation capability (often called a Monkey) that exposes high-level events for which users can define handlers. These handlers can flexibly direct the Monkey's exploration, and also specify app instrumentation for collecting dynamic state information or for triggering changes in the environment during app execution. Targeted towards operators of app marketplaces, PUMA incorporates mechanisms for scaling dynamic analysis to thousands of apps. We demonstrate the capabilities of PUMA by analyzing seven distinct performance, security, and correctness properties for 3,600 apps downloaded from the Google Play store.

This paper describes the design, implementation, and evaluation of VanarSena, an automated fault finder for mobile applications (``apps''). The techniques in VanarSena are driven by a study of 25 million real-world crash reports of Windows Phone apps reported in 2012. Our analysis indicates that a modest number of root causes are responsible for many observed failures, but that they occur in a wide range of places in an app, requiring a wide coverage of possible execution paths. VanarSena adopts a ``greybox'' testing method, instrumenting the app binary to achieve both coverage and speed. VanarSena runs on cloud servers: the developer uploads the app binary; VanarSena then runs several app ``monkeys'' in parallel to emulate user, network, and sensor data behavior, returning a detailed report of crashes and failures. We have tested VanarSena with 3000 apps from the Windows Phone store, finding that 1108 of them had failures; VanarSena uncovered 2969 distinct bugs in existing apps, including 1227 that were not previously reported. Because we anticipate VanarSena being used in regular regression tests, testing speed is important. VanarSena uses two techniques to improve speed. First, it uses a ``hit testing'' method to quickly emulate an app by identifying which user interface controls map to the same execution handlers in the code. Second, it generates a ProcessingCompleted event to accurately determine when to start the next interaction. These features are key benefits of VanarSena's greybox philosophy.

Mobile app marketplaces are dominated by free apps that rely on advertising for their revenue. These apps place increased demands on the already limited battery lifetime of modern phones. For example, in the top 15 free Windows Phone apps, we found in-app advertising contributes to 65% of the app's total communication energy (or 23% of the app's total energy). Despite their small size, downloading ads each time an app is started and at regular refresh intervals forces the network radio to be continuously woken up, thus leading to a high energy overhead, so-called 'tail energy' problem. A straightforward mechanism to lower this overhead is to prefetch ads in bulk and serve them locally. However, the prefetching of ads is at odds with the real-time nature of modern advertising systems wherein ads are sold through real-time auctions each time the client can display an ad.

Outsourcing data streams and desired computations to a third party such as the cloud is a desirable option to many companies. However, data outsourcing and remote computations intrinsically raise issues of trust, making it crucial to verify results returned by third parties. In this context, we propose a novel solution to verify outsourced grouped aggregation queries (e.g., histogram or SQL Group-by queries) that are common in many business applications. We consider a setting where a data owner employs an untrusted remote server to run continuous grouped aggregation queries on a data stream it forwards to the server. Untrusted clients then query the server for results and efficiently verify correctness of the results by using a small and easy-to-compute signature provided by the data owner. Our work complements previous works on authenticating remote computation of selection and aggregation queries. The most important aspect of our solution is that it is publicly verifiable - unlike most prior works, we support untrusted clients (who can collude with other clients or with the server). Experimental results on real and synthetic data show that our solution is practical and efficient.

A recent study showed that while US consumers spent 30% more time on mobile apps than on traditional web, advertisers spent 1600% less money on mobile ads. One key reason is that unlike most web ad providers, today's mobile ads are not contextual---they do not take into account the content of the page they are displayed on. Thus, most mobile ads are irrelevant to what the user is interested in. For example, it is not uncommon to see gambling ads being displayed in a Bible app. This irrelevance results in low clickthrough rates, and hence advertisers shy away from the mobile platform. Using data from top 1200 apps in Windows Phone marketplace, and a one-week trace of ad keywords from Microsoft's ad network, we show that content displayed by mobile apps is a potential goldmine of keywords that advertisers are interested in.

In feed-following applications such as Twitter and Facebook, users (consumers) follow a large number of other users (producers) to get personalized feeds, generated by blending producers- feeds. With the proliferation of Cloud-connected smart edge devices such as smartphones, producers and consumers of many feed-following applications reside on edge devices and the Cloud. An important design goal of such applications is to minimize communication (and energy) overhead of edge devices. In this paper, we abstract distributed feed-following applications as a view maintenance problem, with the goal of optimally placing the views on edge devices and in the Cloud to minimize communication overhead between edge devices and the Cloud. The view placement problem for general network topology is NP Hard; however, we show that for the special case of Cloud-edge topology, locally optimal solutions yield a globally optimal view placement solution. Based on this powerful result, we propose view placement algorithms that are highly efficient, yet provably minimize global network cost. Compared to existing works on feed-following applications, our algorithms are more general--they support views with selection, projection, correlation (join) and arbitrary black-box operators, and can even refer to other views. We have implemented our algorithms within a distributed feed-following architecture over real smartphones and the Cloud. Experiments over real datasets indicate that our algorithms are highly scalable and orders-of-magnitude more efficient than existing strategies for optimal placement. Further, our results show that optimal placements generated by our algorithms are often several factors better than simpler schemes.

We propose an acquisitional context engine (ACE), a middleware that supports continuous context-aware applications while mitigating sensing costs for inferring contexts. The ACE provides user's current context to applications running on it. In addition, it dynamically learns relationships among various context attributes (e.g., whenever the user is Driving, he is not AtHome). The ACE exploits these automatically learned relationships for two powerful optimizations. The first is inference caching that allows the ACE to opportunistically infer one context attribute (AtHome) from another already-known attribute (Driving), without acquiring any sensor data. The second optimization is speculative sensing that enables the ACE to occasionally infer the value of an expensive attribute (e.g., AtHome) by sensing cheaper attributes (e.g., Driving). Our experiments with two real context traces of 105 people and a Windows Phone prototype show that the ACE can reduce sensing costs of three context-aware applications by about 4.2 times, compared to a raw sensor data cache shared across applications, with a very small memory and processing overhead.

Mobile advertising is an increasingly important driver in the Internet economy. We point out fundamental trade-offs between important variables in the mobile advertisement ecosystem. In order to increase relevance, ad campaigns tend to become more targeted and personalized by using context information extracted from user's interactions and smartphone's sensors. This raises privacy concerns that are hard to overcome due to the limited resources (energy and bandwidth) available on the phones. We point out that in the absence of a trusted third party, it is impossible to maximize these three variables - ad relevance, privacy, and efficiency - in a single system. This leads to the natural question: can we formalize a common framework for personalized ad delivery that can be instantiated to any desired trade-off point? We propose such a flexible ad-delivery framework where personalization is done jointly by the server and the phone. We show that the underlying optimization problem is NP-hard and present an efficient algorithm with a tight approximation guarantee.

We propose ACE (Acquisitional Context Engine), a middleware that supports continuous context-aware applications while mitigating sensing costs for inferring contexts. ACE provides user's current context to applications running on it. In addition, it dynamically learns relationships among various context attributes (e.g., whenever the user is Driving, he is not AtHome). ACE exploits these automatically learned relationships for two powerful optimizations. The first is inference caching that allows ACE to opportunistically infer one context attribute (AtHome) from another already-known attribute (Driving), without acquiring any sensor data. The second optimization is speculative sensing that enables ACE to occasionally infer the value of an expensive attribute (e.g., AtHome) by sensing cheaper attributes (e.g., Driving). Our experiments with two real context traces of 105 people and a Windows Phone prototype show that ACE can reduce sensing costs of three context-aware applications by about 4.2x, compared to a raw sensor data cache shared across applications, with a very small memory and processing overhead.

The Cloud-Edge topology - where multiple smart edge devices such as phones are connected to one another via the Cloud - is becoming ubiquitous. We demonstrate RACE, a novel framework and system for specifying and efficiently executing distributed real-time applications in the Cloud-Edge topology. RACE uses LINQ for StreamInsight to succinctly express a diverse suite of useful real-time applications. Further, it exploits the processing power of edge devices and the Cloud to partition and execute such queries in a distributed manner. RACE features a novel cost-based optimizer that efficiently finds the optimal placement, minimizing global communication cost while handling multi-level join queries and asymmetric network links.

The rise of smartphones equipped with various sensors has enabled personalization of various applications based on user contexts extracted from sensor readings. At the same time it has raised serious concerns about the privacy of user contexts.

Efficient thermal management is important in modern data centers as cooling consumes up to 50% of the total energy. Unlike previous work, we consider proactive thermal management, whereby servers can predict potential overheating events due to dynamics in data center configuration and workload, giving operators enough time to react. However, such forecasting is very challenging due to data center scales and complexity. Moreover, such a physical system is influenced by cyber effects, including workload scheduling in servers. We propose ThermoCast, a novel thermal forecasting model to predict the temperatures surrounding the servers in a data center, based on continuous streams of temperature and airflow measurements. Our approach is (a) capable of capturing cyberphysical interactions and automatically learning them from data; (b) computationally and physically scalable to data center scales; (c) able to provide online prediction with real-time sensor measurements. The paper's main contributions are: (i) We provide a systematic approach to integrate physical laws and sensor observations in a data center; (ii) We provide an algorithm that uses sensor data to learn the parameters of a data center's cyber-physical system. In turn, this ability enables us to reduce model complexity compared to full-fledged fluid dynamics models, while maintaining forecast accuracy; (iii) Unlike previous simulation-based studies, we perform experiments in a production data center. Using real data traces, we show that ThermoCast forecasts temperature better than a machine learning approach solely driven by data, and can successfully predict thermal alarms 4.2 minutes ahead of time.

We present Fuzzy Prophet, a probabilistic database tool for constructing, simulating and analyzing business scenarios with uncertain data. Fuzzy Prophet takes externally defined probability distribution (so called VG-Functions) and a declarative description of a target scenario, and performs Monte Carlo simulation to compute probability distribution of the scenario's outcomes. In addition, Fuzzy Prophet supports parameter optimization,where probabilistic models are parameterized and a large parameter space must be explored to find parameters that optimize or achieve a desired goal. Fuzzy Prophet's key innovation is to use 'fingerprints' that can identify parameter values producing correlated outputs of a user-provided stochastic function and to reuse computations across such values. Fingerprints significantly expedite the process of parameter exploration in offline optimization and interactive what-if exploration tasks.

Probabilistic databases, in particular ones that allow users to externally define models or probability distributions – so called VG-Functions – are an ideal tool for constructing, simulating and analyzing hypothetical business scenarios. Enterprises often use such tools with parameterized models and need to explore a large parameter space in order to discover parameter values that optimize for a given goal. Parameter space is usually very large, making such exploration extremely expensive. We present Jigsaw, a probabilistic database-based simulation framework that addresses this performance problem. In Jigsaw, users define what-if style scenarios as parameterized probabilistic database queries and identify parameter values that achieve desired properties. Jigsaw uses a novel “fingerprinting” technique that efficiently identifies correlations between a query’s output distribution for different parameter values. Using fingerprints, Jigsaw is able to reuse work performed for different parameter values, and obtain speedups of as much as 2 orders of magnitude for several real business scenarios.

A surprising query result is often an indication of errors in the query or the underlying data. Recent work suggests using causal reasoning to find explanations for the surprising result. In practice, however, one often has multiple queries and/or multiple answers, some of which may be considered correct and others unexpected. In this paper, we focus on determining the causes of a set of unexpected results, possibly conditioned on some prior knowledge of the correctness of another set of results. We call this problem View-Conditioned Causality. We adapt the definitions of causality and responsibility for the case of multiple answers/views and provide a non-trivial algorithm that reduces the problem of finding causes and their responsibility to a satisfiability problem that can be solved with existing tools. We evaluate both the accuracy and effectiveness of our approach on a real dataset of user-generated mobile device tracking data, and demonstrate that it can identify causes of error more effectively than static Boolean influence and alternative notions of causality.

Shared sensing infrastructures that allow multiple applications to share deployed sensors are emerging and Internet protocol based access for such sensors has already been prototyped and deployed. As a large number of applications start accessing shared sensors, the efficiency of resource usage at the embedded nodes and in the network infrastructure supporting them becomes a concern. To address this, we develop methods that detect when common data and common stream processing is requested by multiple applications, including cases where only some of the data is shared or only intermediate processing steps are common. The communication and processing is then modified to eliminate the redundancies. Specifically, we use an interval-cover graph to minimize communication redundancies and a joint data flow graph optimization to remove computational redundancies. Both methods operate online and allow application requests to be dynamically added or removed. The proposed methods are evaluated using applications on a road traffic sensing infrastructure.

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.

Online aggregation is a promising solution to achieving fast early responses for interactive ad-hoc queries that compute aggregates on a large amount of data. Essential to the success of online aggregation is a good non-blocking join algorithm that enables both (i) high early result rates with statistical guarantees and (ii) fast end-to-end query times. We analyze existing non-blocking join algorithms and find that they all provide sub-optimal early result rates, and those with fast end-to-end times achieve them only by further sacrificing their early result rates.

We consider the problem of computing all-pair correlations in a warehouse containing a large number (e.g., tens of thousands) of time-series (or, signals). The problem arises in automatic discovery of patterns and anomalies in data intensive applications such as data center management, environmental monitoring, and scientific experiments. However, with existing techniques, solving the problem for a large stream warehouse is extremely expensive, due to the problem's inherent quadratic I/O and CPU complexities.

We propose the first differentially private aggregation algorithm for distributed time-series data that offers good practical utility without any trusted server. This addresses two important challenges in participatory data-mining applications where (i) individual users collect temporally correlated time-series data (such as location traces, web history, personal health data), and (ii) an untrusted third-party aggregator wishes to run aggregate queries on the data.

Contemporary datacenters house tens of thousands of servers. The servers are closely monitored for operating conditions and utilizations by collecting their performance data (e.g., CPU utilization). In this paper, we show that existing database and file-system solutions are not suitable for warehousing performance data collected from a large number of servers because of the scale and the complexity of performance data. We describe the design and implementation of DataGarage, a performance data warehousing system that we have developed at Microsoft. DataGarage is a hybrid solution that combines benefits of DBMSs, file-systems, and MapReduce systems to address unique challenges of warehousing performance data. We describe how DataGarage allows efficient storage and analysis of years of historical performance data collected from many tens of thousands of servers---on commodity servers. We also report DataGarage's performance with a real dataset and a 32-node, 256-core shared-nothing cluster and our experience of using DataGarage at Microsoft for the last one year.

A sensor network data gathering and visualization infrastructure is demonstrated, comprising of global sensor networks (GSN) middleware and Microsoft SensorMap. Users are invited to actively participate in the process of monitoring real-world deployments and can inspect measured data in the form of contour plots overlayed onto a high resolution map and a digital topographic model. Users can go back in time virtually to search for interesting events or simply to visualize the temporal dependencies of the data. The system presented is not only interesting and visually enticing for non-expert users but brings substantial benefits to environmental scientists. The easily installed data acquisition component as well as the powerful data sharing and visualization platform opens up new ground in collaborative data gathering and interpretation in the spirit of Web 2.0 applications.

We consider the problem of collectively approximating a set of sensor signals using the least amount of space so that any individual signal can be efficiently reconstructed within a given maximum (L∞) error ε. The problem arises naturally in applications that need to collect large amounts of data from multiple concurrent sources, such as sensors, servers and network routers, and archive them over a long period of time for offline data mining. We present GAMPS, a general framework that addresses this problem by combining several novel techniques. First, it dynamically groups multiple signals together so that signals within each group are correlated and can be maximally compressed jointly. Second, it appropriately scales the amplitudes of different signals within a group and compresses them within the maximum allowed reconstruction error bound. Our schemes are polynomial time O(α, β approximation schemes, meaning that the maximum (L∞) error is at most α ε and it uses at most β times the optimal memory. Finally, GAMPS maintains an index so that various queries can be issued directly on compressed data. Our experiments on several real-world sensor datasets show that GAMPS significantly reduces space without compromising the quality of search and query.

We consider the Outsourced Aggregation model, where sensing services outsource their sensor data collection and aggregation tasks to third-party service providers called aggregators. As aggregators can be untrusted or compromised, it is essential for a sensing service to be able to verify the correctness of aggregation results. This work presents SECOA, a framework with a family of novel and optimally-secure protocols for secure outsourced aggregation. Our framework is based on a unified use of one-way chains. It supports a large and diverse set of aggregate functions, can have multiple hierarchically organized aggregators, can deterministically detect any malicious aggregation behavior without communication with sensors, and incurs a small and workload-independent communication load on sensors. We also present extensive evaluation results to demonstrate the feasibility of our framework.

We present Cypress, a novel framework to archive and query massive time series streams such as those generated by sensor networks, data centers, and scientific computing. Cypress applies multi-scale analysis to decompose time series and to obtain sparse representations in various domains (e.g. frequency domain and time domain). Relying on the sparsity, the time series streams can be archived with reduced storage space. We then show that many statistical queries such as trend, histogram and correlations can be answered directly from compressed data rather than from reconstructed raw data. Our evaluation with server utilization data collected from real data centers shows significant benefit of our framework.

We present SenseWeb, an open and scalable infrastructure for sharing and geocentric exploration of sensor data streams. SenseWeb allows sensor owners to share data streams across multiple applications and users, thus amortizing sensor deployment costs effectively. It also provides mechanisms to transparently index and cache data, to process spatio-temporal queries on real-time and historic data, and to aggregate and present results on a geocentric web interface. In this paper, we present the architecture of SenseWeb, its techniques to enable global sharing of heterogeneous sensors, and its mapbased front-end for spatio-temporal data exploration. We enable interactive geocentric data exploration in the mapbased front-end using techniques for rapidly changing map overlaid visualizations of numerous data streams. We also demonstrate flexibility and scalability of the architecture by evaluating a deployed prototype of SenseWeb, which has been publicly available since March 2008.

We present COLR-Tree, an abstraction layer designed to support efficient spatio-temporal queries on live data gathered from a large collection of sensors. We use COLR-Tree in a publicly-available sensor web portal to separate the concerns of sensor data management from the web portal application. COLR-Tree uses two techniques to optimize end-to-end latencies of users' queries by minimizing expensive data collection from sensors. First, it uses a novel technique to effectively cache aggregate results computed over sensor data with different expiry times. Second, it incorporates an efficient one-pass sampling algorithm with its range lookup to utilize cached data and compensate for occasional unavailability of sensors. We evaluate our implementation of COLR-Tree on SQL Server 2005 with a real, large workload from Windows Live Local. Our experiments demonstrate that COLR-Tree significantly improves both the end-to-end query performance and the number of sensors accessed compared to existing techniques.

Recent advances in flash media have made it an attractive alternative for data storage in a wide spectrum of computing devices, such as embedded sensors, mobile phones, PDA's, laptops, and even servers. However, flash media has many unique characteristics that make existing data management/analytics algorithms designed for magnetic disks perform poorly with flash storage. For example, while random (page) reads are as fast as sequential reads, random (page) writes and in-place data updates are orders of magnitude slower than sequential writes. In this paper, we consider an important fundamental problem that would seem to be particularly challenging for flash storage: efficiently maintaining a very large (100 MBs or more) random sample of a data stream (e.g., of sensor readings). First, we show that previous algorithms such as reservoir sampling and geometric file are not readily adapted to flash. Second, we propose B-FILE, an energy-efficient abstraction for flash media to store self-expiring items, and show how a B-FILE can be used to efficiently maintain a large sample in flash. Our solution is simple, has a small (RAM) memory footprint, and is designed to cope with flash constraints in order to reduce latency and energy consumption. Third, we provide techniques to maintain biased samples with a B-FILE and to query the large sample stored in a B-FILE for a subsample of an arbitrary size. Finally, we present an evaluation with flash media that shows our techniques are several orders of magnitude faster and more energy-efficient than (flash-friendly versions of) reservoir sampling and geometric file. A key finding of our study, of potential use to many flash algorithms beyond sampling, is that "semi-random" writes (as defined in the paper) on flash cards are over two orders of magnitude faster and more energy-efficient than random writes.

Previous approaches for computing duplicate-sensitive aggregates in wireless sensor networks have used a tree topology, in order to conserve energy and to avoid double-counting sensor readings. However, a tree topology is not robust against node and communication failures, which are common in sensor networks. In this article, we present synopsis diffusion , a general framework for achieving significantly more accurate and reliable answers by combining energy-efficient multipath routing schemes with techniques that avoid double-counting. Synopsis diffusion avoids double-counting through the use of order- and duplicate-insensitive (ODI) synopses that compactly summarize intermediate results during in-network aggregation. We provide a surprisingly simple test that makes it easy to check the correctness of an ODI synopsis. We show that the properties of ODI synopses and synopsis diffusion create implicit acknowledgments of packet delivery. Such acknowledgments enable energy-efficient adaptation of message routes to dynamic message loss conditions, even in the presence of asymmetric links. Finally, we illustrate using extensive simulations the significant robustness, accuracy, and energy-efficiency improvements of synopsis diffusion over previous approaches.

Geographic routing is a useful and scalable point-to-point communication primitive for wireless sensor networks. However, previous work on geographic routing makes the unrealistic assumption that all the nodes in the network are awake during routing. This overlooks the common deployment scenario where sensor nodes are duty-cycled to save energy. In this paper we investigate several important aspects of geographic routing over duty-cycled nodes. First, we extend existing geographic routing algorithms to handle the highly dynamic networks resulting from duty-cycling. Second, we provide the first formal analysis of the performance of geographic routing on duty-cycled nodes. Third, we use this analysis to develop an efficient decentralized sleep scheduling algorithm for reducing the number of awake nodes while maintaining both network coverage and a (tunable) target routing latency. Finally, we evaluate via simulation the performance of our approach versus running existing geographic routing algorithms on sensors duty-cycled according to previous sleep scheduling algorithms. Our results show, perhaps surprisingly, that a network of duty-cycled nodes can have slightly better routing performance than a static network that uses comparable energy. Our results further show that, compared to previous algorithms, our sleep scheduling algorithm significantly improves routing latency and network lifetime.

FlashDB is a self-tuning database optimized for sensor networks using NAND flash storage. In practical systems flash is used in different packages such as on-board flash chips, compact flash cards, secure digital cards and related formats. Our experiments reveal non-trivial differences in their access costs. Furthermore, databases may be subject to different types of workloads. We show that existing databases for flash are not optimized for all types of flash devices or for all workloads and their performance is thus suboptimal in many practical systems. FlashDB uses a novel self-tuning index that dynamically adapts its storage structure to workload and underlying storage device. We formalize the self-tuning nature of an index as a two-state task system and propose a 3-competitive online algorithm that achieves the theoretical optimum. We also provide a framework to determine the optimal size of an index node that minimizes energy and latency for a given device. Finally, we propose optimizations to further improve the performance of our index. We prototype and compare different indexing schemes on multiple flash devices and workloads, and show that our indexing scheme outperforms existing schemes under all workloads and flash devices we consider.

No abstract available.

Most current sensor network research explores the use of extremely simple sensors on small devices called motes and focuses on over-coming the resource constraints of these devices. In contrast, our research explores the challenges of multimedia sensors and is motivated by the fact that multimedia devices, such as cameras, are rapidly becoming inexpensive, yet their use in a sensor network presents a number of unique challenges. For example, the data rates involved with multimedia sensors are orders of magnitude greater than those for sensor motes and this data cannot easily be processed by traditional sensor network techniques that focus on scalar data. In addition, the richness of the data generated by multimedia sensors makes them useful for a wide variety of applications. This paper presents an overview of IRISNET, a sensor network architecture that enables the creation of a planetary-scale infrastructure of multimedia sensors that can be shared by a large number of applications. To ensure the efficient collection of sensor readings, IRISNET enables the application-specific processing of sensor feeds on the significant computation resources that are typically attached to multimedia sensors. IRISNET enables the storage of sensor readings close to their source by providing a convenient and extensible distributed XML database infrastructure. Finally, IRISNET provides a number of multimedia processing primitives that enable the effective processing of sensor feeds in-network and at-sensor.

Existing energy-efficient approaches to in-network aggregation in sensor networks can be classified into two categories, tree-based and multi-path-based, with each having unique strengths and weaknesses. In this paper, we introduce Tributary-Delta, a novel approach that combines the advantages of the tree and multi-path approaches by running them simultaneously in different regions of the network. We present schemes for adjusting the regions in response to changes in network conditions, and show how many useful aggregates can be readily computed within this new framework. We then show how a difficult aggregate for this context---finding frequent items---can be efficiently computed within the framework. To this end, we devise the first algorithm for frequent items (and for quantiles) that provably minimizes the worst case total communication for non-regular trees. In addition, we give a multi-path algorithm for frequent items that is considerably more accurate than previous approaches. These algorithms form the basis for our efficient Tributary-Delta frequent items algorithm. Through extensive simulation with real-world and synthetic data, we show the significant advantages of our techniques. For example, in computing Count under realistic loss rates, our techniques reduce answer error by up to a factor of 3 compared to any previous technique.

Previous approaches for computing duplicate-sensitive aggregates in sensor networks (e.g., in TAG) have used a tree topology, in order to conserve energy and to avoid double-counting sensor readings. However, a tree topology is not robust against node and communication failures, which are common in sensor networks. In this paper, we present synopsis diffusion, a general framework for achieving signi.cantly more accurate and reliable answers by combining energy-efficient multi-path routing schemes with techniques that avoid double-counting. Synopsis diffusion avoids double-counting through the use of order- and duplicate-insensitive (ODI) synopses that compactly summarize intermediate results during in-network aggregation. We provide a surprisingly simple test that makes it easy to check the correctness of an ODI synopsis. We show that the properties of ODI synopses and synopsis di.usion create implicit acknowledgments of packet delivery. We show that this property can, in turn, enable the system to adapt message routing to dynamic message loss conditions, even in the presence of asymmetric links. Finally, we illustrate, using extensive simulations, the significant robustness, accuracy, and energy-efficiency improvements of synopsis diffusion over previous approaches.

Webcams, microphones, pressure gauges and other sensors provide exciting new opportunities for querying and monitoring the physical world. In this paper we focus on querying wide area sensor databases, containing (XML) data derived from sensors spread over tens to thousands of miles. We present the first scalable system for executing XPATH queries on such databases. The system maintains the logical view of the data as a single XML document, while physically the data is fragmented across any number of host nodes. For scalability, sensor data is stored close to the sensors, but can be cached elsewhere as dictated by the queries. Our design enables self starting distributed queries that jump directly to the lowest common ancestor of the query result, dramatically reducing query response times. We present a novel query-evaluate gather technique (using XSLT) for detecting (1) which data in a local database fragment is part of the query result, and (2) how to gather the missing parts. We define partitioning and cache invariants that ensure that even partial matches on cached data are exploited and that correct answers are returned, despite our dynamic query-driven caching. Experimental results demonstrate that our techniques dramatically increase query throughputs and decrease query response times in wide area sensor databases.

No abstract available.