Recent research has shown that single-vector embedding retrieval models face a fundamental bottleneck: the finite dimensionality of single-vector representations limits their capacity to represent arbitrary top-k relevant item combinations, even with perfect training. This inherent bottleneck substantially limits the expressive capacity of such models and reduces their ability to capture complex user-item interaction patterns. To overcome this bottleneck, we propose Adaptive Rich-kernelized Contrastive Learning (ARC), which enhances model expressiveness while maintaining the computational efficiency of single-vector retrieval. ARC replaces the fixed inner product with a learnable spherical kernel family parameterized by a truncated Gegenbauer expansion, thereby increasing the model's effective dimensionality while preserving single-vector efficiency and low-pass inductive bias for generalization. Specifically, we construct a positive-definite kernel on the unit sphere using a positive combination of Gegenbauer polynomials, and adopt a contrastive learning objective to jointly learn the polynomials weights and user–item embeddings. Through data-driven optimization, the adaptive kernel induces a more expressive representation space, enabling the model to better capture complex preferences. From a theoretical perspective, the learned kernel implicitly maps embeddings into a higher-dimensional Reproducing Kernel Hilbert Space, allowing the model to capture a broader range of top-k item combinations before reaching the geometric limit imposed by the embedding dimensionality. Consequently, the proposed ARC framework effectively alleviates the inherent representational bottleneck in traditional single-vector embedding models. Extensive experiments on four real-world datasets demonstrate the effectiveness of our method, showing consistent improvements over strong baselines and state-of-the-art models.

Collaborative filtering is a primary paradigm of modern recommender systems. A typical practice is to embed collaborative signals into a latent space and infer recommendation scores based on the similarities between user and item embeddings. Besides inter-type similarities (i.e., user-item relationships), intra-type similarities (i.e., user-user, and item-item) are also essential as they capture the intrinsic structure of users and items. However, many existing recommendation models only learn inter-type similarities using objectives like ranking loss or binary classification loss, while neglecting intra-type similarities. Consequently, the intrinsic structures of users and items are often distorted in the latent space, where users with similar historical interactions diverge more than those dissimilar. In this study, we show the importance of preserving the ordinal relations of intra-type similarities. We provide a theoretical analysis suggesting that preserving intra-type similarity rankings can enhance a model's generalizability and interpretability. In addition, we propose a regularization that enforces a constraint on the rankings of intra-type similarities, ensuring that learning inter-type similarities does not break intrinsic ordinal structures. It can be seamlessly integrated into most latent factor models and can be jointly trained with their original objectives. Extensive experiments on 4 benchmark datasets and 5 representative models show that our ordinal regularization can consistently improve recommendation performance, and enhance the intra-type similarity coherence in the latent space. The results also exhibit enhanced generalizability and interpretability of recommendations.

State-of-the-art Time Series Classification (TSC) models such as HC2 and MultiRocket-Hydra reach high accuracy but rely on representations that are inherently difficult to interpret. Interval-based classifiers summarize local segments and thus provide more intuitive features. However, they are usually behind the most accurate methods. Our approach PULSAR—Pooled mUlti-scaLe Summaries from rAndomized inteRvals significantly enhances the accuracy of interval-based approaches and is close to MultiRocket-Hydra. PULSAR first converts every series into several representations (raw, derivative, periodogram, and others). It then uses sub-series of varied length and dilation and computes simple local statistics. To build higher-order features, it partitions each sequence of local statistics at multiple depths, applies a randomly chosen set of pooling operators to every partition, and keeps all aggregates from the coarsest level. For finer partitions we apply a supervised feature selection strategy to retain only the most discriminative features. Finally, we concatenate the selected aggregates with the global ones and train an ensemble classifier. We test PULSAR on 142 UCR datasets. It outperforms all interval-based approaches by a statistically significant margin and matches the predictive performance of HC2 and MultiRocket-Hydra. PULSAR sets a new benchmark for interval-based TSC while preserving a feature structure that we can still interpret.

Abstract Time series classification(TSC) aims to predict the class label of a given time series, which is critical to a rich set of application areas such as economics and medicine. State-of-the-art TSC methods have mostly focused on classification accuracy, without considering classification speed. However, efficiency is important for big data analysis. Datasets with a large training size or long series challenge the use of the current highly accurate methods, because they are usually computationally expensive. Similarly, classification explainability, which is an important property required by modern big data applications such asappliance modelingand legislation such as theEuropean General Data Protection Regulation, has received little attention. To address these gaps, we propose a novel TSC method – theRandomized-Supervised Time Series Forest(r-STSF). r-STSF is extremely fast and achieves state-of-the-art classification accuracy. It is an efficient interval-based approach that classifies time series according to aggregate values of the discriminatory sub-series (intervals). To achieve state-of-the-art accuracy, r-STSF builds an ensemble of randomized trees using the discriminatory sub-series. It uses four time series representations, nine aggregation functions and a supervised binary-inspired search combined with a feature ranking metric to identify highly discriminatory sub-series. The discriminatory sub-series enable explainable classifications. Experiments on extensive datasets show that r-STSF achieves state-of-the-art accuracy while being orders of magnitude faster than most existing TSC methods and enabling for explanations on the classifier decision.

