Abnormal human mobility patterns often signal disruptions, emergencies, or health-related risks, making their detection critical for applications in public safety, urban monitoring, and healthcare. Existing approaches for human mobility anomaly detection typically focus on either identifying visits to unusual places or overall deviations from individual- and population-level norms at the agent-level. However, these methods often (1) overlook fine-grained temporal anomalies, and (2) lack interpretability, as they do not reveal which specific spatiotemporal components of a visit contribute to its anomalous nature. To overcome these limitations, we present ICAD (Interpretable Component-wise Anomaly Detection), a self-supervised autoregressive model that detects both spatial and temporal anomalies by modeling deviations in an individual's visit-level mobility behavior. ICAD is trained on normal visit sequences using a next-visit prediction objective to learn the distribution of visits under regular conditions. At inference, it computes component-wise anomaly scores for each visit by measuring relative divergence from the learned distribution of normal behavior. Specifically, ICAD proposes a top-k deviation metric for discrete spatial anomalies and introduces a novel relative mode-based scoring function for detecting temporal anomalies in continuous time. Experiments on a large scale synthetic human mobility dataset show that ICAD outperforms prior methods in both visit-level and agent-level anomaly detection. For reproducability purposes, the source code is accessible at https://github.com/USC-InfoLab/ICAD.

Road traffic congestion is a persistent problem. Focusing resources on the causes of congestion is a potentially efficient strategy for reducing slowdowns. We present NEXICA, an trained binary classifier to discover which parts of the highway system tend to cause slowdowns on other parts of the highway. We use time series of road speeds as inputs to our causal discovery algorithm, and we concentrate on just the presence or absence of events (traffic slowdowns). We test on six months of road speed data from 195 different highway speed sensors in the Los Angeles area, showing that our approach is superior to state-of-the-art baselines in both accuracy and computation speed.

Encoding geospatial objects is fundamental for geospatial artificial intelligence (GeoAI) applications, which leverage machine learning (ML) models to analyze spatial information. Common approaches transform each object into known formats, like image and text, for compatibility with ML models. However, this process often discards crucial spatial information, such as the object's position relative to the entire space, reducing downstream task effectiveness. Alternative encoding methods that preserve some spatial properties are often devised for specific data objects (e.g., point encoders), making them unsuitable for tasks that involve different data types (i.e., points, polylines, and polygons). To this end, we propose Poly2Vec, a polymorphic Fourier-based encoding approach that unifies the representation of geospatial objects, while preserving the essential spatial properties. Poly2Vec incorporates a learned fusion module that adaptively integrates the magnitude and phase of the Fourier transform for different tasks and geometries. We evaluate Poly2Vec on five diverse tasks, organized into two categories. The first empirically demonstrates that Poly2Vec consistently outperforms object-specific baselines in preserving three key spatial relationships: topology, direction, and distance. The second shows that integrating Poly2Vec into a state-of-the-art GeoAI workflow improves the performance in two popular tasks: population prediction and land use inference.

Generating realistic human mobility data is essential for various application domains, including transportation, urban planning, and epidemic control, as real data is often inaccessible to researchers due to high costs and privacy concerns. Existing deep generative models learn from real trajectories to generate synthetic ones. Despite the progress, most of them suffer from training stability issues and scale poorly with increasing data size. More importantly, they often lack control mechanisms to guide the generated trajectories under constraints such as enforcing specific visits. To address these limitations, we formally define the controlled trajectory generation problem for effectively handling multiple spatiotemporal constraints. We introduce Geo-Llama, a novel LLM finetuning framework that can enforce multiple explicit visit constraints while maintaining contextual coherence of the generated trajectories. In this approach, pre-trained LLMs are fine-tuned on trajectory data with a visit-wise permutation strategy where each visit corresponds to a specific time and location. This strategy enables the model to capture spatiotemporal patterns regardless of visit orders while maintaining flexible and in-context constraint integration through prompts during generation. Extensive experiments on real-world and synthetic datasets validate the effectiveness of Geo-Llama, demonstrating its versatility and robustness in handling a broad range of constraints to generate more realistic trajectories compared to existing methods.

The abundance of vehicle trajectory data offers a new opportunity to compute driving routes between origins and destinations. Current graph-based routing pipelines, while effective, involve substantial costs in constructing, maintaining, and updating road network graphs to reflect real-time conditions. In this study, we propose a new trajectory-based routing paradigm that bypasses current workflows by directly utilizing raw trajectory data to compute efficient routes. Our method, named TrajRoute, uniquely “follows” historical trajectories from a source to a destination, constructing paths that reflect actual driver behavior and implicit preferences. To supplement areas with sparse trajectory data, the road network is also incorporated into TrajRoute's index, and tunable parameters are introduced to control the balance between road segments and trajectories, ensuring a unified and adaptable routing approach. We experimentally verify our approach by comparing it to an existing online routing service. Our results demonstrate that as the number of trajectories covering the road network increases, TrajRoute produces increasingly accurate travel time and route length estimates while gradually eliminating the need to downgrade to the road network. This highlights the potential of simpler, data-driven pipelines for routing, offering lowermaintenance alternatives to conventional systems.

