Trajectory similarity in road networks is pivotal for numerous applications in transportation, urban planning, and ridesharing. However, due to the varying lengths of trajectories, employing similarity metrics directly on raw trajectory data (e.g., DTW [1]) becomes impractical at scale. Therefore, current research primarily revolves around applying deep learning to embed trajectories into vector representations, i.e., embeddings, enabling the application of simpler (and indexable) similarity metrics such as Euclidean distance. Existing research either involves embedding trajectories independent of the downstream tasks, or tailors the embedding specifically for a designated similarity metric. While the former offers versatility and allows for easy fine-tuning to accommodate various metrics, the latter typically yields more effective results but necessitates reconfiguration for different, yet similar metrics. Moreover, both approaches neglect the intrinsic spatiotemporal continuity in trajectory data, resulting in suboptimal trajectory modeling. Our objective is to address the limitations in modeling and have the best of the two worlds. Initially, we generate an embedding through pre-training, decoupled from any particular similarity metric. Subsequently, through a meticulous yet less complex fine-tuning process, we enhance the embedding to encapsulate the nuances of a designated similarity metric. Moreover, a significant aspect of our approach lies in our trajectory modeling that captures spatiotemporal continuity, which mainly consists of a trajectory-oriented road segment embedding and a Transformer encoder enhanced by spatiotemporal semantics inherent in road network-constrained trajectories. Our experimental results demonstrate the superiority of our approach in approximating multiple trajectory similarity metrics over existing state-of-the-art models from both categories of approaches.

Traffic Signal Control plays a vital role in modern traffic management. However, most existing methods focus exclusively on vehicle flow, neglecting the critical role of pedestrians, leading to suboptimal performance in intersections with mixed vehicle-pedestrian traffic. Pedestrian behavior presents unique challenges due to its irregularity and flexibility, such as non-lane-based movements and uncertain crossing directions, which cannot be modeled by existing methods. To address this limitation, we propose VPLight, a comprehensive framework designed to manage bothVehicle andPedestrian dynamics in traffic signal control. Specifically, we first design the Pedestrian Feature Extractor to capture the spatiotemporal dynamics of pedestrian movement, offering a robust representation of their irregular patterns. Subsequently, to coordinate traffic signal control at multiple intersections, we develop a novel communication approach called V-Comm to enable effective integration among intersections. Extensive experiments show that VPLight outperforms state-of-the-art baselines with significant margins (up to +44.04%). Our results demonstrate that VPLight can remarkably address the challenges of mixed vehicle-pedestrian traffic control and enhance the overall traffic flow efficiency across the road network.

Clinical time series are often irregularly sampled, with varying sensor frequencies, missing observations, and misaligned timestamps. Prior approaches typically address these irregularities by interpolating data into regular sequences, thereby introducing bias, or by generating inconsistent and uninterpretable relationships across sensor measurements, complicating the accurate learning of both intra-series and inter-series dependencies. We introduce WaveGNN, a model that operates directly on irregular multivariate time series without interpolation or conversion to a regular representation. WaveGNN combines a decay-aware Transformer to capture intra-series dynamics with a sample-specific graph neural network that models both short-term and long-term inter-sensor relationships. Therefore, it generates a single, sparse, and interpretable graph per sample. Across multiple benchmark datasets (P12, P19, MIMIC-III, and PAM), WaveGNN delivers consistently strong performance, whereas other state-of-the-art baselines tend to perform well on some datasets or tasks but poorly on others. While WaveGNN does not necessarily surpass every method in every case, its consistency and robustness across diverse settings set it apart. Moreover, the learned graphs align well with known physiological structures, enhancing interpretability and supporting clinical decision-making.

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.

Inferring social relationships from mobility data is crucial for many applications because it reflects real-world connections among people. However, large-scale trajectory datasets with ground-truth social ties are exceedingly scarce, making it difficult to train deep models for relationship inference. To address this gap, we propose a transferable social relationship inference framework that can be trained on one high-quality, labeled dataset and then generalized to new datasets, even from different cities. Our framework rests on the key insight that social bonds depend largely on the frequency of individual meetings and the popularity of those meeting locations, both of which can be inferred statistically from raw trajectory data, irrespective of the underlying geographic semantics. It comprises two main modules: 1) Universal Social Relationship Classifier (USRC): A model trained to infer social relationships from trajectory data, and 2) Spatial Embedding Transfer (SET): A location embedding alignment technique that adapts new datasets to the pre-trained USRC model. By aligning location embeddings, SET module enables the pre-trained USRC to interpret previously unseen datasets without extra supervision. Experiments on five public datasets demonstrate that our method achieves state-of-the-art performance in zero-shot social relationship inference, surpassing other unsupervised, and in some cases, even supervised, approaches. Additionally, the SET module significantly improves location embedding alignment, outperforming existing baseline methods. The source code and data are available at https://github.com/chuchen2017/SET.

Accurately attributing user visits to specific Points of Interest (POIs) is a foundational task for mobility analytics, personalized services, marketing and urban planning. However, POI attribution remains challenging due to GPS inaccuracies, typically ranging from 2 to 20 meters in real-world settings, and the high spatial density of POIs in urban environments, where multiple venues can coexist within a small radius (e.g., over 50 POIs within a 100-meter radius in dense city centers). Relying on proximity is therefore often insufficient for determining which POI was actually visited. We introduce POIFormer, a novel Transformer-based framework for accurate and efficient POI attribution. Unlike prior approaches that rely on limited spatiotemporal, contextual, or behavioral features, POIFormer jointly models a rich set of signals, including spatial proximity, visit timing and duration, contextual features from POI semantics, and behavioral features from user mobility and aggregated crowd behavior patterns-using the Transformer's self-attention mechanism to jointly model complex interactions across these dimensions. By leveraging the Transformer to model a user's past and future visits (with the current visit masked) and incorporating crowd-level behavioral patterns through pre-computed kernel density estimates (KDEs), POIFormer enables accurate, efficient attribution in large, noisy mobility datasets. Its architecture supports generalization across diverse data sources and geographic contexts while avoiding reliance on hard-to-access or unavailable data layers, making it practical for real-world deployment. Extensive experiments on real-world mobility datasets demonstrate significant improvements over existing baselines, particularly in challenging real-world settings characterized by spatial noise and dense POI clustering.

Recent advances in large foundation models (FMs) have enabled learning general-purpose representations in natural language, vision, and audio. Yet geospatial artificial intelligence (GeoAI) still lacks widely adopted foundation models that generalize across tasks that require joint reasoning over geospatial objects and human mobility. Such tasks are crucial as mobility, along with satellite imagery, street view, and text, is a core modality for understanding the physical world. We argue that a key bottleneck is the absence of unified, general-purpose, and transferable representations for geospatially embedded objects (GEOs). Such objects include points, polylines, and polygons in geographic space, enriched with semantic context and critical for geospatial reasoning. Much current GeoAI research compares GEOs to tokens in language models, where patterns of human movement and spatiotemporal interactions yield contextual meaning similar to patterns of words in text. However, modeling GEOs introduces challenges fundamentally different from language, including spatial continuity, variable scale and resolution, temporal dynamics, and data sparsity. Moreover, privacy constraints and global variation in mobility further complicates modeling and generalization. This paper formalizes these challenges, identifies key representational gaps, and outlines research directions for building foundation models that learn behavior-informed, transferable representations of GEOs from large-scale human mobility data, as well as static contextual information such as points of interest, object shapes and spatio-temporal semantics.

Image geolocalization-the task of determining an image's geographic origin-poses significant challenges, largely due to visual similarities across disparate locations and the large search space. To address these issues, we propose a hierarchical sequence prediction approach inspired by how humans narrow down locations from broad regions (e.g., country) to specific addresses (e.g., street name and house number). Analogously, our model predicts geographic tokens hierarchically, first identifying a general region and then sequentially refining predictions to increasingly precise locations. Rather than relying on explicit semantic partitions (e.g., country, city), our method uses S2 cells, a nested, multiresolution global grid, and sequentially predicts finer-level cells conditioned on visual inputs and previous predictions. This procedure mirrors autoregressive text generation in large language models. Much like in language modeling, final performance depends not only on training but also on inference-time strategy. We investigate multiple top-down traversal methods for autoregressive sampling, incorporating techniques from test-time compute scaling used in language models. Specifically, we integrate beam search and multi-sample inference while exploring various selection strategies to determine the final output. This approach enables the model to manage uncertainty by exploring multiple plausible paths through the hierarchy. We evaluate our method on the Im2GPS3k and YFCC4k datasets against two distinct sets of baselines: those that operate without a Multimodal Large Language Model (MLLM) and those that leverage one. In the MLLM-free setting, our model surpasses other comparable baselines on nearly all metrics, achieving state-of-the-art performance with accuracy gains of up to 13.9%. When augmented with an MLLM, our model again outperforms all baselines, setting a new state of the art across every metric. The source code is available at https://github.com/NNargesNN/GeoToken.

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.

Understanding human mobility behavior is crucial for numerous applications, including crowd management, location-based recommendations, and the estimation of pandemic spread. Machine learning models can predict the Points of Interest (POIs) that individuals are likely to visit in the future by analyzing their historical visit patterns. Previous studies address this problem by learning a POI classifier, where each class corresponds to a POI. However, this limits their applicability to predict a new POI that was not in the training data, such as the opening of new restaurants. To address this challenge, we propose a model designed to predict a new POI outside the training data as long as its context is aligned with the user’s interests. Unlike existing approaches that directly predict specific POIs, our model first forecasts the semantic context of potential future POIs, then combines this with a proximity-based prior probability distribution to determine the exact POI. Experimental results on real-world visit data demonstrate that our model outperforms baseline methods that do not account for semantic contexts, achieving a 17% improvement in accuracy. Notably, as new POIs are introduced over time, our model remains robust, exhibiting a lower decline rate in prediction accuracy compared to existing methods.

and we propose a spatial indexing algorithm that accounts for fairness. Our KD-tree inspired approach significantly improves fairness while maintaining high learning accuracy, as shown by extensive experimental results on real data.

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.

The Wearables for Health Toolkit (W4H Toolkit) is an open-source platform that provides a robust, end-to-end solution for the centralized management and analysis of wearable data. With integrated tools and frameworks, the toolkit facilitates seamless data acquisition, integration, storage, analysis, and visualization of both stored and streaming data from various wearable devices. The W4H Toolkit is designed to provide medical researchers and health practitioners with a unified framework that enables the analysis of health-related data for various clinical applications. We provide an overview of the system and demonstrate how it can be used by health researchers to import and analyze a wide range of wearable data and perform data analysis, highlighting the versatility and functionality of the system across diverse healthcare domains and applications.

Real-world datasets are often incomplete due to data collection cost, privacy considerations or as a side effect of data integration/preparation. We focus on answering aggregate queries on such datasets, where data incompleteness causes the answers to be inaccurate. To address this problem, assuming typical relational data, existing work generates synthetic data to complete the database, a challenging task, especially in the presence of bias in observed data.

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.

While extremely useful (e.g., for COVID-19 forecasting and policy-making, urban mobility analysis and marketing, and obtaining business insights), location data collected from mobile devices often contain data from a biased population subset, with some communities over or underrepresented in the collected datasets. As a result, aggregate statistics calculated from such datasets (as is done by various companies including Safegraph, Google, and Facebook), while ignoring the bias, leads to an inaccurate representation of population statistics. Such statistics will not only be generally inaccurate, but the error will disproportionately impact different population subgroups (e.g., because they ignore the underrepresented communities). This has dire consequences, as these datasets are used for sensitive decision-making such as COVID-19 policymaking. This paper tackles the problem of providing accurate population statistics using such biased datasets. We show that statistical debiasing, although in some cases useful, often fails to improve accuracy. We then propose BiasBuster, a neural network approach that utilizes the correlations between population statistics and location characteristics to provide accurate estimates of population statistics. Extensive experiments on real-world data show that BiasBuster improves accuracy by up to 2 times in general and up to 3 times for underrepresented populations.

In various application domains like transportation, urban planning, and public health, analyzing human mobility, represented as a sequence of consecutive visits (aka trajectories), is crucial for uncovering essential mobility patterns. Current practices often discretize space and time to model trajectory data with sequence-analysis techniques like Transformers and LSTM, but this discretization tends to obscure the intrinsic spatial and temporal characteristics inherent in trajectories. Recent work shows the effectiveness of modeling trajectories directly in continuous space and time using the spatiotempo-ral point process (STPP). However, these approaches often assume that all observed trajectories originate from a single underlying dynamic. In reality, real-world trajectories exhibit varying dynamics or moving patterns. We hypothesize that grouping trajectories governed by similar dynamics into clusters before trajectory modeling could enhance modeling effectiveness. Thus, we present a novel approach that simultaneously models trajectories in continuous space and time using STPP while clustering them. Our method leverages a variational Expectation-Maximization (EM) framework to iteratively improve the learning of trajectory dynamics and refine cluster assignments within a single training phase. Extensive tests on synthetic and real-world data demonstrate its effectiveness in clustering and modeling trajectories.

Real-world datasets are often incomplete due to data collection cost, privacy considerations or as a side effect of data integration/preparation. We focus on answering aggregate queries on such datasets, where data incompleteness causes the answers to be inaccurate. To address this problem, assuming typical relational data, existing work generates synthetic data to complete the database, a challenging task, especially in the presence of bias in observed data. Instead, we propose a paradigm shift by learning to directly estimate query answers, circumventing the difficult data generation step. Our approach, dubbed NeuroComplete, learns to answer queries in three steps. First, NeuroComplete generates a set of queries for which accurate answers can be computed given the incomplete dataset. Next, it embeds queries in a feature space, through which each query is effectively represented with the portion of the database that contributes to the query answer. Finally, it trains a neural network in a supervised learning fashion: both query features (input) and correct answers (labels) are known. The learned model generates accurate answers to new queries at test time, exploiting the generalizability of the learned model in the embedding space. Extensive experimental results on real datasets show up to 4 times for AVG queries and 10 times for COUNT queries error reduction compared with the state-of-the-art.

Abstract Location-based alerts have gained increasing popularity in recent years, whether in the context of healthcare (e.g., COVID-19 contact tracing), marketing (e.g., location-based advertising), or public safety. However, serious privacy concerns arise when location data are used in clear in the process. Several solutions employ searchable encryption (SE) to achieve secure alerts directly on encrypted locations. While doing so preserves privacy, the performance overhead incurred is high. We focus on a prominent SE technique in the public-key setting–hidden vector encryption, and propose a graph embedding technique to encode location data in a way that significantly boosts the performance of processing on ciphertexts. We show that the optimal encoding is NP-hard, and we provide three heuristics that obtain significant performance gains: gray optimizer, multi-seed gray optimizer and scaled gray optimizer. Furthermore, we investigate the more challenging case of dynamic alert zones, where the area of interest changes over time. Our extensive experimental evaluation shows that our solutions can significantly improve computational overhead compared to existing baselines.

Forecasting the number of visits to Points-of-Interest (POI) in an urban area is critical for planning and decision making in various application domains, from urban planning and transportation management to public health and social studies. Although this forecasting problem can be formulated as a multivariate time-series forecasting task, current approaches cannot fully exploit the ever-changing multi-context correlations among POIs. Therefore, we propose Busyness Graph Neural Network (BysGNN), a temporal graph neural network designed to learn and uncover the underlying multi-context correlations between POIs for accurate visit forecasting. Unlike other approaches where only time-series data is used to learn a dynamic graph, BysGNN utilizes all contextual information and time-series data to learn an accurate dynamic graph representation. By incorporating all contextual, temporal, and spatial signals, we observe a significant improvement in our forecasting accuracy over state-of-the-art forecasting models in our experiments with real-world datasets across the United States.