A space-filling curve (SFC) maps points in a multi-dimensional space to one-dimensional points by discretizing the multi-dimensional space into cells and imposing a linear order on the cells. This way, an SFC enables computing a one-dimensional layout for multidimensional data storage and retrieval. Choosing an appropriate SFC is crucial, as different SFCs have different effects on query performance. Currently, there are two primary strategies: 1) deterministic schemes, which are computationally efficient but often yield suboptimal query performance, and 2) dynamic schemes, which consider a broad range of candidate SFCs based on cost functions but incur significant computational overhead. Despite these strategies, existing methods cannot efficiently measure the effectiveness of SFCs under heavy query workloads and numerous SFC options. To address this problem, we propose means of constant-time cost estimations that can enhance existing SFC selection algorithms, enabling them to learn more effective SFCs. Additionally, we propose an SFC learning method that leverages reinforcement learning and our cost estimations to choose an SFC pattern efficiently. Experimental studies offer evidence of the effectiveness and efficiency of the proposed means of cost estimation and SFC learning.

Learned indices can leverage the high prediction accuracy and efficiency of modern deep learning techniques. They are capable of delivering better query performance than traditional indices over one-dimensional data. Recent studies demonstrate that we can also achieve query-efficient learned in-dices for spatial data by partitioning and subsequently transforming spatial data to one-dimensional values, after which existing techniques can be applied. While enabling efficient querying, building and rebuilding learned spatial indices efficiently remains largely unaddressed. As the model training needed to learn a spatial index is costly, efficient building and rebuilding of learned spatial indices on large data sets is challenging if performed by means of model training and retraining.To advance the practicality of learned spatial indices, we propose a system named ELSI that enables the efficient building and rebuilding of a class of learned spatial indices that follow two simple design principles. The core idea is to reduce the model (re-)building times by engineering reduced training sets that preserve key data distribution patterns. ELSI encompasses a suite of methods for constructing small and distribution-preserving training sets from input data sets. Further, given an input data set, ELSI can adaptively select a method that produces a learned index with high query efficiency. Experiments on real data sets of 100+ million points show that ELSI can reduce the build times of four different learned spatial indices consistently (by up to two orders of magnitude) without jeopardizing query efficiency.

On-demand ride-sharing services such as Uber and Lyft have gained tremendous popularity over the past decade, largely driven by the omnipresence of mobile devices. Ride-sharing services can provide economic and environmental benefits such as reducing traffic congestion and vehicle emissions. Multi-hop ride-sharing enables passengers to transfer between vehicles within a single trip, which significantly extends the benefits of ride-sharing and provides ride opportunities that are not possible otherwise. Despite its advantages, offering real-time multi-hop ride-sharing services at large scale is a challenging computational task due to the large combination of vehicles and passenger transfer points. To address these challenges, we propose exact and approximation algorithms that are scalable and achieve real-time responses for highly dynamic ride-sharing scenarios in large metropolitan areas. Our experiments on real-world datasets show the benefits of multi-hop ride-sharing services and demonstrate that our proposed algorithms are more than two orders of magnitude faster than the state-of-the-art. Our approximation algorithms offer a comparable trip quality to our exact algorithm, while improving the ride-sharing request matching time by another order of magnitude.

Time series classification (TSC) aims to predict the class label of a given time series. Modern applications such as appliance modelling require to model an abundance of long time series, which makes it difficult to use many state-of-the-art TSC techniques due to their high computational cost and lack of interpretable outputs. To address these challenges, we propose a novel TSC method: the Supervised Time Series Forest (STSF). STSF improves the classification efficiency by examining only a (set of) sub-series of the original time series, and its tree-based structure allows for interpretable outcomes. STSF adapts a top-down approach to search for relevant sub-series in three different time series representations prior to training any tree classifier, where the relevance of a sub-series is measured by feature ranking metrics (i.e., supervision signals). Experiments on extensive real datasets show that STSF achieves comparable accuracy to state-of-the-art TSC methods while being significantly more efficient, enabling TSC for long time series.

