Understanding individual human mobility is critical for a wide range of applications. Real-world trajectory datasets provide valuable insights into actual movement behaviors but are often constrained by data sparsity and participant bias. Synthetic data, by contrast, offer scalability and flexibility but frequently lack realism. To address this gap, we introduce a comprehensive software pipeline for generating, calibrating, and processing large-scale human mobility datasets that integrate the realism of empirical data with the control and extensibility of Patterns-of-Life simulations. Our system consists of three integrated components. First, a genetic algorithm-based calibration module fine-tunes simulation parameters to align with real-world mobility characteristics, such as daily trip counts and radius of gyration, enabling realistic behavioral modeling. Second, a data generation engine constructs geographically grounded simulations using OpenStreetMap data to produce diverse mobility logs. Third, a data processing suite transforms raw simulation logs into structured formats suitable for downstream applications, including model training and benchmarking.

Staypoint detection is an important step in human trajectory analysis. Transformation transforms sequences of raw geolocations into semantic staypoints such as staying at work, staying in a restaurant, or staying at home. A common used algorithm for staypoint detection is the Sliding Window Staypoint Detection Algorithm with is implemented in many tools for trajectory data analysis such as Trackintel. This algorithm assumes that noise is minimal, which causes spurious, non-existent staypoints to appear in the resultant data if the data is indeed noisy. We offer a simple solution to remove such spurious staypoints without compromising any of the other capabilities of the algorithm, resulting in higher quality staypoints which are important to downstream tasks. Our experiments show that our proposed improvement, applied to common trajectory datasets, vastly reduces the number of spurious staypoints.

We present a demonstration of a highly scalable, spatially explicit infectious disease simulation that models the spread of disease across all 220,000+ census block groups in the United States using a compartmental Susceptible-Infectious-Recovered (SIR) epidemiological framework. To achieve this unprecedented scale and resolution, our system leverages efficient sparse matrix and vector operations alongside statistical approximations of large numbers of independent random events via Poisson and Normal distributions. The resulting simulation produces realistic spatiotemporal dynamics that align with empirical patterns observed in major epidemics, including the COVID-19 outbreak. Our live demonstration at the conference will highlight the simulation's computational efficiency and interactive capabilities. Starting from the conference venue in Minneapolis, participants will be able to configure disease parameters and observe the geographic spread of infection in real time, offering both an educational and analytical perspective on pandemic modeling.

Individual-level human mobility prediction has emerged as a significant topic of research. In this paper, we focus on an underexplored problem in human mobility prediction: determining the best practices to train a machine learning model using historical data to forecast an individuals complete trajectory over the next days and weeks. In this experiment paper, we undertake a comprehensive experimental analysis of diverse models, parameter configurations, and training strategies, accompanied by an in-depth examination of the statistical distribution inherent in human mobility patterns. Our empirical evaluations encompass both Long Short-Term Memory and Transformer-based architectures, and further investigate how incorporating individual life patterns can enhance the effectiveness of the prediction. Moreover, since the absence of explicit user information is often missing due to user privacy, we show that the sampling of users may exacerbate data skewness and result in a substantial loss in predictive accuracy. To mitigate data imbalance and preserve diversity, we apply user semantic clustering with stratified sampling to ensure that the sampled dataset remains representative. Our results further show that small-batch stochastic gradient optimization improves model performance, especially when human mobility training data is limited.

The prediction of individual-level human mobility has emerged as a critical research domain. However, human trajectories are inherently complex and subject to perturbations from exogenous factors such as meteorological conditions, collective social behaviors, and temporal events including public holidays. These external influences introduce substantial variability, thereby complicating predictive modeling. In this study, we propose a novel framework for human mobility trajectory prediction. Unlike existing methods that focus primarily on a single temporal scale, our approach leverages multi-scale modeling through a hybrid Temporal Convolutional Network-Transformer encoder to capture both local and global mobility dynamics. The framework further integrates user profile embeddings to incorporate individual and group-level behavioral patterns, and employs a sparse Mixture-of-Experts architecture with top-1 routing to achieve scalable specialization at fixed inference cost.

Pathogen genome data offers valuable structure for spatial models, but its utility is limited by incomplete sequencing coverage. We propose a probabilistic framework for inferring genetic distances between unsequenced cases and known sequences within defined transmission chains, using time-aware evolutionary distance modeling. The method estimates pairwise divergence from collection dates and observed genetic distances, enabling biologically plausible imputation grounded in observed divergence patterns, without requiring sequence alignment or known transmission chains. Applied to highly pathogenic avian influenza A/H5 cases in wild birds in the United States, this approach supports scalable, uncertainty-aware augmentation of genomic datasets and enhances the integration of evolutionary information into spatiotemporal modeling workflows.

From the beginning of the COVID-19 pandemic, thousands of laboratories have sequenced cases that are publicly available. This genetic information of sequenced cases allows the creation of a phylogenic tree which connects cases to their most recent genetic ancestor. Combined with temporal and spatial information, phylogenetic trees provide an understanding of where cases occurred and how they spread. In this paper, we examine the spatiotemporal evolution of COVID-19 using the case study of Louisiana, USA. In a given branch of a phylogenetic tree, we impute the location of hidden cases using the Viterbi algorithm alongside human mobility data, achieving 88.07% accuracy. These results illustrate the utility of inference algorithms for determining plausible pathways a pathogen may take. Such findings may be crucial for understanding the transmission patterns of future pathogens within populations.

Massive datasets related to infectious diseases became available after the COVID-19 pandemic, supporting data-driven approaches in modeling and forecasting infectious diseases. However, these approaches are known to exacerbate data biases present in the training data such as having certain demographic groups being over or underrepresented in the data. Such data collection biases may propagate through the modeling and prediction pipelines to decision-making, and the consequences are relatively unknown. Therefore, efforts are needed to understand how data collection bias affects data-driven infectious disease models. This datasets and benchmarks paper provides a suite of datasets, each corresponding to a simulated disease spread among a population of 5000 simulated agents over 90 days in Atlanta and San Francisco. For each dataset, we provide not only the full (simulated ground truth) of the disease spread in terms of when, where, and by whom the disease spreads, but also information on which cases are observed when different types and degrees of data collection bias are applied. The agents' characteristics, check-ins, and social network data are also available to support downstream tasks. Additionally, we also describe how to use the simulation to re-generate the data and to generate new datasets in different regions and with different parameters. With the provided datasets and the simulation tools, researchers studying the spread of infectious diseases may better understand, account for, and correct the systematic bias caused by the inherent real-world data bias, and hence improve the prediction of infectious diseases.