Accessing realistic human movements (aka trajectories) is essential for many application domains, such as urban planning, transportation, and public health. However, due to privacy and commercial concerns, real-world trajectories are not readily available, giving rise to an important research area of generating synthetic but realistic trajectories. Inspired by the success of deep neural networks (DNN), data-driven methods learn the underlying human decision-making mechanisms and generate synthetic trajectories by directly fitting real-world data. However, these DNN-based approaches do not exploit people's moving behaviors (e.g., work commute, shopping purpose), significantly influencing human decisions during the generation process. This paper proposes MBP-GAIL, a novel framework based on generative adversarial imitation learning that synthesizes realistic trajectories that preserve moving behavior patterns in real data. MBP-GAIL models temporal dependencies by Recurrent Neural Networks (RNN) and combines the stochastic constraints from moving behavior patterns and spatial constraints in the learning process. Through comprehensive experiments, we demonstrate that MBP-GAIL outperforms state-of-the-art methods and can better support decision making in trajectory simulations.

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.

Human mobility data is useful for various applications in urban planning, transportation, and public health, but collecting and sharing real-world trajectories can be challenging due to privacy and data quality issues. To address these problems, recent research focuses on generating synthetic trajectories, mainly using generative adversarial networks (GANs) trained by real-world trajectories. In this paper, we hypothesize that by explicitly capturing the modality of transportation (e.g., walking, biking, driving), we can generate not only more diverse and representative trajectories for different modalities but also more realistic trajectories that preserve the geographical density, trajectory, and transition level properties by capturing both cross-modality and modality-specific patterns. Towards this end, we propose a Clustering-based Sequence Generative Adversarial Network (CSGAN) that simultaneously clusters the trajectories based on their modalities and learns the essential properties of real-world trajectories to generate realistic and representative synthetic trajectories. To measure the effectiveness of generated trajectories, in addition to typical density and trajectory level statistics, we define several new metrics for a comprehensive evaluation, including modality distribution and transition probabilities both globally and within each modality. Our extensive experiments with real-world datasets show the superiority of our model in various metrics over state-of-the-art models.

In the last decade or so, fairness in AI has received widespread attention, both within the scientific community and the general media. Researchers have made significant progress towards fairer AI, with work exploring everything from statistical definitions of fairness for individual and group fairness to fairness constraints and algorithms for debiasing models and datasets. Given the nascent nature of the field, however, progress in the space has been haphazard. For work in fair-AI to have as much real-world impact as possible, we need to take a step back and gauge the gaps and which research questions need urgent attention. This work analyzes where the field is currently and proposes more focused questions and new research areas within fair AI.

Several "data-for-good" projects [1, 5, 12] initiated by major companies (e.g., Meta, Google) release to the public spatio-temporal datasets to benefit COVID-19 spread modeling [17, 47, 64] and understand human mobility [14, 24]. Most often, spatio-temporal data are provided in the form of snapshot high resolution population density information, where the released statistics capture population counts in small areas for short time periods. Since high resolution is required for utility (e.g., in modeling COVID hotspots) privacy risks are elevated. To prevent malicious actors from using the data to infer sensitive details about individuals, the released datasets must be first sanitized. Typically, [1, 5, 7, 12], differential privacy (DP) is employed as protection model, due to its formal protection guarantees that prevent an adversary to learn whether a particular individual's data has been included in the release or not.

Range aggregate queries (RAQs) are an integral part of many real-world applications, where, often, fast and approximate answers for the queries are desired. Recent work has studied answering RAQs using machine learning (ML) models, where a model of the data is learned to answer the queries. However, there is no theoretical understanding of why and when the ML based approaches perform well. Furthermore, since the ML approaches model the data, they fail to capitalize on any query specific information to improve performance in practice. In this paper, we focus on modeling "queries" rather than data and train neural networks to learn the query answers. This change of focus allows us to theoretically study our ML approach to provide a distribution and query dependent error bound for neural networks when answering RAQs. We confirm our theoretical results by developing NeuroSketch, a neural network framework to answer RAQs in practice. Extensive experimental study on real-world, TPC-benchmark and synthetic datasets show that NeuroSketch answers RAQs multiple orders of magnitude faster than state-of-the-art and with better accuracy.

Bike-sharing systems, where people rent bikes typically for last-mile commuting, has gained great popularity in recent years due to the rapid development of mobile networks. Station-based bike-sharing systems have been widely studied in both academia and industry, where problems like bike rental demand prediction and bike redistribution have been discussed. In contrast, not much attention has been paid to the routing algorithms for shared-bike riders. A routing solution consists of two stations, suggesting where to rent and return a bike. Existing routing works generally target a single rider. However, during the rush hours, there often exist routing requests from multiple riders simultaneously, which has not been carefully investigated before. In this paper, we study the routing problem for multiple shared-bike riders with hardness analyses and approximation algorithms. The challenge lies in how to allocate the limited resources (bikes/docks at the stations) among the competing riders. We show that this problem is NP-hard, and thus propose two heuristics. We also propose an optimization technique on routing plan generations, to improve the efficiency of the algorithms. Extensive experiments have been carried out to verify the performance of the proposed algorithms. It turns out that the greedy-based routing algorithm, which has an approximation factor of 1/3, is both effective and efficient.

The analysis of trajectory datasets has numerous applications ranging from urban planning to human mobility understanding, but to protect the privacy of individuals trajectory datasets are rarely released to researchers. And even when they are, they are limited in size and spatio-temporal coverage. To address these issues a number of methods for generating synthetic yet realistic trajectory datasets have been proposed. These existing methods either require a lot of complex parameters to be calibrated (simulators) or rely on existing trajectory datasets (generative models). In this paper, we propose Data-Driven Trajectory Generator, dubbed DDTG, a data-driven, model-free, and parameter-less algorithm for generating realistic synthetic vehicle trajectory datasets. Unlike existing approaches, DDTG relies on aggregate origin-destination and traffic data, both of which are publicly available and free of privacy concerns. Furthermore, we show that our method is orthogonal to the existing approaches with which DDTG can be combined to generate synthetic datasets of higher quality. Our experiments with real-world trajectory and traffic data show that the datasets generated by DDTG follow distributions that are very close to the distributions of real trajectory datasets.

Accurately monitoring the number of individuals inside a building is vital to limiting COVID-19 transmission. Low adoption of contact tracing apps due to privacy concerns has increased pervasiveness of passive digital tracking alternatives. Large arrays of WiFi access points can conveniently track mobile devices on university and industry campuses. The CrowdMap system employed by the University of Southern California enables such tracking by collecting aggregate statistics from connections to access points around campus. However, since these devices can be used to infer the movement of individuals, there is still a significant risk that even aggregate occupancy statistics will violate the location privacy of individuals. We examine the use of Differential Privacy in reporting statistics from this system as measured using point and range count queries. We propose discretization schemes to model the positions of users given only user connections to WiFi access points. Using this information we are able to release accurate counts of occupants in areas of campus buildings such as labs, hallways, and large discussion halls with minimized risk to individual users' privacy.

Fairness in data-driven decision-making studies scenarios where individuals from certain population segments may be unfairly treated when being considered for loan or job applications, access to public resources, or other types of services. In location-based applications, decisions are based on individual whereabouts, which often correlate with sensitive attributes such as race, income, and education. While fairness has received significant attention recently, e.g., in machine learning, there is little focus on achieving fairness when dealing with location data. Due to their characteristics and specific type of processing algorithms, location data pose important fairness challenges. We introduce the concept of spatial data fairness to address the specific challenges of location data and spatial queries. We devise a novel building block to achieve fairness in the form of fair polynomials. Next, we propose two mechanisms based on fair polynomials that achieve individual spatial fairness, corresponding to two common location-based decision-making types: distance-based and zone-based. Extensive experimental results on real data show that the proposed mechanisms achieve spatial fairness without sacrificing utility.

Mobile apps and location-based services generate large amounts of location data. Location density information from such datasets benefits research on traffic optimization, context-aware notifications and public health (e.g., disease spread). To preserve individual privacy, one must sanitize location data, which is commonly done using differential privacy (DP). Existing methods partition the data domain into bins, add noise to each bin and publish a noisy histogram of the data. However, such simplistic modelling choices fall short of accurately capturing the useful density information in spatial datasets and yield poor accuracy. We propose a machine-learning based approach for answering range count queries on location data with DP guarantees. We focus on countering the sources of error that plague existing approaches (i.e., noise and uniformity error) through learning, and we design a neural database system that models spatial data such that density features are preserved, even when DP-compliant noise is added. We also devise a framework for effective system parameter tuning on top of public data, which helps set important system parameters without expending scarce privacy budget. Extensive experimental results on real datasets with heterogeneous characteristics show that our proposed approach significantly outperforms the state of the art.

No abstract available.

No abstract available.

The pervasive deployment of IoT devices along with the advancements in Deep Neural Network (DNN) models have enabled video analytics at the edge, the so-called Edge AI systems, in support of various large smart-city applications such as automatic road damage evaluation and fire detection. Current solutions require the model developer to make the placement decision by manually assigning models to edge devices. However, an Edge AI solution could entail hundreds of mobile edge devices operating in a large geographical region (e.g., installed on vehicles) with various resource capabilities and different DNN models, hence rendering manual placement ineffective. This paper presents alternative methods to automatically place various models on a diverse set of edge devices, considering the geospatial coverage of video data, resource capabilities of edge devices, and the characteristics of the trained models. First, we mathematically formulate the model placement as an optimization problem which is proven to be NP-Hard. We then propose several heuristics to solve it efficiently and evaluate them with a real-world dataset collected along the 165 bus route trajectories in the City of San Francisco. Our placement algorithm yields a higher recall in object detection and is more robust to the uncertainty of the underlying location context, without sacrificing much utilization cost.

Location data are widely used in mobile apps, ranging from location-based recommendations, to social media and navigation. A specific type of interaction is that of location-based alerts, where mobile users subscribe to a service provider (SP) in order to be notified when a certain event occurs nearby. Consider, for instance, the ongoing COVID-19 pandemic, where contact tracing has been singled out as an effective means to control the virus spread. Users wish to be notified if they came in proximity to an infected individual. However, serious privacy concerns arise if the users share their location history with the SP in plaintext. To address privacy, recent work proposed several protocols that can securely implement location-based alerts. The users upload their encrypted locations to the SP, and the evaluation of location predicates is done directly on ciphertexts. When a certain individual is reported as infected, all matching ciphertexts are found (e.g., according to a predicate such as “10 feet proximity to any of the locations visited by the infected patient in the last week”), and the corresponding users notified. However, there are significant performance issues associated with existing protocols. The underlying searchable encryption primitives required to perform the matching on ciphertexts are expensive, and without a proper encoding of locations and search predicates, the performance can degrade a lot. In this paper, we propose a novel method for variable-length location encoding based on Huffman codes. By controlling the length required to represent encrypted locations and the corresponding matching predicates, we are able to significantly speed up performance. We provide a theoretical analysis of the gain achieved by using Huffman codes, and we show through extensive experiments that the improvement compared with fixed-length encoding methods is substantial. © 2021 Copyright held by the owner/author(s).

CrowdMap is an anonymous occupancy monitoring system developed in response to the COVID-19 pandemic. CrowdMap collects, cleans, and visualizes occupancy data derived from connection logs generated by large arrays of Wi-Fi access points. Thus, CrowdMap is a passive digital tracking tool that can be used to reopen buildings safely, as it helps actively manage occupancy limits and identify utilization trends at scale. Occupancy monitoring is possible at various levels of resolution over large spatial (e.g., from individual rooms to entire buildings) and temporal (e.g., from hours to months) extents. The CrowdMap web-based front-end implements powerful spatiotemporal querying and visualization tools to quickly and effectively explore occupancy patterns throughout large campuses. We will demonstrate CrowdMap and its spatiotemporal GUI that was deployed for an entire university campus with data continuously being collected since summer 2020.

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.

With the availability of massive amounts of visual data covering wide geographical regions, various image learning applications have emerged, including classifying the street cleanliness level, detecting forest fires or road hazards. Such applications share similar characteristics as they need to 1) detect specific objects or events (what), 2) associate the detected object with a location (where), and 3) know the time that the event happened (when). Advancements in image-based machine learning (ML) benefit these applications as they can automate the detection of objects of interest. Along with the edge computing (EC) paradigm, the processing cost is offloaded to the devices, hence reducing latency and communication cost. Moreover, sensors on the edge devices (e.g., GPS) enrich the collected data with metadata. However, a shortcoming of existing approaches is that they rely on pre-trained "static" models. Nonetheless, crowdsourced data at diverse locations can be leveraged to iteratively improve the robustness of a model. We refer to the aforementioned strategy as "spatial crowd-based learning".To showcase this class of applications, we present FloraVision, an end-to-end system that integrates ML, crowdsourcing, and EC to automate the detection, mapping, and exploration of California Native Plants. FloraVision implements a pipeline to collect and clean publicly available image data, train a lightweight MobileNet-based classification model, and then deploy the model on mobile devices. It leverages spatial crowd-based learning to iteratively evolve the initial model from crowdsourced data. Its mobile application facilitates detecting plants and mapping their geolocations. Finally, it allows end-users to submit ad hoc spatio-temporal nearest neighbor queries and visualizes the results in an augmented reality user interface. Although our application focuses on plants, several other applications follow similar architectural patterns.

Contact tracing is an essential public health tool for controlling epidemic disease outbreaks such as the COVID-19 pandemic. Digital contact tracing using real-time locations or proximity of individuals can be used to significantly speed up and scale up contact tracing. In this demonstration, we present our system, REACT, for REAl-time Contact Tracing and risk monitoring via privacy-enhanced tracking of users' locations. With privacy enhancement that allows users to control and refine the precision with which their information will be collected and used, REACT will enable: 1) contact tracing of individuals who are exposed to infected cases and identification of hot-spot locations, 2) individual risk monitoring based on the locations they visit and their contact with others. In this paper, we demonstrate the procedure of contact tracing using our application and the utility of contact tracing given the protected locations.

Skyline computation is an increasingly popular query, with broad applicability to many domains. Given the trend to outsource databases, and due to the sensitive nature of the data (e.g., in healthcare), it is essential to evaluate skylines on encrypted datasets. Research efforts acknowledged the importance of secure skyline computation, but existing solutions suffer from several shortcomings: (i) they only provide ad-hoc security; (ii) they are prohibitively expensive; or (iii) they rely on assumptions such as the presence of multiple non-colluding parties in the protocol. Inspired by solutions for secure nearest-neighbors, we conjecture that a secure and efficient way to compute skylines is through result materialization. However, materialization is much more challenging for skylines queries due to large space requirements. We show that pre-computing skyline results while minimizing storage overhead is NP-hard, and we provide heuristics that solve the problem more efficiently, while maintaining storage at reasonable levels. Our algorithms are novel and also applicable to regular skyline computation, but we focus on the encrypted setting where materialization reduces the response time of skyline queries from hours to seconds. Extensive experiments show that we clearly outperform existing work in terms of performance, and our security analysis proves that we obtain a small (and quantifiable) data leakage.

