B1-ABSTRACT.tex

%\vspace{-2.5cm}
\chapter*{\zihao{2}\heiti{摘~~~~要}}
%\vspace{-1cm}
近年来，随着智能手机等移动定位设备的大量使用，人们在生产生活中获得了飞速增长的轨迹大数据。该类大数据包含了车、人、动物甚至商品的移动行为。由于数据采集来源广、数据量大、数据增长快等原因，轨迹大数据往往以分布式形式存储。海量的轨迹数据不仅刻画了移动对象个体和群体的时空动态性，还蕴含着移动对象的行为信息，对交通导航、城市规划、物流调度等应用具有重要的价值。为充分挖掘轨迹数据的价值，学术界和工业界对轨迹数据管理和分析开展了大量研究工作，包括轨迹数据索引、轨迹聚类、轨迹分类、轨迹异常检测和行为预测等问题。

本文首先针对海量轨迹数据，研究了如何实现构建基于计算机集群的轨迹管理系统。现有的轨迹管理系统面临着I/O开销过高以致无法提供低延时查询服务的问题。为此，本文设计了基于分布式内存的轨迹管理系统TrajSpark。
系统提出了基于列存储的轨迹表达方式，大大提高了内存的利用率。设计了两层索引结构，以提高查找效率。此外，
TrajSpark引入了时间衰减模型以监控数据分布的变化并自动更新数据划分策略。该模型能有效降低新数据到达时的划分开销，提高了系统的可扩展性。

进一步地，本文研究了分布式$k$近邻查询。尽管现有方法能提供查询结果，但面临着通信开销大的问题。此外，目前存在着许多轨迹距离度量方法，而现有处理方法往往只适用于单一距离函数，缺乏通用性。
为处理以上挑战，本文提出使用概要数据进行距离范围估计并剪枝的思想，以达到降低通信和计算开销的目的。在该思想中，
针对不同距离函数，分别设计了基于距离上、下界的剪枝策略和基于下界的剪枝查询策略。前一种策略适用于能根据概要数据同时计算出上、下界的距离函数，而后一种适用于根据概要数据仅能计算出下界的距离函数。
最后，验证了具体的欧氏距离和动态时间弯曲距离在两种策略下的实现。
本文主要贡献包括如下三方面：

\begin{itemize}
	\item[1.]\textbf{设计了基于分布式内存的轨迹管理系统TrajSpark，以提供低延时的轨迹查询。}
	现有基于分布式磁盘的管理系统无法提供低延时的查询服务。为此，本文研究并构建了基于分布式内存的轨迹管理系统TrajSpark。TrajSpark提出了新的基于内存的轨迹表达结构IndexTRDD。该结构引入了高效的轨迹表示方法和两层索引策略。系统针对典型轨迹查询，设计了高效的查询算法。
	此外，系统引入了时间衰减模型以减少数据增加后所造成的重新划分开销。海量轨迹数据集下的实验结果表明，TrajSpark相比已有系统具有较好的优越性。
	
	\item [2.]\textbf{设计了使用概要数据计算距离上、下界的逐步剪枝策略，实现了欧氏距离在该策略下的查询算法。}
	轨迹压缩是降低通信开销的有效方法，而使用计算复杂度更低的距离上、下界进行剪枝是降低查询时间的有效途径。本文融合这两种方法，设计了使用轨迹压缩技术以得到多粒度概要数据，并使用该数据不断计算距离上、下界以逐步剪枝的查询策略FTB（Framework with Two Bounds）。
	为验证该策略的有效性，本文研究了使用该策略进行基于欧氏距离的$k$近邻查询。首先，本文使用哈尔小波系数作为多粒度概要数据。接着，设计了基于部分哈尔小波系数的欧氏距离上界和下界，并证明了随着数据粒度的增加所得到的距离上、下界会越来越紧。基于以上结论，设计了欧氏距离和FTB框架相结合的ED-FTB算法。最后，理论分析和实验结果相结合，展示了ED-FTB算法相比于基准算法的优越性。
	