On-demand ride-sharing is rapidly growing. Matching trip requests to vehicles efficiently is critical for the service quality of ride-sharing. To match trip requests with vehicles, a prune-and-select scheme is commonly used. The pruning stage identifies feasible vehicles that can satisfy the trip constraints (e.g., trip time). The selection stage selects the optimal one(s) from the feasible vehicles. The pruning stage is crucial to lowering the complexity of the selection stage and to achieve efficient matching. We propose an effective and efficient pruning algorithm called GeoPrune. GeoPrune represents the time constraints of trip requests using circles and ellipses, which can be computed and updated efficiently. Experiments on real-world datasets show that GeoPrune reduces the number of vehicle candidates in nearly all cases by an order of magnitude and the update cost by two to three orders of magnitude compared to the state-of-the-art.

Activity-Based ride-sharing is a new paradigm which enhances the current model based on fixed origins and destinations, namely trip-based ride-sharing. In this new model, a user issues a ride-sharing request with his origin and the activity he wants to perform at any convenient destination. Then, the system computes the travel plans and users will be suggested the optimal destinations, which may be common to many users. In this way, the set of possible destinations for each user is expanded and further distance savings can be made as we have already shown in our previous work [1, 3]. In this paper, we show Activity-Based ride-sharing in action through our web-service-based framework, which is able to suggest routes and meeting points for many users in a city-scale scenario.

Microscopic traffic simulators play a major role to carry research on transportation problems. Microscopic traffic simulation is powerful because it enables efficient analysis of complex traffic problems to the highest level of detail. We developed Scalable Microscopic Adaptive Road Traffic Simulator (SMARTS) [14] that can perform large-scale simulations at a high speed by utilizing distributed computing resources. Previous results show that SMARTS can run 1.14 times faster than real time when simulating one million vehicles for the city of Melbourne on 30 distributed processors, while producing highly accurate simulation results. SMARTS' pluggable architecture allows it to be easily extended to simulate specific scenarios of interest to users. In this demonstration we show how SMARTS can be used to simulate an intersection design, the P-turn, in a major intersection of Melbourne. Our simulation shows the impact of the design on the traffic flow, confirming the justification for introduction of the particular intersection. The demo can be used as a template for future use of the simulator for other traffic problems.

Studying trajectories of individuals has received growing interest. The aggregated movement behaviour of people provides important insights about their habits, interests, and lifestyles. Understanding and utilizing trajectory data is a crucial part of many applications such as location based services, urban planning, and traffic monitoring systems. Spatial histograms and spatial range queries are key components in such applications to efficiently store and answer queries on trajectory data. A spatial histogram maintains the sequentiality of location points in a trajectory by a strong sequential dependency among histogram cells. This dependency is an essential property in answering spatial range queries. However, the trajectories of individuals are unique and even aggregating them in spatial histograms cannot completely ensure an individual's privacy. A key technique to ensure privacy for data publishing ϵ-differential privacy as it provides a strong guarantee on an individual's provided data. Our work is the first that guarantees ϵ-differential privacy for spatial histograms on trajectories, while ensuring the sequentiality of trajectory data, i.e., its consistency. Consistency is key for any database and our proposed mechanism, PriSH, synthesizes a spatial histogram and ensures the consistency of published histogram with respect to the strong dependency constraint. In extensive experiments on real and synthetic datasets, we show that (1) PriSH is highly scalable with the dataset size and granularity of the space decomposition, (2) the distribution of aggregate trajectory information in the synthesized histogram accurately preserves the distribution of original histogram, and (3) the output has high accuracy in answering arbitrary spatial range queries.

Ride-sharing is rapidly becoming an alternative form of transportation mainly due to its economic benefits. Existing research on ridesharing aims to optimally match trajectories between people with pre-selected destinations. In this paper, we show better ride-sharing arrangements are possible when users are presented with more destinations and agree on a common destination. Given a set of points of interest (POIs) and a set of users, our approach presents destination POIs and computes ride-sharing plans. Each arrangement for a subset of users that fit in a car can be presented as a minimum Steiner tree (MST) problem. An optimal solution of the overall problem minimizes the total length of all the MSTs. The problem is a version of the set cover problem and is NP-hard. We first develop a series of baseline methods which use a popular MST algorithm. Then, we propose our method which uses constraints on intermediary points where users can meet to share rides. These constraints reduce the time complexity significantly and our method is up to two orders of magnitude faster than the best baseline method. Since our algorithm finds the subsets of users and POIs for each arrangement, we define and solve a new type of MST problem as a first step. Our experiments show that our method can provide a fast and readily deployable solution for real world large city scenarios.

