Best-Compromise In-Route Nearest Neighbor Queries

Humans are animals of habit, e.g., people follow typical and/or familiar paths in their daily routines. With that in mind we investigate the problem where a user, traveling on his/her preferred path, needs to visit one of many available points-of-interest while (1) minimizing his/her total travel distance and also (2) minimizing the detour distance incurred to reach the chosen point-of-interest. We call this new problem the "Best-Compromise In-Route Nearest Neighbor" query in order to emphasize that a route cannot typically optimize both criteria at the same time, but rather find a compromise between them. In fact, the competing nature of these two criteria resembles the notion of skyline queries. In that context, we propose a solution based on using suitable upper-bounds to both cost criteria to prune uninteresting paths. It returns all linearly non-dominated paths that are optimal under any given linear combination of the two competing criteria. Our experiments using real data sets of different sizes show that our proposal can be orders of magnitude faster than a straightforward alternative.