Effective indexing for approximate constrained shortest path queries on large road networks

• المؤلفون الرئيسيون: Wang, Sibo, Xiao, Xiaokui, Yang, Yin, Lin, Wenqing
• مؤلفون آخرون: School of Computer Science and Engineering
• التنسيق: Conference or Workshop Item
• اللغة: English
• منشور في: 2017
• الموضوعات: Constrained shortest path; Large road networks
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/81353; http://hdl.handle.net/10220/43454
• المؤسسة: Nanyang Technological University

In a constrained shortest path (CSP) query, each edge in the road network is associated with both a length and a cost. Given an origin s, a destination t, and a cost constraint θ, the goal is to find the shortest path from s to t whose total cost does not exceed θ. Because exact CSP is NP-hard, prev...