Hitchhiking is the oldest ridesharing process without prior arrangements by the ride sharers. It usually involves uncertain waiting times and various combinations of lifts on roads. For this way of traveling, the problem of finding an optimal route is extremely important and has not been studied. We propose the concept of a hitchhiking graph to represent all possible decisions that a hitchhiker can consider on a road network. We develop an efficient pruning technique for a faster computation of the optimal route with the least expected journey time. The effectiveness of our methods is evaluated on road networks of selected countries.

Since its introduction a decade ago, differential privacy has been deployed and adapted in different application scenarios due to its rigorous protection of individuals' privacy regardless of the adversary's background knowledge. An urgent open research issue is how to query/release time evolving datasets in a differentially private manner. Most of the proposed solutions in this area focus on releasing private counters or histograms, which involve low sensitivity, and the main focus of these solutions is minimizing the amount of noise and the utility loss throughout the process. In this paper we consider the case of releasing private numerical values with unbounded sensitivity in a dataset that grows over time. While providing utility bounds for such case is of particular interest, we show that straightforward application of current mechanisms cannot guarantee (differential) privacy for individuals under an open-world assumption where data is continuously being updated, especially if the dataset is updated by an outlier.

Microscopic traffic simulators are important tools for studying transportation systems as they describe the evolution of traffic to the highest level of detail. A major challenge to microscopic simulators is the slow simulation speed due to the complexity of traffic models. We have developed the Scalable Microscopic Adaptive Road Traffic Simulator (SMARTS), a distributed microscopic traffic simulator that can utilize multiple independent processes in parallel. SMARTS can perform fast large-scale simulations. For example, when simulating 1 million vehicles in an area the size of Melbourne, the system runs 1.14 times faster than real time with 30 computing nodes and 0.2s simulation timestep. SMARTS supports various driver models and traffic rules, such as the car-following model and lane-changing model, which can be driver dependent. It can simulate multiple vehicle types, including bus and tram. The simulator is equipped with a wide range of features that help to customize, calibrate, and monitor simulations. Simulations are accurate and confirm with real traffic behaviours. For example, it achieves 79.1% accuracy in predicting traffic on a 10km freeway 90 minutes into the future. The simulator can be used for predictive traffic advisories as well as traffic management decisions as simulations complete well ahead of real time. SMARTS can be easily deployed to different operating systems as it is developed with the standard Java libraries.

With the popularity of mobile GPS devices such as on-board navigation systems and smart phones, users can contribute their GPS trajectory data for creating geo-volunteered road maps. However, the quality of these road maps cannot be guaranteed due to the lack of expertise among contributing users. Therefore, important challenges are (i) to automatically generate accurate roads from GPS traces and (ii) to validate the correctness of existing road maps. To address these challenges, we propose a novel Spatial-Linear Clustering (SLC) technique to infer road segments from GPS traces. In our algorithm, we propose the use of spatial-linear clusters to appropriately represent the linear nature of GPS points collected from the same road segment. Through inferring road segments our algorithm can detect missing roads and checking the correctness of existing road network. For our evaluation, we conduct extensive experiments that compare our method to the state-of-the-art methods on two real data sets. The experimental results show that the F1 score of our algorithm is on average 10.7% higher than the best state-of-the-art method.

A Group Nearest Neighbor (GNN) query finds a point of interest (POI) that minimizes the aggregate distance for a group of users. In current systems, users have to reveal their exact, often sensitive locations to issue a GNN query. This calls for private GNN queries. However, existing methods for private GNN queries either are computationally too expensive for mobile phones or cannot resist sophisticated attacks. Our approach can efficiently and effectively process an important variant of private GNN queries: queries that minimize the maximum distance for any user in the group. To achieve high efficiency we develop a distributed multi-party private protocol to compute the maximum function. Our method exploits geometric constraints to prune POIs and avoids unnecessary data disclosure. In contrast to current state of the art multi-party private protocols, our proposed protocol does not rely on cryptography and has a fast runtime. Importantly, a user does not have to provide a location directly, even in imprecise form.

Recent advancements in data mining coupled with the ubiquity of mobile devices has led to the possibility of mining for events in real-time. We introduce the problem of mining for an individual's encounters. As people travel, they may have encounters with one another. We are interested in detecting the encounters of traveling individuals at the exact moment in which each of them occur. A simple solution is to use a nearest neighbor search to return potential encounters, this results in slow query response times. To mine for encounters in real-time, we introduce a new algorithm that is efficient in capturing encounters by exploiting the observation that just the neighbors in a defined proximity needs to be maintained. Our evaluation demonstrates that our proposed method mines for encounters for millions of individuals in a city area within milliseconds.

