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.

Family caregivers of people living with dementia need easy-to-access strategies to manage changing care needs. Music therapy is valuable for supporting dementia care, but not always accessible. Technologies could potentially facilitate accessible, home-based music therapy support, but need to be carefully evaluated. We conducted an 8-week field trial of a prototype mobile application, MATCH, with caregivers and people living with dementia. MATCH contains training videos and suggested playlists showing how to use music for specific care needs. MATCH, and music streaming broadly, enabled caregivers to add new strategies to their care repertoire, addressing a range of care needs and enhancing the care relationship. To make MATCH work, however, caregivers needed to fit it into complex care environments and existing technologies. We argue that digital therapeutic tools need to be adopted by caregivers to fit their individual contexts, and this can challenge assumptions about how therapeutic tools will work in practice.

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.

Short bursts of repeating patterns [intervals of recurrence (IoR)] manifest themselves in many applications, such as in the time-series data captured from an athlete's movements using a wearable sensor while performing exercises. We present an efficient, online, one-pass, and real-time algorithm for finding and tracking IoR in a time-series data stream. We provide a detailed theoretical analysis of the behavior of any IoR and derive fundamental properties that can be used on real-world data streams. We show that why our method, unlike current state-of-the-art techniques, is robust to variations in repeats of the same pattern adjacent to each other. To evaluate our algorithm, we build a wearable device that runs our algorithm to conduct a user study. Our results show that our algorithm can detect intervals of repeating activities on edge devices with high accuracy (over 70% F1 -Score) and in a real-time environment with only a 1.5-s lag. Our experimental results from real-world datasets demonstrate that our approach outperforms state-of-the-art algorithms in both accuracy and robustness to variations of the signal of recurrence.

In time series data, consecutively repeated patterns occur in many applications, including activity recognition from wearable sensors. Repeating patterns may vary over time and present in various shapes and sizes, which makes their detection a challenging problem. We develop a novel technique, RP-Mask, that can detect and localise segments of consecutively repeated patterns, without prior knowledge about the shape and length of the repeats. Our technique represents time series using recurrence plots (RP), a method for visualising repetition in time series. We identify two key features of recurrence plots-checkerboard patterns and vertical/horizontal lines marking the start and end of checkerboard patterns. We use object recognition on RP images to detect and localise the checkerboard patterns, which are mapped to the segments of consecutively repeating patterns on the underlying time series. Since the collection and labeling of a real world dataset that exhibits all possible variations of a repetition is prohibitive, we demonstrate that our model is able to effectively learn from synthetically curated data and perform equally effective on a real world dataset, while it is noise tolerant. We compare our method to a number of state-of-the-art techniques and show that our method outperforms the state of the art both when trained using real activity recognition and synthetic data.

Today's vehicles are advancing from stand-alone transportation means to vehicle-to-vehicle, and vehicle-to-infrastructure communications enabled devices which are able to exchange data through the transportation communication infrastructure. As the IoT and data remain intrinsically linked together, the fast-changing mobility landscape of intent-based networking for the Internet of connected vehicles comes with a great risk of data security and privacy violations. This paper considers the privacy issues in the distributed edge computing, in which the data is communicated between a number of vehicles in the IoT layer and potentially untrusted edge controllers at the edge of the network. The sensory data communicated by the vehicles contain sensitive information, such as location and speed, which could violate the users' privacy if they are leaked with no perturbation. Recent studies suggest mechanisms for randomizing the stream of data to ensure individuals' privacy. Although the past works on differential privacy provide a strong privacy guarantee, they are limited to applications where communication parties are trusted and/or there is no correlation between the users or the featured of sensory data. In this paper, we address this gap by proposing a differentially private data streaming system that adds a correlated noise in the vehicle's side (IoT layer) rather than the transportation infrastructure. Also, our system is able to ensure a strong privacy level over time. The proposed mechanism is data-adaptive and scales the noise with respect to the data correlation. Our extensive experiments demonstrate that the utility of the output generated by our method outperforms the recent approaches.

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.

