In-Path Oracles for Road Networks
In-Path Oracles for Road Networks
复制标题
DOI：
10.3390/ijgi12070277
复制
发表时间：
2023-07
期刊：
影响因子：
--
通讯作者：
Debajyoti Ghosh;Jagan Sankaranarayanan;Kiran Khatter;H. Samet
中科院分区：
文献类型：
--
作者：
Debajyoti Ghosh;Jagan Sankaranarayanan;Kiran Khatter;H. Samet
许多空间应用程序受益于对看似简单的空间查询的快速回答：“兴趣点（POI）是否在源和目的地之间最短路径的路径中？”在这种情况下，路径内POI是指位于最短路径上的POI，或者可以在距离最短路径有限但很小的绕行范围内到达的POI。路径内查询的快速应答取决于能够在运行时确定而不必实际计算最短路径。因此，这需要一个预计算的解决方案。本文的主要贡献是开发了一个路径内oracle，该oracle基于对给定POI的哪些源和目的地对在路径内的预计算。对于具有n个节点和m个poi的给定路网，基于路网的良好分离对（WSP）分解的约简，设想了一个O（m×n）大小的oracle。此外，可以使用b树在数据库中索引oracle， b树可以以非常高的吞吐量回答查询。在真实路网POI数据集上的实验结果表明，与基线算法相比，该技术具有优越性。所提出的方法每秒可以回答约150万个路径内查询，而使用合适的基线方法每秒可以回答几百个查询。
Many spatial applications benefit from the fast answering to a seemingly simple spatial query: “Is a point of interest (POI) ‘in-path’ to the shortest path between a source and a destination?” In this context, an in-path POI is one that is either on the shortest path or can be reached within a bounded yet small detour from the shortest path. The fast answering of the in-path queries is contingent on being able to determine without having to actually compute the shortest paths during runtime. Thus, this requires a precomputation solution. The key contribution of the paper is the development of an in-path oracle that is based on precomputation of which pairs of sources and destinations are in-path with respect to the given POI. For a given road network with n nodes and m POIs, an O(m×n)-sized oracle is envisioned based on the reduction of the well-separated pairs (WSP) decomposition of the road network. Furthermore, an oracle can be indexed in a database using a B-tree that can answer queries at very high throughput. Experimental results on the real road network POI dataset illustrate the superiority of this technique compared to a baseline algorithm. The proposed approach can answer ≈ 1.5 million in-path queries per second compared to a few hundred per second using a suitable baseline approach.