Generating hyper-local news at scale is challenging because publicly available data is not provided at the desired spatial and temporal granularity. Besides, there is a lack of automated analytical and publishing tools. Crosstown Foundry, which is being actively developed and used by engineers and journalists, is a novel data-driven system that leverages a massive multi-modal dataset to generate personalized newsletters for Los Angeles County readers.

Effectively and accurately forecasting the congestion in indoor spaces has become particularly important during the pandemic in order to reduce the risk of exposure to airborne viruses. However, there is a lack of readily available indoor congestion data to train such models. Therefore, in this demo paper we propose EPICGen , an experimental platform for indoor congestion generation to support congestion forecasting in indoor spaces. EPICGen consists of two components: (i) Grid Overlayer , which models the floor plans of buildings; and (ii) Congestion Generator , a realistic indoor congestion generator. We demonstrate EPICGen through an intuitive map-based user interface that enables end-users to customize the parameters of the system and visualize generated datasets.

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).

In this paper, for the first time, we study label propagation in heterogeneous graphs under heterophily assumption. Homophily label propagation (i.e., two connected nodes share similar labels) in homogeneous graph (with same types of vertices and relations) has been extensively studied before. Unfortunately, real-life networks (e.g., social networks) are heterogeneous, they contain different types of vertices (e.g., users, images, and texts) and relations (e.g., friendships and co-tagging) and allow for each node to propagate both the same and opposite copy of labels to its neighbors. We propose a IC-partite label propagation model to handle the mystifying combination of heterogeneous nodes/relations and heterophily propagation. With this model, we develop a novel label inference algorithm framework with update rules in near-linear time complexity. Since real networks change overtime, we devise an incremental approach, which supports fast updates for both new data and evidence (e.g., ground truth labels) with guaranteed efficiency. We further provide a utility function to automatically determine whether an incremental or a re-modeling approach is favored. Extensive experiments on real datasets have verified the effectiveness and efficiency of our approach, and its superiority over the state-of-the-art label propagation methods.

For efficient road maintenance, an automated monitoring system is required to avoid laboriously and time-consuming manual inspection by road administration crews. One potential solution is to utilize image processing-based technologies, especially, as various sources of images have readily been available, e.g., surveillance cameras, in-vehicle cameras, or smartphones. Such image-based solutions enable detecting and classifying road damages. This paper introduces deep learning-based image analysis for road damage detection and classification. Our ensemble learning approaches with test time augmentation were thoroughly evaluated using the 2020 IEEE Big Data Global Road Damage Detection Challenge Dataset. Experimental results show that our approaches achieved an F1 score of up to 0.67, allowing us to win the Challenge.

We aim to find the geographical coordinates of (geolocate) a large number of old building facades extracted from historical photographs. We can acquire the geo-coordinates of some of these facades either through crowdsourcing or exploring their metadata. Using these "seed" buildings and through spatial reasoning within and across the historical pictures, in this paper, we show how we infer the geolocation of the other facades. We propose a probabilistic inference approach that first constructs a graph with facades as nodes and their spatial distances as edges, and then through probabilistic inference on this graph, geolocates the facades. Our experiments show that with 10% of the building geolocated as seed buildings, we can quite accurately geolocate the rest of the buildings in our dataset.

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.

Due to the prevalence of GPS-equipped cameras (e.g., smartphones and surveillance cameras), massive amounts of geo-tagged images capturing urban streets are increasingly being collected. Consequently, many smart city applications have emerged, relying on efficient image search. Such searches include spatial-visual queries in which spatial and visual properties are used in tandem to retrieve similar images to a given query image within a given geographical region. Towards this end, new index structures that organize images based on both spatial and visual properties are needed to efficiently execute such queries. Based on our observation that street images are typically similar in the same spatial locality, index structures for spatial-visual queries can be effectively built on a spatial index (i.e., R*-tree). Therefore, we propose a class of R*-tree indexes, particularly, by associating each node with two separate minimum bounding rectangles (MBR), one for spatial and the other for (dimension-reduced) visual properties of their contained images, and adapting the R*-tree optimization criteria to both property types.

In the public transportation domain, accurate estimation of travel times helps to manage rider expectations as well as to provide a powerful tool for transportation agencies to coordinate the public transport vehicles. Although many statistical and machine learning methods have been proposed to estimate travel times, none of the methods consider utilizing predicted traffic information. Forecasting how congestion is going to evolve is critical for accurate travel time estimations. In this paper, we present DeepTRANS, which incorporates traffic forecasting information to our prior Deep Learning-based Bus Estimated Time of Arrival (ETA) model, increasing its accuracy by 21% in estimating bus travel time.

Real-time outlier detection in data streams has drawn much attention recently as many applications need to be able to detect abnormal behaviors as soon as they occur. The arrival and departure of streaming data on edge devices impose new challenges to process the data quickly in real-time due to memory and CPU limitations of these devices. Existing methods are slow and not memory efficient as they mostly focus on quick detection of inliers and pay less attention to expediting neighbor searches for outlier candidates. In this study, we propose a new algorithm, CPOD, to improve the efficiency of outlier detections while reducing its memory requirements. CPOD uses a unique data structure called "core point" with multi-distance indexing to both quickly identify inliers and reduce neighbor search spaces for outlier candidates. We show that with six real-world and one synthetic dataset, CPOD is, on average, 10, 19, and 73 times faster than M_MCOD, NETS, and MCOD, respectively, while consuming low memory.

Identifying mobility behaviors in rich trajectory data is of great economic and social interest to various applications including urban planning, marketing and intelligence. Existing work on trajectory clustering often relies on similarity measurements that utilize raw spatial and/or temporal information of trajectories. These measures are incapable of identifying similar moving behaviors that exhibit varying spatiotemporal scales of movement. In addition, the expense of labeling massive trajectory data is a barrier to supervised learning models. To address these challenges, we propose an unsupervised neural approach for mobility behavior clustering, called the Deep Embedded TrajEctory ClusTering network (DETECT). DETECT operates in three parts: first it transforms the trajectories by summarizing their critical parts and augmenting them with context derived from their geographical locality (e.g., using POIs from gazetteers). In the second part, it learns a powerful representation of trajectories in the latent space of behaviors, thus enabling a clustering function (such as k-means) to be applied. Finally, a clustering oriented loss is directly built on the embedded features to jointly perform feature refinement and cluster assignment, thus improving separability between mobility behaviors. Exhaustive quantitative and qualitative experiments on two real-world datasets demonstrate the effectiveness of our approach for mobility behavior analyses.

Mobile devices with rich features can record videos, traffic parameters or air quality readings along user trajectories. Although such data may be valuable, users are seldom rewarded for collecting them. Emerging digital marketplaces allow owners to advertise their data to interested buyers. We focus on geo-marketplaces, where buyers search data based on geo-tags. Such marketplaces present significant challenges. First, if owners upload data with revealed geo-tags, they expose themselves to serious privacy risks. Second, owners must be accountable for advertised data, and must not be allowed to subsequently alter geo-tags. Third, such a system may be vulnerable to intensive spam activities, where dishonest owners flood the system with fake advertisements. We propose a geo-marketplace that addresses all these concerns. We employ searchable encryption, digital commitments, and blockchain to protect the location privacy of owners while at the same time incorporating accountability and spam-resilience mechanisms. We implement a prototype with two alternative designs that obtain distinct trade-offs between trust assumptions and performance. Our experiments on real location data show that one can achieve the above design goals with practical performance and reasonable financial overhead.

An isochrone is generally defined as a curve drawn on a map connecting points at which moving objects (e.g., cars) arrive at the same time. Their construction is an important task in many application domains. As an example, in urban planning, isochrones are essential when assessing the placement of public services like hospitals and fire departments. In this study, we formally define the isochrone and reverse isochrone problems, describe our approach to solving them and provide a fully functional system that is capable of visualizing the reachability in various ways. Unlike other studies, our approach is purely data-driven and does not depend on the underlying road network for computing the isochrone. Instead, we focus on directly processing trajectory data. Our system processes two real-world taxi datasets to visualize the reachability of the cities of Seoul and Xi'an. As our experiments show, our approach outperforms the traditional graph-theory techniques while eliminating the expensive need of preprocessing the data.

Several applications in urban planning, ride-sharing or marketing, require access to the location popularity of a geographical area (e.g., city block, city, county) in near real-time and at different resolutions. To conceptualize such an access, imagine a visualization tool to view a heatmap of location popularity of a region on-the-fly as a user interacts seamlessly by zooming in and out. The access method required to enable such a seamless visualization must support: 1) updating the heatmap cells frequently as the raw data (e.g., check-ins) arrives at a high rate in a streaming fashion, and 2) splitting and merging the adjacent cells quickly to support zooming in and out, respectively. This is challenging because the most useful metric for location popularity, location entropy, requires counting the number of unique visits per user, and hence: 1) a large data structure should be maintained and updated per cell, and 2) the adjacent cells must be aggregated/disaggregated quickly while the unique visits are not additive. Due to these challenges, the previous techniques for OLAP cubes, streaming sketches and index structures are not effective. In this paper, we propose a new index structure called MR-Cube that approximates the popularity by maintaining sketches of streamed data per cell, supports time-decay for older visits and aggregates the non-additive location popularity quickly and accurately at different resolutions. We evaluate the accuracy and efficiency of MR-Cube using real-world and synthetic datasets and show its utility for our application.

Continuous outlier detection in data streams is an important topic in data mining and has applications in various domains such as fraud detection, weather analysis, and intrusion detection. The non-stationary characteristic of real-world data streams brings the challenge of updating the outlier detection model in a timely and accurate manner. In this paper, we propose a framework for outlier detection in non-stationary data streams (O-NSD) which detects changes in the underlying data distribution to trigger a model update. We propose an improved distance function between sliding windows which offers a monotonicity property; we develop two accurate change detection algorithms, one of which is parameter-free; and we further propose new evaluation measures that quantify the timeliness of the detected changes. Our extensive experiments with real-world and synthetic datasets show that our change detection algorithms outperform the state-of-the-art solution. In addition, we demonstrate our O-NSD framework with two popular unsupervised outlier classifiers. Empirical results show that our framework offers higher accuracy and requires a much lower running time, compared to retrain-based and incremental update approaches.

Due to the ubiquity of GPS-equipped cameras such as smartphones, more photos are getting automatically tagged with camera locations (referred to as geo-tagged images) so large-scale geo-tagged image datasets are available on the Web. And a significant portion of online images such as travel and surveillance may not be meaningful without their location information. Thus, image localization for untagged images has been studied. However, the point camera location of an image might be quite different from the location of the scene depicted in the image (referred to as scene location) rendering image localization inaccurate. To address this problem, we propose a data-centric framework for image scene localization using a CNN-based classification in three steps. First, the framework provides two mechanisms for constructing a reference image dataset tagged with scene locations. Second, a spatial-visual classification approach organizes a dataset spatially using R-tree to generate a set of geographical regions tightly bounding the image scene locations. Then, we train a classifier based on the classes of images corresponding to the generated regions. Finally, to enhance the classification accuracy, we train a set of hierarchical classification models utilizing the spatial hierarchical structure of the R-tree where the trained models enable learning the visual features of images at different geographical granularities. We evaluate our framework using a geo-tagged image dataset obtained from Google Street View and demonstrate that the utilization of scene locations enables localizing images far more accurately as compared with camera location based localization.

With recent advances in technology, it is feasible to conveniently monitor urban roads using various cameras, such as surveillance cameras, in-vehicle cameras, or smartphones, and recognize their conditions by detecting specific types of road damages in order to plan maintenance resources efficiently based on the identified spots. This paper describes a road damage type detection and classification solution submitted to the IEEE BigData Cup Challenge 2018. Our solution is based on the state-of-the-art deep learning methods for an object detection task. In particular, our approach utilizes an object detection algorithm to detect various types of road damages by training the detector on different image examples categorized into a set of damages defined by Japan Road Association. We evaluated our approach thoroughly using different versions of trained models. Our experiments show that our approach was able to achieve an F1 score up to 0.62.

Ridesharing platforms use dynamic pricing as a means to control the network's supply and demand at different locations and times (e.g., Lyft's Prime Time and Uber's Surge Pricing) to increase revenue. These algorithms only consider the network's current supply and demand only at a ride's origin to adjust the price of the ride. In this work, we show how we can increase the platform's revenue while lowering the prices as compared to state-of-the-art algorithms, by considering the network's future demand. Furthermore, we show if rather than setting the price of a ride only based on the supply and demand at its origin, we use predictive supply and demand at both the ride's origin and destination, we can further increase the platform's overall revenue. Using a real-world data set from New York City, we show our pricing method can increase the revenue by up to 15% while reducing the price of the rides by an average of 5%. Furthermore, we show that our methods are resilient to up to 25% error in future demand prediction.

Forecasting spatially correlated time series data is challenging because of the linear and non-linear dependencies in the temporal and spatial dimensions. Air quality forecasting is one canonical example of such tasks. Existing work, e.g., auto-regressive integrated moving average (ARIMA) and artificial neural network (ANN), either fails to model the non-linear temporal dependency or cannot effectively consider spatial relationships between multiple spatial time series data. In this paper, we present an approach for forecasting short-term PM2.5 concentrations using a deep learning model, the geo-context based diffusion convolutional recurrent neural network, GC-DCRNN. The model describes the spatial relationship by constructing a graph based on the similarity of the built environment between the locations of air quality sensors. The similarity is computed using the surrounding "important" geographic features regarding their impacts to air quality for each location (e.g., the area size of parks within a 1000-meter buffer, the number of factories within a 500-meter buffer). Also, the model captures the temporal dependency leveraging the sequence to sequence encoder-decoder architecture. We evaluate our model on two real-world air quality datasets and observe consistent improvement of 5%-10% over baseline approaches.

With the widespread installation of location-enabled devices on public transportation, public vehicles are generating massive amounts of trajectory data in real time. However, using these trajectory data for meaningful analysis requires careful considerations in storing, managing, processing, and visualizing the data. Using the location data of the Los Angeles Metro bus system, along with publicly available bus schedule data, we conduct a data processing and analyses study to measure the performance of the public transportation system in Los Angeles utilizing a number of metrics including travel-time reliability, on-time performance, bus bunching, and travel-time estimation. We demonstrate the visualization of the data analysis results through an interactive web-based application. The developed algorithms and system provide powerful tools to detect issues and improve the efficiency of public transportation systems.

With spatial crowdsourcing (SC), requesters outsource their spatiotemporal tasks (tasks associated with location and time) to a set of workers, who will perform the tasks by physically traveling to the tasks' locations. However, current solutions require the locations of the workers and/or the tasks to be disclosed to untrusted parties (SC server) for effective assignments of tasks to workers. In this paper we propose a framework for assigning tasks to workers in an online manner without compromising the location privacy of workers and tasks. We perturb the locations of both tasks and workers based on geo-indistinguishability and then devise techniques to quantify the probability of reachability between a task and a worker, given their perturbed locations. We investigate both analytical and empirical models for quantifying the worker-task pair reachability and propose task assignment strategies that strike a balance among various metrics such as the number of completed tasks, worker travel distance and system overhead. Extensive experiments on real-world datasets show that our proposed techniques result in minimal disclosure of task locations and no disclosure of worker locations without significantly sacrificing the total number of assigned tasks.

