Semantically diverse and spatially constrained queries

One of the most popular applications of Location-Based Services (LBS) is to recommend proximal Points of Interest (PoIs) – e.g., nearby restaurants and museums, police stations, hospitals, etc. – or a sequence of PoIs to visit. An important variant of the problem that is recently addressed not only considers the preference of distance/proximity, but also desires 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. In my PhD dissertation, a topic modeling approach based on the Latent Dirichlet Allocation (LDA) was introduced 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. More importantly, for efficiency purpose, we devised two novel indexing structures – Diversity Map and Diversity Aggregated R-tree, which in turn enabled us to develop efficient algorithms to generate the answer-set for two novel categories of queries. While both queries focus on determining the recommended locations among a set of PoIs that maximizes the semantic diversity within distance limits along a given road network, they each tackle a different variant. The first type of query is kDRQ, which finds k such PoIs with respect to a given user’s location. The second query kDPQ generates a path to be used to visit a sequence of k such locations (i.e., with max diversity), starting at the user’s current location, and its extended variant k
T
DPQ allows user to specify not only starting location but also destination. Moreover, we tackled another query PaDOC of jointly generating a path that: (1) can be traversed within a user-specified budget (e.g., limit on distance); (2) starts at one of the user-specified origin locations (e.g., a hotel); and (3) contains PoIs from a user-specified list of PoI categories. Based on a novel indexing structure k-Closest Category Matrix, we proposed two efficient algorithms for approximate PaDOC query processing based on both conservative and progressive distance estimations.