We describe and evaluate two methods for device pose classification and walking speed estimation that generalize well to new users, compared to previous work. These machine learning based methods are designed for the general case of a person holding a mobile device in an unknown location and require only a single low-cost, low-power sensor: a triaxial accelerometer. We evaluate our methods in straight-path indoor walking experiments as well as in natural indoor walking settings. Experiments with 14 human participants to test user generalization show that our pose classifier correctly selects among four device poses with 94% accuracy compared to 82% for previous work, and our walking speed estimates are within 12-15% (straight/indoor walk) of ground truth compared to 17-22% for previous work. Implementation on a mobile phone demonstrates that both methods can run efficiently online.

Current mobile devices continuously estimate their locations, allowing users to “check in”, find nearby friends and interests, and determine routes to their destinations. While underlying satellite, cell, and WiFi-based positioning systems can return an accurate and meaningful position in many cases, extending them to work energy-efficiently, particularly indoors, remains an open problem. In this work, we study energy-efficient and robust human-scale motion classifiers and their use in room-grain, collaborative indoor positioning systems. Previous work on improving energy-efficiency in positioning systems has assumed sensor input from an energy-cheaper alternative: using an accelerometer in lieu of GPS, for example. Unfortunately, even these alternative sensors are not practical for everyday use because of their own energy consumption, at least when sampled continuously. After studying what accelerometer sampling rates are feasible, we compare six methods for motion classification, two of which are new. We find that the existing simple statistical methods are not sufficiently robust with respect to different kinds of movement and different users, because the thresholds between movement and non-movement are too tight. In contrast we find that the two new, more sophisticated models, one based on Page-Hinkley statistics, and the other inspired by the Discrete Fourier Transform, provide a clearer differentiation between the two states. Only the Page-Hinkley-based one is as energy-efficient as the simple statistical methods, however. Through a WiFi geolocation system that relies on motion detection, we show how the choice of the underlying motion classifier can have a significant impact on user-perceived performance.

Many indoor localization methods are based on the association of 802.11 wireless RF signals from wireless access points (WAPs) with location labels. An “organic” RF positioning system relies on regular users, not dedicated surveyors, to build the map of RF fingerprints to location labels. However, signal variation due to device heterogeneity may degrade localization performance. We analyze the diversity of those signal characteristics pertinent to indoor localization - signal strength and AP detection - as measured by a variety of 802.11 devices. We first analyze signal strength diversity, and show that pairwise linear transformation alone does not solve the problem. We propose kernel estimation with a wide kernel width to reduce the difference in probability estimates. We also investigate diversity in access point detection. We demonstrate that localization performance may degrade significantly when AP detection rate is used as a feature for localization, and correlate the loss of performance to a device dissimilarity measure captured by Kullback-Leibler divergence. Based on this analysis, we show that using only signal strength, without incorporating negative evidence, achieves good localization performance when devices are heterogeneous.

We describe the design, implementation, and evaluation of Molé, a mobile organic localization engine. Unlike previous work on crowd-sourced WiFi positioning, Mole uses a hierarchical name space. By not relying on a map and by being more strict than uninterpreted names for places, Molé aims for a more flexible and scalable point in the design space of localization systems. Molé employs several new techniques, including a new statistical positioning algorithm to differentiate between neighboring places, a motion detector to reduce update lag, and a scalable “cloud”-based fingerprint distribution system. Molé's localization algorithm, called Maximum Overlap (MAO), accounts for temporal variations in a place's fingerprint in a principled manner. It also allows for aggregation of fingerprints from many users and is compact enough for on-device storage. We show through end-to-end experiments in two deployments that MAO is significantly more accurate than state-of-the-art Bayesian-based localizers. We also show that non-experts can use Molé to quickly survey a building, enabling room-grained location-based services for themselves and others.