We demonstrate the Patterns of Life Simulation to create realistic simulations of human mobility in a city. This simulation has recently been used to generate massive amounts of trajectory and check-in data. Our demonstration focuses on using the simulation twofold: (1) using the graphical user interface (GUI), and (2) running the simulation headless by disabling the GUI for faster data generation. We further demonstrate how the Patterns of Life simulation can be used to simulate any region on Earth by using publicly available data from OpenStreetMap. Finally, we also demonstrate recent improvements to the scalability of the simulation allows simulating up to 100,000 individual agents for years of simulation time. During our demonstration, as well as offline using our guides on GitHub, participants will learn: (1) The theories of human behavior driving the Patters of Life simulation, (2) how to simulate to generate massive amounts of synthetic yet realistic trajectory data, (3) running the simulation for a region of interest chosen by participants using OSM data, (4) learn the scalability of the simulation and understand the properties of generated data, and (5) manage thousands of parallel simulation instances running concurrently.

The increased availability of datasets during the COVID-19 pandemic enabled machine-learning approaches for modeling and forecasting infectious diseases. However, such approaches are known to amplify the bias in the data they are trained on. Bias in such input data like clinical case data for COVID-19 is difficult to measure due to disparities in testing availability, reporting standards, and healthcare access among different populations and regions. Furthermore, the way such biases may propagate through the modeling pipeline to decision-making is relatively unknown. Therefore, we present a system that leverages a highly detailed agent-based model (ABM) of infectious disease spread in a city to simulate the collection of biased clinical case data where the bias is known. Our system allows users to load either a pre-selected region or select their own (using OpenStreetMap data for the environment and census data for the population), specify population and infectious disease parameters, and the degree(s) to which different populations will be overrep-resented or underrepresented in the case data. In addition to the system, we provide a large number of benchmark datasets that produce case data at different levels of bias for different regions. We hope that infectious disease modelers will use these datasets to investigate how well their models are robust to data bias or whether their model is overfit to biased data.

Semantic trajectories, which enrich spatial-temporal data with textual information such as trip purposes or location activities, are key for identifying outlier behaviors critical to healthcare, social security, and urban planning. Traditional outlier detection relies on heuristic rules, which requires domain knowledge and limits its ability to identify unseen outliers. Besides, there lacks a comprehensive approach that can jointly consider multi-modal data across spatial, temporal, and textual dimensions. Addressing the need for a domain-agnostic model, we propose the Transferable Outlier Detection for Human Semantic Trajectories (TOD4Traj) framework. TOD4Traj first introduces a modality feature unification module to align diverse data feature representations, enabling the integration of multi-modal information and enhancing transferability across different datasets. A contrastive learning module is further proposed for identifying regular mobility patterns both temporally and across populations, allowing for a joint detection of outliers based on individual consistency and group majority patterns. Our experimental results have shown TOD4Traj's superior performance over existing models, demonstrating its effectiveness and adaptability in detecting human trajectory outliers across various datasets.

The advancements in Location Based Services (LBS) and Location Based Social Networks (LBSN) have spurred multiple research efforts in query processing as well as recommendation systems that enable planning trips based on combining location and semantic properties of Points of Interest (POI). However, often times such trips need to involve the reality of existing road networks, for the purpose of obeying constraints such as distance or travel-time. Although there are many publicly available datasets (e.g., Gowalla) that include check-in data at POIs with location, they are often not integrated with existing roads-based data (e.g., Open Street Maps (OSM)) causing researchers to spend extra time and labour to experimentally evaluate their findings. In this paper, we present: (1) methodologies for extracting information regarding POIs from publicly available datasets based on users posting; (2) extracting concise semantic categories for each POI; (3) integrating their location and semantic categories with an existing road network. In addition to the methodologies, we also provide two datasets (based on POIs and road networks in Chicago and New York City) constructed using our methodologies that researchers can readily use for their semantic-aware POIs with location and trip based query processing tasks as well as deep learning tasks.

Source localization aims to locate information diffusion sources only given the diffusion observation, which has attracted extensive attention in the past few years. Existing methods are mostly tailored for single networks and may not be generalized to handle more complex networks like cross-networks. Cross-network is defined as two interconnected networks, where one network's functionality depends on the other. Source localization on cross-networks entails locating diffusion sources on the source network by only giving the diffused observation in the target network. The task is challenging due to challenges including: 1) diffusion sources distribution modeling; 2) jointly considering both static and dynamic node features; and 3) heterogeneous diffusion patterns learning. In this work, we propose a novel method, namely CNSL, to handle the three primary challenges. Specifically, we propose to learn the distribution of diffusion sources through Bayesian inference and leverage disentangled encoders to learn static and dynamic node features separately. The learning objective is coupled with the cross-network information propagation estimation model to make the inference of diffusion sources considering the overall diffusion process. Additionally, we also provide two novel cross-network datasets collected by ourselves. Extensive experiments are conducted on both datasets to demonstrate the effectiveness of CNSL in handling the source localization on cross-networks.

Individual human location trajectory and check-in data have been the driving force for human mobility research in recent years. However, existing human mobility datasets are very limited in size and representativeness. For example, one of the largest and most commonly used datasets of individual human location trajectories, GeoLife, captures fewer than two hundred individuals. To help fill this gap, this Data and Resources paper leverages an existing data generator based on fine-grained simulation of individual human patterns of life to produce large-scale trajectory, check-in, and social network data. In this simulation, individual human agents commute between their home and work locations, visit restaurants to eat, and visit recreational sites to meet friends. We provide large datasets of months of simulated trajectories for two example regions in the United States: San Francisco and New Orleans. In addition to making the datasets available, we also provide instructions on how the simulation can be used to re-generate data, thus allowing researchers to generate the data locally without downloading prohibitively large files.

Route planning based on user’s preferences and Points of Interests (POIs) is one of the most popular applications of Location-Based Services (LBS). Variants of route planning consider distance constraints (e.g., the maximum length of the route), origin constraints (e.g., a set of possible starting locations of the route), and category constraints (e.g., a multiset of POI categories that the route must visit). However, the problem of deciding whether a route exists that visits all required POI categories under the distance constraint is known to be NP-hard. Assuming P ≠ NP, this means that there is no efficient (polynomial time) solution to find such paths. Recently, approximate algorithms have been proposed for searching for such a path. This demonstration leverages several of these algorithms to provide a web-based system with a graphical user interface (UI) which allows the users to find a path that: (a) satisfies a distance limit; (b) generates a route to visit a list of POIs, based on the user’s preferred categories; (c) provides a set of hotels (as possible starting locations of the path). If the approximate search algorithms are able to find such a path, it will be displayed on a Mapbox-based map interface that shows: (1) all POIs on a path and (2) alternative paths if any were found. The system then allows a user to explore the returned paths, select a path, or refine their constraints. Moreover, the system allows the users to select which approximate algorithm they would prefer to execute.