A group of friends located at their working places may want to plan a trip to visit a shopping center, have dinner at a restaurant, watch a movie at a theater, and then finally return to their homes with the minimum total trip distance. For a group of spatially dispersed users a group trip planning (GTP) query returns points of interests (POIs) of different types such as a shopping center, a restaurant and a movie theater that minimize the aggregate trip distance for the group. The aggregate trip distance could be the sum or maximum of the trip distances of all users in the group, where the users travel from their source locations via the jointly visited POIs to their individual destinations. In this paper, we develop both optimal and approximation algorithms for GTP queries for both Euclidean space and road networks. Processing GTP queries in real time is a computational challenge as trips involve POIs of multiple types and computation of aggregate trip distances. We develop novel techniques to refine the POI search space for a GTP query based on geometric properties of ellipses, which in turn significantly reduces the number of aggregate trip distance computations. An extensive set of experiments on a real and synthetic datasets shows that our approach outperforms the most competitive approach on an average by three orders of magnitude in terms of processing time.

We introduce a new type of spatial query, Optimal Accessible Location (OAL) query. When a set of paths is provided the query finds the best location from a set of locations that has the optimal accessibility from these paths. OAL queries have many applications such as the selection of the optimal location for a mobile facility such as a food truck or selection of a venue for an event. We exploit geometric properties and develop pruning techniques to eliminate unrelated path segments as well as locations. Our experimental results demonstrate that we provide a readily deployable solution for real-life applications.

Trajectory inference from raw location samples of a mobile device is an important task for many location based services, such as crowd sourced traffic monitoring, fleet management and personalized trip planning. This task becomes challenging when location samples are obtained only from the connected cell towers (GSM localization), instead of using other localization sensors such as GPS or Wi-Fi. Cell tower based localization consumes negligible energy compared to GPS or Wi-Fi and has high availability. However, it can have large inaccuracy, making the task of cellular trajectory mapping extremely challenging. In previous studies, cellular trajectory inference has been performed assuming the availability of knowledge of the cellular network or the signal strengths of the neighbouring cell towers. However, for a mobile application running on a user's device, this information may be hard to obtain and it may also require additional storage and computation costs. In this paper, we propose a novel cellular trajectory inference method which requires only the user's connected cell tower location, time and speed information. Exploiting the preciseness of the time dimension, we accurately compute the distance a user has travelled within a cell and use it to infer the straight line segments and turning points of a trajectory. We show that using the distance information of three consecutive cells, exact inference of the line segment is possible. Our method achieves high accuracy for trajectory inference in urban areas with high cell density and straight line road segments. It does not require any historical trajectory information or pre-training and incurs low storage and computation costs.

Localization schemes used for positioning are currently based on either range-based or range-free principles. We propose a unified approach that combines the strengths of both methods while overcoming their limitations. Range-based methods rely on taking reliable measurements in which geometric techniques are then applied. These techniques are very susceptible to imprecision in captured measurements. Range-free methods do not consider the actual numerical sensor value, rather comparing magnitudes across sensors. These comparisons are not always reliable and may lead to an accumulation of errors. Our unified approach mitigates these effects by first using a range-based method to determine an approximate location followed by a range-free method to refine the positioning estimate further. Our experiments show the mean estimation error improves when applying our localization scheme to a Bluetooth system.

Monitoring and predicting traffic conditions are of utmost importance in reacting to emergency events in time and for computing the real-time shortest travel-time path. Mobile sensors, such as GPS devices and smartphones, are useful for monitoring urban traffic due to their large coverage area and ease of deployment. Many researchers have employed such sensed data to model and predict traffic conditions. To do so, we first have to address the problem of associating GPS trajectories with the road network in a robust manner. Existing methods rely on point-by-point matching to map individual GPS points to a road segment. However, GPS data is imprecise due to noise in GPS signals. GPS coordinates can have errors of several meters and, therefore, direct mapping of individual points is error prone. Acknowledging that every GPS point is potentially noisy, we propose a radically different approach to overcome inaccuracy in GPS data. Instead of focusing on a point-by-point approach, our proposed method considers the set of relevant GPS points in a trajectory that can be mapped together to a road segment. This clustering approach gives us a macroscopic view of the GPS trajectories even under very noisy conditions. Our method clusters points based on the direction of movement as a spatial-linear cluster, ranks the possible route segments in the graph for each group, and searches for the best combination of segments as the overall path for the given set of GPS points. Through extensive experiments on both synthetic and real datasets, we demonstrate that, even with highly noisy GPS measurements, our proposed algorithm outperforms state-of-the-art methods in terms of both accuracy and computational cost.