%	我们将欧式距离跟FTB相融合的查询算法
	
	
	\item [3.]\textbf{设计了使用概要数据计算距离下界的逐步剪枝策略，实现了动态时间弯曲距离在该策略下的查询算法。}
	针对根据概要数据仅能设计出距离下界的情况，设计了仅使用下界进行逐步剪枝的查询策略FLB（Framework with Lower Bound）。FLB通过计算一个不断逼近全局第$k$小距离的阈值来剪枝。为验证该策略的有效性，本文研究了使用FLB策略实现基于动态时间弯曲距离的$k$近邻查询。首先，设计了多粒度包围信封以作为概要数据。接着，提出了基于包围信封的动态时间弯曲距离下界，并证明了随着包围信封粒度的增加所得到的距离下界会越来越紧。基于以上分析，设计了动态时间弯曲距离和FLB框架相结合的DTW-FLB算法。该算法引入了在计算下界过程中剪枝的策略以提高执行效率。最后，我们在真实轨迹数据集上验证了算法的有效性和可扩展性。
	
%	\item[1.] \textbf{设计了两种查询框架FTB和FLB以处理分布式$k$近邻轨迹查询。}
%	在这两个框架中，我们将查询轨迹的多粒度概要数据，由粗到细发送到远程结点中。远程结点根据获取的概要数据进行距离范围估计，并利用估计值进行剪枝。随着所获概要数据粒度的增加，所估计的距离范围也越来越紧，剪枝后所剩候选也越来越少，直到只剩下$k$个候选。由于概要数据的大小远小于查询轨迹本身，因此使用概要数据进行剪枝的方式能显著减少通信开销。此外，使用概要数据计算估计值的时间也远小于计算真实距离的时间。从而使得这两个框架的效率也高。最后，这两个框架的主要区别在于FTB框架要求使用概要数据能同时估计出距离的上界和下界。而FLB框架仅要求能估计出下界。任一距离度量方式只要设计出能够满足距离估计的概要数据，就可以应用到对应框架中。
	
%	\item[2.] \textbf{设计了ED-FTB算法以处理基于欧式距离的分布式$k$近邻轨迹查询。}欧式距离因其简单易算等特性，被广泛应用于时间序列数据分析。为此，本文研究了基于该距离准则的查询。我们首先使用哈尔小波对轨迹数据进行变换，得到多粒度的哈尔小波系数并使用其作为概要数据。接着，设计了基于部分哈尔小波系数的欧式距离上界和下界，并证明了随着系数数据的增加所得到的距离上、下界同时会越来越紧。基于以上结论，设计了欧式距离和FTB框架相结合的ED-FTB算法。在该算法中，引入了在计算上、下界过程中进行剪枝的策略以提高执行效率。最后，理论分析和实验结果相结合，展示了ED-FTB算法相比于基准算法的优越性。
	
%	\item[3.] \textbf{设计了DTW-FLB算法以处理基于动态时间弯曲距离的分布式$k$近邻轨迹查询。}动态时间弯曲距离因允许两轨迹变化的速度不一样同样也被广泛应用时间序列数据的分析中。比如，在寻找相似的运动轨迹时，只要路径一样，哪怕速度或步行时间不一致也被认为是极相似的轨迹。为此，本文研究了基于动态时间弯曲距离的查询。首先，设计了满足动态时间弯曲约束的包围信封。在此基础之上，设计了多粒度包围信封。接着，设计了基于包围信封的动态时间弯曲距离下界，并证明了随着包围信封粒度的增加所得到的距离的下界会越来越紧。基于以上分析，设计了动态时间弯曲距离和FLB框架箱结合的DTW-FLB算法。同样在该算法中引入了在计算下界过程中进行剪枝和使用多个下界进行级联剪枝的策略以提高执行效率。最后，我们在真实轨迹数据集上验证了算法的有效性和可扩展性。
\end{itemize}
\hspace{-0.5cm}
\sihao{\heiti{关键词:}} \xiaosi{轨迹，数据管理，分布式$k$近邻查询，距离上/下界，通信开销，时间开销.}
%额外空白页