Human mobility modeling from GPS-trajectories and synthetic trajectory generation are crucial for various applications, such as urban planning, disaster management and epidemiology. Both of these tasks often require filling gaps in a partially specified sequence of visits, - a new problem that we call "controlled" synthetic trajectory generation. Existing methods for next-location prediction or synthetic trajectory generation cannot solve this problem as they lack the mechanisms needed to constrain the generated sequences of visits. Moreover, existing approaches (1) frequently treat space and time as independent factors, an assumption that fails to hold true in real-world scenarios, and (2) suffer from challenges in accuracy of temporal prediction as they fail to deal with mixed distributions and the inter-relationships of different modes with latent variables (e.g., day-of-the-week). These limitations become even more pronounced when the task involves filling gaps within sequences instead of solely predicting the next visit.

Human mobility data, represented as sequences of visits, are crucial for various application domains, including transportation, urban planning, and public health. However, large-scale human mobility data is typically inaccessible to researchers due to the high cost of data collection and privacy concerns. This limitation has led to several studies proposing learned models to generate synthetic visit sequences. Despite this progress, existing approaches lack mechanisms to control the generation process, which prevents the incorporation of prior knowledge and the spatiotemporal specification of certain visits. To address these limitations, we formally define the Constraint Trajectory Generation problem and introduce Geo-CETRA (Constraint Enforced Trajectory Generation), a novel framework that operates within the continuous spatiotemporal space, enabling direct generation of geographical coordinates and durations of each visit in a trajectory. Geo-CETRA reparameterizes the sampling space for effective enforcement of various spatiotemporal constraints. Furthermore, incorporating a constraint factorization approach along with an innovative beam decoding module, Geo-CETRA facilitates the production of high-quality synthetic trajectories that realistically emulate human movement while satisfying predefined spatiotemporal constraints. Experiments on real and synthetic datasets demonstrate Geo-CETRA's superior precision and contextual accuracy compared to existing approaches.

Understanding human mobility patterns is crucial for urban planning, resource allocation, and personalized recommendations. However, real-world trajectory data are rarely released publicly due to privacy concerns. At the same time, metropolitan cities are becoming equipped with various roadside sensors, such as CCTV cameras and RFIDs. Unlike trajectory data, these sensors do not uniquely identify and track vehicles, making extracting mobility patterns from their detections challenging. In this paper, we propose VPE, a framework that processes roadside sensor observations to estimate the probability that a vehicle visits a road segment at a certain time. At the core of VPE, we implement LEM, a novel mathematical model that calculates location transition probabilities taking into account the sensors’ reliability. Lastly, we propose APD+, an algorithm that captures the uncertainty of movement between two endpoints. Our experiments show that the proposed methods achieve high accuracy while maintaining practical computation time.

Location measurements from people are very often sparsely sampled due to power constraints or as an attempt at location privacy. However, we would still like to reason about location changes between samples in order to infer visits or understand moving behavior. In this work, we present a method for representing this location uncertainty while constraining the moving object to the road network, which is more realistic and precise for human mobility. Unlike the most straightforward method, fastest path, our method explicitly represents the location uncertainty between location measurements with probabilities. We introduce road network-based bridgelets, which are spatiotemporal probability clouds that model the location uncertainty between two endpoints, and we propose an algorithm, APD*, to generate bridgelets efficiently. In our experimental section, we evaluate the performance of APD* and provide visual examples to compare its output with other baseline methods.

Location measurements from people and vehicles often have long temporal gaps between them. However, we would still like to reason about location behavior during these gaps. This paper presents a new method for filling these gaps that is both principled and data-driven. Unlike the most common method, linear interpolation, our method explicitly represents the location uncertainty in the gaps with probability. It also learns from actual mobility data. We introduce bridgelets, which are small, spatio-temporal, maximum entropy clouds that model spatial uncertainty over small gaps. Using actual trajectories, we combine bridgelets into probabilistic bridges that are specific to absolute start and end locations on the map. The resulting bridges give the probability of visiting certain in-between locations given only the start and end points. Using real trajectory data, we compare our maximum entropy bridges to a popular baseline to show how our approach is much more accurate.

Regular people give away their location data without much knowledge about what can be inferred from it. This paper presents a sensitivity analysis of location disclosure, showing what can be inferred from even just a few place visits. The aim is to highlight how modern inference algorithms can take small location disclosures and create detailed inferences about where else a person is likely to go and what sorts of places they tend to visit. Based on an analysis of over 100,000 people, we show how disclosing just one location point can be used to predict other visits with an AUC of 0.88. We develop another algorithm that shows the types of places a person has an unusually high propensity to visit, and we use this result as part of an economic analysis of delivering targeted advertising. This research serves to raise awareness about what can be inferred from even very small location disclosures, which can in turn inform regular people about their true privacy risks.