Trajectory data does not only show the location of users over a period of time, but also reveals a high level of detail regarding their lifestyle, preferences and habits. Hence, it is highly susceptible to privacy concerns. Trajectory privacy has become a key research topic when sharing/exchanging trajectory datasets. Most existing studies focus on protecting trajectory data through obfuscating, anonymising or perturbing the data with the aim to maximize user privacy. Although such approaches appear plausible, our work suggests that precise trajectory information can be inferred even from other sources of data. We consider the case in which a location service provider only shares POI query results of users with third parties instead of exchanging users' raw trajectory data to preserve privacy. We develop an inference algorithm and show that it can effectively approximate original trajectories using solely the POI query results.

Research on cognitive science indicates that humans often use different criteria for route selection. An alternative type of spatial proximity search on road networks recently has been proposed to find the easiest-to-reach neighboring object with the smallest navigation complexity. This paper presents an evaluation to compare the effectiveness of easiest-to-reach neighbor query against a classic nearest neighbor query in a real-world setting. Our user study demonstrates usability of the new spatial query type and suggests people may not always care about travel distance most. To provide flexibility to accommodate different requirements, we also show how to achieve tradeoff between navigation complexity and travel distance for advanced navigational assistance.

Mining GPS trajectories of moving vehicles has led to many research directions, such as traffic modeling and driving predication. An important challenge is how to map GPS traces to a road network accurately under noisy conditions. However, to the best of our knowledge, there is no existing work that first simplifies a trajectory to improve map matching. In this paper we propose three trajectory simplification algorithms that can deal with both offline and online trajectory data. We use weighting functions to incorporate spatial knowledge, such as segment lengths and turning angles, into our simplification algorithms. In addition, we measure the noise degree of a GPS point based on its spatio-temporal relationship to its neighbors. The effectiveness of our algorithms is comprehensively evaluated on real trajectory datasets with varying the noise levels and sampling rates. Our evaluation shows that under highly noisy conditions, our proposed algorithms considerably improve map matching accuracy and reduce computational costs compared to the state-of-the-art methods.

In this paper, we introduce obstructed group nearest neighbor (OGNN) queries, that enable a group to meet at a point of interest (e.g., a restaurant) with the minimum aggregate travel distance in an obstructed space. In recent years, researchers have focused on developing algorithms for processing GNN queries in the Euclidean space and road networks, which ignore the impact of obstacles such as buildings and lakes in computing distances. We propose the first comprehensive approach to process an OGNN query. We present an efficient algorithm to compute aggregate obstructed distances, which is an essential component for processing OGNN queries. We exploit geometric properties to develop pruning techniques that reduce the search space and incur less processing overhead. We validate the efficacy and efficiency of our solution through extensive experiments using both real and synthetic datasets.

Substring matching is fundamental to data mining methods for sequential data. It involves checking the existence of a short subsequence within a longer sequence, ensuring no gaps within a match. Whilst a large amount of existing work has focused on substring matching and mining techniques for certain sequences, there are only a few results for uncertain sequences. Uncertain sequences provide powerful representations for modelling sequence behavioural characteristics in emerging domains, such as bioinformatics, sensor streams and trajectory analysis. In this paper, we focus on the core problem of computing substring matching probability in uncertain sequences and propose an efficient dynamic programming algorithm for this task. We demonstrate our approach is both competitive theoretically, as well as effective and scalable experimentally. Our results contribute towards a foundation for adapting classic sequence mining methods to deal with uncertain data.

Privacy concerns place a great impediment to publishing and/or exchanging trajectory data across companies and institutions. This has urged researchers to address privacy issues prior to trajectory data release. Currently, privacy preserving solutions distort original data unnecessarily, hence, degrade data utility and make such data less useful for third parties. We consider a trajectory as a sequence of stops and moves, and propose an approach that exploits features of a trajectory as means for preserving privacy while maintaining a high level of utility. We introduce the concept of sensitivity for stops based on the assumption that they are more vulnerable to privacy threats. We propose an efficient algorithm that either substitutes sensitive stop points of a trajectory with moves from the same trajectory or introduces a minimal detour if a less sensitive stop can not be found on the same route. Our experiments shows that our method balances user privacy and data utility: it protects privacy through preventing an adversary from making inferences about sensitive stops while maintaining a high level of data similarity to the original dataset.

Uncertainty is common in real-world applications, for example, in sensor networks and moving object tracking, resulting in much interest in item set mining for uncertain transaction databases. In this paper, we focus on pattern mining for uncertain sequences and introduce probabilistic frequent spatial-temporal sequential patterns with gap constraints. Such patterns are important for the discovery of knowledge given uncertain trajectory data. We propose a dynamic programming approach for computing the frequentness probability of these patterns, which has linear time complexity, and we explore its embedding into pattern enumeration algorithms using both breadth-first search and depth-first search strategies. Our extensive empirical study shows the efficiency and effectiveness of our methods for synthetic and real-world datasets.