Shortest path computation is a fundamental operation in many application domains and is especially challenging in frequently evolving small-world networks (i.e., graphs in which many nodes can be reached from every other node by a small number of hops). Index-based methods, especially ones based on 2-hop labeling are often used for high query efficiency. However, the evolvements of small-world networks in many realistic scenarios pose the challenge of efficient maintenance of the shortest path index. In this work, we adopt the state-of-the-artParallel Shortest-distance Labeling (PSL)as the underlying 2-hop labeling construction method, and design algorithms to support its efficient update given edge weight changes (increase and decrease). Specifically, we focus on weightedPSL (WPSL)and propose a propagation-based update mechanism for both synchronous and asynchronous propagation. We also identify thecurse of pruning powerin the edge weight increase case, and solve it with a balance between index size and effectiveness. Followed by, we extend the asynchronous propagation method toPruned Landmark Labeling (PLL)for faster index maintenance and query processing with a smaller index size. Finally, we further optimize the index performance by reducing the index size through graph contraction and accelerating the index update through parallelized mix index update. Our experimental results on real-life and synthetic networks demonstrate the superiority of our algorithms over the relevant baselines on index maintenance.

Since the onset of the COVID-19 pandemic, mil-lions of coronavirus sequences have been rapidly deposited in publicly available repositories. The sequences have been used primarily to monitor the evolution and transmission of the virus. In addition, the data can be combined with spatiotemporal information and mapped over space and time to understand transmission dynamics further. For example, the first COVID-19 cases in Australia were genetically related to the dominant strain in Wuhan, China, and spread via international travel. These data are currently available through the Global Initiative on Sharing Avian Influenza Data (GISAID) yet generally remains an untapped resource for data scientists to analyze such multi-dimensional data. Therefore, in this study, we demonstrate a system named Phyloview, a highly interactive visual environment that can be used to examine the spatiotemporal evolution of COVID-19 (from-to) over time using the case study of Louisiana, USA. PhyloView (powered by ArcGIsInsights) facilitates the visualization and exploration of the different dimensions of the phylogenetic data and can be layered with other types of spatiotemporal data for further investigation. Our system has the potential to be shared as a model to be used by health officials that can access relevant data through GISAID, visualize, and analyze it. Such data is essential for a better understanding, predicting, and responding to infectious diseases.

One of the most popular applications of Location Based Services (LBS) is recommending a Point of Interest (POI) based on user's preferences and geo-locations. However, the existing approaches have not tackled the problem of jointly determining: (a) a sequence of POIs that can be traversed within certain budget (i.e., limit on distance) and simultaneously provide a high-enough diversity; and (b) recommend the best origin (i.e., the hotel) for a given user, so that the desired route of POIs can be traversed within the specified constraints. In this work, we take a first step towards identifying this new problem and formalizing it as a novel type of a query. Subsequently, we present naïve solutions and experimental observations over a real-life datasets, illustrating the trade-offs in terms of (dis)associating the initial location from the rest of the POIs.

Adverse side effects of a drug may vary over space and time due to different populations, environments, and drug quality. Discovering all side effects during the development process is impossible. Once a drug is approved, observed adverse effects are reported by doctors and patients and made available in the Adverse Event Reporting System provided by the U.S. Food and Drug Administration . Mining such records of reported adverse effects, this study proposes a spatial clustering approach to identify regions that exhibit similar adverse effects. We apply a topic modeling approach on textual representations of reported adverse effects using Latent Dirichlet Allocation. By describing a spatial region as a mixture of the resulting latent topics, we find clusters of regions that exhibit similar (topics of) adverse events for the same drug using Hierarchical Agglomerative Clustering. We investigate the resulting clusters for spatial autocorrelation to test the hypothesis that certain (topics of) adverse effects may occur only in certain spatial regions using Moran’s I measure of spatial autocorrelation.

Earth observation data is collected by ever-expanding fleets of satellites including Landsat1-8, Sentinel1 & Sentinel2, SPOT1-7 and WorldView1-3. These satellites generate at spatial resolutions (pixel size) from 30m to 31cm and provide revisit rates of as frequent as every 5 days. This allows us not only to look at high-resolution images of every corner of the Earth, but also to track events and observe change over time. During the past 5 years, medium spatial resolution satellite data (30 − 10m pixels) have developed very high temporal revisit frequencies of 5-16 days and spatial-temporal structures have been developed to manage these vast data sets. However, high resolution satellite images and rapidly increasing revisit rates create major data management and mining challenges. This work discusses six challenges of integrating observations at different times, from different sensors, at different spatial resolutions and different temporal frequencies into a unified Earth Observation Data Cube, that is, a tensor of location, time, and spectral bands. Challenges include creating a unified data cube from heterogeneous sensors, scaling geo-registration (mapping pixel between images), accounting for uncertainty across observations, imputing missing observations, broad area event detection, and ultimately, predicting the future state of our planet. With such a unified Earth Observation Data Cube in place, we describe potential application areas such as detecting anthropogenic land cover change, early warning of natural hazards, tracing movement of animals, finding missing airplanes, and rapid detection of forest fires.

Ever increasing traffic and consequential congestion wastes fuel and is a significant contributor to Green House Gas (GHG) emissions. Contributors here include ride-sharing services such as Uber, Lyft, and Didi, with their drivers not only transporting passengers, but also spending a considerable time in traffic searching for new ones. To mitigate their impact, this work proposes a novel algorithm to improve the efficiency the drivers' search for passengers. Our algorithm directs unassigned drivers to locations where new passengers are expected to emerge. We use a non-negative matrix factorization approach to model the time and location of passengers given historical training data. A probabilistic search strategy then guides drivers to nearby locations for which we predict new passengers. To ensure that drivers do not over subscribe to such areas, we randomize destinations and provide each driver with a home location destination when unassigned. An experimental evaluation using real-world data from Manhattan shows that our approach actually reduces the search time of drivers and the wait time of passengers compared to baseline solutions.

Traffic sensing has been revolutionized with the commoditization of GPS technology. Smartphone navigation applications ubiquitously track vehicles as samples of the overall traffic. This so-called Probe Vehicle Data (PVD) has replaced traditional road-side sensor technologies, such as induction loops and microwave sensors, given its relative low cost, good coverage, and reliability. However, while PVD allows us to assess speed and by extension the overall traffic condition in a road network, this sample-based approach does not provide us with traffic flow, i.e., the number of vehicles passing through an edge of the road network. This paper bridges this gap by proposing and evaluating a range of methods to infer traffic flow for a road network that is ubiquitously observed using probe data but having traffic flow measurements only in very road-side sensor locations. We create Road Segment Archetypes that relate PVD speeds to flow from road-side sensors for these locations. These archetypes are then extended to the entire network covered only by PVD based on similar traffic characteristics. Using these archetypes we augment and experimentally evaluate different traffic flow estimation models using real-world traffic data. Experimental results show that the Road Archetype flow estimation is comparable to the accuracy of prediction models that would be based on actual road-side sensor flows.