To analyse visual systems, the concept of an ideal observer promises an optimal response for a given task. Bayesian ideal observers can provide optimal responses under uncertainty, if they are given the true distributions as input. In visual search tasks, prior studies have used signal to noise ratio (SNR) or psychophysics experiments to set the distributional parameters for simple targets on backgrounds with known patterns, however these methods do not easily translate to complex targets on natural scenes. Here, we develop a model of target detectability in natural images to estimate the parameters of target-present and target-absent distributions for a visual search task. We present a novel approach for approximating the foveated detectability of a known target in natural backgrounds based on biological aspects of human visual system. Our model considers both the uncertainty about target position and the visual system's variability due to its reduced performance in the periphery compared to the fovea. Our automated prediction algorithm uses trained logistic regression as a post processing phase of a pre-trained deep neural network. Eye tracking data from 12 observers detecting targets on natural image backgrounds are used as ground truth to tune foveation parameters and evaluate the model, using cross-validation. Finally, the model of target detectability is used in a Bayesian ideal observer model of visual search, and compared to human search performance.

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.

We describe a new generative algorithm called trajectory generative mechanism (TGM) for publishing trajectory datasets with ε-differential privacy guarantee, which achieves substantially higher computational efficiency and utility (practical) than the state-of-the-art algorithms. Our algorithm first encodes (models) the data as a graphical generative model and accurately captures the statistics of moving object trajectories. Using this model, TGM then privately generates synthetic trajectories such that the noise is optimally added to capture the movement direction of an object. Our algorithm preserves both the spatial and temporal information of trajectories in the generated dataset, requires less memory and computation than the competing approaches, and preserves the properties of real trajectory data in terms of traveled distance and stay location. We demonstrate the performance of TGM on both real and simulated datasets with a wide range of settings. Our experimental results show that TGM achieves high utility and efficiency by using the properties of the data.

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.

Smartphones have allowed us to make ad-hoc travel arrangements. Ride-sharing is emerging as one of the new types of transportation enabled by smartphone revolution. Ride-sharing aims to alleviate current environmental, social and economical issues many big cities are facing due to low vehicle occupancy rates. Although ride-sharing companies have millions of users around the world, some of them do not offer true ride-sharing but a similar service called ride-sourcing where private car owners provide for-hire rides. Ride-sharing uptake has not been wide due to lack of convenience and incentives. We propose an enhanced ride-sharing model through the inclusion of proper places to meet that we call hot-spots. Hot-spots are shown to increase the convenience by solving the round-trip ride-sharing problem. As we represent our enhanced model through graphs, we introduce a new graph problem that we call Constrained Variable Steiner Tree, which is NP-hard. An effective and readily deployable heuristic solution to this problem is presented which is up to two orders of magnitude faster than the state-of-the-art solution as combinatorial explosion is avoided by the usage of a novel monotonic nondecreasing function.

There are many applications that rely on the analysis of historical trajectory data provided by location-aware devices. Traffic management, ridesharing and Pay-As-You-Drive insurance are some example applications. These applications require one to scan a large-scale historical dataset in order to extract similar trajectories to a query trajectory. A naive approach is a one-by-one similarity comparison between the query trajectory and dataset trajectories. However, most existing methods for assessing similarity between pairs of trajectories have quadratic time-complexity, making sequential scan of a large dataset computationally expensive. Existing solutions for this problem mainly focus on reducing the computation time by summarizing the trajectories or by defining upper-bounds (lower-bounds) for the similarity between two trajectories. However, these solutions do not directly address the efficiency challenge. To tackle this challenge of large scale similar trajectory retrieval, we propose an efficient index structure that filters out distant trajectories and outputs an approximate set of similar trajectories. Experimental results show that our novel index structure significantly improves the efficiency of trajectory retrieval, whilst maintaining high accuracy.

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.

Emergency vehicle prioritization is important to the efficiency of emergency services. To address certain challenges in emergency vehicle prioritization, we perform microscopic simulations of an intelligent transportation system, where emergency vehicles broadcast certain information about their routes to nearby vehicles and traffic lights. Our study shows that broadcasting the route information can help reduce the response time of emergency vehicles significantly. In certain case, travel time of emergency vehicles can be as low as 37.1% of that of non-priority vehicles.