Moving object data, in particular of mobile users, is becoming widely available. A GPS trajectory of a moving object is a time-stamped sequence of latitude and longitude coordinates. The analysis and extraction of knowledge from GPS trajectories is important for a range of applications. Existing studies have extracted knowledge from trajectory patterns for both single and multiple GPS trajectories. However, few works have taken into account the unreliability of GPS measurements for mobile devices or focused on the extraction of fine-grained events from a user's GPS trajectory, such as waiting in traffic, at an intersection, or at a bus stop. In this paper, we develop and experimentally evaluate a novel algorithm that analyses a mobile user's bearing change distribution, together with speed and acceleration, to extract significant places of events from their GPS trajectory.

Origin-destination matrices are important for effective real time traffic management. These matrices contain the spatial and temporal distribution of traffic demand, which is a vital input for transportation planning processes. Trajectories represent the different traffic flow routes between the source destination pairs taken by the travelling vehicles. We present a privacy aware model to compute origin-destination (OD) matrix and the corresponding trajectories. Our main contribution is the use of partial vehicle information to compute the trajectories and OD matrix while maintaining accuracy and privacy. We propose local re-identification of vehicles to build local transition matrices at every node of the network. We introduce k-anonymous l-grouping for our trajectory estimation to provide a trade-off between accuracy and privacy. We present a Trajectory Estimation algorithm to determine trajectories and estimate the OD matrix.

We propose and study a new type of location optimization problem: given a set of clients and a set of existing facilities, we select a location from a given set of potential locations for establishing a new facility so that the average distance between a client and her nearest facility is minimized. We call this problem the min-dist location selection problem, which has a wide range of applications in urban development simulation, massively multiplayer online games, and decision support systems. We explore two common approaches to location optimization problems and propose methods based on those approaches for solving this new problem. However, those methods either need to maintain an extra index or fall short in efficiency. To address their drawbacks, we propose a novel method (named MND), which has very close performance to the fastest method but does not need an extra index. We provide a detailed comparative cost analysis on the various algorithms. We also perform extensive experiments to evaluate their empirical performance and validate the efficiency of the MND method.