One crucial task in intelligent transportation systems is estimating the duration of a potential trip given the origin location, destination location as well as the departure time. Most existing approaches for travel time estimation assume that the route of the trip is given, which does not hold in real-world applications since the route can be dynamically changed due to traffic conditions, user preferences, etc. As inferring the path from the origin and the destination can be time-consuming and nevertheless error-prone, it is desirable to perform origin-destination travel time estimation, which aims to predict the travel time without online route information. This problem is challenging mainly due to its limited amount of information available and the complicated spatiotemporal dependency. In this paper, we propose a MUlti-task Representation learning model for Arrival Time estimation (MURAT). This model produces meaningful representation that preserves various trip properties in the real-world and at the same time leverages the underlying road network and the spatiotemporal prior knowledge. Further-more, we propose a multi-task learning framework to utilize the path information of historical trips during the training phase which boosts the performance. Experimental results on two large-scale real-world datasets show that the proposed approach achieves clear improvements over state-of-the-art methods

Reverse k-nearest neighbor (RkNN) queries are prevalent in location-based services to find those locations that have the query point as one of their k nearest neighbors. However, such query requires users to disclose the location of the query point to a service provider who might be untrustworthy. Previous attempts to preserve the privacy of RkNN queries are either based on weaker notions of privacy such as location cloaking or not efficient when k > 1. In this paper, we propose novel solutions based on the private information retrieval (PIR) mechanism to preserve the privacy of RkNN query points. Our solutions include server-side data indexing and client-side query processing methods to facilitate PIR which is an inherently expensive data retrieval mechanism. We experimentally evaluate our approach using real-world datasets and show that it preserves the location privacy of queries with reasonable computation and storage overhead.

Spatial Crowdsourcing (SC) is a novel platform that engages individuals in the act of collecting various types of spatial data. This method of data collection can significantly reduce cost and turnover time and is particularly useful in urban environmental sensing, where traditional means fail to provide fine-grained field data. In this study, we introduce hyperlocal spatial crowdsourcing, where all workers who are located within the spatiotemporal vicinity of a task are eligible to perform the task (e.g., reporting the precipitation level at their area and time). In this setting, there is often a budget constraint, either for every time period or for the entire campaign, on the number of workers to activate to perform tasks. The challenge is thus to maximize the number of assigned tasks under the budget constraint despite the dynamic arrivals of workers and tasks. We introduce a taxonomy of several problem variants, such as budget-per-time-period vs. budget-per-campaign and binary-utility vs. distance-based-utility . We study the hardness of the task assignment problem in the offline setting and propose online heuristics which exploit the spatial and temporal knowledge acquired over time. Our experiments are conducted with spatial crowdsourcing workloads generated by the SCAWG tool, and extensive results show the effectiveness and efficiency of our proposed solutions.

A new platform, termed spatial crowdsourcing (SC), is emerging that enables a requester to commission workers to physically travel to some specified locations to perform a set of spatial tasks (i.e., tasks related to a geographical location and time). For spatial crowdsourcing to scale to millions of workers and tasks, it should be able to efficiently assign tasks to workers, which in turn consists of both matching tasks to workers and computing a schedule for each worker. The current approaches for task assignment in spatial crowdsourcing cannot scale as either task matching or task scheduling will become a bottleneck. Instead, we propose an on-line assignment approach utilizing an auction-based framework where workers bid on every arriving task and the server determines the highest bidder, resulting in splitting the assignment responsibility between workers (for scheduling) and the server (for matching) and thus eliminating all bottlenecks. Through several experiments on both real-world and synthetic datasets, we compare the accuracy and efficiency of our real-time algorithm with state of the art algorithms proposed for similar problems. We show how other algorithms cannot generate as good of an assignment because they fail to manage the dynamism and/or take advantage of the spatiotemporal characteristics of SC.

Due to the availability of large transportation (e.g., road network sensor data) and transportation-related (e.g., pollution, crime) data as well as the ubiquity of car navigation systems, recent route planning techniques need to optimize for multiple criteria (e.g., travel time or distance, utility/value such as safety or attractiveness). In this paper, we introduce a novel problem called Twofold Time-Dependent Arc Orienteering Problem (2TD-AOP), which seeks to find a path from a source to a destination maximizing an accumulated value (e.g., attractiveness of the path) while not exceeding a cost budget (e.g., total travel time). 2TD-AOP has many applications in spatial crowdsourcing, real-time delivery, and online navigation systems (e.g., safest path, most scenic path). Although 2TD-AOP can be framed as a variant of AOP, existing AOP approaches cannot solve 2TD-AOP accurately as they assume that travel-times and values of network edges are constant. However, in real-world the travel-times and values are time-dependent, where the actual travel time and utility of an edge depend on the arrival time to the edge. We first discuss the practicality of this novel problem by demonstrating the benefits of considering time-dependency, empirically. Subsequently, we show that optimal solutions are infeasible (NP-hard) and solutions to the static problem are often invalid (i.e., exceed the cost budget). Therefore, we propose an efficient approximate solution with spatial pruning techniques, optimized for fast response systems. Experiments on a large-scale, fine-grained, real-world road network demonstrate that our approach always produces valid paths, is orders of magnitude faster than any optimal solution with acceptable accumulated value.

Sentiment analysis of disaster-related posts in social media can contribute to the situation awareness and better understanding of the dynamics of disaster events by identifying the polarity of sentiments expressed by the public. However, Even though many sentiment analysis techniques have been developed and available, there are still limitations in reliably using sentiment analysis since there is no dominantly accepted technique in disasters. Taking advantage of existing state-of-the-art sentiment classifiers, this paper proposes a novel framework for geo-spatial sentiment analysis of disaster-related social media data objects. Our framework addresses three types of challenges: the inaccuracy and discrepancy associated with various text and image sentiment classifiers, the geo-sentiment discrepancy among data objects in a local geographical area, and observing diverse sentiments from multimedia data objects (i.e., text and image). The extracted sentiments are aggregated geographically for the purpose of extracting more accurate local regional insights. For the evaluation of the framework, we explored Twitter and Flickr datasets at the time of Hurricane Sandy and Napa Earthquake and showed how our approach can provide a better understanding of disaster events.

Driven by the advances in control engineering, material science and sensor technologies, drones are becoming significantly prevalent in daily life (e.g., event coverage, tourism). Consequently, an unprecedented number of drone videos (or aerial videos) are recorded and consumed. In such a large repository, it is difficult to index and search aerial videos in an unstructured form. However, due to the rich sensor instrumentations of drones, aerial videos can be geotagged (e.g., GPS locations, drone rotation angles) at the acquisition time, providing an opportunity for efficient management of aerial videos by exploiting their corresponding spatial structures. Each aerial video frame can thus be represented as its spatial coverage, termed aerial Field-Of-View (aerial-FOV). This effectively converts a challenging aerial video management problem into a spatial database problem on aerial-FOVs. In this paper, we focus on efficient indexing and querying of aerial-FOVs.

Ride-sharing has the potential of addressing many socioeconomic challenges related to transportation. The rising popularity of ride-sharing platforms (e.g., Uber, Lyft, DiDi) in addition to the emergence of new applications like food delivery and grocery shopping which use a similar platform, calls for an in-depth and detailed evaluation of various aspects of this problem.

With the rapid advancement of mobile devices and crowdsourcing platforms, spatial crowdsourcing has attracted much attention from various research communities. A spatial crowdsourcing system periodically matches a number of locationbased workers with nearby spatial tasks (e.g., taking photos or videos at some specific locations). Previous studies on spatial crowdsourcing focus on task assignment strategies that maximize an assignment score based solely on the available information about workers/tasks at the time of assignment. These strategies can only achieve local optimality by neglecting the workers/tasks that may join the system in a future time. In contrast, in this paper, we aim to improve the global assignment, by considering both present and future (via predictions) workers/tasks. In particular, we formalize a new optimization problem, namely maximum quality task assignment (MQA). The optimization objective of MQA is to maximize a global assignment quality score, under a traveling budget constraint. To tackle this problem, we design an effective grid-based prediction method to estimate the spatial distributions of workers/tasks in the future, and then utilize the predictions to assign workers to tasks at any given time instance. We prove that the MQA problem is NPhard, and thus intractable. Therefore, we propose efficient heuristics to tackle the MQA problem, including MQA greedy and MQA divide-and-conquer approaches, which can efficiently assign workers to spatial tasks with high quality scores and low budget consumptions. Through extensive experiments, we demonstrate the efficiency and effectiveness of our approaches on both real and synthetic datasets.

Due to the recent vast availability of transportation traffic data, major research efforts have been devoted to traffic prediction, which is useful in many applications such as urban planning, traffic management and navigations systems. Current prediction methods that independently train a model per traffic sensor cannot accurately predict traffic in every situation (e.g., rush hours, constructions and accidents) because there may not exist sufficient training samples per sensor for all situations. To address this shortcoming, our core idea is to explore the commonalities of prediction tasks across multiple sensors who behave similarly in a specific traffic situation. Instead of building a model independently per sensor, we propose a Multi-Task Learning (MTL) framework that aims to first automatically identify the traffic situations and then simultaneously build one forecasting model for similar-behaving sensors per traffic situation. The key innovation here is that instead of the straightforward application of MTL where each "task" corresponds to a sensor, we relate each MTL's "task" to a traffic situation. Specifically, we first identify these traffic situations by running clustering algorithms on all sensors' data. Subsequently, to enforce the commonalities under each identified situation, we use the group Lasso regularization in MTL to select a common set of features for the prediction tasks, and we adapt efficient FISTA algorithm with guaranteed convergence rate. We evaluated our methods with a large volume of real-world traffic sensor data; our results show that by incorporating traffic situations, our proposed MTL framework performs consistently better than naively applying MTL per sensor. Moreover, our holistic approach, under different traffic situations, outperforms all the best traffic prediction approaches for a given situation by up to 18% and 30% in short and long term predictions, respectively.

Traffic forecasting is a vital part of intelligent transportation systems. It becomes particularly challenging due to short-term (e.g., accidents, constructions) and long-term (e.g., peak-hour, seasonal, weather) traffic patterns. While most of the previously proposed techniques focus on normal condition forecasting, a single framework for extreme condition traffic forecasting does not exist. To address this need, we propose to take a deep learning approach. We build a deep neural network based on long short term memory (LSTM) units. We apply Deep LSTM to forecast peak-hour traffic and manage to identify unique characteristics of the traffic data. We further improve the model for post-accident forecasting with Mixture Deep LSTM model. It jointly models the normal condition traffic and the pattern of accidents. We evaluate our model on a real-world large-scale traffic dataset in Los Angeles. When trained end-to-end with suitable regularization, our approach achieves 30%–50% improvement over baselines. We also demonstrate a novel technique to interpret the model with signal stimulation. We note interesting observations from the trained neural network.

The turn-by-turn directions provided in existing navigation applications are exclusively derived from underlying road network topology information, i.e., the connectivity of edges to each other. Therefore, the turn-by-turn directions are simplified as metric translation of physical world (e.g. distance/time to turn) to spoken language. Such translation - that ignores human cognition of the geographic space - is often verbose and redundant for the drivers who have knowledge about the geographical areas. In this paper, we study a Personalized RoutE Guidance System dubbed PaRE - with which the goal is to generate more customized and intuitive directions based on user generated content. PaRE utilizes a wealth of user generated historical trajectory data to extract namely "landmarks" (e.g., point of interests or intersections) and frequently visited routes between them from the road network. The extracted information is used to obtain cognitive customized directions for each user. We formalize this task as a problem of finding the optimal partition for a given route that maximizes the familiarity while minimizing the number of segments in the partition, and propose two efficient algorithms to solve it. For empirical study, we apply our solution to both real and synthetic trajectory datasets to evaluate the performance and effectiveness of PaRE.

Crowdsourcing is a new computing paradigm where humans are actively enrolled to participate in the procedure of computing, especially for tasks that are intrinsically easier for humans than for computers. The popularity of mobile computing and sharing economy has extended conventional web-based crowdsourcing to spatial crowdsourcing (SC), where spatial data such as location, mobility and the associated contextual information, plays a central role. In fact, spatial crowdsourcing has stimulated a series of recent industrial successes including Citizen Sensing (Waze), P2P ride-sharing (Uber) and Real-time Online-To-Offline (O2O) services (Instacart and Postmates). In this tutorial, we review the paradigm shift from web-based crowdsourcing to spatial crowdsourcing. We dive deep into the challenges and techniques brought by the unique spatio-temporal characteristics of spatial crowdsourcing. Particularly, we survey new designs in task assignment, quality control, incentive mechanism design and privacy protection on spatial crowdsourcing platforms, as well as the new trend to incorporate crowdsourcing to enhance existing spatial data processing techniques. We also discuss case studies of representative spatial crowdsourcing systems and raise open questions and current challenges for the audience to easily comprehend the tutorial and to advance this important research area.

Traffic incidents and their impacts have been largely studied to improve road safety and to reduce incurred life and economic losses. However, the inaccuracy of incident data collected from transportation agencies, especially the start time, poses a great challenge to traffic incident research. We present INFIT, a system that infers the incident start time utilizing traffic data collected by loop sensors. The core of INFIT is IIG, our newly developed inference algorithm. The key idea is that IIG considers the traffic speed at multiple upstream locations, to mitigate the randomness in traffic data and to distinguish among multiple impact factors. INFIT includes an interactive interface with real-world incident datasets. We demonstrate INFIT with three exploratory use cases and show the usefulness of our inference algorithms.

Real-time ride-sharing, which enables on-the-fly matching between riders and drivers (even en-route), is an important problem due to its environmental and societal benefits. With the emergence of many ride-sharing platforms (e.g., Uber and Lyft), the design of a scalable framework to match riders and drivers based on their various constraints while maximizing the overall profit of the platform becomes a distinguishing business strategy.

Location entropy (LE) is a popular metric for measuring the popularity of various locations (e.g., points-of-interest). Unlike other metrics computed from only the number of (unique) visits to a location, namely frequency, LE also captures the diversity of the users' visits, and is thus more accurate than other metrics. Current solutions for computing LE require full access to the past visits of users to locations, which poses privacy threats. This paper discusses, for the first time, the problem of perturbing location entropy for a set of locations according to differential privacy. The problem is challenging because removing a single user from the dataset will impact multiple records of the database; i.e., all the visits made by that user to various locations. Towards this end, we first derive non-trivial, tight bounds for both local and global sensitivity of LE, and show that to satisfy ε-differential privacy, a large amount of noise must be introduced, rendering the published results useless. Hence, we propose a thresholding technique to limit the number of users' visits, which significantly reduces the perturbation error but introduces an approximation error. To achieve better utility, we extend the technique by adopting two weaker notions of privacy: smooth sensitivity (slightly weaker) and crowd-blending (strictly weaker). Extensive experiments on synthetic and real-world datasets show that our proposed techniques preserve original data distribution without compromising location privacy.

Finding influential people in a society has been the focus of social studies for decades due to its numerous applications, such as viral marketing or spreading ideas and practices. A critical first step is to quantify the amount of influence an individual exerts on another, termed pairwise influence. Early social studies had to confine themselves to surveys and manual data collections for this purpose; more recent studies have exploited web data (e.g., blogs). In this paper, for the first time, we utilize people's movement in the real world (aka spatiotemporal data) to derive pairwise influence. We first define followship to capture the phenomenon of an individual visiting a real-world location (e.g., restaurant) due the influence of another individual who has visited that same location in the past. Subsequently, we coin the term spatial influence as the concept of inferring pairwise influence from spatiotemporal data by quantifying the amount of followship influence that an individual has on others. We then propose the Temporal and Locational Followship Model (TLFM) to estimate spatial influence, in which we study three factors that impact followship: the time delay between the visits, the popularity of the location, and the inherent coincidences in individuals' visiting behaviors. We conducted extensive experiments using various real-world datasets, which demonstrate the effectiveness of our TLFM model in quantifying spatial influence.

