Interactive route search in the presence of order constraints

Y Kanza, R Levin, E Safra, Y Sagiv - Proceedings of the VLDB …, 2010 - dl.acm.org
Y Kanza, R Levin, E Safra, Y Sagiv
Proceedings of the VLDB Endowment, 2010dl.acm.org
A route search is an enhancement of an ordinary geographic search. Instead of merely
returning a set of entities, the result is a route that goes via entities that are relevant to the
search. The input to the problem consists of several search queries, and each query defines
a type of geographical entities. When visited, some of the entities succeed in satisfying the
user while others fail to do so; however, only the probability of success is known prior to
arrival. The main task is to find a route that visits at least one satisfying entity of each type. In …
A route search is an enhancement of an ordinary geographic search. Instead of merely returning a set of entities, the result is a route that goes via entities that are relevant to the search. The input to the problem consists of several search queries, and each query defines a type of geographical entities. When visited, some of the entities succeed in satisfying the user while others fail to do so; however, only the probability of success is known prior to arrival. The main task is to find a route that visits at least one satisfying entity of each type. In an interactive search, the route is computed in steps. In each step, only the next entity of the route is given to the user, and after visiting that entity, the user provides a feedback specifying whether the entity satisfies her.
This paper investigates interactive route search in the presence of order constraints that specify that some types of entities should be visited before others. We present heuristic algorithms for interactive route search for two cases, depending on whether the constraints define a complete order or a partial one. The main challenge is to utilize the feedback in order to compute a route that is shorter and has a higher degree of success, compared to routes that are computed non-interactively. We also discuss how to compare the results of the algorithms and introduce suitable measures for doing so. Experiments on real-world data illustrate the efficiency and effectiveness of our algorithms.
ACM Digital Library
以上显示的是最相近的搜索结果。 查看全部搜索结果