Geofences are a fundamental tool of location-based services. A geofence is usually activated by detecting a location measurement inside the geofence region. However, location measurements such as GPS often appear sporadically on smart-phones, partly due to weak signals or privacy preservation. Users may restrict location sensing, or conserve energy, because sensing locations can consume a significant amount of battery. These unpredictable, and sometimes long, gaps between measurements mean that entry into a geofence can go completely undetected. In this paper we argue that short term location prediction can help alleviate this problem by computing the probability of entering a geofence in the future. Complicating this prediction approach is the fact that another location measurement could appear at any time, making the prediction redundant and wasteful. Therefore, we develop a framework that accounts for uncertain location predictions and the possibility of new measurements to trigger geofence activations. Our framework optimizes over the benefits and costs of correct and incorrect geofence activations, leading to an algorithm that reacts intelligently to the uncertainties of future movements and measurements.

The Brownian bridge is a method for probabilistically interpolating the location of a moving person, animal, or object between two measured points. This type of probabilistic interpolation is useful, because it represents the uncertainty of the interpolated points. It can be used to infer the probability of having visited a certain location, including possible exposure to disease. In the class of probabilistic interpolators, the Brownian bridge is attractive, because it has only a single adjustable parameter, the diffusion coefficient. This paper investigates the suitability of the Brownian bridge for interpolating human locations using mobility data from over 12 million people. One section looks at the consistency of the diffusion coefficient from person to person. As part of this, the paper presents, for the first time, a closed form solution for the maximum likelihood estimate of this parameter. The paper also presents statistical tests aimed at evaluating the accuracy of the Brownian bridge for interpolating human location.

A trajectory, defined as a sequence of location measurements, contains valuable information about movements of an individual. Its value of information (VOI) may change depending on the specific application. However, in a variety of applications, knowing the intrinsic VOI of a trajectory is important to guide other subsequent tasks or decisions. This work aims to find a principled framework to quantify the intrinsic VOI of trajectories from the owner's perspective. This is a challenging problem because an appropriate framework needs to take into account various characteristics of the trajectory, prior knowledge, and different types of trajectory degradation. We propose a framework based on information gain (IG) as a principled approach to solve this problem. Our IG framework transforms a trajectory with discrete-time measurements to a canonical representation, i.e., continuous in time with continuous mean and variance estimates, and then quantifies the reduction of uncertainty about the locations of the owner over a period of time as the VOI of the trajectory. Qualitative and extensive quantitative evaluation show that the IG framework is capable of effectively capturing important characteristics contributing to the VOI of trajectories.

Mobile apps that use location data are pervasive, spanning domains such as transportation, urban planning and healthcare. Important use cases for location data rely on statistical queries, e.g., identifying hotspots where users work and travel. Such queries can be answered efficiently by building histograms. However, precise histograms can expose sensitive details about individual users. Differential privacy (DP) is a mature and widely-adopted protection model, but most approaches for DP-compliant histograms work in a data-independent fashion, leading to poor accuracy. The few proposed data-dependent techniques attempt to adjust histogram partitions based on dataset characteristics, but they do not perform well due to the addition of noise required to achieve DP. We identify density homogeneity as a main factor driving the accuracy of DP-compliant histograms, and we build a data structure that splits the space such that data density is homogeneous within each resulting partition. We show through extensive experiments on large-scale real-world data that the proposed approach achieves superior accuracy compared to existing approaches.

Various phenomena such as viruses, gossips, and physical objects (e.g., packages and marketing pamphlets) can be spread through physical contacts. The spread depends on how people move, i.e., their mobility patterns. In practice, mobility patterns of an entire population is never available, and we usually have access to location data of a subset of individuals. In this paper, we formalize and study the problem of estimating the spread of a phenomena in a population, given that we only have access to sub-samples of location visits of some individuals in the population. We show that simple solutions that estimate the spread in the sub-sample and scale it to the population, or more sophisticated solutions that rely on modeling location visits of individuals do not perform well in practice. Instead, we directly model the co-locations between the individuals. We introduce PollSpreader and PollSusceptible, two novel approaches that model the co-locations between individuals using a contact network , and infer the properties of the contact network using the sub-sample to estimate the spread of the phenomena in the entire population. We analytically show that our estimates provide an upper bound and a lower bound on the spread of the disease in expectation. Finally, using a large high-resolution real-world mobility dataset, we experimentally show that our estimates are accurate in practice, while other methods that do not correctly account for co-locations between individuals result in entirely wrong observations (e.g, premature prediction of herd-immunity).

Location fingerprinting is a technique for determining the location of a device by measuring ambient signals such as radio signal strength, temperature, or any signal that varies with location. The accuracy of the technique is compromised by signal noise, quantization, and limited calibration resources. We develop generic, probabilistic models of location fingerprinting to find accuracy estimates. In one case, we look at predeployment modeling to predict accuracy before any signals have been measured using a new concept of noisy reverse geocoding. In another case, we model a previously deployed system to predict its accuracy. The models allow us to explore the accuracy implications of signal noise, calibration effort, and quantization of signals and space.

