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.

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.

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.

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.

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.

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