Home // GEOProcessing 2012, The Fourth International Conference on Advanced Geographic Information Systems, Applications, and Services // View article

O*-W: An Efficient O* algorithm to Process Optimal Sequence Traversal Query in a Complete Directed Graph

Authors:
Qifeng Lu
Kathleen Hancock

Keywords: Bivariate Best First Search, Heuristic, OSTQ, O*, O*-SCDMST, O*-W

Abstract:
Optimal Sequence Traversal Query (OSTQ) is a graph based query that retrieves a minimum cost path that starts from a predefined vertex, traverses a set of given vertices, and ends at a predefined vertex. One of its applications is trip planning in the GeoProcessing domain in transportation. With sound theoretical support for optimally efficient, optimal, and greedy solutions, best first search in the artificial intelligence domain is effective to process such trip planning queries. O* is an existing bivariate best first search framework and its special case O*-SCDMST was proposed recently to retrieve optimal solutions for such a query. In this paper, we propose O*-W, a novel O* algorithm that uses a globally admissible heuristic to obtain optimal solutions for such a query. The performance of O*-W and O*-SCDMST in a complete directed graph whose vertices only contain the origin, the destination, and the vertices of interest, and is studied through a set of experiments, and the result demonstrates that when the number of vertices of interest is up to 15, on average, O*-W reduces computation time by more than one order of magnitude when compared to O*-SCDMST. More importantly, on average and in worst cases, O*-W increasingly outperforms O*-SCDMST when the number of points of interest increases.

Pages: 204 to 208

Copyright: Copyright (c) IARIA, 2012

Publication date: January 30, 2012

Published in: conference

ISSN: 2308-393X

ISBN: 978-1-61208-178-6

Location: Valencia, Spain

Dates: from January 30, 2012 to February 4, 2012