Privacy-Protected Route-Based Spatial-Textual Location Search in Road Networks

Hongwei Liu, Yongjiao Sun, Gang Wu, Guoren Wang

Abstract

Modern location-based services (LBS) frequently require users to disclose specific textual preferences to find relevant points of interest (POIs) along a travel route. This disclosure poses significant privacy risks, allowing service providers to construct detailed user profiles. This paper introduces the Privacy-Protected Route-Based Spatial-Textual Location (PPRSTL) query, which utilizes a two-phase filter-and-refinement mechanism. By delegating spatial filtering to the server and textual matching to the client, the system ensures privacy while maintaining high search efficiency. Experimental results on real-world and synthetic road networks demonstrate that the proposed Selected Expansion Search (SES) algorithm outperforms basic methods by up to 100% in terms of CPU time.

Introduction

Most existing location-based services focus on Point Nearest Neighbor (PNN) queries, which identify objects closest to a user's current GPS coordinates. However, for travelers on a road trip, the priority is finding POIs near their intended route rather than their current position. This is known as a Path Nearest Neighbor (PNN) query.

Existing PNN research often suffers from two major limitations: a lack of textual context and significant privacy risks. Standard queries might return a spatially close result that is irrelevant to the user's specific needs (e.g., a burger joint when the user wants sushi). Furthermore, to receive relevant recommendations, users typically must send their specific keywords to a server, enabling providers to build invasive profiles of user habits.

Figure 1: Example of a route-based spatial-textual query in a road network, where objects have both spatial locations and textual attributes.

Methodology: The PPRSTL Framework

The authors propose a two-phase search mechanism following a filter-and-refinement paradigm to address these challenges. This approach splits the workload between the server and the client to protect user privacy.

Filter Phase (Server-Side)

The server performs a spatial expansion from the query route to identify a set of candidate locations. Crucially, the server remains unaware of the user's specific keywords. It identifies locations that are spatially "close enough" to the route based on a calculated spatial-textual upper bound.

Refinement Phase (Client-Side)

The server transmits this candidate set to the user's device. The client-side application then performs the final matching against the user's private keywords to identify the optimal result. This "set-based" access ensures that the server cannot pinpoint the user's exact preference from the broader candidate list.

Search Algorithms

To optimize the server-side filtering, the authors developed two algorithms:

  1. Basic Expansion Search (BES): Expands the search from the two endpoints of the route.
  2. Selected Expansion Search (SES): An advanced version that selects multiple "expansion centers" along the route. By intelligently picking these centers, SES "hugs" the route more tightly, significantly reducing the search space and the number of irrelevant locations processed.
Figure 5: The Selected Expansion Search (SES) strategy utilizing multiple expansion centers along a route to create a tighter search area.

Experimental Evaluation

The researchers evaluated their algorithms using the Beijing Road Network (BRN), featuring 28,342 vertices, and a Synthetic Road Network (SRN) for scalability testing.

Key findings include:

  • Efficiency: The SES algorithm consistently outperformed BES, reducing CPU time by 80% to 100% in most scenarios.
  • Scalability: SES demonstrated superior performance as route lengths increased, proving its suitability for long-distance travel compared to the rapidly growing processing time of BES.
  • Robustness: The system remained effective across various importance settings (λ), balancing detour distance and keyword matching accuracy without compromising pruning efficiency.

Conclusion and Future Work

The PPRSTL query provides a robust solution for privacy-preserving, route-based searches. While highly effective, the authors identify several areas for future improvement, including the integration of semantic keyword matching (e.g., recognizing that a "diner" is similar to a "restaurant") and the incorporation of real-time traffic data to replace static road distances. Additionally, future research may explore methods to obfuscate the route itself from the server to provide a more comprehensive privacy shield.

Summary updated

Abstract

Location search and recommendation have received significant attention in recent years. To protect the users' privacy, we propose and study a novel privacy-protected route-based spatial-textual location (PPRSTL) query in road networks. Given a set of locations O with the textual description, a query route q with a set of query keywords to describe user's preference, the PPRSTL query finds the location with the highest spatial-textual similarity to the query route q. We believe that such type of query is very useful in many mobile applications such as location recommendation and discovery, and location-based services in general. The problem is challenging due to three reasons: (1) how to model the spatial and textual similarity practically; (2) how to constrain the search space in a comparatively small range in the spatial and textual domains, and; (3) how to protect the users' privacy when returning the query results. To overcome these challenges, we define a boolean spatial-textual measure to evaluate the similarity in the spatial and textual domains, and a two-phase search mechanism to protect users' privacy. We develop two expansion search algorithms that follow the filter-and-refinement paradigm, to compute the queries efficiently. Two pairs of upper and lower bounds are defined to prune the search space effectively. In addition, we adopt an expansion center selection method to further enhance the query efficiency. Finally, we conduct extensive experiments on real and synthetic spatial data sets to verify the performance of the developed algorithms.
BibTeX
@article{liu2019privacy,
  author = {Hongwei Liu and Yongjiao Sun and Gang Wu and Guoren Wang},
  title = {{Privacy-Protected Route-Based Spatial-Textual Location Search in Road Networks}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2903898},
}
Figure