A geo-marketplace allows users to be paid for their location data. Users concerned about privacy may want to charge more for data that pinpoints their location accurately, but may charge less for data that is more vague. A buyer would prefer to minimize data costs, but may have to spend more to get the necessary level of accuracy. We call this interplay between privacy, utility, and price spatial privacy pricing. We formalize the issues mathematically with an example problem of a buyer deciding whether or not to open a restaurant by purchasing location data to determine if the potential number of customers is sufficient to open. The problem is expressed as a sequential decision making problem, where the buyer first makes a series of decisions about which data to buy and concludes with a decision about opening the restaurant or not. We present two algorithms to solve this problem, including experiments that show they perform better than baselines.

As any other type of data, GPS traces contain noise, anomaly, and sometimes unexpected values. Normally, researchers and data engineers analysts would start dealing with GPS data by removing those noises and outliers. However, in this work, we take the opposite direction. We focus on analyzing those unexpected values rather than discarding them. Interestingly, we discovered useful findings from an insight look at the noise in GPS trajectories. The intuition behind those discoveries is that when unexpected GPS readings are observed several times around a specific location, we study the nature of that location rather than thrown away those reading. By doing so, we are able to tell the type of area around those readings. For example, we can infer that a driver is passing by a tall building or through a forest based on the pattern of noise in the GPS readings. We are also able to question the quality of the underlying road map. Our findings and discoveries are based on the analysis of real GPS data for the Microsoft shuttles.

Taking speed reports from vehicles is a proven, inexpensive way to infer traffic conditions. However, due to concerns about privacy and bandwidth, not every vehicle occupant may want to transmit data about their location and speed in real time. We show how to drastically reduce the number of transmissions in two ways, both based on a Markov random field for modeling traffic speed and flow. First, we show that a only a small number of vehicles need to report from each location. We give a simple, probabilistic method that lets a group of vehicles decide on which subset will transmit a report, preserving privacy by coordinating without any communication. The second approach computes the potential value of any location’s speed report, emphasizing those reports that will most affect the overall speed inferences, and omitting those that contribute little value. Both methods significantly reduce the amount of communication necessary for accurate speed inferences on a road network.

Human activity is one of the most important pieces of context affecting an individual's information needs. Understanding the relationship between activities, time, location, and other contextual features can improve the quality of various intelligent systems, including contextual search engines, task managers, digital personal assistants, chat bots, and recommender systems.

GPS data is noisy by nature. A typical location-based service would start by filtering out the noise from the raw GPS points that are generated by moving objects. Once the locations of the objects are identified, the location-based service is provided. In this paper, we decide not to throw away the noise. Instead, we consider the noise as an asset. We analyze the various noise patterns under different conditions and region characteristics. More specifically, we focus on one example where a lot of GPS noise is experienced; which is urban canyons. We believe that learning the GPS noise patterns in a supervised environment enables us to discover knowledge about new areas or areas where we have little knowledge. This paper is based on the analysis of GPS traces that are collected from the shuttle service within the Microsoft campuses around Seattle, Washington.

It is a fact that there are tons of GPS traces generated every minute by the millions of in-road vehicles over the world. Naturally, those traces contain imprecise readings, and most of the time they include noise and outliers. Therefore, there is a real need for a tool to allow users, companies, and researchers to get a deep insight into those raw traces and discover potential knowledge out of it. This knowledge would uncover the quality level of the GPS traces and, indeed, the quality level of the underlying map. It would also help discover interesting facts about the surrounding environment such as the type and height of buildings, the landscape cover, the weather conditions, and the nature of businesses and activities. This demo presents a system that allows users to interactively explore their collected GPS traces. Users can visually inspect the precision of their raw GPS traces, and snap these traces to the underlying road network map. Furthermore, users have the ability to clean their traces by applying various types of spatio-temporal filters. Users can perform noise analysis and produce statistics over regions of interest on the map. Last but not least, the system gives suggestions or guesses on the surrounding environment by comparing the perceived noise patterns to a database of pre-stored noise patterns. For the demo purpose, the system is initially populated with a rich data set of trajectories generated from the Microsoft shuttle service around the Greater Area of Seattle.

Location data from mobile devices is a sensitive yet valuable commodity for location-based services and advertising. We investigate the intrinsic value of location data in the context of strong privacy, where location information is only available from end users via purchase. We present an algorithm to compute the expected value of location data from a user, without access to the specific coordinates of the location data point. We use decision-theoretic techniques to provide a principled way for a potential buyer to make purchasing decisions about private user location data. We illustrate our approach in two scenarios: the delivery of targeted ads specific to a user's home location and the estimation of traffic speed. In both cases, the methodology leads to quantifiably better purchasing decisions than competing methods.

Computerized generation of humor is a notoriously difficult AI problem.We develop an algorithm called Libitum that helps humans generate humor in a Mad Lib R , which is a popular fill-in-the-blank game.The algorithm is based on a machine learned classifier that determines whether a potential fill-in word is funny in the context of the Mad Lib story.We use Amazon Mechanical Turk to create ground truth data and to judge humor for our classifier to mimic, and we make this data freely available.Our testing shows that Libitum successfully aids humans in filling in Mad Libs that are usually judged funnier than those filled in by humans with no computerized help.We go on to analyze why some words are better than others at making a Mad Lib funny.