Urban areas provide us with a treasure trove of available data capturing almost every aspect of a population's life. This work focuses on mobility data and how it will help improve our understanding of urban mobility patterns. Readily available and sizable farecard data captures trips in a public transportation network. However, such data typically lacks temporal signatures and as such the task of inferring trip semantics, station function, and user clustering is quite challenging. While existing approaches either focus on station-level or user-level signals only, we propose a Station-to-User (S2U) transfer learning framework, which augments user-level learning with shared temporal patterns learned from station-level signals. Our framework is based on a novel, so-called "Tidal-Regularized Non-negative Matrix Factorization" method, which incorporates a-priori tidal traffic patterns in generic Non-negative Matrix Factorization. To evaluate our model performance, a user clustering stability test based on the classical Rand Index is introduced as a metric to benchmark different unsupervised learning models. Using this metric, quantitative evaluations on three real-world datasets show that S2U outperforms two baselines methods by 7-21%. We also provide a qualitative analysis of the user clustering and station functions for the Washington D.C. metro and show how S2U can support spatiotemporal urban analytics.

Location-based social networks (LBSNs) have been studied extensively in recent years. However, utilizing real-world LBSN data sets yields several weaknesses: sparse and small data sets, privacy concerns, and a lack of authoritative ground-truth. To overcome these weaknesses, we leverage a large-scale LBSN simulation to create a framework to simulate human behavior and to create synthetic but realistic LBSN data based on human patterns of life. Such data not only captures the location of users over time but also their interactions via social networks. Patterns of life are simulated by giving agents (i.e., people) an array of “needs” that they aim to satisfy, e.g., agents go home when they are tired, to restaurants when they are hungry, to work to cover their financial needs, and to recreational sites to meet friends and satisfy their social needs. While existing real-world LBSN data sets are trivially small, the proposed framework provides a source for massive LBSN benchmark data that closely mimics the real-world. As such, it allows us to capture 100% of the (simulated) population without any data uncertainty, privacy-related concerns, or incompleteness. It allows researchers to see the (simulated) world through the lens of an omniscient entity having perfect data. Our framework is made available to the community. In addition, we provide a series of simulated benchmark LBSN data sets using different synthetic towns and real-world urban environments obtained from OpenStreetMap. The simulation software and data sets, which comprise gigabytes of spatio-temporal and temporal social network data, are made available to the research community.

Location-Based Services are often used to find proximal Points of Interest PoI - e.g., nearby restaurants and museums, police stations, hospitals, etc. - in a plethora of applications. An important recently addressed variant of the problem not only considers the distance/proximity aspect, but also desires semantically diverse locations in the answer-set. For instance, rather than picking several close-by attractions with similar features - e.g., restaurants with similar menus; museums with similar art exhibitions - a tourist may be more interested in a result set that could potentially provide more diverse types of experiences, for as long as they are within an acceptable distance from a given (current) location. Towards that goal, in this work we propose a novel approach to efficiently retrieve a path that will maximize the semantic diversity of the visited PoIs that are within distance limits along a given road network. We introduce a novel indexing structure - the Diversity Aggregated R-tree, based on which we devise efficient algorithms to generate the answer-set - i.e., the recommended locations among a set of given PoIs - relying on a greedy search strategy. Our experimental evaluations conducted on real datasets demonstrate the benefits of proposed methodology over the baseline alternative approaches.

Our ability to extract knowledge from evolving spatial phenomena and make it actionable is often impaired by unreliable, erroneous, obsolete, imprecise, sparse, and noisy data. Integrating the impact of this uncertainty is a paramount when estimating the reliability/confidence of any time-varying query result from the underlying input data. The goal of this advanced seminar is to survey solutions for managing, querying and mining uncertain spatial and spatio-temporal data. We survey different models and show examples of how to efficiently enrich query results with reliability information. We discuss both analytical solutions as well as approximate solutions based on geosimulation.

Fixed-route bus systems are an important part of the urban transportation mix. A considerable disadvantage of buses is their slow speed, which is in part due to frequent stops, but also due to the lack of segregation from other vehicles in traffic. As such, assessing bus routes is an important aspect of route planning, scheduling, and the creation of dedicated bus lanes. In this work, we use bus tracking data from the Washington Metropolitan Area Transit Authority to discover speed patterns in relation to bus stops throughout the day. This gives us an insight on whether the routes are affected by traffic congestion or more random events such as traffic lights. We first employ a macro-level qualitative analysis to identify patterns across different trips. A micro-level quantitative analysis further refines this approach by analyzing the speed patterns around bus stops. Our analysis is based on bus odometer data, which is a one-dimensional representation of trips that has considerable accuracy when looking at speed patterns. Exploiting route metadata in relation to stops, we use Dynamic Time Warping to cluster different stops based on their speed profiles throughout the day. The clustering can be used to generate a spatiotemporal route profile and we show how such a profile provides actionable intelligence for route planning purposes.

Zoning Improvement Plan (ZIP) Codes provide a sub-division of space. Interestingly, the ZIP code area polygons for different data sources do not match, resulting in uncertainty for a range of services that rely on such data. This paper presents a system that employs traditional classification methods to map a given spatial coordinate to a distribution of ZIP-codes using various public available ZIP-code maps as predictors, and using the (not publicly available) United States Postal Service (USPS) map as an authoritative ground truth. We show that large sets of microblog data, from which we extract potential ZIP-codes, can significantly improve classification accuracy despite the noise of such data. The demonstrator allows users to select locations on a map of Orlando, FL, view the resulting distribution of ZIP-codes predicted for this location, compare the results to the ground-truth, and view the microblogs that have enriched the result. A focus will be on showing that the signal present in large, noisy, and 99.99% unrelated microblog data can indeed be used to improve reverse ZIP code geo-coding.

Data generators have been heavily used in creating massive trajectory datasets to address common challenges of real-world datasets, including privacy, cost of data collection, and data quality. However, such generators often overlook social and physiological characteristics of individuals and as such their results are often limited to simple movement patterns. To address these shortcomings, we propose an agent-based simulation framework that facilitates the development of behavioral models in which agents correspond to individuals that act based on personal preferences, goals, and needs within a realistic geographical environment. Researchers can use a drag-and-drop interface to design and control their own world including the geospatial and social (i.e. geo-social) properties. The framework is capable of generating and streaming very large data that captures the basic patterns of life in urban areas. Streaming data from the simulation can be accessed in real time through a dedicated API.

Congested traffic wastes billions of liters of fuel and is a significant contributor to Green House Gas (GHG) emissions. Although convenient, ride sharing services such as Uber and Lyft are becoming a significant contributor to these emissions not only because of added traffic but by spending time on the road while waiting for passengers. To help improve the impact of ride sharing, we propose an algorithm to optimize the efficiency of drivers searching for customers. In our model, the main goal is to direct drivers represented as idle agents, i.e., not currently assigned a customer or resource, to locations where we predict new resources to appear. Our approach uses non-negative matrix factorization (NMF) to model and predict the spatio-temporal distributions of resources. To choose destinations for idle agents, we employ a greedy heuristic that strikes a balance between distance greed, i.e., to avoid long trips without resources and resource greed, i.e., to move to a location where resources are expected to appear following the NMF model. To ensure that agents do not oversupply areas for which resources are predicted and under supply other areas, we randomize the destinations of agents using the predicted resource distribution within the local neighborhood of an agent. Our experimental evaluation shows that our approach reduces the search time of agents and the wait time of resources using real-world data from Manhattan, New York, USA.

