PrivateTrace-Core

项目地址

一、选题背景

云外包时空数据查询服务面临数据泄露、数据推断等安全威胁。时空数据包含用户行动轨迹、生活习惯等个人敏感数据，时空数据泄露与滥用将对个人生活造成极大困扰，对社会造成严重负面影响，阻碍时空数据要素资源的开发利用。

目前，基于隐私计算等相关技术可以达到“数据可用不可见”的目标。但是，由于这种技术采用同态加密、计算操作在密文上完成，计算的复杂度高、时间长的缺点。这就需要我们改进传统的比较算法O(n²)，从数据结构等角度出发，设计出减小关键算子计算量的算法。

为了应对这些挑战，本项目以设计安全且高效的隐私保护时空接触追溯系统为基本目标。一方面，我们使用多种基本数据结构如双向链表，红黑树等设计高抽象的高级数据结构，另一方面基于设计的数据结构，完成高效的密态轨迹比较算法，在保证不泄露隐私数据的前提下减少算法额外开销，实现面向密态时空数据的精准查询和追溯，最终形成安全且高效的隐私保护时空接触追溯系统。

二、方案论证(设计理念)

2.1 编码机制

本系统使用用户随身携带的具有GPS信号接受装置的设备（如手机，智能手表等）收集轨迹数据，用户收集的轨迹数据将表示为一系列的具有时间戳的经纬度和海拔信息。然而，使用经纬度计算距离涉及到地球的曲率和三角函数，计算复杂度高，在密文域的计算效率低。

为此，我们设计了一种编码方式，将经纬度映射到空间三维坐标系，使用三维空间坐标x,y,z来表示位置。这样距离计算可以使用简单的欧氏距离表示，降低了计算量。

2.2 数据结构与比较算法

2.2.1 同心圆和同心圆树

在相同时间段内，我们利用待比较的位置之间的距离信息，建立“同心圆”数据结构，通过一次比较排除不可能存在轨迹相交的位置数据，减少了比较的数量。此处我们使用了ArrayList、HashMap和红黑树这三种基本数据结构。

具体来说， 我们使用ArrayList存储所有时空信息，使用HashMap建立ArrayList的索引，使用红黑树排序并索引同心圆。图1(a) 是我们建立的数据结构“同心圆”的示例图。

基于这种数据结构，我们可以通过一次比较排除大量数据、我们称之为“一维裁剪”。裁剪算法如图2(a) 我们通过第一步与圆心的比较，就可以确定出后续比较中可能产生交集的部分（图中绿色区域），其他部分不可能与轨迹产生交集，因此被裁剪。

图1 “同心圆”和“同心圆树”数据结构示意图

图2 “同心圆”和“同心圆树”的比较算法示意图

在上述“同心圆”的基础上，我们考虑到轨迹信息里面包含的时空信息具有前后关联的特性，并且基于这一特性引入了双向链表的思想。如图1(b) 所示，每个同心圆组中的同心圆将存储与之相邻的同心圆的引用，建立起双向链表的结构，最终建立整个“同心圆树”。基于这一数据结构，我们能够在完成一次比较的时候同时尝试裁剪部分与之相邻的同心圆（一般位于不同的同心圆中，即同心圆树的不同层）。如图2(b)，在第一步进行比较之后，我们根据比较的结果，裁剪同一轨迹的前后位置（图中②），我们把这个称之为“二维裁剪”。

通过以上的数据结构和比较算法，我们能够实现与传统比较方式2倍的加速，同时在追踪轨迹增大的情况下，我们具有近似于O(logn)的性能表现，具体性能分析数据将在第四部分给出。

三、过程论述

3.1 编码机制

我们设计了一种编码方式，将经纬度映射到空间三维坐标系，使用三维空间坐标来表示位置。具体使用的公式如下：

其中e为参考椭球第一扁率，N为大地水准面差距，定义为：

这样距离计算可以使用简单的欧氏距离表示，即:

我们定义并实现了以下类：

Location.java Utils.java 实现地点的编码和转换及加密。

3.2 数据结构与比较算法