Summary form only given. We are all people who have a definite location, but our intuitions about people and their locations are not always correct. Fortunately, researchers have been looking at how people behave with respect to location, and they have discovered surprising facts that do not necessarily match our assumptions. For example, as technologists, we tend to assume that people have strong concerns about their location privacy. But is this really true? As another example, researchers have tried to show that the same models of location behavior apply to both people and animals. Does this survive scrutiny? And if people exhibit complex behavior in terms of location, does this mean it is difficult to predict where they will go in the future? Not necessarily. The last few decades have seen principled answers to these and other questions, with research driven by growing demand for mobile computing, increasing availability of location data, and expanding problems in transportation. In this talk I will present several ways that our intuition about people and location does not match reality.

All current navigation systems return efficient source-to-destination routes assuming a "one-size-fits-all" set of objectives, without addressing most personal preferences. Although they allow some customization (like "avoid highways" or "avoid tolls"), the choices are very limited and require some sophistication on the part of the user. In this paper we present, implement, and test a framework that generates personalized driving directions by automatically analyzing users' GPS traces. Our approach learns cost functions using coordinate descent, leveraging a state-of-the-art route planning engine for efficiency. In an extensive experimental study, we show that this framework infers user-specific driving preferences, significantly improving the route quality. Our approach can handle continental-sized inputs (with tens of millions of vertices and arcs) and is efficient enough to be run on an autonomous device (such as a car navigation system) preserving user privacy.

We present a methodology for automatically extracting and summarizing reports of significant local events from large-scale Twitter feeds. While previous work has relied on an analysis of tweet text to identify local events, we show how to reliably detect events using only time series analysis of geotagged tweet volumes from localized regions. The algorithm sweeps through different spatial and temporal resolutions and finds events as anomalous spikes in the rate of geotagged tweets. We applied the approach to a corpus of over 733 million geotagged tweets. Using a panel of 103 crowdsourced judges who tagged 2400 detected events, we achieved a local event detection precision of 70%. Using these judged events as ground truth, a decision tree classifier was able to raise the detection precision to 93%.

Time of use tiered pricing schedules encourage shifting electricity demand from peak to off-peak hours. Charging times for electric vehicles (EV) can be shifted into overnight hours, which are usually off-peak. EVs can also be used as energy storage devices, available during certain peak hours to power a house with electricity stored during off-peak hours. Studies suggest both techniques are practical, but were based on simulated demand patterns or large commercial fleets. To investigate feasibility on a per home basis, we collected data from 15 EV homes using the Lab of Things sensing infrastructure. We evaluate a scheme that powers homes with their car battery during expensive electricity periods and then charges the battery during cheaper periods. We show an average potential savings of $10.91/month for shifting charging times, and an additional $13.58/month for powering the home from the EV, even accounting for the inefficiencies of electric conversion.

Place labeling is the process of giving semantic labels to locations, such as home, work, and school. For a particular person, these labels can be computed automatically based on features of that person's visits to these locations. A previous system called Placer used the person's demographic data and the timing of their visits to label places with a learned decision tree. We developed Placer++ as a more accurate labeler, augmenting Placer's features of individual visits with (1) labeled visits from other people and (2) features about the sequence of the individual's visits. In processing sequences, we adopt structural learning techniques to take into account the relationships between visits. Accuracy increased by 8.85 percentage points over the baseline of Placer. We describe and justify the features and present our experiments on government diary data.

Semantic place labels are labels like "home", "work", and "school" given to geographic locations where a person spends time. Such labels are important both for giving understandable location information to people and for automatically inferring activities. Deployed products often compute semantic labels with heuristics, which are difficult to program reliably. In this paper, we develop Placer, an algorithm to infer semantic places labels. It uses data from two large, government diary studies to create a principled algorithm for labeling places based on machine learning. Our labeling reduces to a classification problem, where we classify locations into different label categories based on individual demographics, the timing of visits, and nearby businesses. Using these government studies gives us an unprecedented amount of training and test data. For instance, one of our experiments used training data from 87,600 place visits (from 10,372 distinct people) evaluated on 1,135,053 visits (from 124,517 distinct people). We show labeling accuracy for a number of experiments, including one that gives a 14 percentage point increase in accuracy when labeling is a function of nearby businesses in addition to demographic and time features. We also test on GPS data from 28 subjects.

Much work has been done on predicting where is one going to be in the immediate future, typically within the next hour. By contrast, we address the open problem of predicting human mobility far into the future, a scale of months and years. We propose an efficient nonparametric method that extracts significant and robust patterns in location data, learns their associations with contextual features (such as day of week), and subsequently leverages this information to predict the most likely location at any given time in the future. The entire process is formulated in a principled way as an eigendecomposition problem. Evaluation on a massive dataset with more than 32,000 days worth of GPS data across 703 diverse subjects shows that our model predicts the correct location with high accuracy, even years into the future. This result opens a number of interesting avenues for future research and applications.