Car occupancy rates (travelers per vehicle) are currently very low in most developed countries, for example, on average between 1.15 and 1.25 in Australia. Enabling shared rides on short notice can be an effective solution to counter the problem of increasing traffic through the use of the untapped transportation capacity. Common inhibitors for the uptake of ride sharing services are privacy and safety concerns. We present an approach to ride sharing where the pick up/drop off locations for passengers are selected from a fixed set, which has the advantage of increased safety through video surveillance. We present a scheme that chooses optimally fixed locations of Pick up Points (PuPs) and aims to maximize the car occupancy rates while preserving user privacy and safety. Our method enhances privacy as the users do not need to provide their precise home/work locations. We have extended the well studied 1-coverage problem, i.e., to cover an area with the minimum number of circles of a given radius [1], to road networks. The challenges for road networks are the varying population densities of suburbs which requires circles of different radii. The aim is to ensure that every point of a city's area is covered by at least one PuP while minimizing the total number of PuPs. By ensuring that we have different circle radii for PuPs the anonymity of individuals is the same throughout. Using Voronoi diagrams we present a k-anonymity model that guarantees a minimum number of individuals covered by every PuP. Our problem is a multi objective problem where we aim to maximize coverage, k-anonymity and privacy provided by the system to its users while facilitating ride sharing. Through greedy randomized adaptive search procedure (GRASP) we find out the Pareto front of solutions and evaluate their impact on ride sharing.

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.

This paper considers what we can learn from the experiences of people who choose not to participate in technology-based social interventions. We conducted ethnographically-informed field studies with socially isolated older adults, who used and evaluated a new iPad application designed to help build new social connections. In this paper we reflect on how the values and assumptions guiding the technological intervention were not always shared by those participating in the evaluation. Drawing on our field notes and interviews with the older adults who chose to discontinue participation, we use personas to illustrate the complexities and tensions involved in individual decisions to not participate. This analysis contributes to HCI research calling for a more critical perspective on technological interventions. We provide detailed examples highlighting the complex circumstances of our non-participants' lives, present a framework that outlines the socio-technical context of non-participation, and use our findings to promote reflective practice in HCI research that aims to address complex social issues.

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.

The advancement of sensor equipped smartphones provides tremendous opportunities for fine-grained monitoring of user Points of Interest (POIs) for a range of mobile applications such as place-based advertisement, personalised healthcare services, location based social networks. Existing systems, however, cannot infer both indoor and outdoor POIs using a single approach and typically require a mix of technologies for localization such as GPS, GSM or Wi-Fi. The accuracy of these techniques depend on the availability of local infrastructure and normally can retrieve POIs only at a coarse level, for example at the level of a building or region. We develop a novel algorithm to automatically detect user POIs in near real time at room level accuracy using only lightweight ambient environment sensors. Our method can infer both indoor and outdoor POIs at a fine granularity without depending on local infrastructure or without using GPS or Wi-Fi. It works in an unsupervised manner using covariances of ambient sensor data to detect user visits to POIs. An experimental study with real-world data shows that our system can achieve an F1 score of approximately 80% for the top 3 retrieved locations and outperforms the existing approaches such as Google place search and Foursquare venue search.

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.

People are increasingly volunteering personal data. Services based on this data rely on a high number of participants and high data quality. Personal data is often seen as private and individuals are more likely to provide such data if they can choose its granularity, e.g., instead of an exact value, they may provide a range. Focusing on spatial crowdsourced data, this work aims to determine whether the common method of coarsening location data of privacy-conscious individuals is an effective approach if fine-grained location data has also been submitted by privacy-apathetic users. We propose a novel inference attack to refine the location of privacy-conscious individuals. Our experiments suggest that even with a dataset that is mostly populated with privacy-conscious users, our technique succeeds with high precision and recall.

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.

In this paper we examine the use of a novel social technology to support the provision of formal aged care services to clients who live in their own homes. Social technologies offer enormous potential for enhancing aged care, but research on their use in aged care has largely focused on institutional or informal care settings, rather than formal care in the home. Meanwhile, technologies for aging in place typically focus on monitoring and security, rather than psychosocial support. We conducted a field study in which aged care managers used a photo and message-sharing tool to communicate with clients living in their own homes. Our findings demonstrate that visual and social forms of communication are valuable for supporting psychosocial care-giving, but there are barriers to effectively adopting new communication tools in this setting. Time constraints inhibited care managers' use of the technology, which was also influenced by their efforts to carefully maintain boundaries between their personal and professional lives.

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.

