Entanglement of Distance and Semantic Constraints for PoI (Sequence) Recommendation

One of the most popular applications of Location-Based Services (LBS) is to recommend proximal Points of Interest (PoI) – e.g., nearby restaurants and museums, police stations, hospitals, etc. A variant of the problem is to recommend a sequence of PoIs to visit – and an important recently addressed “twist” is to not only consider the preference of distance/proximity, but also ensure that the returned proximal objects satisfy certain semantic constraints. For instance, rather than picking several close-by attractions with similar features – e.g., restaurants with similar menus; museums with similar art exhibitions – a tourist may be more interested in a result set that could potentially provide more diverse types of experiences, as long as they are within an acceptable distance from a given location.

After a brief introduction/motivation, followed by formalization of the problem and overview of the related works, this talk will address a few variations of the problem of efficiently detecting routes that satisfy both distance-based and semantic-based constraints. In particular, we will consider in detail the following two categories: (1) topic modeling approach based on the Latent Dirichlet Allocation (LDA) – a generative statistical model, to effectively model and exploit a fine-grained notion of diversity, based on sets of keywords and/or reviews instead of a coarser user-given category. (2) jointly determining: (a) a sequence of PoIs that satisfies both traveling budget and the user-desired semantic diversity; (b) recommend the best origin (e.g., hotel) for a given user. For each category, we will explain the peculiarities of the problem and formalize the novel query-types; followed by the corresponding indexing structures that were introduced to speedup the query processing, along with the algorithms relying on those structures. As the problems turn out to be NP-hard, the algorithmic solutions are essentially heuristics – and we will present the extensive experimental results (with a note that both the source code as well as (importantly) the real-life datasets are publicly available). The final part of the talk will outline challenges and opportunities in the context of PoI recommendations, and discuss broadening the scope beyond traditional semantic trajectories.

This is a joint work with Xu Teng (ESRI) and Andreas Zufle (Emory Univ.)