Most location-aware mobile applications only make use of the user's current location, but there is an opportunity for them to infer the user's future locations. We present Trajectory-Aware Search (TAS), a mobile local search application that predicts the user's destination in real-time based on location data from the current trip and shows search results near the predicted location. TAS demonstrates the feasibility of destination prediction in an interactive mobile application. Our user study of TAS shows using predicted destinations to help select search results positively augments the local search experience.

The 20th ACM SIGSPATIAL Conference on Advances in Geographic Information Systems (GIS) was held in November of 2012. In conjunction with this conference, we organized the conference's first competition, called the SIGSPATIAL GIS Cup 2012. The subject of the competition was map matching, which is the problem of correctly matching a sequence of noisy GPS points to roads. We describe the details of the contest, the results of the competition, and the lessons we learned in running a contest like this.

We investigate opportunistic routing, centering on the recommendation of ideal diversions on trips to a primary destination when an unplanned waypoint, such as a rest stop or a refueling station, is desired. In the general case, an automated routing assistant may not know the driver's final destination and may need to consider probabilities over destinations in identifying the ideal waypoint along with the revised route that includes the waypoint. We consider general principles of opportunistic routing and present the results of several studies with a corpus of real-world trips. Then, we describe how we can compute the expected value of asking a user about the primary destination so as to remove uncertainly about the goal and show how this measure can guide an automated system's engagements with users when making recommendations for navigation and analogous settings in ubiquitous computing.

Home heating is a major factor in worldwide energy use. Our system, PreHeat, aims to more efficiently heat homes by using occupancy sensing and occupancy prediction to automatically control home heating. We deployed PreHeat in five homes, three in the US and two in the UK. In UK homes, we controlled heating on a per-room basis to enable further energy savings. We compared PreHeat's prediction algorithm with a static program over an average 61 days per house, alternating days between these conditions, and measuring actual gas consumption and occupancy. In UK homes PreHeat both saved gas and reduced MissTime (the time that the house was occupied but not warm). In US homes, PreHeat decreased MissTime by a factor of 6-12, while consuming a similar amount of gas. In summary, PreHeat enables more efficient heating while removing the need for users to program thermostat schedules.

People often search for local information (e.g., a restaurant, store, gas station, or attraction) from their mobile device. We show, via a survey of 929 mobile searchers at a large software company, that local searches tend to be highly contextual, influenced by geographic features, temporal aspects, and the searcher's social context. While location was reported to be very important, respondents looked for information about places close to their current location only 40% of the time. Instead, they were often in transit (68% of our searchers) and wanted information related to their destination (27% of searchers), en route to their destination (12%), or near their destination (12%). Additionally, 63% of our participants' mobile local searches took place within a social context and were discussed with someone else. We discuss these findings to present a picture of how location, time, and social context impact mobile local searches.

Instead of traditional ways of creating road maps, an attractive alternative is to create a map based on GPS traces of regular drivers. One important aspect of this approach is to automatically compute the number and locations of driving lanes on a road. We introduce the idea of using a Gaussian mixture model (GMM) to model the distribution of GPS traces across multiple traffic lanes. The GMM naturally accounts for the inherent spread in GPS data. We present a new variation of the GMM that enforces constant lane width and GPS variance in each lane. For fitting the GMM, we also introduce a new regularizer that is sensitive to the overall spread of the GPS data across the road. Our experiments on real GPS data show that our new GMM is better at counting lanes than a more traditional GMM, and it gives more consistent results across our data set.

Long-term personal GPS data is useful for many UbiComp services such as traffic monitoring and environmental impact assessment. However, inference attacks on such traces can reveal private information including home addresses and schedules. We asked 32 participants from 12 households to collect 2 months of GPS data, and showed it to them in visualizations. We explored if they understood how their individual privacy concerns mapped onto 5 location obfuscation schemes (which they largely did), which obfuscation schemes they were most comfortable with (Mixing, Deleting data near home, and Randomizing), how they monetarily valued their location data, and if they consented to share their data publicly. 21/32 gave consent to publish their data, though most households' members shared at different levels, which indicates a lack of awareness of privacy interrelationships. Grounded in real decisions about real data, our findings highlight the potential for end-user involvement in obfuscation of their own location data.

This paper presents a method for automatically converting raw GPS traces from everyday vehicles into a routable road network. The method begins by smoothing raw GPS traces using a novel aggregation technique. This technique pulls together traces that belong on the same road in response to simulated potential energy wells created around each trace. After the traces are moved in response to the potential fields, they tend to coalesce into smooth paths. To help adjust the parameters of the constituent potential fields, we present a theoretical analysis of the behavior of our algorithm on a few different road configurations. With the resulting smooth traces, we apply a custom clustering algorithm to create a graph of nodes and edges representing the road network. We show how this network can be used to plan reasonable driving routes, much like consumer-oriented mapping Web sites. We demonstrate our algorithms using real GPS data collected on public roads, and we evaluate the effectiveness of our approach on public roads, and we evaluate the effectiveness of our approach by comparing the route planning results suggested by our generated graph to a commercial route planner.

