Semantically Diverse Path Search

Location-Based Services are often used to find proximal Points of Interest PoI-e.g., nearby restaurants and museums, police stations, hospitals, etc.-in a plethora of applications. An important recently addressed variant of the problem not only considers the distance/proximity aspect, but also desires semantically diverse locations in the answer-set. 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, for as long as they are within an acceptable distance from a given (current) location. Towards that goal, in this work we propose a novel approach to efficiently retrieve a path that will maximize the semantic diversity of the visited PoIs that are within distance limits along a given road network. We introduce a novel indexing structure-the Diversity Aggregated R-Tree, based on which we devise efficient algorithms to generate the answer-set-i.e., the recommended locations among a set of given PoIs-relying on a greedy search strategy. Our experimental evaluations conducted on real datasets demonstrate the benefits of proposed methodology over the baseline alternative approaches.