• a novel segmentation-based approach to estimate intention of a mobile agent. • an efficient implementation of a new segmentation-based algorithm for continues or realtime intention recognition. • evaluation of the latency, stability, and accuracy of the proposed algorithm compared to other state-of-the-art online intention algorithms. This paper proposes and evaluates an efficient online algorithm for recognizing the movement intentions of mobile agents. As an agent reveals new movements, our algorithm continuously ranks various possible intentions, such as reaching a specific destination or avoiding a particular area, using a novel approach to semantic trajectory segmentation. We empirically validate the performance of our algorithm against state-of-the-art alternatives in the path planning using simulated movement data. The results show that our approach improves reliability and accuracy in identifying true intention in scenarios with an increased number of candidate destinations, or when a mobile agent takes less planned and predictable routes.

The advancement of indoor location-aware technologies enables a wide range of location based services in indoor spaces. In this paper, we formulate a novel Indoor Facility Location Selection (IFLS) query that finds the optimal location for placing a new facility (e.g., a coffee station) in an indoor venue (e.g., a university building) such that the maximum distance of all clients (e.g., staffs/students) to their nearest facility is minimized. To the best of our knowledge we are the first to address this problem in an indoor setting. We first adapt the state-of-the-art solution in road networks for indoor settings, which exposes the limitations of existing approaches to solve our problem in an indoor space. Therefore, we propose an efficient approach which prunes the search space in terms of the number of clients considered, and the total number of facilities retrieved from the database, thus reducing the total number of indoor distance calculations required. The key idea of our approach is to use a single pass on a state-of-the-art index for an indoor space, and reuse the nearest neighbor computation of clients to prune irrelevant facilities and clients. We evaluate the performance of both approaches on four indoor datasets. Our approach achieves a speedup from 2.84× to 71.29× for synthetic data and 97.74× for real data over the baseline.

Safety on the roads has become a major concern in recent days. Travellers prefer to avoid road inconveniences that may occur from crime incidents, street harassment, protests or riots during unrest in a country. To facilitate safe travel, we introduce a novel query for road networks called the$k$safest nearby neighbor (SNN) query. Given a query location$v_{l}$, a distance constraint$d_{c}$and a point of interest$p_{i}$, we define the safest path from$v_{l}$to$p_{i}$as the path with the highestpath safety scoreamong all the paths from$v_{l}$to$p_{i}$with length less than$d_{c}$. The path safety score is computed considering the road safety of each road segment on the path. Given a query location$v_{l}$, a distance constraint$d_{c}$and a set of POIs$P$, a$k$SNN query returns$k$POIs with the$k$highest path safety scores in$P$along with their respective safest paths from the query location. We develop two novel indexing structures called$Ct$-tree and a safety score based Voronoi diagram (SNVD). We propose two efficient query processing algorithms each exploiting one of the proposed indexes to effectively refine the search space using the properties of the index. Our extensive experimental study on real datasets demonstrates that our solution is on average an order of magnitude faster than the baseline.

Ensuring travelers’ safety on roads has become a research challenge in recent years. We introduce a novel safe route planning problem and develop an efficient solution to ensure travelers’ safety on roads. Though few research attempts have been made in this regard, all of them assume that people share their sensitive travel experiences with a centralized entity for finding the safest routes, which is not ideal in practice for privacy reasons. Furthermore, existing works formulate safe route planning in ways that do not meet a traveler's need for safe travel on roads. Our approach finds the safest routes within a user-specified distance threshold based on the personalized travel experience of the knowledgeable crowd without involving any centralized computation. We develop a privacy-preserving model to quantify the travel experience of a user into personalized safety scores. Our algorithms, direct and iterative for finding the safest route further enhance user privacy by minimizing the exposure of personalized safety scores with others. Our safe route planner can find the safest routes for individuals and groups by considering both a fixed and a set of flexible destination locations. Extensive experiments using real datasets show that our approach finds the safest route in seconds. Compared to the direct algorithm, our iterative algorithm requires 43% less exposure of personalized safety scores.

In this COVID-19 pandemic era, students with Autism Spectrum Disorder (ASD) are struggling to adapt to classes in the online environment using Google Meet or Zoom. Failing to keep sustained attention in the class is a common problem for students with ASD. In face-to-face classes, teachers can track a student's behavior and activity to infer the student's attentiveness level and act accordingly. However, it becomes difficult for a teacher to monitor the attentiveness level of multiple students simultaneously on online platforms like Zoom. Detecting the attentiveness level of a student and notifying the teacher in an automated way can play a crucial role in improving the learning outcome. In this paper, we propose the first deep learning based attentiveness level prediction technique for students with ASD. Our model detects the behavior (e.g., unusual movement, gaze etc.) and activities from real-time videos and uses them as features to classify the attentiveness level as low, mid and high. Existing state-of-the-art techniques to detect the attentiveness level of typically developed students using gaze or facial expression cannot be trivially extended for students with ASD as they do not exhibit regular and consistent behavior. We collect video data belonging to different classes covering various types of activities over a long period, train our classifier, and run extensive experiments to validate the prediction performance. Our solution outperforms existing baselines by a large margin.