Location-based social networks (LBSNs) have been studied extensively in recent years. However, utilizing real-world LBSN datasets in such studies has severe weaknesses: sparse and small datasets, privacy concerns, and a lack of authoritative ground-truth. Our vision is to create a large scale geo-simulation framework to simulate human behavior and to create synthetic but realistic LBSN data that captures the location of users over time as well as social interactions of users in a social network. While existing LBSN datasets are trivially small, such a framework would provide the first source of massive LBSN benchmark data which would closely mimic the real world, containing high-fidelity information of location, and social connections of millions of simulated agents over several years of simulated time. Therefore, it would serve the research community by revitalizing and reshaping research on LBSNs by allowing researchers to see the (simulated) world through the lens of an omniscient entity having perfect data. These evaluations will guide future research enabling us to develop solutions to improve LBSN applications such as user-location recommendation, friend recommendation, location prediction, and location privacy.

Our goal is to incorporate uncertainty information in the querying process to enhance results with probabilistic guarantees. Existing probabilistic querying solutions can not be scaled to realistic data sets due to #P-complete nature of querying uncertain data. We present a new approach to query uncertain sets of spatial data by sampling the possible database worlds, each resulting in a possible query result. The main challenge is to find a consensus of the retrieved results. We tackle this by finding query results that are representative. A representative query result is associated with a probabilistic guarantee, stating that with a guaranteed probability, the true (but unknown) query result is sufficiently similar. Our experiments show that our sampling approach provides probabilistic guarantees while scaling to large data sets, thus allowing to perform queries such as range queries, kNN queries, RkNN queries and ranking queries, where state-of-the-art solutions do not scale.

Proximity-oriented spatial queries, such as range queries and k-nearest neighbors (kNNs), are common in many applications, notably in Location Based Services (LBS). However, in many settings, users may also desire that the returned proximal objects exhibit (likely) maximal and fine-grained semantic diversity. For instance, nearby restaurants with different menu items are more interesting than close ones offering similar menus. Towards that goal, we propose a topic modeling approach based on the Latent Dirichlet Allocation, a generative statistical model, to effectively model and exploit a fine-grained notion of diversity, namely based on sets of keywords (e.g., menu items) instead of a coarser user-given category (e.g., a restaurant's cuisine). In addition, and relying on the notion of Distance Signatures, we propose an index structure that can be used to effectively extract the k objects that are within a range distance from a given query location, and which are also semantically diverse. Our experimental evaluations using real datasets demonstrate that the proposed methodology is able to provide highly diversified answers to cardinality-wise constrained range queries much more efficiently than a straightforward alternative solution.

In this paper, we address the problem of optimizing information propagation in uncertain networks given a constrained budget of edges. We show that this problem requires to solve two NP-hard subproblems: the computation of expected information flow, and the optimal choice of edges. To compute the expected information flow to a source vertex, we propose the F-tree as a specialized data structure, that identifies independent components of the graph for which the information flow can either be computed analytically and efficiently, or for which traditional Monte-Carlo sampling can be applied independently of the remaining network.

It is important for decision-makers to effectively and proactively differentiate the significance of various public concerns, and address them with optimal strategy under the limited resources. Online Petition Platforms (OPPs) are replacing traditional social and market surveys for the advantages of low financial cost and high-fidelity social indicators. Despite benefits from OPPs, the raw information from millions of petition signers can easily overwhelm decision makers. In addition, spatio-temporal and semantic dissemination patterns increase the complexity of such OPP data. These two aspects show the necessity of a framework that learns from all available data, which is encoded by dynamic representation of features, to predict whether a petition will successfully lead to a change by decision makers. To build such framework, we need to overcome several challenges including: 1) missing values in dynamic features; 2) strong uncertainty in petition prediction; 3) unknown labels for ongoing petitions and 4) Scalability regarding increasing features and petitions. To address these difficulties simultaneously, we propose a novel chain-structure Multi-task Learning framework with Uncertainty Estimation (MLUE) to predict potentially victorious petitions, which facilitates the process of decision making. Specifically, we divide data into different Increasing Feature Blocks (IFBs) according to missing patterns. Besides, we propose a novel criterion to estimate uncertainty in order to label petitions as early as possible. To handle the challenge of scalability, we present an Expectation-Maximization (EM)-based algorithm to optimize the non-convex objective function accurately and efficiently. Various experiments on six petition datasets demonstrate that our MLUE outperformed other baselines by a large margin.

Reliable propagation of information through large networks, e.g., communication networks, social networks, or sensor networks is very important in many applications concerning marketing, social networks, and wireless sensor networks. However, social ties of friendship may be obsolete, and communication links may fail, inducing the notion of uncertainty in such networks. In this paper, we address the problem of optimizing information propagation in uncertain networks given a constrained budget of edges. We show that this problem requires to solve two NP-hard subproblems: the computation of expected information flow, and the optimal choice of edges. To compute the expected information flow to a source vertex, we propose the F-tree as a specialized data structure, that identifies independent components of the graph for which the information flow can either be computed analytically and efficiently, or for which traditional Monte-Carlo sampling can be applied independently of the remaining network. For the problem of finding the optimal edges, we propose a series of heuristics that exploit properties of this data structure. Our evaluation shows that these heuristics lead to high quality solutions, thus yielding high information flow, while maintaining low running time.

An inherent challenge arising in any dataset containing information of space and/or time is uncertainty due to various sources of imprecision. Integrating the impact of the uncertainty is a paramount when estimating the reliability (confidence) of any query result from the underlying input data. To deal with uncertainty, solutions have been proposed independently in the geo-science and the data-science research community. This interdisciplinary tutorial bridges the gap between the two communities by providing a comprehensive overview of the different challenges involved in dealing with uncertain geo-spatial data, by surveying solutions from both research communities, and by identifying similarities, synergies and open research problems.

The proliferation of the Web 2.0 and the ubiquitousness of social media yield a huge flood of heterogenous data that is voluntarily published and shared by billions of individual users all over the world. As a result, the representation of an entity (such as a real person) in this data may consist of various data types, including location and other numeric attributes, textual descriptions, images, videos, social network information and other types of information. Searching similar entities in this multi-enriched data exploiting the information of multiple representations simultaneously promises to yield more interesting and relevant information than searching among each data type individually. While efficient similarity search on single representations is a well studied problem, existing studies lacks appropriate solutions for multi-enriched data taking into account the combination of all representations as a whole. In this paper, we address the problem of index-supported similarity search on multi-enriched (a.k.a. multi-represented) objects based on a set of metrics, one metric for each representation. We define multimetric similarity search queries by employing user-defined weight function specifying the impact of each metric at query time. Our main contribution is an index structure which combines all metrics into a single multi-dimensional access method that works for arbitrary weights preferences. The experimental evaluation shows that our proposed index structure is more efficient than existing multi-metric access methods considering different cost criteria and tremendously outperforms traditional approaches when querying very large sets of multi-enriched objects.