The problem of matching measured latitude/longitude points to roads is becoming increasingly important. This paper describes a novel, principled map matching algorithm that uses a Hidden Markov Model (HMM) to find the most likely road route represented by a time-stamped sequence of latitude/longitude pairs. The HMM elegantly accounts for measurement noise and the layout of the road network. We test our algorithm on ground truth data collected from a GPS receiver in a vehicle. Our test shows how the algorithm breaks down as the sampling rate of the GPS is reduced. We also test the effect of increasing amounts of additional measurement noise in order to assess how well our algorithm could deal with the inaccuracies of other location measurement systems, such as those based on WiFi and cell tower multilateration. We provide our GPS data and road network representation as a standard test set for other researchers to use in their map matching work.

Location systems have long been identified as an important component of emerging mobile applications. Most research on location systems has focused on precise location in indoor environments. However, many location applications (for example, location-aware web search) become interesting only when the underlying location system is available ubiquitously and is not limited to a single office environment. Unfortunately, the installation and calibration overhead involved for most of the existing research systems is too prohibitive to imagine deploying them across, say, an entire city. In this work, we evaluate the feasibility of building a wide-area 802.11 Wi-Fi-based positioning system. We compare a suite of wireless-radio-based positioning algorithms to understand how they can be adapted for such ubiquitous deployment with minimal calibration. In particular, we study the impact of this limited calibration on the accuracy of the positioning algorithms. Our experiments show that we can estimate a user's position with a median positioning error of 13-40 meters (depending upon the characteristics of the environment). Although this accuracy is lower than existing positioning systems, it requires substantially lower calibration overhead and provides easy deployment and coverage across large metropolitan areas.

We present a method for computing the location of a device down to a radius of several miles within a greater metropolitan area by analyzing the signal strengths observed from commercial FM radio stations. The use of ambient commercial radio signals allows for wide coverage, both indoor and outdoor reception, client-side computing for privacy, and the feasibility of employing inexpensive, low-power measurement hardware. Our technique is based on a model for computing the likelihood of locations using both received signal strengths and information from a simulated signal strength map. Using simulated signal strengths relieves the burden of manually measuring signal strength as a function of location. We account for the inevitable measurement variations among devices by comparing rankings of radio stations by signal strength. Our experiments show we can measure location down to a median error of about 8 kilometers (5 miles) in the greater Seattle area by listening to seven different radio stations.

Context is a critical ingredient of ubiquitous computing. While it is possible to use specialized sensors and beacons to measure certain aspects of a user's context, we are interested in what we can infer from using the existing 802.11 wireless network infrastructure that already exists in many places. The context parameters we infer are the location of a client (with a median error of 1.5 meters) and an indicator of whether or not the client is in motion (with a classification accuracy of 87%). Our system, called LOCADIO, uses Wi-Fi signal strengths from existing access points measured on the client to infer both pieces of context. For motion, we measure the variance of the signal strength of the strongest access point as input to a simple two-state hidden Markov model (HMM) for smoothing transitions between the inferred states of "still" and "moving". For location, we exploit the fact that Wi-Fi signal strengths vary with location, and we use another HMM on a graph of location nodes whose transition probabilities are a function of the building's floor plan, expected pedestrian speeds, and our still/moving inference. Our probabilistic approach to inferring context gives a convenient way of balancing noisy measured data such as signal strengths against our a priori assumptions about a user's behavior.

Intelligent rooms equipped with video cameras can exhibit compelling behaviors, many of which depend on object recognition. Unfortunately, object recognition algorithms are rarely written with a normal consumer in mind, leading to programs that would be impractical to use for a typical person. These impracticalities include speed of execution, elaborate training rituals, and setting adjustable parameters. We present an algorithm that can be trained with only a few images of the object, that requires only two parameters to be set, and that runs at 0.7 Hz on a normal PC with a normal color camera. The algorithm represents an object’s features as small, quantized edge templates, and it represents the object’s geometry with “Hough kernels”.

We use the color cooccurrence histogram (CH) for recognizing objects in images. The color CH keeps track of the number of pairs of certain colored pixels that occur at certain separation distances in image space. The color CH adds geometric information to the normal color histogram, which abstracts away all geometry. We compute model CHs based on images of known objects taken from different points of view. These model CHs are then matched to subregions in test images to find the object. By adjusting the number of colors and the number of distances used in the CH, we can adjust the tolerance of the algorithm to changes in lighting, viewpoint, and the flexibility of the object We develop a mathematical model of the algorithm's false alarm probability and use this as a principled way of picking most of the algorithm's adjustable parameters. We demonstrate our algorithm on different objects, showing that it recognizes objects in spite of confusing background clutter partial occlusions, and flexing of the object.

Background maintenance is a frequent element of video surveillance systems. We develop Wallflower, a three-component system for background maintenance: the pixel-level component performs Wiener filtering to make probabilistic predictions of the expected background; the region-level component fills in homogeneous regions of foreground objects; and the frame-level component detects sudden, global changes in the image and swaps in better approximations of the background. We compare our system with 8 other background subtraction algorithms. Wallflower is shown to outperform previous algorithms by handling a greater set of the difficult situations that can occur. Finally, we analyze the experimental results and propose normative principles for background maintenance.