We introduce a novel safe route planning problem and develop an efficient solution to ensure the travelers' safety on roads. Though few research attempts have been made in this regard, all of them assume that people share their sensitive travel experiences with a centralized entity for finding the safest routes, which is not ideal in practice for privacy reasons. Furthermore, existing works formulate the safe route planning query in ways that do not meet a traveler's need for safe travel on roads. Our approach finds the safest routes within a user-specified distance threshold based on the personalized travel experience of the knowledgeable crowd without involving any centralized computation. We develop a privacy preserving model to quantify the travel experience of a user into personalized safety scores. Our algorithms for finding the safest route further enhance user privacy by minimizing the exposure of personalized safety scores with others. We implement a working prototype of our solution on the Android platform. Extensive experiments using real datasets show that our approach finds the safest route in seconds with 50% less exposure of personalized safety scores.

In this paper, we propose an iterative approach to estimate the frequent itemsets with high accuracy while satisfying the local differential privacy (LDP). The key component behind the improved accuracy of the estimated frequent itemsets by our approach is our novel two-level randomization technique for guaranteeing the LDP. Our randomization technique exploits the correlation of the presence of items in a user’s itemset, which has not been considered before. We present a mathematical proof that shows that our approach satisfies the LDP constraint. Extensive experiments are performed to validate the effectiveness and efficiency of our proposed algorithms using real datasets.

Given a set of obstacles in 2D or 3D space, a set of n candidate locations where facilities can be established, the Maximum Visibility Facility Selection (MVFS) query finds k out of the n locations, that yield the maximum visibility coverage of the data space. Though the MVFS problem has been extensively studied in visual sensor networks, computational geometry, and computer vision in the form of optimal camera placement problem, existing solutions are designed for discretized space and only work for MVFS instances having a few hundred facilities. In this paper, we revisit the MVFS problem to support new spatial database applications like "where to place security cameras to ensure better surveillance of a building complex?" or "where to place billboards in the city to maximize visibility from the surrounding space?". We introduce the concept of equivisibility triangulation to devise the first approach to accurately determine the visibility coverage of continuous data space from a subset of the facility locations, which avoids the limitations of discretizing the data space. Then, we propose an efficient graph-theoretic approach that exploits the idea of vertex separators for efficient exact in-memory solution of the MVFS problem. Finally, we propose the first external-memory based approximation algorithm (with a guaranteed approximation ratio of 1 - 1/e) that is scalable for a large number of obstacles and facility locations. We conduct extensive experimental study to show the effectiveness and efficiency of our proposed algorithms.

In this paper, we study continuous detour queries in the indoor space. A continuous detour query finds the nearest indoor detour object like an ATM or a printer for a moving user walking towards a target location in an indoor venue, where the detour distance for an indoor object is measured as the total indoor distance of the object from the user's current and target locations. The continuous detour query has been already studied for the outdoor space, but the solutions are not adaptable for the indoor space due to the unique characteristics of indoor venues. We develop the first solution for efficient processing of the continuous detour query in the indoor space. The novelty of our solution comes from the computation of safe zones for the indoor objects by exploiting the geometric properties of hyperbolas, additively weighted Voronoi diagram and indoor partitions. The safe zone represents an area such that the nearest detour object remains unchanged as long as the user is in this area. The key ideas behind the efficiency of our solution are reducing the number of re-evaluation of the detour queries for the location change of a moving user, pre-computing the safe zones, and indexing them using a grid structure. The experiments show that our solution can process continuous detour queries efficiently and reduces the communication overhead.

A user’s location is a sensitive data and can reveal private information about the user’s health, habit and preferences. Due to privacy concerns, people may hesitate to share their locations and prohibit the growth of location-based services and analysis. The problem of protecting location privacy has been extensively studied in the literature. Sharing location data in sequence enable adversaries to apply privacy attacks by exploiting spatio-temporal constraints in road networks. In this paper, we identify a novel privacy attack that existing solutions cannot overcome for not considering upcoming sensitive locations in advance. We develop a technique to precompute the warning zone, i.e. the refined area where the disclosure of a user’s actual location may enable adversaries to identify the user’s sensitive locations in the future. Warning zones also enable users to reduce the frequency of not sharing locations for privacy reasons, and thereby improve the accuracy and utility of shared locations while guaranteeing the required level of location privacy of a user. Experiments using real datasets show that our approach significantly outperforms the state-of-the-art technique in terms of privacy, data utility and computational overhead.

Recent improvement in genomic research is paving the way towards significant progress in diagnosis and treatment of diseases. A disease risk query returns the probability of a patient to develop a particular disease based on her genomic and clinical data. Despite various innovative prospects, frequent and ubiquitous usage of genomic data in medical tests and personalized medicine may cause various privacy threats like genetic discrimination, exposure of susceptibility to diseases, and revelation of genomic data of relatives. Another major concern is on ensuring the reliability of the genome data and the correctness of the computed disease risk, which is known as authentication. We develop a novel secret sharing approach to protect privacy of sensitive genomic and clinical data, disease markers, disease name, and the query answer while ensuring authenticated result of the disease risk query. Experiments with real datasets show that our approach for authenticated disease risk queries achieves a high level of privacy with reduced processing and storage overhead.