Directions and paths, as commonly provided by route guidance systems, are usually derived considering absolute metrics, e.g., finding the shortest path within the underlying road network. This demo presents a framework which uses crowdsourced geospatial data to obtain paths that do not only minimize travel time but also guide users along popular points of interest (POIs). By analyzing textual travel blog data and Flickr data, we define a measure for popularity of POIs. This measure is used as an additional cost criterion in the underlying road network graph. Furthermore, we propose an approach to reduce the problem of finding paths which maximize popularity while minimizing travel time to the computation of bicriterion pareto optimal paths. The presented framework allows users to specify origin and destination within a road network, returning the set of pareto optimal paths or a subset thereof if a desired number of POIs along the path has been specified. Each of the returned routes is enriched with representative Flickr images and textual information from travel blogs. The framework and its results show that the computed paths yield competitive solutions in terms of travel time while also providing more “popular” paths, making routing easier and more informative for the user.

Fuzzy object databases are becoming more and more important in the context of image analysis. Examples include satellite images where blurred trees, houses or lakes can still be organized and searched in a meaningful manner and biomedical images which can be utilized to find similar disease patterns and monitor disease progress. One problem of the underlying data is that it contains blurred image content, i.e., fuzzy data. Therefore, an image-based similarity search, which can process huge amounts of fuzzy data in an efficient and effective way, is desirable. The aim of this work is to develop efficient and effective methods for similarity search in fuzzy object databases. First, a suitable similarity measure based on a shape similarity is proposed. Based on this, two novel k-nearest neighbor algorithms for efficient similarity search are presented. The first approach gains efficiency at the cost of incurring only approximate results, while the second approach uses a filter-refinement approach to prune computation. Our experimental evaluation shows the efficiency of the proposed algorithms.

The challenges associated with handling uncertain data, in particular with querying and mining, are finding increasing attention in the research community. Here we focus on clustering uncertain data and describe a general framework for this purpose that also allows to visualize and understand the impact of uncertainty---using different uncertainty models---on the data mining results. Our framework constitutes release 0.7 of ELKI (http://elki.dbs.ifi.lmu.de/) and thus comes along with a plethora of implementations of algorithms, distance measures, indexing techniques, evaluation measures and visualization components.

Directions and paths, as commonly provided by navigation systems, are usually derived considering absolute metrics, e.g., finding the shortest path within an underlying road network. With the aid of crowdsourced geospatial data we aim at obtaining paths that do not only minimize distance but also lead through more popular areas using knowledge generated by users. We extract spatial relations such as "nearby" or "next to" from geo-textual travel blogs, that define closeness between pairs of points of interest (POIs) and quantify each of these relations using a probabilistic model. Using Bayesian inference, we obtain a probabilistic measure of spatial closeness according to the crowd. Applying this measure to the corresponding road network, we derive an altered cost function taking crowdsourced spatial relations into account. We propose two routing algorithms on the enriched road networks. To evaluate our approach, we use Flickr photo data as a ground truth for popularity. Our experimental results -- based on real world datasets -- show that the computed paths yield competitive solutions in terms of path length while also providing more "popular" paths, making routing easier and more informative for the user.

Location-related data has a tremendous impact in many applications of high societal relevance and its growing volume from heterogeneous sources is one true example of a Big Data [1]. An inherent property of any spatio-temporal dataset is uncertainty due to various sources of imprecision. This tutorial provides a comprehensive overview of the different challenges involved in managing uncertain spatial and spatio-temporal data and presents state-of-the-art techniques for addressing them.

This paper targets the problem of computing meaningful clusterings from uncertain data sets. Existing methods for clustering uncertain data compute a single clustering without any indication of its quality and reliability; thus, decisions based on their results are questionable. In this paper, we describe a framework, based on possible-worlds semantics; when applied on an uncertain dataset, it computes a set of representative clusterings, each of which has a probabilistic guarantee not to exceed some maximum distance to the ground truth clustering, i.e., the clustering of the actual (but unknown) data. Our framework can be combined with any existing clustering algorithm and it is the first to provide quality guarantees about its result. In addition, our experimental evaluation shows that our representative clusterings have a much smaller deviation from the ground truth clustering than existing approaches, thus reducing the effect of uncertainty.

This demonstration presents our Uncertain-Spatio-Temporal (UST)} framework that we have developed in recent years. The framework allows not only to visualize and explore spatio-temporal data consisting of (location, time, object)-triples but also provides an extensive codebase easily extensible and customizable by developers and researchers. The main research focus of this UST-framework is the explicit consideration of uncertainty, an aspect that is inherent in spatio-temporal data, due to infrequent position updates, due to physical limitations and due to power constraints. The UST-framework can be used to obtain a deeper intuition of the quality of spatio-temporal data models. Such models aim at estimating the position of a spatio-temporal object at a time where the object's position is not explicitly known, for example by using both historic (traffic-) pattern information, and by using explicit observations of objects. The UST-framework illustrates the resulting distributions by allowing a user to move forward and backward in time. Additionally the framework allows users to specify simple spatio-temporal queries, such as spatio-temporal window queries and spatio-temporal nearest neighbor (NN) queries. Based on recently published theoretic concepts, the UST-framework allows to visually explore the impact of different models and parameters on spatio-temporal data. The main result showcased by the UST-framework is a minimization of uncertainty by employing stochastic processes, leading to small expected distances between ground truth trajectories and modelled positions.

This work tackles the management of novel types of inconsistencies in Spatio-Temporal Databases, different from traditional database settings where integrity constraints pertain to the explicitly stored (or, defined via views and aggregates) values. We observe that spatio-temporal data has its specific types of ßemanticconstraints and we aim at minimization of the changes needed for repairing their violations.

In Voronoi-based nearest neighbor search, the Voronoi cell of every point p in a database can be used to check whether p is the closest to some query point q. We extend the notion of Voronoi cells to support uncertain objects, whose attribute values are inexact. Particularly, we propose the Possible Voronoi cell (or PV-cell). A PV-cell of a multi-dimensional uncertain object o is a region R, such that for any point pϵR, o may be the nearest neighbor of p. If the PV-cells of all objects in a database S are known, they can be used to identify objects that have a chance to be the nearest neighbor of q. However, there is no efficient algorithm for computing an exact PV-cell. We hence study how to derive an axis-parallel hyper-rectangle (called the Uncertain Bounding Rectangle, or UBR) that tightly contains a PV-cell. We further develop the PV-index, a structure that stores UBRs, to evaluate probabilistic nearest neighbor queries over uncertain data. An advantage of the PV-index is that upon updates on S, it can be incrementally updated. Extensive experiments on both synthetic and real datasets are carried out to validate the performance of the PV-index.

