Representative Routes Discovery From Massive Trajectories

本文研究了如何在大规模轨迹数据中找到𝑘最具代表性的路线，这是一个有利于各种现实世界应用的基本操作，如交通监控和公共交通规划。操作员是时间敏感的，因为它必须能够适应交通条件变化的结果。首先证明了该问题的np -困难性，然后提出了一系列响应时间短的有效近似解。首先建立一个查找表，用于存储给定路网中每条边所覆盖的轨迹;我们不是对所有可能的路径执行深度优先搜索，而是通过开发一个最大权重算法来找到一个1/𝜂的近似解决方案。由于同一路径上的每条边都可能靠近多条轨迹，进一步提出了一种覆盖优先算法来定位解决路径集中覆盖增益最大的边。通过观察在现实世界中，每条边只连接到道路网络中的少数其他边，我们开发了一种连接优先算法，通过贪婪地选择具有最大边际收益的边为𝑘代表路线找到连续的边。最后，在两个真实数据集上进行了全面的实验，验证了所提算法的有效性和效率，并证明了所提算法在交通监控任务中的有用性和快速响应时间。

 

 4 REPRESENTATIVE ROUTE DISCOVERY

理想情况下，𝑘最具代表性的路线可以通过深度优先的方式枚举给定预算限制的所有可能路线来找到。然而，获得这种最优解的计算量很大。因此，在本节中，我们提出三种高效的算法来发现高质量的近似解。 

4.1 Maximum-weight Algorithm

我们引入一种最大权算法来近似最优解，并利用动态规划在满足预算约束的边图中寻找𝑘最大权路径。 

阅读者总结：文中提出的问题很具有代表性，并且证明这是一种NP问题，采用近似算法。