The evolution of ridesharing services has reduced the road traffic congestions in recent years. However, a major concern for ridesharing services is sharing rides with strangers. To address this issue, a few ridesharing approaches have considered social closeness of group members for identifying a ridesharing group. Again, users do not feel comfortable to disclose such personal data (e.g, friendship information) with an untrusted service provider for privacy reasons. We propose a novel way to form ridesharing groups that reveals user social data in community levels, and ensures that a group member shares at least k common communities with at least other m members in the ridesharing group, where k and m are personalized parameters of every group member. We formulate a Community aware Ridesharing Group (CaRG) query that satisfies the constraints of m and k, and returns a ridesharing group with the minimum cost in terms of the spatial proximity of riders from the driver. We show in experiments that our approach to process CaRG queries outperforms a baseline approach with a large margin.

Reducing the road traffic congestion has become an important challenge in recent years; the researchers have focused on identifying causes and remedies for the traffic congestion. However, the impact of the locations and activity time of points of interests (POIs) on the road traffic has not yet been explored. Moreover, in developing countries, POIs are not established in planned manner and cause the traffic congestion. In this paper, we analyze how POI locations and activities affect the road traffic. Specifically, we identify the congestion pattern caused by POI activities in the field study and develop a model to quantify the spatio-temporal impact of POI activities on the traffic congestion. Moreover, we develop a model to predict the impact of POI activities on the road traffic congestion using fuzzy regressions for different POI categories. We perform a set of case studies and experiments to show the effectiveness of our models using real datasets of POI activities and road traffic.

In this paper, we introduce the concept of "dynamic groups" for Group Trip Planning (GTP) queries and propose a novel query type Dynamic Group Trip Planning (DGTP) queries. The traditional GTP query assumes that the group members remain static or fixed during the trip, whereas in the proposed DGTP queries, the group changes dynamically over the duration of a trip where members can leave or join the group at any point of interest (POI) such as a shopping center, a restaurant or a movie theater. The changes of members in a group can be either predetermined (i.e., group changes are known before the trip is planned) or in real-time (changes happen during the trip). In this paper, we provide efficient solutions for processing DGTP queries in the Euclidean space. A comprehensive experimental study using real and synthetic datasets shows that our efficient approach can compute DGTP query solutions within few seconds and significantly outperforms a naive approach in terms of query processing time and I/O access.

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.

Sexual harassment of women in public places (e.g., foot-paths, buses, and shopping malls) of major cities in developing countries is a growing concern. These harassments can happen in various forms ranging from commenting, catcalling, and staring to touching and groping, to attacking and raping. Though, the most severe form of harassments such as attacking and raping get some attention from the society, NGOs and law-enforcement agencies, unfortunately, other forms of harassments that are more widespread in public places remain largely un-attended or ignored in our conservative society. However, these harassments are more common and can have various negative psychological impacts on women that include a persistent feeling of insecurity, loss of self-esteem, restricted participation in daily life activities in public places. In this paper, we propose a crowd-powered privacy-aware location based mobile application, SafeStreet, that empowers women in public places against sexual harassments. SafeStreet allows a women to privately capture and share her own experiences in the street. SafeStreet enables a women to find a safe path, i.e., the path to a destination that has less harassment hazard, at any point of time.

The recent advancement of GPS-enabled mobile technologies and the proliferation of map-based applications are attracting an increasing number of people to use location based services (LBSs). Processing a larger number of simultaneous queries efficiently have become an important research topic in recent years. In this paper, we focus on an important class of LBSs, shortest path queries (SP-queries) in road networks. Given a source and a destination in a road network, an SP-query returns the path from the source to the destination that minimizes the travel time. We particularly focus on batch processing of simultaneous SP-queries in road networks. Traditional systems that process one query at a time usually provide slow responses, causing the machine to flood with incoming queries. Existing fast solutions for SP-queries require expensive pre-processing steps and are incapable of adapting with the continuous change in traffic on the roads. We propose an efficient group based approach that provides an approximate solution with reduced cost and high accuracy. An important benefit of our approach is that it does not require expensive pre-processing. The key concept is to exploit the path-coherence property of road networks by grouping queries that share substantial common paths in their shortest paths and processing the group in a single pass. Our approach incurs an average relative error of 0.5% and is on average 6 times faster than the straightforward approach that evaluates each SP-query individually.

The proliferation of location-based social networks allows people to access location-based services as a group. We address Group Optimal Sequenced Route (GOSR) queries that enable a group to plan a trip with a minimum aggregate trip distance. The trip starts from the source locations of the group members, goes via a predefined sequence of different point of interests (POIs) such as a restaurant, shopping center and movie theater, and ends at the destination locations of the group members. The aggregate trip distance can be the total or the maximum trip distance of the group members. We introduce a novel approach to efficiently compute group optimal sequenced routes in road networks. We exploit elliptical properties to refine the POI search space and develop efficient algorithms for GOSR queries. Experiments show that our approach outperforms a naive approach significantly in terms of processing time and I/Os.

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.

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.

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.