Real-time traffic prediction from high-fidelity spatiotemporal traffic sensor datasets is an important problem for intelligent transportation systems and sustainability. However, it is challenging due to the complex topological dependencies and high dynamism associated with changing road conditions. In this paper, we propose a Latent Space Model for Road Networks (LSM-RN) to address these challenges holistically. In particular, given a series of road network snapshots, we learn the attributes of vertices in latent spaces which capture both topological and temporal properties. As these latent attributes are time-dependent, they can estimate how traffic patterns form and evolve. In addition, we present an incremental online algorithm which sequentially and adaptively learns the latent attributes from the temporal graph changes. Our framework enables real-time traffic prediction by 1) exploiting real-time sensor readings to adjust/update the existing latent spaces, and 2) training as data arrives and making predictions on-the-fly. By conducting extensive experiments with a large volume of real-world traffic sensor data, we demonstrate the superiority of our framework for real-time traffic prediction on large road networks over competitors as well as baseline graph-based LSM's.

In this paper, we study a route summarization framework for Personalized Navigation dubbed PerNav - with which the goal is to generate more intuitive and customized turn-by-turn directions based on user generated content. The turn-by-turn directions provided in the existing navigation applications are exclusively derived from underlying road network topology information i.e., the connectivity of nodes to each other. Therefore, the turn-by-turn directions are simplified as metric translation of physical world (e.g. distance/time to turn) to spoken language. Such translation- that ignores human cognition about the geographic space- is often verbose and redundant for the drivers who have knowledge about the geographical areas. PerNav utilizes wealth of user generated historical trajectory data to extract namely "landmarks" (e.g., point of interests or intersections) and frequently visited routes between them from the road network. Then this extracted information is used to obtain cognitive turn-by-turn directions customized for each user.

Discovering latent structures in spatial data is of critical importance to understanding the user behavior of location-based services. In this paper, we study the problem of geographic segmentation of spatial data, which involves dividing a collection of observations into distinct geo-spatial regions and uncovering abstract correlation structures in the data. We introduce a novel, Latent Poisson Factor (LPF) model to describe spatial count data. The model describes the spatial counts as a Poisson distribution with a mean that factors over a joint item-location latent space. The latent factors are constrained with weak labels to help uncover interesting spatial dependencies. We study the LPF model on a mobile app usage data set and a news article readership data set. We empirically demonstrate its effectiveness on a variety of prediction tasks on these two data sets.

Continuous outlier detection in data streams has important applications in fraud detection, network security, and public health. The arrival and departure of data objects in a streaming manner impose new challenges for outlier detection algorithms, especially in time and space efficiency. In the past decade, several studies have been performed to address the problem of distance-based outlier detection in data streams (DODDS), which adopts an unsupervised definition and does not have any distributional assumptions on data values. Our work is motivated by the lack of comparative evaluation among the state-of-the-art algorithms using the same datasets on the same platform. We systematically evaluate the most recent algorithms for DODDS under various stream settings and outlier rates. Our extensive results show that in most settings, the MCOD algorithm offers the superior performance among all the algorithms, including the most recent algorithm Thresh_LEAP.

Many applications deal with moving object datasets, e.g., mobile phone social networking, scientific simulations, and ride-sharing services. These applications need to handle a tremendous number of spatial objects that continuously move and execute spatial queries to explore their surroundings. To manage such update-heavy workloads, several throwaway index structures have recently been proposed, where a static index is rebuilt periodically from scratch rather than updated incrementally. It has been shown that throwaway indices outperform specialized moving-object indices that maintain location updates incrementally. However, throwaway indices suffer from scalability due to their single-server design and the only distributed throwaway index (D-MOVIES), extension of a centralized approach, does not scale out as the number of servers increases, especially during query processing phase.

The advent of geolocation technologies has generated unprecedented rich datasets of people’s location information at a very high fidelity. These location datasets can be used to study human behavior; for example, social studies have shown that people who are seen together frequently at the same place and same time are most probably socially related. In this article, we are interested in inferring these social connections by analyzing people’s location information; this is useful in a variety of application domains, from sales and marketing to intelligence analysis. In particular, we propose an entropy-based model (EBM) that not only infers social connections but also estimates the strength of social connections by analyzing people’s co-occurrences in space and time. We examine two independent methods: diversity and weighted frequency , through which co-occurrences contribute to the strength of a social connection. In addition, we take the characteristics of each location into consideration in order to compensate for cases where only limited location information is available. We also study the role of location semantics in improving our computation of social strength. We develop a parallel implementation of our algorithm using MapReduce to create a scalable and efficient solution for online applications. We conducted extensive sets of experiments with real-world datasets including both people’s location data and their social connections, where we used the latter as the ground truth to verify the results of applying our approach to the former. We show that our approach is valid across different networks and outperforms the competitors.

With the rise of mobile technologies (e.g., smart phones, wearable technologies) and location-aware Internet browsers, a massive amount of spatial data is being collected since such tools allow users to geo-tag user content (e.g., photos, tweets). Meanwhile, cloud computing providers such as Amazon and Microsoft allow users to lease computing resources where users are charged based on the amount of time they reserve each server, with no consideration of utilization. One key factor that affects server utilization is partitioning method especially in data-driven location-based services. Because if the data partitions are not accessed, the servers storing them remain idle but the user is still charged. Whereas, existing spatial data partitioning techniques aim to 1) cluster spatially close data objects to minimize disk I/O and 2) create equi-sized partitions. On the contrary, the objective is different for cloud given the current pricing models. In this paper, we propose a novel cost-efficient partitioning method for spatial data where an increase in the servers' utilizations yields less number of servers to support the same workload, thus saving cost. Extensive experiments on Amazon EC2 infrastructure demonstrate that our approach is efficient and reduces the cost by up to 40%.

Efficient and thorough data collection and its timely analysis are critical for disaster response and recovery in order to save peoples lives during disasters. However, access to comprehensive data in disaster areas and their quick analysis to transform the data to actionable knowledge are challenging. With the popularity and pervasiveness of mobile devices, crowdsourcing data collection and analysis has emerged as an effective and scalable solution. This paper addresses the problem of crowdsourcing mobile videos for disasters by identifying two unique challenges of 1) prioritizing visualdata collection and transmission under bandwidth scarcity caused by damaged communication networks and 2) analyzing the acquired data in a timely manner. We introduce a new crowdsourcing framework for acquiring and analyzing the mobile videos utilizing fine granularity spatial metadata of videos for a rapidly changing disaster situation. We also develop an analytical model to quantify the visual awareness of a video based on its metadata and propose the visual awareness maximization problem for acquiring the most relevant data under bandwidth constraints. The collected videos are evenly distributed to off-site analysts to collectively minimize crowdsourcing efforts for analysis. Our simulation results demonstrate the effectiveness and feasibility of the proposed framework.

Due to the availability of large historical and real-time traffic data, car navigation systems are becoming more and more advanced in predicting the travel time for various routes and finding the fastest route from a source to a destination given a start time. The most advanced of these systems predict the travel time of the routes, given past traffic patterns in order to find the best route. However, the best route is not necessarily a reliable route as well, i.e., the route with the least variation in possible travel times. The most reliable route is desirable when traveling with a deadline, e.g., to reach a flight at the airport or to arrive on time for an important meeting. To find the most reliable route, one needs to predict the probability distribution of travel times for that route. This in turn requires the estimation of travel time probability distributions for each and every link, given a link-entrance-time. In this paper we address the problem of computing these link travel time distributions. To the best of our knowledge there has not been any study on how to compute probability distributions for links (/edges) in road networks. We show how this first step can affect the accuracy of the travel time distribution over the entire route. Our final challenge is to evaluate the result of different approaches in computing these travel time distributions, which is difficult because the reported travel time is not a single value but a probabilistic distribution highly depending on the trip start time. We thus propose a statistical test that enables us to evaluate these outcomes.

A new platform, termed spatial crowdsourcing, is emerging which enables a requester to commission workers to physically travel to some specified locations to perform a set of spatial tasks (i.e., tasks related to a geographical location and time). The current approach is to formulate spatial crowdsourcing as a matching problem between tasks and workers; hence the primary objective of the existing solutions is to maximize the number of matched tasks. Our goal is to solve the spatial crowdsourcing problem in the presence of multiple workers where we optimize for both travel cost and the number of completed tasks, while taking the tasks' expiration times into consideration. The challenge is that the solution should be a mixture of task-matching and task-scheduling, which are fundamentally different. In this paper, we show that a baseline approach that performs a task-matching first, and subsequently schedules the tasks assigned per worker in a following phase, does not perform well. Hence, we add a third phase in which we iterate back to the matching phase to improve the assignment per the output of the scheduling phase, and thus further improves the quality of matching and scheduling. Even though this 3-phase approach generates high quality results, it is very slow and does not scale. Hence, to scale our algorithm to large number of workers and tasks, we propose a Bisection-based framework which recursively divides all the workers and tasks into different partitions such that assignment and scheduling can be performed locally in a much smaller and promising space. Our experiments show that this approach is three orders of magnitude faster than the 3-phase approach while it only sacrifices 4% of the results' quality.

With the proliferation of local services and GPS-enabled mobile phones, reverse spatial-keyword Nearest Neighbor queries are becoming an important type of query. Given a service object (e.g., shop) q as the query, which has a location and a text description, we return customers such that q is one of top-k spatial-keyword relevant service objects for each result customer. Existing algorithms for answering reverse nearest neighbor queries cannot be used for processing reverse spatial-keyword nearest neighbor queries due to the additional text information. To design efficient algorithms, for the first time we theoretically analyze an ideal case, which minimizes the object/index node accesses, for processing reverse spatial-keyword nearest neighbor queries. Under the derived theoretical guidelines, we design novel search algorithms for efficiently answering the queries. Empirical studies show that the proposed algorithms offer scalability and are orders of magnitude faster than existing methods for reverse spatial-keyword nearest neighbor queries.

Traditional route planning problems mainly focus on finding the shortest path considering the travel distance or time. In this paper, we aim to find the most scenic path that offers the most beautiful sceneries on the arcs of a path while the total travel cost (distance or time) is within a user-specified budget. This is a challenging problem as the optimization objective is to maximize the value of the path (i.e., its scenic value) instead of minimizing its cost (distance or time). The problem can be formulated as a variant of the Arc Orienteering Problem (AOP), which is a well-known NP-hard combinatorial optimization problem. Due to the fast response-time requirements of interactive mobile and online applications (e.g., within 300 milliseconds) and the large scale of real-world road networks, existing heuristic algorithms for AOP fail to solve the most scenic road problem. Therefore, unlike the existing approaches for AOP where they treat the road network as a traditional graph in which all-pair distances are pre-computed a priori, in this work, we treat the road network as a spatial network, utilizing the techniques from the field of spatial database: ellipse pruning and spatial indexing. Experiments on two real-world datasets demonstrate the efficiency and accuracy of our proposed algorithms, which can achieve over 95% accuracy within 300 milliseconds on large-scale datasets (over 100K network nodes).

Social relationships between people, e.g., whether they are friends with each other, can be inferred by observing their behaviors in the real world. Thanks to the popularity of GPS-enabled mobile devices or online services, a large amount of high-resolution location data becomes available for such inference studies. However, due to the sensitivity of location data and user privacy concerns, those studies cannot be largely carried out on individually contributed data without privacy guarantees. Furthermore, we observe that the actual location may not be needed for social relationship studies, but rather the fact that two people met and some statistical properties about their meeting locations, which can be computed in a private manner. In this paper, we envision an extensible framework, dubbed Privacy-preserving Location Analytics and Computation Environment (PLACE), which enables social relationship studies by analyzing individually generated location data. PLACE utilizes an untrusted server and computes several building blocks to support various social relationship studies, without disclosing location information to the server and other untrusted parties. We present PLACE with three example social relationship studies which utilize four privacy-preserving blocks with encryption and differential privacy primitives. The successful realization of PLACE will facilitate private location data acquisition from individual devices, thanks to the strong privacy guarantees, and will enable a wide range of applications.

Spatial Crowdsourcing (SC) is a novel and transformative platform that engages individuals, groups and communities in the act of collecting, analyzing, and disseminating environmental, social and other spatio-temporal information. SC outsources a set of spatio-temporal tasks to a set of workers, i.e., individuals with mobile devices that perform the tasks by physically traveling to specified locations of interest. Protecting location privacy is an important concern in SC, as an adversary with access to individual whereabouts can infer sensitive details about a person (e.g., health status, political views). Due to the challenging nature of protecting worker privacy in SC, solutions for this problem are quite complex, and require tuning of several parameters to obtain satisfactory results. In this paper, we propose PrivGeoCrowd, a toolbox for interactive visualization and tuning of SC private task assignment methods. This toolbox is useful for several real-world entities that are involved in SC, such as: mobile phone operators that want to sanitize datasets with worker locations, spatial task requesters, and SC-service providers that match workers to tasks.

Recently spatial crowd sourcing was introduced as a natural extension to traditional crowd sourcing allowing for tasks to have a geospatial component, i.e., A task can only be performed if a worker is physically present at the location of the task. The problem of assigning spatial tasks to workers in a spatial crowd sourcing system can be formulated as a weighted bipartite b-matching graph problem that can be solved optimally by existing methods for the minimum cost maximum flow problem. However, these methods are still too complex to run repeatedly for an online system, especially when the number of incoming workers and tasks increases. Hence, we propose a class of approaches that utilizes an online partitioning method to reduce the problem space across a set of cloud servers to construct independent bipartite graphs and solve the assignment problem in parallel. Our approaches solve the spatial task assignment approximately but competitive to the exact solution. We experimentally verify that our approximate approaches outperform the centralized and Map Reduce version of the exact approach with acceptable accuracy and thus suitable for online spatial crowd sourcing at scale.

Graph partitioning has attracted considerable attention due to its high practicality for real-world applications. It is particularly relevant to social networks because it enables the grouping of users into communities for market analysis and advertising purposes. In this paper, we introduce RMGP, a type of real-time multi-criteria graph partitioning for social networks that groups the users based on their connectivity and their similarity to a set of input classes. We consider RMGP as an on-line task, which may be frequently performed for different query parameters (e.g., classes). In order to overcome the serious performance issues associated with the large social graphs found in practice, we develop solutions based on a game theoretic framework. Specifically, we consider each user as a player, whose goal is to find the class that optimizes his objective function. We propose algorithms based on best-response dynamics, analyze their properties, and show their efficiency and effectiveness on real datasets under centralized and decentralized scenarios.

An unprecedented number of user-generated videos (UGVs) are currently being collected by mobile devices, however, such unstructured data are very hard to index and search. Due to recent development, UGVs can be geo-tagged, e.g., GPS locations and compass directions, at the acquisition time at a very fine spatial granularity. Ideally, each video frame can be tagged by the spatial extent of its coverage area, termed Field-Of-View (FOV). In this paper, we focus on the challenges of spatial indexing and querying of FOVs in a large repository. Since FOVs contain both location and orientation information, and their distribution is non-uniform, conventional spatial indexes (e.g., R-tree, Grid) cannot index them efficiently. We propose a class of new R-tree-based index structures that effectively harness FOVs' camera locations, orientations and view-distances, in tandem, for both filtering and optimization. In addition, we present novel search strategies and algorithms for efficient range and directional queries on FOVs utilizing our indexes. Our experiments with a real-world dataset and a large synthetic video dataset (over 30 years worth of videos) demonstrate the scalability and efficiency of our proposed indexes and search algorithms and their superiority over the competitors.

