论文阅读 - Finding Time Period-Based Most Frequent Path in Big Trajectory Data

Finding Time Period-Based Most Frequent Path in Big Trajectory Data. SIGMOD 2013

本文定义了一个基于时间段的最频繁路径查询，即：

用户给定一个时间段，起点和终点，返回一个最热门的路线$(TPMFP)$

# 本文主要工作：

1、热门度定义

2、高效搜索$(TPMFP)$

# 热门度定义

如何很好的对热门度进行量化呢？

1、首先简单的统计每条路段上通过的轨迹（轨迹经过终点）数目不能很好地反映一条路线的热门度 原因：考虑图 1，从$v_1～v_{12}$ 的最热门路线，只单纯考虑从起点到终点经过的轨迹数目，那么$v_1-v_2-v_{12}$ 为最热门路线，但是对于$v_2～v_{12}$ 来说，最热门路线应当为v_2-v_3-v_

2、 其他的一些方法通过对节点或者边赋予一个权重，通过聚合函数（相加 / 累积）求得边的频繁度，但是这种方法仍然存在一定的问题，如果是将不同边上的权重进行相加，那么最热门路径会更偏向于路段数更多的路线，对于先前 11 年的论文（利用转移概率的方法找到最热门的路径）会更倾向于路段数更少的路线。

因此为了定义一个更合理的热门度，本文定义的热门路线需满足三个条件

• 后缀优先：任何最热门路径的后缀仍然是最热门路径

• 长度敏感：长度不敏感，$MFP$ 不偏向于更短或者更长的路径

• 没有瓶颈：不包含任何不频繁的边

# 高效搜索 TPMFP

同时由于历史轨迹数据非常庞大，并且本文是用户指定时间段，因为不可能将所有时间段的 TPMFP 结果都计算保存起来，所以在线计算的开销是不可避免的，为了使得 TPMFP 的查询更加高效，本文设计了特殊的索引结构（减少了从磁盘中获取的轨迹数量）。

本文的基本想法是通过序列值代替之前的标量值来去表示一条路线。首先给的终点和时间段，首先构造了一个带权重的路网子图$(footmark)$，在$footmark$ 中，每条边的权重被定义为经过这条边的轨迹（轨迹经过终点呢）数目。

$TPMFP$ 算法总流程：

为了构造$footmark$ 图，首先需要将每条轨迹从磁盘中读出，之后判断其是否能形成$footmark$ 图，这样时间复杂度就为$O(|\widetilde Υ| \times l)$，即$footmark$ 的个数乘上$footmarks$ 的平均长度。

为了减少$I/O$ 磁盘消耗，本文设计了$FMI$ 高效的过滤掉了那些不包含$footmarks$ 的轨迹（用索引进行查询优化），进一步的通过获取支配轨迹来减少随机页的访问。

对于 FMI，首先针对$footmarks$ 图上的每一个节点$v_i$ 构造了一棵 B + 树，B + 树的每一个叶子结点的格式为$<tid, t_a>$，$tid$ 代表轨迹的$id$，$t_a$ 代表轨迹到达$v_i$ 的时间。通过构建$FMI$，可将搜索$(v_d, T)$ 的时间缩短至$O(log(|Υ_{v_d}|+|Υ_({v_d,_T})|))$。这时算法瓶颈就出现在将轨迹从磁盘中读出的时间开销（代码中的第四行），会导致$|Υ_({v_d,_T})|$ 的页面访问，为了进一步去除这种随机读写，开发了$CFMI$ 的索引结构，这里首先定义了支配轨迹的概念，即轨迹集合中没有任何轨迹能够包含该轨迹（除该轨迹本身），考虑到支配轨迹包含了其余的轨迹，那么只需要记录支配轨迹，并记录下被支配轨迹在支配轨迹的起始位置，这样就不用再去访问其他轨迹了。

这里使用支配轨迹主要有两个原因，第一个原因是支配轨迹的数量远远小于所有的轨迹数量，如果我们能够只去访问支配轨迹就能有效的减少页面随机访问的次数；第二，本文设定的时间段 T，一般远大于轨迹从起点到终点的时间，这意味着大多数轨迹的开始时间都在时间段$T$ 内（这段话不是很懂）。$CFMI$ 改进了在 FMI 中的索引结构，B + 树中叶子结点的关键字格式变为$<tid,t_s,t_a,did,sloc>$，分别代表轨迹$id$，轨迹开始时间，轨迹到终点的时间，支配该轨迹的轨迹$id$ 和在被支配轨迹$id$ 中的位置。

最后，由于$footmarks$ 上路线序列非递减的特性，可使用$dp$ 快速找到$TPMFP$。在线规划部分使用类似$bell-fold$ 的方法找到$TPMFP$。

可以借鉴的地方：

可以借鉴其设计$CFMI$ 索引结构获取轨迹数据来减少磁盘$I/O$ 开销的问题

疑问：

这里热门路线定义为什么是非单调递减？任何最热门路径的后缀仍然是最热门路径？