用于点云近似查询的高效路径预言器

《ACM Transactions on Database Systems》：Efficient Path Oracles for Proximity Queries on Point Clouds

点云技术相较于三角网（TIN）在邻近查询中更具优势，现有在途最短路径算法和oracles效率低下，且无法直接支持点云环境。本研究提出两种高效点云最短路径oracles，分别处理POI间及任意点与POI的查询，并完成四项适应性改进，使oracles构建时间、存储大小和邻近查询效率较现有最佳方法提升12至42,000倍。

　　

摘要

计算机图形技术的普及推动了点云技术的发展，点云在邻近查询方面相比三角不规则网络（TIN）具有明显优势。目前所有针对TIN的即时最短路径查询算法和预言器都效率较低，且没有算法能够直接在点云上回答最短路径查询。因此，我们提出了两种高效的点云最短路径预言器：一种用于查询一对兴趣点（POI）之间的最短路径，另一种用于查询任意点与兴趣点之间的最短路径。我们还对这些预言器进行了四种改进，以适应查询任意点与兴趣点之间的路径（或在未提供兴趣点时查询任意点之间的路径）。此外，我们还基于这些预言器设计了两种高效的邻近查询算法。我们的两种预言器及其邻近查询算法在预言器构建时间、预言器大小和邻近查询时间方面，均比现有的最佳改进型预言器性能提升了12至42,000倍。