The widespread use of GPS-enabled devices have led to a number of emerging applications that require monitoring and querying a large number of moving objects, such as in location-based services, mobile phone social networking, UAV surveillance, and car navigation systems. In such applications, indexes for moving objects must support queries efficiently and also cope with frequent updates. In this paper, we propose a cloud-based throwaway index structure, dubbed ToSS-it, where we generate the index from scratch in a short period of time rather than updating it with every location change of the moving objects. ToSS-it employs inter-node and intra-node multi-core parallelism paradigm to rapidly construct a distributed Voronoi Diagram. ToSS-it scales out by using a voronoi partitioning technique that minimizes the network message exchanges between the nodes (i.e., The major overhead in parallel generation of Voronoi Diagrams), and scales up since it fully exploits the multi-core CPUs available on each server. As a comparison point, with the state-of-the-art cloud-based spatial index structure (RT-CAN), if at least 7% of the objects are moving and issue updates to the index, it is faster to recreate ToSS-it from scratch than updating RT-CAN.

Spatial Crowdsourcing (SC) is a transformative platform that engages individuals, groups and communities in the act of collecting, analyzing, and disseminating environmental, social and other spatio-temporal information. The objective of SC is to outsource a set of spatio-temporal tasks to a set of workers , i.e., individuals with mobile devices that perform the tasks by physically traveling to specified locations of interest. However, current solutions require the workers, who in many cases are simply volunteering for a cause, to disclose their locations to untrustworthy entities. In this paper, we introduce a framework for protecting location privacy of workers participating in SC tasks. We argue that existing location privacy techniques are not sufficient for SC, and we propose a mechanism based on differential privacy and geocasting that achieves effective SC services while offering privacy guarantees to workers. We investigate analytical models and task assignment strategies that balance multiple crucial aspects of SC functionality, such as task completion rate, worker travel distance and system overhead. Extensive experimental results on real-world datasets show that the proposed technique protects workers' location privacy without incurring significant performance metrics penalties.

Outsourcing spatial databases to the cloud provides an economical and flexible way for data owners to deliver spatial data to users of location-based services. However, in the database outsourcing paradigm, the third-party service provider is not always trustworthy, therefore, ensuring spatial query integrity is critical. In this paper, we propose an efficient road network k-nearest-neighbor query verification technique which utilizes the network Voronoi diagram and neighbors to prove the integrity of query results. Unlike previous work that verifies k-nearest-neighbor results in the Euclidean space, our approach needs to verify both the distances and the shortest paths from the query point to its kNN results on the road network. We evaluate our approach on real-world road networks together with both real and synthetic points of interest datasets. Our experiments run on Google Android mobile devices which communicate with the service provider through wireless connections. The experiment results show that our approach leads to compact verification objects (VO) and the verification algorithm on mobile devices is efficient, especially for queries with low selectivity.

Geographic objects associated with descriptive texts are becoming prevalent, justifying the need for spatial-keyword queries that consider both locations and textual descriptions of the objects. Specifically, the relevance of an object to a query is measured by spatial-textual similarity that is based on both spatial proximity and textual similarity. In this article, we introduce the Reverse Spatial-Keyword k -Nearest Neighbor (RSK k NN) query, which finds those objects that have the query as one of their k -nearest spatial-textual objects. The RSK k NN queries have numerous applications in online maps and GIS decision support systems. To answer RSK k NN queries efficiently, we propose a hybrid index tree, called IUR-tree (Intersection-Union R-tree) that effectively combines location proximity with textual similarity. Subsequently, we design a branch-and-bound search algorithm based on the IUR-tree. To accelerate the query processing, we improve IUR-tree by leveraging the distribution of textual description, leading to some variants of the IUR-tree called Clustered IUR-tree (CIUR-tree) and combined clustered IUR-tree (C 2 IUR-tree), for each of which we develop optimized algorithms. We also provide a theoretical cost model to analyze the efficiency of our algorithms. Our empirical studies show that the proposed algorithms are efficient and scalable.

In this paper, we propose a new framework for opinion summarization based on sentence selection. Our goal is to assist users to get helpful opinion suggestions from reviews by only reading a short summary with few informative sentences, where the quality of summary is evaluated in terms of both aspect coverage and viewpoints preservation. More specifically, we formulate the informative-sentence selection problem in opinion summarization as a community-leader detection problem, where a community consists of a cluster of sentences towards the same aspect of an entity. The detected leaders of the communities can be considered as the most informative sentences of the corresponding aspect, while informativeness of a sentence is defined by its informativeness within both its community and the document it belongs to. Review data from six product domains from Amazon.com are used to verify the effectiveness of our method for opinion summarization.

Histograms have been extensively used for selectivity estimation by academics and have successfully been adopted by database industry. However, the estimation error is usually large for skewed distributions and biased attributes, which are typical in real-world data. Therefore, we propose effective models to quantitatively measure bias and selectivity based on information entropy. These models together with the principles of maximum entropy are then used to develop a class of entropy-based histograms. Moreover, since entropy can be computed incrementally, we present the incremental variations of our algorithms that reduce the complexities of the histogram construction from quadratic to linear. We conducted an extensive set of experiments with both synthetic and real-world datasets to compare the accuracy and efficiency of our proposed techniques with many other histogram-based techniques, showing the superiority of the entropy-based approaches for both equality and range queries.

With the progress of mobile devices and wireless broadband, a new eMarket platform, termed spatial crowdsourcing is emerging, which enables workers (aka crowd) to perform a set of spatial tasks (i.e., tasks related to a geographical location and time) posted by a requester. In this paper, we study a version of the spatial crowd-sourcing problem in which the workers autonomously select their tasks, called the worker selected tasks (WST) mode. Towards this end, given a worker, and a set of tasks each of which is associated with a location and an expiration time, we aim to find a schedule for the worker that maximizes the number of performed tasks. We first prove that this problem is NP-hard. Subsequently, for small number of tasks, we propose two exact algorithms based on dynamic programming and branch-and-bound strategies. Since the exact algorithms cannot scale for large number of tasks and/or limited amount of resources on mobile platforms, we also propose approximation and progressive algorithms. We conducted a thorough experimental evaluation on both real-world and synthetic data to compare the performance and accuracy of our proposed approaches.

With the abundance and ubiquity of mobile devices, a new class of applications, called spatial crowdsourcing, is emerging, which enables spatial tasks (i.e., tasks related to a location) assigned to and performed by human workers. However, one of the major challenges with spatial crowdsourcing is how to verify the validity of the results provided by workers, when the workers are not trusted equally. To tackle this problem, we assume every worker has a reputation score, which states the probability that the worker performs a task correctly. Moreover, we define a confidence level for every spatial task, which states that the answer to the given spatial task is only accepted if its confidence is higher than a certain threshold. Thus, the problem we are trying to solve is to maximize the number of spatial tasks that are assigned to a set of workers while satisfying the confidence levels of those tasks. Note that a unique aspect of our problem is that the optimal assignment of tasks heavily depends on the geographical locations of workers and tasks. This means that every spatial task should be assigned to enough number of workers such that their aggregate reputation satisfies the confidence of the task. Consequently, an exhaustive approach needs to compute the aggregate reputation score (using a typical decision fusion aggregation mechanism, such as voting) for all possible subsets of the workers, which renders the problem complex (we show it is NP-hard). Subsequently, we propose a number of heuristics and utilizing real-world and synthetic data in extensive sets of experiments we show that we can achieve close to optimal performance with the cost of a greedy approach, by exploiting our problem's unique characteristics.

The advances in mobile computing and social networking services enable people to probe the dynamics of a city. In this paper, we address the problem of detecting and describing traffic anomalies using crowd sensing with two forms of data, human mobility and social media. Traffic anomalies are caused by accidents, control, protests, sport events, celebrations, disasters and other events. Unlike existing traffic-anomaly-detection methods, we identify anomalies according to drivers' routing behavior on an urban road network. Here, a detected anomaly is represented by a sub-graph of a road network where drivers' routing behaviors significantly differ from their original patterns. We then try to describe the detected anomaly by mining representative terms from the social media that people posted when the anomaly happened. The system for detecting such traffic anomalies can benefit both drivers and transportation authorities, e.g., by notifying drivers approaching an anomaly and suggesting alternative routes, as well as supporting traffic jam diagnosis and dispersal. We evaluate our system with a GPS trajectory dataset generated by over 30,000 taxicabs over a period of 3 months in Beijing, and a dataset of tweets collected from WeiBo, a Twitter-like social site in China. The results demonstrate the effectiveness and efficiency of our system.

The advances in sensor technologies enable real-time collection of high-fidelity spatiotemporal data on transportation networks of major cities. In this paper, using two real-world transportation datasets: 1) incident data and 2) traffic data, we address the problem of predicting and quantifying the impact of traffic incidents. Traffic incidents include any non-recurring events on road networks, including accidents, weather hazard, road construction or work zone closures. By analyzing archived incident data, we classify incidents based on their features (e.g., time, location, type of incident). Subsequently, we model the impact of each incident class on its surrounding traffic by analyzing the archived traffic data at the time and location of the incidents. Consequently, in real-time, if we observe a similar incident (from real-time incident data), we can predict and quantify its impact on the surrounding traffic using our developed models. This information, in turn, can help drivers to effectively avoid impacted areas in real-time. To be useful for such real-time navigation application, and unlike current approaches, we study the dynamic behavior of incidents and model the impact as a quantitative time varying spatial span. In addition to utilizing incident features, we improve our classification approach further by analyzing traffic density around the incident area and the initial behavior of the incident. We evaluated our approach with very large traffic and incident datasets collected from the road networks of Los Angeles County and the results show that we can improve our baseline approach, which solely relies on incident features, by up to 45%.

The ubiquity of mobile devices and the popularity of location-based-services have generated, for the first time, rich datasets of people's location information at a very high fidelity. These location datasets can be used to study people's behavior - for example, social studies have shown that people, who are seen together frequently at the same place and at the same time, are most probably socially related. In this paper, we are interested in inferring these social connections by analyzing people's location information, which is useful in a variety of application domains from sales and marketing to intelligence analysis. In particular, we propose an entropy-based model (EBM) that not only infers social connections but also estimates the strength of social connections by analyzing people's co-occurrences in space and time. We examine two independent ways: diversity and weighted frequency, through which co-occurrences contribute to social strength. In addition, we take the characteristics of each location into consideration in order to compensate for cases where only limited location information is available. We conducted extensive sets of experiments with real-world datasets including both people's location data and their social connections, where we used the latter as the ground-truth to verify the results of applying our approach to the former. We show that our approach outperforms the competitors.

With the popularity of location-based services and the abundant usage of smart phones and GPS-enabled devices, the necessity of outsourcing spatial data has grown rapidly over the past few years. Meanwhile, the fast arising trend of cloud storage and cloud computing services has provided a flexible and cost-effective platform for hosting data from businesses and individuals, further enabling many location-based applications. Nevertheless, in this database outsourcing paradigm, the authentication of the query results at the client remains a challenging problem. In this paper, we focus on the Outsourced Spatial Database (OSDB) model and propose an efficient scheme, called VN-Auth, which allows a client to verify the correctness and completeness of the result set. Our approach is based on neighborhood information derived from the Voronoi diagram of the underlying spatial data set and can handle fundamental spatial query types, such as k nearest neighbor and range queries, as well as more advanced query types like reverse k nearest neighbor, aggregate nearest neighbor, and spatial skyline. We evaluated VN-Auth based on real-world data sets using mobile devices (Google Droid smart phones with Android OS) as query clients. Compared to the current state-of-the-art approaches (i.e., methods based on Merkle Hash Trees), our experiments show that VN-Auth produces significantly smaller verification objects and is more computationally efficient, especially for queries with low selectivity.

Outsourcing spatial databases, including both road networks and points of interest, to a third party Cloud service provider has attracted much attention from individual and business data owners. With popularity of mobile devices, providing instant and reliable location-based services to smartphones and tablets has been a major means of delivering spatial data to real-world users. Therefore, ensuring spatial query integrity in database outsourcing paradigms is critical. In this paper, we propose a novel road network k-nearest-neighbor query verification technique which utilizes the network Voronoi diagrams and neighbors to prove the integrity of the query result. Unlike previous work that verifies k-nearest-neighbor results in the Euclidean space, our approach verifies both the distances and the shortest paths from the query point to its kNN result on the road network.

With the ubiquity of mobile devices, spatial crowdsourcing is emerging as a new platform, enabling spatial tasks (i.e., tasks related to a location) assigned to and performed by human workers. In this paper, for the first time we introduce a taxonomy for spatial crowdsourcing. Subsequently, we focus on one class of this taxonomy, in which workers send their locations to a centralized server and thereafter the server assigns to every worker his nearby tasks with the objective of maximizing the overall number of assigned tasks. We formally define this maximum task assignment (or MTA) problem in spatial crowdsourcing, and identify its challenges. We propose alternative solutions to address these challenges by exploiting the spatial properties of the problem space. Finally, our experimental evaluations on both real-world and synthetic data verify the applicability of our proposed approaches and compare them by measuring both the number of assigned tasks and the travel cost of the workers.

For the first time, real-time high-fidelity spatiotemporal data on transportation networks of major cities have become available. This gold mine of data can be utilized to learn about traffic behavior at different times and locations, potentially resulting in major savings in time and fuel, the two important commodities of 21st century. As a first step towards the utilization of this data, in this paper, we study the real-world data collected from Los Angeles County transportation network in order to incorporate the data's intrinsic behavior into a time-series mining technique to enhance its accuracy for traffic prediction. In particular, we utilized the spatiotemporal behaviors of rush hours and events to perform a more accurate prediction of both short-term and long-term average speed on road-segments, even in the presence of infrequent events (e.g., accidents). Our result shows that taking historical rush-hour behavior we can improve the accuracy of traditional predictors by up to 67% and 78% in short-term and long-term predictions, respectively. Moreover, we can incorporate the impact of an accident to improve the prediction accuracy by up to 91%.

With the advent of reliable positioning technologies and prevalence of location-based services, it is now feasible to accurately study the propagation of items such as infectious viruses, sensitive information pieces, and malwares through a population of moving objects, e.g., individuals, mobile devices, and vehicles. In such application scenarios, an item passes between two objects when the objects are sufficiently close (i.e., when they are, so-called, in contact ), and hence once an item is initiated, it can penetrate the object population through the evolving network of contacts among objects, termed contact network . In this paper, for the first time we define and study reachability queries in large (i.e., disk-resident) contact datasets which record the movement of a (potentially large) set of objects moving in a spatial environment over an extended time period. A reachability query verifies whether two objects are "reachable" through the evolving contact network represented by such contact datasets. We propose two contact-dataset indexes that enable efficient evaluation of such queries despite the potentially humongous size of the contact datasets. With the first index, termed ReachGrid , at the query time only a small necessary portion of the contact network which is required for reachability evaluation is constructed and traversed. With the second approach, termed ReachGraph , we precompute reachability at different scales and leverage these precalculations at the query time for efficient query processing. We optimize the placement of both indexes on disk to enable efficient index traversal during query processing. We study the pros and cons of our proposed approaches by performing extensive experiments with both real and synthetic data. Based on our experimental results, our proposed approaches outperform existing reachability query processing techniques in contact networks by 76% on average.

