## On k-skip shortest paths

Given two vertices s, t in a graph, let P be the shortest path (SP) from s to t, and P* a subset of the vertices in P. P* is a k-skip shortest path from s to t, if it includes at least a vertex out of every k consecutive vertices in P. In general, P* succinctly describes P by sampling the vertices in P with a rate of at least 1/k. This makes P* a natural substitute in scenarios where reporting every single vertex of P is unnecessary or even undesired. This paper studies k-skip SP computation in the context of spatial network databases (SNDB). Our technique has two properties crucial for real-time query processing in SNDB. First, our solution is able to answer k-skip queries significantly faster than finding the original SPs in their entirety. Second, the previous objective is achieved with a structure that occupies less space than storing the underlying road network. The proposed algorithms are the outcome of a careful theoretical analysis that reveals valuable insight into the characteristics of the k-skip SP problem. Their efficiency has been confirmed by extensive experiments with real data. © 2011 ACM.

### Duke Scholars

## Published In

## DOI

## ISSN

## Publication Date

## Start / End Page

### Citation

*Proceedings of the ACM SIGMOD International Conference on Management of Data*(pp. 421–432). https://doi.org/10.1145/1989323.1989368

*Proceedings of the ACM SIGMOD International Conference on Management of Data*, 421–32, 2011. https://doi.org/10.1145/1989323.1989368.

*Proceedings of the ACM SIGMOD International Conference on Management of Data*, 2011, pp. 421–32.

*Scopus*, doi:10.1145/1989323.1989368.