We demonstrate a method for collaborative ranking of future events. Previous work on recommender systems typically relies on feedback on a particular item, such as a movie, and generalizes this to other items or other people. In contrast, we examine a setting where no feedback exists on the particular item. Because direct feedback does not exist for events that have not taken place, we recommend them based on individuals' preferences for past events, combined collaboratively with other peoples' likes and dislikes. We examine the topic of unseen item recommendation through a user study of academic (scientific) talk recommendation, where we aim to correctly estimate a ranking function for each user, predicting which talks would be of most interest to them. Then by decomposing user parameters into shared and individual dimensions, we induce a similarity metric between users based on the degree to which they share these dimensions. We show that the collaborative ranking predictions of future events are more effective than pure content-based recommendation. Finally, to further reduce the need for explicit user feedback, we suggest an active learning approach for eliciting feedback and a method for incorporating available implicit user cues.

Most current methods for 802.11-based indoor localization depend on surveys conducted by experts or skilled technicians. Some recent systems have incorporated surveying by users. Structuring localization systems "organically," however, introduces its own set of challenges: conveying uncertainty, determining when user input is actually required, and discounting erroneous and stale data. Through deployment of an organic location system in our nine-story building, which contains nearly 1,400 distinct spaces, we evaluate new algorithms for addressing these challenges. We describe the use of Voronoi regions for conveying uncertainty and reasoning about gaps in coverage, and a clustering method for identifying potentially erroneous user data. Our algorithms facilitate rapid coverage while maintaining positioning accuracy comparable to that achievable with survey-driven indoor deployments.

Network coordinates provide a scalable way to estimate latencies among large numbers of hosts. While there are several algorithms for producing coordinates, none account for the fact that nodes observe a stream of distinct observations that may vary by as much as three orders-ofmagnitude. With such variable data, coordinate systems are prone to high error and instability in live deployments. In addition, dynamics such as triangle violations can lead to coordinate oscillations, producing further instability and making it difficult for applications to know when their coordinates have truly changed. Because simulation results demonstrate that network coordinates are capable of providing low cost and sufficiently accurate answers to common queries, it is vital that we develop the ability to obtain similar results in practice. We propose two filters which combined to improve network coordinate accuracy by 54% and coordinate stability by 96% when run on a real, largescale network.

To use their pool of resources efficiently, distributed stream-processing systems push query operators to nodes within the network. Currently, these operators, ranging from simple filters to custom business logic, are placed manually at intermediate nodes along the transmission path to meet application-specific performance goals. Determining placement locations is challenging because network and node conditions change over time and because streams may interact with each other, opening venues for reuse and repositioning of operators. This paper describes a stream-based overlay network (SBON), a layer between a stream-processing system and the physical network that manages operator placement for stream-processing systems. Our design is based on a cost space, an abstract representation of the network and on-going streams, which permits decentralized, large-scale multi-query optimization decisions. We present an evaluation of the SBON approach through simulation, experiments on PlanetLab, and an integration with Borealis, an existing stream-processing engine. Our results show that an SBON consistently improves network utilization, provides low stream latency, and enables dynamic optimization at low engineering cost.

Numerous proposals exist for load balancing in peer-to-peer (p2p) networks. Some focus on namespace balancing, making the distance between nodes as uniform as possible. This technique works well under ideal conditions, but not under those found empirically. Instead, researchers have found heavy-tailed query distributions (skew), high rates of node join and leave (churn) and wide variation in node network and storage capacity (heterogeneity). Other approaches tackle these less-than-ideal conditions, but give up on important security properties. We propose an algorithm that both facilitates good performance and does not dilute security. Our algorithm, k-choices, achieves load balance by greedily matching nodes' target workloads with actual applied workloads through limited sampling and limits any fundamental decrease in security by basing each nodes' set of potential identifiers on a single certificate. Our algorithm compares favorably to four others in trace-driven simulations. We have implemented our algorithm and found that it improved aggregate throughput by 20% in a widely heterogeneous system in our experiments.