As the popularity of social networks is continuously growing, collected data about online social activities is becoming an important asset enabling many applications such as target advertising, sale promotions, and marketing campaigns. Although most social interactions are recorded through online activities, we believe that social experiences taking place offline in the real physical world are equally if not more important. This paper introduces a geo-social model that derives social activities from the history of people's movements in the real world, i.e., who has been where and when. In particular, from spatiotemporal histories, we infer real-world co-occurrences - being there at the same time - and then use co-occurrences to quantify social distances between any two persons. We show that straightforward measures either do not scale or may overestimate the strength of social connections by giving too much weight to coincidences.

The problem of point-to-point shortest path computation in spatial networks is extensively studied with many approaches proposed to speed-up the computation. Most of the existing approaches make the simplifying assumption that weights (e.g., travel-time) of the network edges are constant. However, with real-world spatial networks the edge travel-times are time-dependent, where the arrival-time to an edge determines the actual travel-time of the edge. With this paper, we study the applicability of existing shortest path algorithms to real-world large time-dependent spatial networks. In addition, we evaluate the importance of considering time-dependent edge travel-times for route planning in spatial networks. We show that time-dependent shortest path computation can reduce the travel-time by 36% on average as compared to the static shortest path computation that assumes constant edge travel-times.

With the popularity of location-based services and the abundant usage of smart phones and GPS enabled devices, the necessity of outsourcing spatial data has grown rapidly over the past few years. Nevertheless, in the database outsourcing paradigm, the authentication of the query results at the client remains a challenging problem. In this paper, we focus on the Outsourced Spatial Database (OSDB) model and propose an efficient scheme, called VN-Auth, that allows a client to verify the correctness and completeness of the result set. Our approach can handle both k nearest neighbor (kNN) and range queries, and is based on neighborhood information derived by the Voronoi diagram of the underlying spatial dataset. Specifically, upon receiving a query result, the client can verify its integrity by examining the signatures and exploring the neighborhood of every object in the result set. Compared to the current state-of-the-art approaches (i.e., methods based on Merkle hash trees), VN-Auth produces significantly smaller verification objects (VO) and is more computationally efficient, especially for queries with low selectivity.

It is cost-effective for data owners to publicize their spatial databases via database outsourcing; however, data privacy and query integrity are major challenges. In this demonstration, we implemented the INTACT (spatial query INTegrity AssuranCe framework for locaTion-based services) framework on the iPhone and the .NET Framework that protects data privacy using space encryption and ensures query integrity via audit queries.

The growing popularity of online Earth visualization tools and geo-realistic games and the availability of high resolution terrain data have motivated a new class of queries to the interests of the GIS and spatial database community: spatial queries (e.g., kNN) over land surface. However, the fundamental challenges that restrict the applicability of these studies to real world applications are the prohibitive time complexity and storage overhead to precompute the shortest surface paths. In this paper, for the first time, we propose an approximate solution to address both challenges and allow browsing the shortest surface paths in O () time, where N is the size of the terrain. With this method, the time and space requirements for an exhaustive all-pair pre-computation have been reduced from O(N 3) to O(N 1.5) and O(N) respectively. The substantial savings in both time and storage are gained by taking advantage of the fact that the O(N 2) surface paths only deviate from approximate straight lines at O ( ) points, termed rough vertices. As a result, we propose a linear time shortest surface path computation algorithm between two arbitrary vertices and a linear size storage structure, which captures all the shortest surface paths between any pair of vertices. We experimentally verified the applicability and scalability of the proposed methods with large real world and synthetic data sets and showed that accuracy higher than 97 % can be obtained in most cases.

In this paper, we present TransDec, an end-to-end-data-driven system which enables spatiotemporal queries in transportation systems with dynamic, real-time and historical data. TransDec fuses a variety of real-world spatiotemporal datasets including massive traffic sensor data, trajectory data, transportation network data, and point-of-interest data to create an immersive and realistic virtual model of a transportation system. With TransDec, we address the challenges in visualization, monitoring, querying and analysis of dynamic and large-scale transportation data in both time and space.

Microsoft SQL Server spatial libraries contain several components that handle geometrical and geographical data types. With advances in geo-sensing technologies, there has been an increasing demand for geospatial streaming applications. Microsoft SQL Server StreamInsight ( StreamInsight , for brevity) is a platform for developing and deploying streaming applications that run continuous queries over high-rate streaming events. With its extensibility infrastructure, StreamInsight enables developers to integrate their domain expertise within the query pipeline in the form of user defined modules. This demo utilizes the extensibility infrastructure in Microsoft StreamInsight to leverage its continuous query processing capabilities in two directions. The first direction integrates SQL spatial libraries into the continuous query pipeline of StreamInsight. StreamInsight provides a well-defined temporal model over incoming events while SQL spatial libraries cover the spatial properties of events to deliver a solution for spatiotemporal stream query processing. The second direction extends the system with an analytical refinement and prediction layer. This layer analyzes historical data that has been accumulated and summarized over the years to refine, smooth and adjust the current query output as well as predict the output in the near future. The demo scenario is based on transportation data in Los Angeles County.

A very important class of spatial queries consists of nearest-neighbor (NN) query and its variations. Many studies in the past decade utilize R-trees as their underlying index structures to address NN queries efficiently. The general approach is to use R-tree in two phases. First, R-tree's hierarchical structure is used to quickly arrive to the neighborhood of the result set. Second, the R-tree nodes intersecting with the local neighborhood ( Search Region ) of an initial answer are investigated to find all the members of the result set. While R-trees are very efficient for the first phase, they usually result in the unnecessary investigation of many nodes that none or only a small subset of their including points belongs to the actual result set. On the other hand, several recent studies showed that the Voronoi diagrams are extremely efficient in exploring an NN search region, while due to lack of an efficient access method, their arrival to this region is slow. In this paper, we propose a new index structure, termed VoR-Tree that incorporates Voronoi diagrams into R-tree, benefiting from the best of both worlds. The coarse granule rectangle nodes of R-tree enable us to get to the search region in logarithmic time while the fine granule polygons of Voronoi diagram allow us to efficiently tile or cover the region and find the result. Utilizing VoR-Tree, we propose efficient algorithms for various Nearest Neighbor queries, and show that our algorithms have better I/O complexity than their best competitors.

Harnessing the potential of today's ever growing and dynamic geospatial data requires the development of novel visual analysis interfaces, tools and technologies. In this paper, we present GeoDec, a generic framework capable of supporting queries and visualizations of real-world spatio-temporal data sets. We show, for various locations and applications, how our innovative Query Driven Design enhances the visual analysis of geospatial data through the interactive manipulation of queries and the temporal navigation of these query results.

We envision participatory texture documentation (PTD) as a process in which a group of users (dedicated individuals and/or general public) with camera-equipped mobile phones participate in collaborative collection of urban texture information. PTD enables inexpensive, scalable and high resolution urban texture documentation. We have proposed to implement PTD in two steps [10]. At the first step, termed viewpoint selection, a minimum number of points in the urban environment are selected from which the texture of the entire urban environment (the part visible to cameras) can be collected/captured. At the second step, called viewpoint assignment, the selected viewpoints are assigned to the participating users such that given a limited number of users with various constraints (e.g., restricted available time) users can collectively capture the maximum amount of texture information within a limited time interval. In this paper, we focus on the viewpoint assignment problem. We first prove that this problem is an NP-hard problem, and therefore, the optimal solution for viewpoint assignment fails to scale as the extent of the urban environment and the number of participating users grow. Subsequently, we propose a family of heuristics for efficient viewpoint assignment to reduce the assignment running time while ensuring an almost complete texture collection. We study, profile and verify our proposed solutions comparatively by both rigorous analysis and extensive experiments.

As geo-realistic rendering of land surfaces is becoming commonplace in geographical information systems (GIS), games and online Earth visualization platforms, a new type of k Nearest Neighbor (kNN) queries, "surface" k Nearest Neighbor (skNN) queries, has emerged and been investigated recently, which extends the traditional kNN queries to a constrained third dimension (i.e., land surface). All existing techniques, however, assume a static environment, limiting their utility in emerging applications (e.g., Location-based Services) where objects move. In this paper, for the first time, we propose two exact methods that can continuously answer skNN queries in a highly dynamic environment which allows for arbitrary movements of data objects. The first method, inspired by the existing techniques in monitoring kNN in road networks [7] maintains an analogous counterpart of the Dijkstra Expansion Tree on land surface, called Surface Expansion Tree (SE-Tree). However, we show the concept of expansion tree for land surface does not work as SE-tree suffers from intrinsic defects: it is fat and short, and hence does not improve the query efficiency. Therefore, we propose a superior approach that partitions SE-Tree into hierarchical chunks of pre-computed surface distances, called Angular Surface Index Tree (ASI-Tree). Unlike SE-tree, ASI-Tree is a well balanced thin and tall tree. With ASI-Tree, we can continuously monitor skNN queries efficiently with low CPU and I/O overheads by both speeding up the surface shortest path computations and localizing the searches. We experimentally verify the applicability and evaluate the efficiency of the proposed methods with both real world and synthetic data sets. ASI-Tree consistently and significantly outperforms SE-Tree in all cases.

In this article, we first introduce the concept of Spatial Skyline Queries (SSQ). Given a set of data points P and a set of query points Q , each data point has a number of derived spatial attributes each of which is the point's distance to a query point. An SSQ retrieves those points of P which are not dominated by any other point in P considering their derived spatial attributes. The main difference with the regular skyline query is that this spatial domination depends on the location of the query points Q . SSQ has application in several domains such as emergency response and online maps. The main intuition and novelty behind our approaches is that we exploit the geometric properties of the SSQ problem space to avoid the exhaustive examination of all the point pairs in P and Q . Consequently, we reduce the complexity of SSQ search from O (| P | 2 | Q |) to O (| S | 2 | C | + √| P |), where | S | and | C | are the solution size and the number of vertices of the convex hull of Q , respectively. Considering Euclidean distance, we propose two algorithms, B 2 S 2 and VS 2 , for static query points and one algorithm, VCS 2 , for streaming Q whose points change location over time (e.g., are mobile). VCS 2 exploits the pattern of change in Q to avoid unnecessary recomputation of the skyline and hence efficiently perform updates. We also propose two algorithms, SNS 2 and VSNS 2 , that compute the spatial skyline with respect to the network distance in a spatial network database. Our extensive experiments using real-world datasets verify that both R-tree-based B 2 S 2 and Voronoi-based VS 2 outperform the best competitor approach in terms of both processing time and I/O cost. Furthermore, their output computed based on Euclidean distance is a good approximation of the spatial skyline in network space. For accurate computation of spatial skylines in network space, our experiments showed the superiority of VSNS 2 over SNS 2 .

In this paper, we outline our efficient sample-based approach to answer fixed-precision approximate continuous aggregate queries in peer-to-peer databases. We describe our approach in the context of Digest, a two-tier system we have developed for correct and efficient query answering by sampling. With Digest, at the top tier we develop a query evaluation engine that uses the samples collected from the peer-to-peer database to continually estimate the running result of the approximate continuous aggregate query with guaranteed precision. For efficient query evaluation, we propose an extrapolation algorithm that predicts the evolution of the running result and adapts the frequency of the continual sampling occasions accordingly to avoid redundant samples. We also introduce a repeated sampling algorithm that draws on the correlation between the samples at successive sampling occasions and exploits linear regression to minimize the number of the samples derived at each occasion. At the bottom tier, we introduce a distributed sampling algorithm for random sampling (uniform and nonuniform) from peer-to-peer databases with arbitrary network topology and tuple distribution. Our sampling algorithm is based on the Metropolis Markov Chain Monte Carlo method that guarantees randomness of the sample with arbitrary small variation difference with the desired distribution, while it is comparable to optimal sampling in sampling cost/time. We evaluate the efficiency of Digest via simulation using real data.

Trajectory segmentation is the process of partitioning a given trajectory into a small number of homogeneous segments w.r.t. some criteria. Conventional segmentation techniques only focus on the spatial features of the movement and could lead to spatially homogeneous segments but with presumably dissimilar temporal structures. Furthermore, trajectories could be over-segmented in the presence of outliers. In this paper, we propose a family of three trajectory segmentation methods that takes into account both geospatial and temporal structures of movement for the segmentation and is also robust with respect to time-referenced spatial outliers. The effectiveness of our methods is empirically demonstrated over three real-world datasets.

Mobile devices equipped with positioning capabilities (e.g., GPS) can ask location-dependent queries to Location Based Services (LBS). To protect privacy, the user location must not be disclosed. Existing solutions utilize a trusted anonymizer between the users and the LBS. This approach has several drawbacks: (i) All users must trust the third party anonymizer, which is a single point of attack. (ii) A large number of cooperating, trustworthy users is needed. (iii) Privacy is guaranteed only for a single snapshot of user locations; users are not protected against correlation attacks (e.g., history of user movement).

The class of k Nearest Neighbor (kNN) queries is frequently used in geospatial applications. Many studies focus on processing kNN in Euclidean and road network spaces. Meanwhile, with the recent advances in remote sensory devices that can acquire detailed elevation data, the new geospatial applications heavily operate on this third dimension, i.e., land surface. Hence, for the field of databases to stay relevant, it should be able to efficiently process spatial queries given this constrained third dimension. However, online processing of the surface k Nearest Neighbor (skNN) queries is quite challenging due to the huge size of land surface models which renders any accurate distance computation on the surface extremely slow. In this paper, for the first time, we propose an index structure on land surface that enables exact and fast responses to skNN queries. Two complementary indexing schemes, namely Tight Surface Index (TSI) and Loose Surface Index (LSI), are constructed and stored collectively on a single novel data structure called Surface Index R-tree (SIR-tree). With those indexes, we can process skNN query efficiently by localizing the search and minimizing the invocation of the costly surface distance computation and hence incurring low I/O and computation costs. Our algorithm does not need to know the value of k a priori and can incrementally expand the search region using SIR-tree and report the query result progressively. It also reports the exact shortest surface paths to the query results. We show through experiments with real world data sets that our algorithm has better performance than the competitors in both efficiency and accuracy.

A frequent query in geospatial planning and decision making domains (e.g., emergency response, data acquisition, street cleaning), is to find an optimal traversal plan (OTP) that traverses an entire area (e.g., a city) by navigating through all its streets. The optimality is defined in terms of the time it takes to complete the traversal. This time depends on the number of times each street segment is traversed as well as the navigation time such as the time spent on changing direction at each intersection.

In this paper, we propose DBSampler, a query execution mechanism to answer "partial selection" queries in peerto- peer databases. A partial selection query is an arbitrary selection query that is satisfied with a fraction \in of the results; a universal operation with applications in database tuning, query optimization and approximate query processing in peer-to-peer databases. DBSampler is based on an epidemic dissemination algorithm. We model the epidemic dissemination as a percolation problem and by rigorous percolation analysis tune DBSampler per-query and on-thefly to answer partial queries correctly and efficiently. We verify the efficiency of DBSampler in terms of query cost and query time via extensive simulation.

Recent sensor networks research has produced a class of data storage and query processing techniques called data-centric storage that leverages locality-preserving distributed indexes to efficiently answer multi-dimensional range and range-aggregate queries. These distributed indexes offer a rich design space of a) logical decompositions of sensor relation schema into indexes, as well as b) physical mappings of these indexes onto sensors. In this paper, we explore this space for energy-efficient data organizations (logical and physical mappings of tuples and attributes to sensor nodes) and devise purely local query optimization techniques for processing queries that span such decomposed relations.