When an airbag deploys on a rear-facing infant seat, it can injure or kill the infant. When an airbag deploys on an empty seat, the airbag and the money to replace it are wasted. We have shown that video images can be used to determine whether or not to deploy the passenger-side airbag in a crash. Images of the passenger seat, taken from a video camera mounted inside the vehicle, can be used to classify the seat as either empty, containing a rear-facing infant seat, or occupied. Our first experiment used a single, monochrome video camera. The system was automatically trained on a series of test images. Using a principle components (eigenimages) nearest neighbor classifier, it achieved a correct classification rate of 99.5% on a test of 910 images. Our second experiment used a pair of monochrome video cameras to compute stereo disparity (a function of 3D range) instead of intensity images. Using a similar algorithm, the second approach achieved a correct classification rate of 95.1% on a test of 890 images. The stereo technique has the advantage of being less sensitive to illumination, and would likely work best in a real system.

This paper presents a new algorithm for detecting objects in images, one of the fundamental tasks of computer vision. The algorithm extends the representational efficiency of eigenimage methods to binary features, which are less sensitive to illumination changes than gray-level values normally used with eigenimages. Binary features (square subtemplates) are automatically chosen on each training image. Using features rather than whole templates makes the algorithm more robust to background clutter and partial occlusions. Instead of representing the features with real-valued eigenvector principle components, we use binary vector quantization to avoid floating point computations. The object is detected in the image using a simple geometric hash table and Hough transform. On a test of 1000 images, the algorithm works on 99.3%. We present a theoretical analysis of the algorithm in terms of the receiver operating characteristic, which consists of the probabilities of detection and false alarm. We verify this analysis with the results of our 1000-image test and we use the analysis as a principled way to select some of the algorithm's important operating parameters.

Visual pose measurement computes the translation and orientation of an object based on an image. The problem is made difficult by background clutter, partial occlusions, and illumination variations. This paper presents a solution to these problems with a new algorithm for planar, visual pose measurement based on compressed, binary subtemplates. For a given object, we take a sequence of training images as the object rotates. On each training image, we detect binary edges and pick binary edge subtemplates as features to model the object. These features are compressed using the Lloyd algorithm, a conventional image compression technique. We detect the object in an image using a Hough transform. We demonstrate the algorithm on images with background clutter, partial occlusions, and illumination variations.

Planar pose measurement from images is an important problem for automated assembly and inspection. In addition to accuracy and robustness, ease of use is very important for real world applications. Recently, Murase and Nayar have presented the "parametric eigenspace " for object recognition and pose measurement based on training images. Although their system is easy to use, it has potential problems with background clutter and partial occlusions. We present an algorithm that is robust in these terms. It uses several small features on the object rather than a monolithic template. These "eigenfeatures" are matched using a median statistic, giving the system robustness in the face of background clutter and partial occlusions. We demonstrate our algorithm's pose measurement accuracy with a controlled test, and we demonstrate its detection robustness on cluttered images with the objects of interest partially occluded.

Uniformly textured surfaces in 3D scenes provide important cues for image understanding. Texture can be used for both segmentation and for 3D shape inference. Unfortunately, virtually all current algorithms are based on assumptions that make it impossible to do texture segmentation and shape-from-texture in the same image. Texture segmentation algorithms rely on an absence of 3D effects that tend to distort the texture. Shape-from-texture algorithms depend on these effects, relying instead on the texture being already segmented. To really understand texture in images, texture segmentation and shape-from-texture must be viewed as a combined problem to be solved simultaneously. We present a solution to this problem with a region-growing algorithm that explicitly accounts for perspective distortions of otherwise uniform texture. We use the image spectrogram to compute local surface normals, which are in turn used to "frontalize" the texture. These frontalized texture patches are then subjected to a region-growing algorithm based on similarity in the local frequency domain and a minimum description length criteria. We show results of our algorithm on real texture images taken in the lab and outdoors.>

It is shown how local spatial image frequency is related to the surface normal of a textured surface. It is found that the Fourier power spectra of any two similarly textured patches on a plane are approximately related to each other by an affine transformation. The transformation parameters are a function of the plane's surface normal. This relationship is used as the basis of an algorithm for finding surface normals of textured shapes using the spectrogram, which is one type of local spatial frequency representation. The relationship is validated by testing the algorithm on real textures. By analyzing shape and texture in terms of the local spatial frequency representation, the advantages of the representation for the shape-from-texture problem can be exploited. Specifically, the algorithm requires no feature detection and can give correct results even when the texture is aliased.>

Real-world scenes contain many interacting phenomena that lead to complex images which are difficult to interpret automatically. Some effects are best described in the spatial domain, while others are more naturally expressed in frequency. In order to resolve this dichotomy, the authors present the combined space/frequency representation which, for each point in an image, shows the spatial frequencies at that point. This representation is useful for developing theories about many important vision phenomena, leading to deeper understanding and better algorithms. The authors show how the representation can be used for the shape from texture problem and to analyze aliasing simply and naturally. The space/frequency representation should be a key aid in untangling the complex interaction of phenomena in images, allowing automatic understanding of real-world scenes.>