Thursday, July 9, 2020

Semantically Diverse Path Search

The Best Paper Award Runner-Up at IEEE MDM 2020 were awarded to the authors of "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.

The nice presentation was given by Xu Teng, Iowa State University, at the IEEE MDM 2020.

X. Teng, G. Trajcevski, J.-S. Kim, and A. Züfle, “Semantically Diverse Path Search,” In Proceedings of IEEE International Conference on Mobile Data Management (MDM 2020), July 2020, pp. 69-78