在相同时间段内，我们利用待比较的位置之间的距离信息，建立“同心圆”数据结构。我使用了ArrayList、HashMap和红黑树这三种基本数据结构。具体来说， 我们使用ArrayList存储所有时空信息，使用HashMap建立ArrayList的索引，使用红黑树排序并索引同心圆。

此外，我们使用双向链表来链接多个同心圆组成同心圆树。具体来说，每个位置信息将拥有前后位置的指针，构成双向链表，以支持双向遍历以及裁剪操作。

我们定义并实现了以下类：

Point.java EncryptedPoint.java 点/加密点类。

Plane.java 平面类。

Circle.java EncryptedCircle.java 圆/加密圆类。

TimeLocationData.java EncTmLocData.java 时空信息/加密时空信息类。

Trajectory.java EncTrajectory.java TrajectoryReader.java 轨迹信息\加密轨迹信息类和轨迹读取类。

3.3 系统实现

我们设计的系统分为三个阶段：离线阶段、在线初始化阶段、在线查询阶段。如图3所示，在离线阶段，使用者使用随身的手机等拥有GPS接收器的设备收集自己日常活动的轨迹信息，然后将轨迹信息编码后使用服务器的公钥加密，并将加密后的轨迹信息上传到服务器1上。在初始化阶段，两个服务器之间将加密的阳性轨迹进行处理，建立“同心圆树”，供后续阶段使用。在查询阶段，服务器将用户上传的轨迹与初始化阶段建立的同心圆树进行比较，并以明文形式返回结果。

图3 系统流程图

我们定义并实现了以下类：

EncSquareDistance.java 加密距离类，重载比较器，用于构建同心圆。

ConcentricCircles.java 同心圆类，实现了同心圆的建立、初始化和比较。

CCirleTree.java 同心圆树类，实现了同心圆树的建立、初始化和比较，实现了双裁剪算法。

Constant.java 定义系统的变量，例如编码精度等。

Main.java 实现系统流程。

四、结果分析

我们使用真实的数据集测试我们设计的系统的正确性和性能，我们使用了微软收集的Microsoft Geolife GPS Trajectory Dataset。该数据集是在 Microsoft Research Geolife 项目中由 178 个用户在四年多的时间里（从2007年4月到 2011年10月）收集的。该数据集的GPS轨迹由一系列带有时间戳的点表示，每个点都包含纬度、经度和高度信息。该数据集包含17,621条轨迹，总距离为1,251,654公里，总时长为48,203 小时。这些轨迹由不同的GPS记录器和GPS手机记录，并具有多种采样率。91%的轨迹以密集表示形式记录，例如每1~5秒或每5~10米/点。同时，该数据集记录了广泛的用户户外运动，不仅包括回家和上班等生活常规，还包括一些娱乐和体育活动，如购物、观光、餐饮、徒步旅行和骑自行车。这个数据集不仅符合我们算法的需求，同时真实、数据量大的特点，符合实验要求。

4.1 编码机制结果分析

在2.1章我们设计了一种轨迹编码机制，在这里我们证明该轨迹编码机制的正确性符合要求。由于本系统仅对位置进行距离的计算和比较，所以我们使用距离计算的正确率来比较我们设计的编码机制与经纬度编码的正确性，这里的错误率定义为d_i/d_e，其中d_i,d_e分别是我们设计的编码机制计算得到的距离和经纬度编码计算得到的距离。如表1所示，我们设计的编码机制的错误率在400米内的最高不超过0.18%，平均错误率为0.167%，具有较高的正确率。

表1 编码机制错误率

4.2 优化结果分析

为了证明我们设计的数据结构和算法对系统性能的影响，我们设计了实验比较了使用我们设计数据结构和算法与常规比较方法的系统运行时间与流量消耗的差距。如图4橙色和黄色所示，我们设计的数据结构和算法相较于常规方法实现了近2倍的加速，同时减少了近一半的流量消耗。

图4 优化结果

4.3 大数据量表现分析

为了说明我们设计的系统具有大规模应用的潜力，我们设计了实验探究在阳性案例增加的情况下对系统性能的影响。如图5所示，在系统的同心圆树的大小增加的情况下，系统比较时间的增加趋近于缓慢，由此证明系统在可以应对大规模的数据，实现广泛的应用。

图5 大数据量表现