Data uncertainty is inherent in emerging applications such as location-based services, sensor monitoring systems, and data integration. To handle a large amount of imprecise information, uncertain databases have been recently developed. In this paper, we study how to efficiently discover frequent itemsets from large uncertain databases, interpreted under the Possible World Semantics. This is technically challenging, since an uncertain database induces an exponential number of possible worlds. To tackle this problem, we propose a novel methods to capture the itemset mining process as a probability distribution function taking two models into account: the Poisson distribution and the normal distribution. These model-based approaches extract frequent itemsets with a high degree of accuracy and support large databases. We apply our techniques to improve the performance of the algorithms for (1) finding itemsets whose frequentness probabilities are larger than some threshold and (2) mining itemsets with the $$k$$ highest frequentness probabilities. Our approaches support both tuple and attribute uncertainty models, which are commonly used to represent uncertain databases. Extensive evaluation on real and synthetic datasets shows that our methods are highly accurate and four orders of magnitudes faster than previous approaches. In further theoretical and experimental studies, we give an intuition which model-based approach fits best to different types of data sets.

Nearest neighbor (NN) queries in trajectory databases have received significant attention in the past, due to their applications in spatio-temporal data analysis. More recent work has considered the realistic case where the trajectories are uncertain; however, only simple uncertainty models have been proposed, which do not allow for accurate probabilistic search. In this paper, we fill this gap by addressing probabilistic nearest neighbor queries in databases with uncertain trajectories modeled by stochastic processes, specifically the Markov chain model. We study three nearest neighbor query semantics that take as input a query state or trajectory q and a time interval, and theoretically evaluate their runtime complexity. Furthermore we propose a sampling approach which uses Bayesian inference to guarantee that sampled trajectories conform to the observation data stored in the database. This sampling approach can be used in Monte-Carlo based approximation solutions. We include an extensive experimental study to support our theoretical results.

Ranking queries have been investigated extensively in the past due to their broad range of applications. In this paper, we study this problem in the context of fuzzy objects that have indeterministic boundaries. Fuzzy objects play an important role in many areas, such as biomedical image databases and GIS. To the best of our knowledge, we present the first efficient approach for similarity ranking in fuzzy object databases. The main challenge of ranking fuzzy objects is that these objects consist of multiple instances, each associated with a probability. We propose a framework to transform fuzzy objects into probabilistic objects which can then be ranked using existing algorithms for probabilistic objects.

The advances in sensing and telecommunication technologies allow the collection and management of vast amounts of spatio-temporal data combining location and time information.Due to physical and resource limitations of data collection devices (e.g., RFID readers, GPS receivers and other sensors) data are typically collected only at discrete points of time. In-between these discrete time instances, the positions of tracked moving objects are uncertain. In this work, we propose novel approximation techniques in order to probabilistically bound the uncertain movement of objects; these techniques allow for efficient and effective filtering during query evaluation using an hierarchical index structure.To the best of our knowledge, this is the first approach that supports query evaluation on very large uncertain spatio-temporal databases, adhering to possible worlds semantics. We experimentally show that it accelerates the existing, scan-based approach by orders of magnitude.

This demo presents a framework for running probabilistic graph queries on uncertain graphs and visualizing their results. The framework supports the most common uncertainty model for uncertain graphs, i.e. existential uncertainty for the edges of the graph. A large variety of meaningful graph queries are supported, such as shortest path, range, kN, reverse kN, reachability and various aggregation queries. Since the problem of exact probability computation according to possible world semantics is in #P-Time for many combinations of model and query, and since ignoring uncertainty (e.g. by using expectations only) will yield counterintuitive and hard to interpret results, our framework uses an optimized version of Monte-Carlo sampling to estimate the results which allows us not only to perform queries that conform to possible world semantics but also to sample only parts of a graph relevant for a given query. The main strength of this framework is the visualization combined with statistic hypothesis tests, which gives the user not only the estimated result of a query, but also an indication of how significant and reliable these results are. The aim of this demonstration is to give an intuition that a sampling based approach to probabilistic graphs is viable, and that the estimated results quickly converge even for very large graphs. A video demonstrating our framework can be downloaded at http://www.dbs.ifi.lmu.de/Publikationen/videos/PGraph.html

The problem of modeling and managing uncertain data has received a great deal of interest, due to its manifold applications in spatial, temporal, multimedia and sensor databases. There exists a wide range of work covering spatial uncertainty in the static (snapshot) case, where only one point of time is considered. In contrast, the problem of modeling and querying uncertain spatio-temporal data has only been treated as a simple extension of the spatial case, disregarding time dependencies between consecutive timestamps. In this work, we present a framework for efficiently modeling and querying uncertain spatio-temporal data. The key idea of our approach is to model possible object trajectories by stochastic processes. This approach has three major advantages over previous work. First it allows answering queries in accordance with the possible worlds model. Second, dependencies between object locations at consecutive points in time are taken into account. And third it is possible to reduce all queries on this model to simple matrix multiplications. Based on these concepts we propose efficient solutions for different probabilistic spatio-temporal queries. In an experimental evaluation we show that our approaches are several order of magnitudes faster than state-of-the-art competitors.

In this paper, we propose a novel, effective and efficient probabilistic pruning criterion for probabilistic similarity queries on uncertain data. Our approach supports a general uncertainty model using continuous probabilistic density functions to describe the (possibly correlated) uncertain attributes of objects. In a nutshell, the problem to be solved is to compute the PDF of the random variable denoted by the probabilistic domination count: Given an uncertain database object B, an uncertain reference object R and a set D of uncertain database objects in a multi-dimensional space, the probabilistic domination count denotes the number of uncertain objects in D that are closer to R than B. This domination count can be used to answer a wide range of probabilistic similarity queries. Specifically, we propose a novel geometric pruning filter and introduce an iterative filter-refinement strategy for conservatively and progressively estimating the probabilistic domination count in an efficient way while keeping correctness according to the possible world semantics. In an experimental evaluation, we show that our proposed technique allows to acquire tight probability bounds for the probabilistic domination count quickly, even for large uncertain databases.

Given a query object q , a reverse nearest neighbor (RNN) query in a common certain database returns the objects having q as their nearest neighbor. A new challenge for databases is dealing with uncertain objects. In this paper we consider probabilistic reverse nearest neighbor (PRNN) queries, which return the uncertain objects having the query object as nearest neighbor with a sufficiently high probability. We propose an algorithm for efficiently answering PRNN queries using new pruning mechanisms taking distance dependencies into account. We compare our algorithm to state-of-the-art approaches recently proposed. Our experimental evaluation shows that our approach is able to significantly outperform previous approaches. In addition, we show how our approach can easily be extended to PR k NN (where k > 1) query processing for which there is currently no efficient solution.

In this paper we focus on the problem of continuously monitoring the set of Reverse k-Nearest Neighbors (RkNNs) of a query object in a moving object database using a client server architecture. The RkNN monitoring query computes for a given query object q, the set RkNN(q) of objects having q as one of their k-nearest neighbors for each point in time. In our setting the central server can poll the exact positions of the clients if needed. However in contrast to most existing approaches for this problem we argue that in various applications, the limiting factor is not the computational time needed but the amount of traffic sent via the network. We propose an approach that minimizes the amount of communication between clients and central server by an intelligent approximation of the position of the clients. Additionally we propose several poll heuristics in order to further decrease the communication costs. In the experimental section we show the significant impact of our proposed improvements to our basic algorithm.

