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.
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:
- Basic Expansion Search (BES): Expands the search from the two endpoints of the route.
- 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.
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