Route Search over Probabilistic Geospatial Data

In a

route search

over geospatial data, a user provides terms for specifying types of geographical entities that she wishes to visit. The goal is to find a route that

(1)

starts at a given location,

(2)

ends at a given location, and

(3)

travels via geospatial entities that are relevant to the provided search terms. Earlier work studied the problem of finding a route that is

effective

in the sense that its length does not exceed a given limit, the relevancy of the objects is as high as possible, and the route visits a single object from each specified type. This paper investigates route search over

probabilistic geospatial data

. It is shown that the notion of an effective route requires a new definition and, specifically, two alternative semantics are proposed. Computing an effective route is more complicated, compared to the non-probabilistic case, and hence necessitates new algorithms. Heuristic methods for computing an effective route, under either one of the two semantics, are developed. (Note that the problem is NP-hard.) These methods are compared analytically and experimentally. In particular, experiments on both synthetic and real-world data illustrate the efficiency and effectiveness of these methods in computing a route under the two semantics.