Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation
Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation
复制标题
DOI：
10.1109/69.687976
复制
发表时间：
1998-05
期刊：
影响因子：
--
通讯作者：
N. Jing;Yun-Wu Huang;Elke A. Rundensteiner
中科院分区：
文献类型：
--
作者：
N. Jing;Yun-Wu Huang;Elke A. Rundensteiner
有效的路径计算对于智能交通系统（ITS）和网络路由等应用至关重要。在ITS导航系统中，许多路径请求可以在小的时间窗口内通过相同的、通常是巨大的交通网络提交。While路径预计算（路径视图）将提供有效的路径查询响应，但它提出了必须解决的三个问题：1）预先计算的路径超过了大型网络的当前计算机主存储器容量; 2）基于磁盘的解决方案效率太低，无法满足这些目标应用的严格要求;以及3）路径视图对于大型图的更新变得太昂贵（导致过时的查询结果）。我们提出了一个分层编码路径视图（HEPV）模型，解决所有这三个问题。通过分层编码部分路径，HEPV减少了视图编码时间，更新时间和存储要求超出以前已知的路径预计算技术，同时显着减少路径检索时间。我们证明了在HEPV检索的路径是最优的。我们提出了完整的解决方案的所有阶段的HEPV方法，包括图分区，层次结构生成，路径视图编码和更新，路径检索。在本文中，我们还提出了一个深入的实验评估HEPV的基础上合成和真实的GIS网络。我们的研究结果证实，HEPV提供的替代路径查找方法的性能和空间效率方面的优势。
Efficient path computation is essential for applications such as intelligent transportation systems (ITS) and network routing. In ITS navigation systems, many path requests can be submitted over the same, typically huge, transportation network within a small time window. While path precomputation (path view) would provide an efficient path query response, it raises three problems which must be addressed: 1) precomputed paths exceed the current computer main memory capacity for large networks; 2) disk-based solutions are too inefficient to meet the stringent requirements of these target applications; and 3) path views become too costly to update for large graphs (resulting in out-of-date query results). We propose a hierarchical encoded path view (HEPV) model that addresses all three problems. By hierarchically encoding partial paths, HEPV reduces the view encoding time, updating time and storage requirements beyond previously known path precomputation techniques, while significantly minimizing path retrieval time. We prove that paths retrieved over HEPV are optimal. We present complete solutions for all phases of the HEPV approach, including graph partitioning, hierarchy generation, path view encoding and updating, and path retrieval. In this paper, we also present an in-depth experimental evaluation of HEPV based on both synthetic and real GIS networks. Our results confirm that HEPV offers advantages over alternative path finding approaches in terms of performance and space efficiency.