移动对象轨迹的新型签名索引方案

### 移动对象轨迹的新型签名索引方案 #### 1. 过去移动对象的轨迹索引方案 要回答带有过去时间的基于轨迹的查询，需要高效搜索那些不再在道路网络上移动的过去移动对象的轨迹。移动对象的轨迹可分为两组：一组常用于基于当前对象轨迹回答查询（COTSS），另一组用于基于过去对象轨迹回答查询（POTSS）。 当 COTSS 中的当前移动对象轨迹由于对象移动完成而不再改变时，该对象轨迹应从 COTSS 移动到 POTSS。COTSS 的签名和位置信息区域驻留在主内存中以便快速检索，而 POTSS 的所有三个区域都保存在二级存储中。 将当前对象轨迹从 COTSS 移动到 POTSS 时，需考虑三个要求： - 高效检索过去对象的轨迹。 - 访问少量分区以回答基于轨迹的查询。 - 构建高效的基于时间的索引结构。 为满足第一个要求，在 POTSS 中使用位切片方法构建基于签名的索引方案，而不是在 COTSS 中使用位串方法。在位切片方法中，为原始签名串中的每个位位置创建一个固定长度的签名切片。当查询轨迹中的段数为 m，分配给一个段的位数为 k 时，位切片方法回答查询所需的页面 I/O 访问次数小于 k*m。因此，当查询轨迹中的段数较小时，由于查询所需的签名切片数量较少，索引方案所需的页面 I/O 访问次数也较少。 为满足第二个要求，维护 POTSS 中的所有分区，使其满足条件：如果 start_time(partition i) < start_time(partition i + 1)，则 end_time(partition i) ≤ end_time(partition i + 1)。若不满足此条件，查询处理可能效率低下。为防止这种情况，若分区 i 的所有轨迹不再改变，而分区 i - 1 的轨迹仍在改变，则交换分区 i - 1 中正在改变的轨迹与分区 i 中结束时间最小的轨迹，然后将分区 i - 1 从 COTSS 移动到 POTSS。 为满足最后一个要求，使用分区的结束时间作为键构建 B + -树，以便快速访问 POTSS 中的分区。时间基 B + -树结构的叶节点记录 Rec 为 <p_start_time, p_end_time, Pid, PLoc>，其中 p_start_time 和 p_end_time 分别表示 POTSS 中一个分区的所有轨迹的最小开始时间和最大结束时间，Pid 和 PLoc 分别表示其分区 ID 和位置。当发出查询以查找时间窗口 [t1, t2] 内的对象轨迹时，首先使用 t1 搜索时间基 B + -树以获取起始叶节点，然后获取满足条件 p_end_time ≥ t1 AND p_start_time ≤ t2 的记录。 #### 2. 移动对象轨迹的插入算法 移动对象轨迹的插入算法可分为初始轨迹插入算法和轨迹段插入算法。 初始轨迹插入时，找到分区表中的最后一个分区，并在最后一个分区中获取一个可用条目（NE）。初始轨迹插入根据有无预期未来轨迹分为两种情况，详细算法因篇幅省略。 对于移动对象轨迹的段插入，使用移动对象的开始时间（ST）从分区表中找到存储其轨迹的分区，并获取分区中存储轨迹信息的条目。以下是段插入算法（InsertSeg）： ```plaintext Algorithm InsertSeg(MOid, TrajSeg, ST) /* TraSeg contains a segment for the trajectory of a moving object Moid, to be stored with an object trajectory’s start time, ST*/ 1. Generate a signature SigTS from TrajSeg 2. Locate a partition P covering ST in partition table 3. Locate an entry E covering ST for the moving object with MOid and get its location, Loc, in the trajectory information area 4. Obtain #actual_seg, #future_seg, and #mismatch of the trajec- tory info entry E (i.e., TE) for the MOid in P 5. if(#future_seg = 0) { // no expected trajectory 6. Insert TrajSeg into(#actual_seg+1)th trajectory segment of TE 7. Store SigTS into the entry E of the signature info area in P} 8. else { // expected trajectory exists 9. seg_pos = find_seg(TrajSeg,Loc) 10. #actual_seg++, #future_seg = #future_seg – seg_pos 11. case(seg_pos = 0) { // find no segment 12. Insert TrajSeg into segment of TE and relocate the future traj segments backward 13. Store SigTS into entry E of signature info area in P } 14. case(seg_pos = 1) //find the first segment 15. Insert TrajSeg into (#actual_seg)-th trajectory segment of TE for exchanging the old segment 16. case(seg_pos > 1) {//find the (seg_pos)-th segment 17. #mismatch = #mismatch + seg_pos – 1 18. Insert TrajSeg into (#actual_seg)-th ```