User privacy in location-based services has attracted great interest in the research community. We introduce a novel framework based on a decentralized architecture for privacy preserving group nearest neighbor queries. A group nearest neighbor (GNN) query returns the location of a meeting place that minimizes the aggregate distance from a spread out group of users; for example, a group of users can ask for a restaurant that minimizes the total travel distance from them. We identify the challenges in preserving user privacy for GNN queries and provide a comprehensive solution to this problem. In our approach, users provide their locations as regions instead of exact points to a location service provider (LSP) to preserve their privacy. The LSP returns a set of candidate answers that includes the actual group nearest neighbor. We develop a private filter that determines the actual group nearest neighbor from the retrieved candidate answers without revealing user locations to any involved party, including the LSP. We also propose an efficient algorithm to evaluate GNN queries with respect to the provided set of regions (the users' imprecise locations). An extensive experimental study shows the effectiveness of our proposed technique.

Continuous queries in road networks have gained significant research interests due to advances in GIS and mobile computing. Consider the following scenario: "A driver uses a networked GPS navigator to monitor five nearest gas stations in a road network." The main challenge of processing such a moving query is how to efficiently monitor network distances of the k nearest and possible resultant objects. To enable result monitoring in real-time, researchers have devised techniques which utilize precomputed distances and results, e.g., the network Voronoi diagram (NVD). However, the main drawback of preprocessing is that it requires access to all data objects and network nodes, which means that it is not suitable for large datasets in many real life situations. The best existing method to monitor kNN results without precomputation relies on executions of snapshot queries at network nodes encountered by the query point. This method results in repetitive distance evaluation over the same or similar sets of nodes. In this paper, we propose a method called the local network Voronoi diagram (LNVD) to compute query answers for a small area around the query point. As a result, our method requires neither precomputation nor distance evaluation at every intersection. According to our extensive analysis and experimental results, our method significantly outperforms the best existing method in terms of data access and computation costs.

Studies in cognitive science have shown that people have differ-ent optimization goals in mind for route selection: beyond shortest travel distance (or time), criteria such as smallest number of turns or straightest path are often considered. A common query that a traveller in a foreign city may ask is “where is a facility of type X”. When multiple facilities of the same type are available in the nearby area, usually not the nearest neighbor but the one which is easiest to find is preferred for giving instructions by locals, especially in an unfamiliar and complex urban environment. This paper studies a novel type of neighboring object selection problem, taking cog-nitive complexity of navigation into account. The main difficulty arises from incorporating spatial chunking and landmark informa-tion into neighbor comparisons. We propose an algorithm based on network expansion, which uses incremental processing of graph transformation that models instruction complexity. Our approach can efficiently find the easiest-to-reach neighbor with the guaran-teed smallest navigation cost. Through experimental evaluation on real road networks, the performance of the proposed algorithm is demonstrated under various settings. Our comparison results reveal that on average the travel distance of the easiest-to-reach neighbor is only 19.3 % longer than that of the nearest neighbor, whereas the navigation cost can achieve a 64.8 % reduction.

ACM International Conference on Advances in Geographic Information Systems (SIGSPATIAL)

We present two novel merging algorithms that optimize traffic flow on highways, particularly at intersections of ramps and main roads. In our work, cars are equipped with sensors that can detect distance to neighboring cars, and communicate their velocity and acceleration readings with one another. Sensor-enabled cars can locally exchange sensed information about traffic and adapt their behavior much earlier than regular cars. However, the accuracy level of sensors is a major challenge for merging algorithms, because inaccuracies can potentially lead to unsafe merging behaviors. In this paper, we investigate how the accuracy of sensors impacts merging algorithms, and design robust merging algorithms that tolerate sensor errors. Experimental results show that our main proposed merging algorithm, which is based on concepts from time geography, is able to guarantee safe merging while tolerating four times more imprecise positioning information, and can double the road capacity and increase the traffic flow by 25%.

This demonstration program presents the V*-kNN algorithm, an efficient algorithm to process moving k nearest neighbor queries (MkNN). The V*-kNN algorithm is based on a safe-region concept called the V*-Diagram. By incrementally maintaining the V*-Diagram, V*-kNN continuously provides accurate MkNN query results and supports dynamically changing values of k. Our approach exploits information regarding the current location of the query point and the search space in addition to the data objects. As a result, the V*-kNN has much smaller IO and computation costs than existing methods.

Existing techniques for autonomous indoor navigation are often environment-specific and thus limited in terms of their applicability. In this paper, we take a fundamentally different approach to indoor navigation and propose an active environment based navigation system. We argue that for a versatile navigation system the environment itself should provide spatial information. In our proposed approach, navigation is based on the concept of space partitions where the location of an agent is approximated by the closest partition. We show that Radio Frequency Identification (RFID) technology is a viable option for generating space partitions. We present a cost effective deployment strategy for passive RFID tags to construct a complete partitioning of the environment. A sparse deployment of tags leads to coarse partitioning, which in turn allows an agent to only approximate its position. We introduce a path planning algorithm that enables an agent reach its destination with a small overhead compared to the shortest path algorithm assuming precise information. Our experiments show that the deployment allows efficient path planning even under a large degree of imprecision.

With recent advances in mobile computing technologies, mobile devices can now render 3D objects realistically. Many users of these devices such as tourists, mixed-reality gamers, and rescue officers, need real-time retrieval of 3D objects over a wireless network. Due to bandwidth and latency restrictions in mobile settings, efficient continuous retrieval of 3D objects remains a challenge. In this paper, we describe a motion-aware approach to this problem. We first introduce multi-resolution storage and retrieval methods for 3D data, which restrict access to only the necessary content based on the client's motion pattern. We then propose a motion-aware buffer management technique as well as an efficient index using multi-resolution representations of objects. Our experiments demonstrate the effectiveness of our solution to continuous retrieval of complex spatial data in mobile settings.

The moving k nearest neighbor (M k NN) query finds the k nearest neighbors of a moving query point continuously. The high potential of reducing the query processing cost as well as the large spectrum of associated applications have attracted considerable attention to this query type from the database community. This paper presents an incremental safe-region-based technique for answering M k NN queries, called the V*-Diagram. In general, a safe region is a set of points where the query point can move without changing the query answer. Traditional safe-region approaches compute a safe region based on the data objects but independent of the query location. Our approach exploits the current knowledge of the query point and the search space in addition to the data objects. As a result, the V*-Diagram has much smaller IO and computation costs than existing methods. The experimental results show that the V*-Diagram outperforms the best existing technique by two orders of magnitude.

For monitoring moving objects via wireless sensor networks, we introduce two aggregate query types: distinct entries to an area and the number of objects in that area. We present a new technique, Distributed Euler Histograms (DEHs), to store and query aggregated moving object data. Aggregate queries occur in a variety of applications ranging from wildlife monitoring to traffic management. We show that DEHs are significantly more efficient, in terms of communication and data storage costs, than techniques based on moving object identifiers and more accurate than techniques based on simple histograms.