Multivariate time series (MTS) data sets are common in-various multimedia, medical and financial application domains. These applications perform several data-analysis operations on large number of MTS data sets such as similarity searches, feature-subset-selection, clustering and classifications. Correlation-based techniques, such as principal component analysis (PCA), have proven to improve the efficiency of many of the above-mentioned data-analysis operations on MTS, which implies that the correlation coefficients concisely represent the original MTS data. However, if the statistical properties (e.g., variance) of MTS data change over time dimension, i.e., MTS data is non-stationary, the correlation coefficients are not stable. In this paper, we propose to utilize the stationarity of the MTS data sets, in order to represent the original MTS data more stably, as well as concisely with the correlation coefficients. That is, before performing any correlation-based data analysis, we first executes the stationarity test to decide whether the MTS data is stationary or not, i.e., whether the correlation is stable or not. Subsequently, for a non-stationary MTS data set, we difference it to render the data set stationary. Even though our approach is general, to focus the discussion we describe our approach within the context of our previously proposed technique for MTS similarity search. In order to show the validity of our approach, we performed several experiments on four real-world data sets. The results show that the performance of our similarity search technique have significantly improved in terms of precision/recall.

Online Scientific Applications (OSA) require statistical analysis of large multidimensional datasets. Towards this end, we have designed and developed a data storage and retrieval system, called ProDA, which deploys wavelet transform and provides fast approximate answers with progressively increasing accuracy in support of the OSA queries. ProDA employs a standard web-service infrastructure to enable remote users to interact with their data. These web-services enable wavelet transformation of large multidimensional datasets as well as inserting, updating, and exact, approximate and progressive querying of these datasets in the wavelet domain. We demonstrate the features of ProDA on a massive atmospheric dataset provided to us by NASA/JPL.

The Discrete Wavelet Transform is a proven tool for a wide range of database applications. However, despite broad acceptance, some of its properties have not been fully explored and thus not exploited, particularly for two common forms of multidimensional decomposition. We introduce two novel operations for wavelet transformed data, termed SHIFT and SPLIT, based on the properties of wavelet trees, which work directly in the wavelet domain. We demonstrate their significance and usefulness by analytically proving six important results in four common data maintenance scenarios, i.e., transformation of massive datasets, appending data, approximation of data streams and partial data reconstruction, leading to significant I/O cost reduction in all cases. Furthermore, we show how these operations can be further improved in combination with the optimal coefficient-to-disk-block allocation strategy. Our exhaustive set of empirical experiments with real-world datasets verifies our claims.

Feature subset selection (FSS) is a known technique to preprocess the data before performing any data mining tasks, e.g., classification and clustering. FSS provides both cost-effective predictors and a better understanding of the underlying process that generated the data. We propose a family of novel unsupervised methods for feature subset selection from multivariate time series (MTS) based on common principal component analysis, termed CLeVer. Traditional FSS techniques, such as recursive feature elimination (RFE) and Fisher criterion (FC), have been applied to MTS data sets, e.g., brain computer interface (BCI) data sets. However, these techniques may lose the correlation information among features, while our proposed techniques utilize the properties of the principal component analysis to retain that information. In order to evaluate the effectiveness of our selected subset of features, we employ classification as the target data mining task. Our exhaustive experiments show that CLeVer outperforms RFE, FC, and random selection by up to a factor of two in terms of the classification accuracy, while taking up to 2 orders of magnitude less processing time than RFE and FC.

Peer-to-peer Data Networks (PDNs) are large-scale, self-organizing, distributed query processing systems. Familiar examples of PDN are peer-to-peer file-sharing networks, which support exact-match search queries to locate user-requested files. In this paper, we formalize the more general problem of similarity-search in PDNs, and propose a family of distributed access methods, termed Small-World Access Methods (SWAM), for efficient execution of various similarity-search queries, namely exact-match, range, and k-nearest-neighbor queries. Unlike its predecessors, i.e., LH* and DHTs, SWAM does not control the assignment of data objects to PDN nodes; each node autonomously stores its own data. Besides, SWAM supports all similarity-search queries on multiple attributes. SWAM guarantees that the query object will be found (if it exists in the network) in average time logarithmically proportional to the network size. Moreover, once the query object is found, all the similar objects would be in its proximate network neighborhood and hence enabling efficient range and k-nearest-neighbor queries.

Scalable storage architectures allow for the addition of disks to increase storage capacity and/or bandwidth. In its general form, disk scaling also refers to disk removals when either capacity needs to be conserved or old disk drives are retired. Assuming random placement of blocks on multiple nodes of a continuous media server, our optimization objective is to redistribute a minimum number of media blocks after disk scaling. This objective should be met under two restrictions. First, uniform distribution and hence a balanced load should be ensured after redistribution. Second, the redistributed blocks should be retrieved at the normal mode of operation in one disk access and through low complexity computation. We propose a technique that meets the objective, while we prove that it also satisfies both restrictions. The SCADDAR approach is based on using a series of REMAP functions which can derive the location of a new block using only its original location as a basis.

Users of decision support system typically submit batches of range-sum queries simultaneously rather than issuing individual, unrelated queries. We propose a wavelet based technique that exploits T/O sharing across a query batch to evaluate the set of queries progressively and efficiently. The challenge is that now controlling the structure of errors across query results becomes more critical than minimizing error per individual query. Consequently, we define a class of structural error penalty functions and show how they are controlled by our technique Experiments demonstrate that our technique is efficient as an exact algorithm, and the progressive estimates are accurate, even after less than one I/O per query.

There is currently great interest in building information mediators that can integrate information from multiple data sources such as databases or Web sources. The query response time for such mediators is typically quite high, mainly due to the time spent in retrieving data from remote sources. We present an approach for optimizing the performance of information mediators by selectively materializing data. We first present our overall framework for materialization in a mediator environment. The data is materialized selectively. We outline the factors that are considered in selecting data to materialize. We present an algorithm for identifying classes of data to materialize by analyzing one of the factors which is the distribution of user queries. We present results with an implemented version of our optimization system for the Ariadne information mediator, which show the effectiveness of our algorithm in extracting patterns of frequently accessed classes from user queries. We also demonstrate the effectiveness of approach in optimizing mediator performance by materializing such classes.

In multiuser multimedia information systems (e.g., movie-on-demand, digital-editing), scheduling the retrievals of continuous media objects becomes a challenging task. This is because of both intra and inter lobject time dependencies. Intraobject time dependency refers to the real-time display requirement of a continuous media object. Interobject time dependency is the temporal relationships defined among multiple continuous media objects. In order to compose tailored multimedia presentations, a user might define complex time dependencies among multiple continuous media objects with various lengths and display bandwidths. Scheduling the retrieval tasks corresponding to the components of such a presentation in order to respect both inter and intra task time dependencies is the focus of this study. To tackle this task scheduling problem (CRS), we start with a simpler scheduling problem (ARS) where there is no inter task time dependency (e.g., movie-on-demand). Next, we investigate an augmented version of ARS (termed ARS/sup +/) where requests reserve displays in advance (e.g., reservation-based movie-on-demand). Finally, we extend our techniques proposed for ARS and ARS/sup +/ to address the CRS problem. We also provide formal definition of these scheduling problems and proof of their NP-hardness.

Moving sensors refers to an emerging class of data intensive applications that inpacts disciplines such as communication, health-care, scientific applications, etc. These applications consist of a fixed number of sensors that move and produce streams of data as a function of time. They may require the system to match these streams against stored streams to retrieve relevant data (patterns). With communication, for example, a speaking impaired individual might utilize a haptic glove that translates hand signs into written (spoken) words. The glove consists of sensors for different finger joints. These sensors report their location and values as a function of time, producing streams of data. These streams are matched against a repository of spatio-temporal streams to retrieve the corresponding English character or word.The contributions of this study are two fold. First, it introduces a framework to store and retrieve "moving sensors" data. The framework advocates physical data independence and software-reuse. Second, we investigate alternative representations for storage and retrieve of data in support of query processing. We quantify the tradeoff associated with these alternatives using empirical data RoboCup soccer matches.

Due to the large amount of the collected scientific data, it is becoming increasingly difficult for scientists to comprehend and interpret the available data. Moreover typical queries on these data sets are in the nature of identifying (or visualizing) trends and surprises at a selected sub-region in multiple levels of abstraction rather than identifying information about a specific data point. The authors propose a versatile wavelet-based data structure, 2D TSA-tree (Trend and Surprise Abstractions Tree), to enable efficient multi-level trend detection on spatial data at different levels. We show how 2D TSA-tree can be utilized efficiently for sub-region selections. Moreover, 2D TSA-tree can be utilized to precompute the reconstruction error and retrieval time of a data subset in advance in order to allow the user to trade off accuracy for response time (or vice versa) at query time. Finally, when the storage space is limited, our 2D Optimal TSA-tree saves on storage by storing only a specific optimal subset of the tree. To demonstrate the effectiveness of our proposed methods, we evaluated our 2D TSA-tree using real and synthetic data. Our results show that our method outperformed other methods (DFT and SVD) in terms of accuracy, complexity and scalability.

An adaptive probe-based optimization technique is developed and demonstrated in the context of an Internet-based distributed database environment. More and more common are database systems, which are distributed across servers communicating via the Internet where a query at a given site might require data from remote sites. Optimizing the response time of such queries is a challenging task due to the unpredictability of server performance and network traffic at the time of data shipment; this may result in the selection of an expensive query plan using a static query optimizer. We constructed an experimental setup consisting of two servers running the same DBMS connected via the Internet. Concentrating on join queries, we demonstrate how a static query optimizer might choose an expensive plan by mistake. This is due to the lack of a priori knowledge of the run-time environment, inaccurate statistical assumptions in size estimation, and neglecting the cost of remote method invocation. These shortcomings are addressed collectively by proposing a probing mechanism. Furthermore, we extend our mechanism with an adaptive technique that detects sub-optimality of a plan during query execution and attempts to switch to the cheapest plan while avoiding redundant work and imposing little overhead. An implementation of our run-time optimization technique for join queries was constructed in the Java language and incorporated into an experimental setup. The results demonstrate the superiority of our probe-based optimization over a static optimization.

Although much has been written about various information integration technologies, little has been said regarding how to combine these technologies together to build an entire application. We demonstrate TheaterLoc, an information integration application that allows users to retrieve information about theatres and restaurants for various U.S. cities, including an interactive map depicting their relative locations. The data retrieved by TheaterLoc comes from five distinct heterogeneous and distributed sources. The enabling technology used to achieve the integration includes: the Ariadne information mediator, a Web site wrapper learning tool, the Theseus execution system, and a mechanism for distributed spatial query planning. Our system is novel because it demonstrates how "virtual applications" can be rapidly built from a set of integration tools and existing online data sources.

The shape of an object is an important feature for image and multimedia similarity retrieval. However, as a consequence of uncertainty, shape representation techniques may sometimes work well only in certain environments, and their performance may depend crucially on the quality of the technique used to represent the shapes. In this study, we focus on shape-based object retrieval under various uncertainty scenarios and conduct a comparison study on four techniques. We measure the effectiveness of the similarity retrieval of the four different shape representation methods (in terms of recall and precision) under the following situations: (1) in the presence of noise in the database, (2) when the exact corner points are unknown, and (3) factoring in the human perception of similarity. Our results show that the similarity retrieval accuracy of our method [MBC-TPVAS (Minimum Bounding Circle with Touch-Point Vertex-Angle Sequence)] is better than that of the other methods under uncertainty and discrepancies.

We introduce a novel wavelet based tree structure, termed TSA-tree, which improves the efficiency of multi-level trend and surprise queries on time sequence data. With the explosion of scientific observation data conceptualized as time sequences, we are facing the challenge of efficiently storing, retrieving and analyzing this data. Frequent queries on this data set are to find trends (e.g., global warming) or surprises (e.g., undersea volcano eruption) within the original time series. The challenge, however is that these trend and surprise queries are needed at different levels of abstractions. To support these multi-level trend and surprise queries, sometimes a huge subset of raw data needs to be retrieved and processed. To expedite this process, we utilize our TSA-tree. Each node of the TSA-tree contains pre-computed trends and surprises at different levels. A wavelet transform is used recursively to construct TSA nodes. As a result, each node of TSA tree is readily available for visualization of trends and surprises. In addition, the size of each node is significantly smaller than that of the original time series, resulting in faster I/O operations. However a limitation of TSA-tree is that its size is larger than the original time series. To address this shortcoming, first we prove that the storage space required to store the optimal subtree of TSA-tree (OTSA-tree) is no more than that required to store the original time series without losing any information. Next, we propose two alternative techniques to reduce the size of the OTSA-tree even further while maintaining an acceptable query precision as compared to querying the original time sequences. Utilizing real and synthetic time sequence databases, we compare our techniques with some well known algorithms.

Many applications require the storage and management of large databases of 2D objects. One of the important functionalities required by all of these applications is the capability to find objects in a database that match a given object. We concentrate on whole matching queries, in which a query object is compared with a set of objects to find the ones that are either exactly identical or similar to the query object. There are two obstacles for efficient execution of whole-match queries. First, the general problem of comparing two 2D objects under rotation, scaling and translation invariance is known to be computationally expensive. Second, the size of the databases are growing, and hence a query should be answered without accessing all the objects in the database. To address both obstacles, we identify a set of six features that could be extracted from the objects' minimum bounding circle (MBC). These are: the radius of the MBC, the coordinates of the center of MBC, the set of touch-points on the MBC, the touch-points angle sequence, the vertex angle sequence and the start-point of the angle sequence. The features are unique per object and can be utilized for both efficiently indexing the objects and expediting the comparison between two objects. We focus on three variations of match queries: an exact shape match, an exact match with rotation, scaling or translation, and similarity shape retrieval.

The representation and processing of spatial queries is important in numerous application domains in the areas of computer-aided design, multimedia databases, spatial and geographic applications. A sample query type in these applications is to find objects that satisfy a specific direction or topological relation with respect to a given object. Due to the large size of these databases and the complexity of geometric algorithms, appropriate indexing techniques and object approximations are crucial. The problem is that the relationships between object approximations are usually a superset of the actual relationships between their corresponding objects, resulting in a number of false hits. A challenge, hence, is to reduce the number of false hits in order to decrease the number of times we invoke the complex geometric algorithms on the actual representations of the objects. In this paper, we describe the support of topological and direction queries using spatial data structures based on the minimum bounding circle (MBC) approximation. By identifying special cases in MBC relations, we propose extra filtering steps to reduce the number of false hits.

The access patterns of the users of a web-site are traditionally analyzed in order to facilitate the user access to the site's information. In this study, however, a systematic approach is introduced in order to analyze the users' navigation paths to the advantage of the web-site owner. Briefly, as users navigate through a web-site, it seems that they are transparently filling a questionnaire designed a priori by the web-site owner. To achieve this, we first cluster the users who navigate similar paths employing the Path Mining algorithm. Next, the correlation between a set of target questions and the structure of the WWW-site is quantified. This has been done by borrowing the concept of channel from information theory. Finally, we compute the probability of a user's certain answer to each question, given the user's navigation path. The accuracy of the computed probabilities highly depends on the channel parameters. Hence, we describe a learning process based on a set of training data...