Wireless sensor technologies have become popular in recent years as the cost of electronics decreases. In addition, various sensors were incorporated into a smartphone, which caused the integration of many applications into one device. Navigation is a typical application of a smartphone. A common assumption in navigation is that a person's position has to be known exactly so most papers have focused on the localization process itself rather than customizing it for a specific application. In this paper we will show that complex systems or algorithms are not necessary for the purpose of getting two parties to meet in indoor situations. A robust localization system was implemented using popular sensors in a smartphone and simple localization techniques. We show that this system can localize a person with room-level accuracy to help two people to meet each other in a building.

Modern sensor-equipped smartphones have attracted significant research interest in the pervasive community for recognizing and creating context-aware applications at a personal or community scale level. In this paper, we propose a proof of concept Do-Not-Disturb (DND) service that can a) determine a user's context relevant for DND service from the built-in smartphone sensors and b) correctly predict the DND status based on the given context such as being in a meeting, sleeping, or working at the office. In this preliminary study, we investigate whether sensor data can be clustered to represent user contexts. We use standard machine learning techniques to learn the relationship between a user's context and the corresponding DND status (available or unavailable). Given a user's current context, the DND service predicts a DND status and configures the mobile device accordingly. Our preliminary experiment demonstrates that the proposed system can achieve a prediction accuracy of up to 90% when trained with sufficient data.

Mobile smart phones capture a great amount of information about a user across a variety of different data domains. This information can be sensitive and allow for identifying a user profile, thus causing potential threats to a user's privacy. Our work shows that diagnostic information that is not considered sensitive, could be used to identify a user after just three consecutive days of monitoring. We have used the Device Analyzer dataset to determine what features of a mobile device are important in identifying a user.

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.

Older adults are normally characterized as consumers, rather than producers, of digital content. Current research concerning the design of technologies for older adults typically focuses on providing access to digital resources. Access is important, but is often insufficient, especially when establishing new social relationships. This paper investigates the nature and role of digital content that has been created by older adults, for the purpose of forging new relationships. We present a unique field study in which seven older adults (aged 71-92 years), who did not know each other, used a prototype iPad application (Enmesh) to create and share photographs and messages. The findings demonstrate that older adults, even those in the \'1c"oldest old\'1d" age group, embraced opportunities to express themselves creatively through digital content production. We show that self-expression and social engagement with peers can be realized when socio-technical systems are suitably designed to allow older adults to create and share their own digital content.

User privacy in location-based services (LBSs) has become an important research area. We introduce a new direction to protect user privacy that evaluates LBSs with crowdsourced data and computation and eliminates the role of a location-based service provider. We focus on the group nearest neighbor (GNN) query that allows a group to meet at their nearest point of interest such as a restaurant that minimizes the total or maximum distance of the group. We develop a crowdsource-based approach, called PrivateMeetUp, to evaluate GNN queries in a privacy preserving manner and implement a working prototype of PrivateMeetUp.

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.

Optimizing travel time and energy consumption without compromising safety to attain efficient road traffic is a key goal in transport telematics. Microscopic traffic simulations are important tools to study the impact of new algorithms on road traffic. The aim of these simulations is to achieve a high degree of realism through the use of microscopic car-following models, which characterize real-time interaction among individual vehicles. These models play a vital role in Advanced Vehicle Control and Safety Systems (AVCSS) such as collision warning, adaptive cruise control, or lane guidance and in modelling simulation of safety studies and capacity analysis in transportation science. Although a range of models have been proposed to model the longitudinal interaction between adjacent vehicles due to its importance, surprisingly few comparative evaluations of the models exist. In this paper, we first identify limitations of the prominent car-following models. We then propose a k-leader fuel-efficient car-following model and show that our model is effective in terms of safety, trip times, flow and fuel efficiency. We also highlight new research challenges and important directions for further research.

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.

Traffic-monitoring systems (TMSs) are vital for safety and traffic optimization. However, these systems may compromise the privacy of drivers once they track the position of each driver with a high degree of temporal precision. In this paper, we argue that aggregated data can protect location privacy while providing accurate information for traffic monitoring. We identify a range of aggregate query types. Our proposedprivacy-aware monitoring system (PAMS)works as an aggregate query processor that protects the location privacy of drivers as it anonymizes the IDs of cars. Our experiments show that PAMS answers queries with high accuracy and efficiency.

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.

In this demonstration we show how RFID technology can be used for sensing spatial information in indoor environments. In particular, we demonstrate how this sensed information can be used for navigation and interaction within an environment.