Fast query processing of complex objects, e.g. spatial or uncertain objects, depends on efficient spatial pruning of objects' approximations, which are typically minimum bounding rectangles (MBRs). In this paper, we propose a novel effective and efficient criterion to determine the spatial topology between multi-dimensional rectangles. Given three rectangles R, A, and B, in a multi-dimensional space, the task is to determine whether A, is definitely closer to R, than B. This domination relation is used in many applications to perform spatial pruning. Traditional techniques apply spatial pruning based on minimal and maximal distance. These techniques however show significant deficiencies in terms of effectivity. We prove that our decision criterion is correct, complete, and efficient to compute even for high dimensional databases. In addition, we tackle the problem of computing the number of objects dominating an object o. The challenge here is to incorporate objects that only partially dominate o. In this work we will show how to detect such partial domination topology by using a modified version of our decision criterion. We propose strategies for conservatively and progressively estimating the total number of objects dominating an object. Our experiments show that the new pruning criterion, albeit very general and widely applicable, significantly outperforms current state-of-the-art pruning criteria.

Managing, searching and mining uncertain data has achieved much attention in the database community recently due to new sensor technologies and new ways of collecting data. There is a number of challenges in terms of collecting, modelling, representing, querying, indexing and mining uncertain data. In its scope, the diversity of approaches addressing these topics is very high because the underlying assumptions of uncertainty are different across different papers. This tutorial provides a comprehensive and comparative overview of general techniques for the key topics in the fields of querying, indexing and mining uncertain data. In particular, it identifies the most generic types of probabilistic similarity queries and discusses general algorithmic methods to answer such queries efficiently. In addition, the tutorial sketches probabilistic methods for important data mining applications in the context of uncertain data with special emphasis on probabilistic clustering and probabilistic pattern mining. The intended audience of this tutorial ranges from novice researchers to advanced experts as well as practitioners from any application domain dealing with uncertain data retrieval and mining.

This paper introduces a scalable approach for probabilistic top-k similarity ranking on uncertain vector data. Each uncertain object is represented by a set of vector instances that is assumed to be mutually exclusive. The objective is to rank the uncertain data according to their distance to a reference object. We propose a framework that incrementally computes for each object instance and ranking position, the probability of the object falling at that ranking position. The resulting rank probability distribution can serve as input for several state-of-the-art probabilistic ranking models. Existing approaches compute this probability distribution by applying the Poisson binomial recurrence technique of quadratic complexity. In this paper, we theoretically as well as experimentally show that our framework reduces this to a linear-time complexity while having the same memory requirements, facilitated by incremental accessing of the uncertain vector instances in increasing order of their distance to the reference object. Furthermore, we show how the output of our method can be used to apply probabilistic top-k ranking for the objects, according to different state-of-the-art definitions. We conduct an experimental evaluation on synthetic and real data, which demonstrates the efficiency of our approach.

In this paper, we propose an original solution for the general reverse k-nearest neighbor (RkNN) search problem. Compared to the limitations of existing methods for the RkNN search, our approach works on top of any hierarchically organized tree-like index structure and, thus, is applicable to any type of data as long as a metric distance function is defined on the data objects. We will exemplarily show how our approach works on top of the most prevalent index structures for Euclidean and metric data, the R-Tree and the M-Tree, respectively. Our solution is applicable for arbitrary values of k and can also be applied in dynamic environments where updates of the database frequently occur. Although being the most general solution for the RkNN problem, our solution outperforms existing methods in terms of query execution times because it exploits different strategies for pruning false drops and identifying true hits as soon as possible.

In this paper, we formalize the novel concept of Constrained Reverse k-Nearest Neighbor (CRkNN) search on mobile objects (clients) performed at a central server. The CRkNN query computes for a given query object q the set RkNN(q) of objects having q as one of their k-nearest neighbors, iff the result set exceeds a specific threshold m, i.e. Card(RkNN(q)) ≥ m. Otherwise, the query reports an empty result. In our setting, the positions of the query object and database objects are approximated by minimal bounding rectangles that depend on the last reported location of the object, as well as on the time that has been passed since the object reported its recent exact location. We propose an approach that minimizes the amount of communication between clients and central server by using the approximation of the positions to identify true hits and true drops. We present a multi-step filter/refinement framework that uses a novel refinement heuristic to minimize the number of objects that are required to provide their exact location. Our solution does not assume any preprocessing steps which makes it applicable for dynamic environments where updates of the database frequently occur. Experiments show that our approach considerably reduces the communication load compared to existing approaches designed for traditional reverse nearest neighbor search in static data.

In this paper, we formalize the novel concept of incremental reverse nearest neighbor ranking and suggest an original solution for this problem. We propose an efficient approach for reporting the results incrementally without the need to restart the search from scratch. Our approach can be applied to a multi-dimensional feature database which is hierarchically organized by any R-tree like index structure. Our solution does not assume any preprocessing steps which makes it applicable for dynamic environments where updates of the database frequently occur. Our experiments show that our approach reports the ranking results with much less page accesses than existing approaches designed for traditional reverse nearest neighbor search applied to the ranking problem.

Probabilistic frequent itemset mining in uncertain transaction databases semantically and computationally differs from traditional techniques applied to standard "certain" transaction databases. The consideration of existential uncertainty of item(sets), indicating the probability that an item(set) occurs in a transaction, makes traditional techniques inapplicable. In this paper, we introduce new probabilistic formulations of frequent itemsets based on possible world semantics. In this probabilistic context, an itemset X is called frequent if the probability that X occurs in at least minSup transactions is above a given threshold τ. To the best of our knowledge, this is the first approach addressing this problem under possible worlds semantics. In consideration of the probabilistic formulations, we present a framework which is able to solve the Probabilistic Frequent Itemset Mining (PFIM) problem efficiently. An extensive experimental evaluation investigates the impact of our proposed techniques and shows that our approach is orders of magnitude faster than straight-forward approaches.

Recently, modern tracking methods started to allow capturing the position of massive numbers of moving objects. Given this information, it is possible to analyze and predict the traffic density in a network which offers valuable information for traffic control, congestion prediction and prevention. In this paper, we propose a novel statistical approach to predict the density on any edge of such a network at some time in the future. Our method is based on short-time observations of the traffic history. Therefore, knowing the destination of each traveling individual is not required. Instead, we assume that the individuals will act rationally and choose the shortest path from their starting points to their destinations. Based on this assumption, we introduce a statistical approach to describe the likelihood of any given individual in the network to be located at a certain position at a certain time. Since determining this likelihood is quite expensive when done in a straightforward way, we propose an efficient method to speed up the prediction which is based on a suffix-tree. In our experiments, we show the capability of our approach to make useful predictions about the traffic density and illustrate the efficiency of our new algorithm when calculating these predictions.