支持隐私保护的障碍空间内的区域最近邻查询系统及方法

摘要

本发明涉及支持隐私保护的障碍空间内的区域最近邻查询系统及方法，本发明提出一种QO-tree索引结构，该方法为当用户提交用户自身的准确位置发送至可信服务器时，可信服务器将用户自身的准确位置处理为包含用户位置的矩形区域R，并发送至LBS服务器，LBS服务器将实际地图中的查询目标建筑物抽象为数据点，将障碍建筑物抽象为障碍物线段，并基于障碍物线段构建QO-tree索引结构，对于包含用户准确位置的矩形区域R利用QO-tree索引结构，进行障碍空间最近邻查询，并发送给可信服务器，可信服务器根据LBS服务器返回的查询结果和用户自身的准确位置，计算出查询结果中距离用户最近的数据点，并利用移动终端反馈给用户。

说明书

技术领域

本发明属于基于位置服务的信息技术领域，具体涉及支持隐私保护的障碍空间内的区域 最近邻查询系统及方法。

背景技术

随着移动通信设备的广泛流行，定位芯片被内置到了越来越多的移动通信设备中，进而 促进了基于位置服务的快速发展。移动用户在使用基于位置的服务时，须向服务提供商提供 自身的位置信息和查询请求内容，移动用户向服务器发送查询请求后，服务器端将查询结果 信息返回给移动用户(如图1所示)。典型的支持位置服务的查询技术包括最近邻查询、基于 范围的最近邻查询、以及障碍最近邻查询等。一般地，被查询对象也称为兴趣点(Points of  Interest，POI)，可以是医院、商场、饭店、宾馆等，障碍可以是各种围栏、铁路，河流和 桥梁等。

目前，主要有以下4种类别的基于位置的查询技术。(1)基于用户准确位置的最近邻查 询技术(CNN查询方法)。现有技术主要采用R-tree等空间索引技术有效地实现点的最近邻 查询。(2)基于用户准确位置的障碍最近邻查询技术(ONN查询方法)。现有技术采用R-tree 等空间索引技术对数据点和障碍物进行索引，有效地实现障碍空间内点的最近邻查询。(3) 基于用户所在区域的最近邻查询技术(RNN查询方法)。现有技术主要是返回用户所在区域 中满足用户查询要求的任一点的最近邻的查询方法。(4)支持隐私的最近邻查询技术。现有 技术主要是通过对用户准确位置进行空间匿名后得到一个隐匿的区域，然后将隐匿的区域发 送给位置服务器进行查询，最终把得到的查询结果发送给用户，用户根据自己的准确位置得 到最终的结果。

上述四种技术存在的问题是不能同时支持隐私保护和障碍最近邻查询：一是支持障碍最 近邻查询的技术在处理查询时会泄露用户的准确位置信息，比如当用户查询距离自己最近的 医院或者银行时，不想泄露自己的准确位置，但是在查询过程中需要把自己的准确位置提供 给LBS服务器，这样很可能导致用户的位置信息泄露；二是支持用户隐私保护的查询技术不 适用于空间中存在障碍物的情况，而障碍物在现实生活中普遍存在着。

发明内容

为解决现有技术存在的问题，本发明提出支持隐私保护的障碍空间内的区域最近邻查询 系统及方法。

本发明的技术方案是：

支持隐私保护的障碍空间内的区域最近邻查询系统，包括移动终端、可信服务器和LBS 服务器；

所述的移动终端，用于用户提交查询请求发送至可信服务器，查询请求即用户自身的准 确位置；

所述的可信服务器，用于将用户自身的准确位置利用空间k匿名处理方法处理为包含用 户准确位置的矩形区域R，并将包含用户准确位置的矩形区域R发送至LBS服务器；同时根 据LBS服务器返回的查询结果集Res和用户自身的准确位置，计算出查询结果集Res中距离 用户最近的数据点，并利用移动终端反馈给用户；

所述的LBS服务器，用于将实际地图中的查询目标建筑物抽象为数据点，组成数据点集 合，将障碍建筑物抽象为障碍物线段，组成障碍物集合，并基于障碍物线段构建QO-tree索 引结构；对于包含用户准确位置的矩形区域R，利用QO-tree索引结构，进行矩形区域R内 障碍空间最近邻查询，将查询得到的数据点存入区域内部的障碍空间最近邻点查询结果集 Res₁中；对于包含用户准确位置的矩形区域R，利用QO-tree索引结构，进行矩形区域R外障 碍空间最近邻查询，将查询得到的数据点存入区域外部的障碍空间最近邻点查询结果集Res₂中；将区域内部的障碍空间最近邻点查询结果集Res₁和区域外部的障碍空间最近邻点查询结 果集Res₂合并为查询结果集Res，并发送给可信服务器；

采用支持隐私保护的障碍空间内的区域最近邻查询系统进行区域最近邻查询的方法，包 括以下步骤：

步骤1：LBS服务器将实际地图中的查询目标建筑物抽象为数据点，组成数据点集合，将 障碍建筑物抽象为障碍物线段，组成障碍物集合，并基于障碍物线段构建QO-tree索引结构；

步骤1.1：将实际地图中的查询目标建筑物抽象为数据点，组成数据点集合；

步骤1.2：将实际地图中的障碍建筑物抽象为障碍物线段，组成障碍物集合；

步骤1.3：根据障碍物线段中点的经纬度坐标确定区域原点坐标：将障碍物线段按照线 段中点的经度坐标排序，并将中间位置的障碍物线段中点的经度坐标作为坐标原点的横坐标； 再将障碍物线段按照线段中点的纬度坐标排序，将中间位置的障碍物线段中点的纬度坐标作 为原点的纵坐标；

步骤1.4：利用距离坐标原点最近的障碍物线段所在直线和与障碍物线段的垂直平分线 将整个地图空间划分为四个子区域；

步骤1.5：将四个子区域中的障碍物线段按照步骤1.3至步骤1.4的过程依次划分出其 子区域，直至子区域内没有障碍物线段为止；

步骤1.6：以障碍物线段中点为中心构建QO-tree索引结构：将整个地图空间作为根节 点、包含障碍物的子区域作为孩子节点、无障碍物的子区域作为叶子节点，在每个叶子节点 上构建一棵R-tree，其中，每棵R-tree包含该子区域的所有数据点、该子区域边界的最近 邻数据点和最近邻障碍物线段端点、该子区域边界的最近邻障碍物线段端点的最近邻数据点；

所述的子区域边界的最近邻数据点和最近邻障碍物线段端点使用最近邻查询技术中的二 分遍历方法求取，子区域边界的最近邻障碍物线段端点的最近邻数据点使用障碍最近邻查询 技术中的构建可见图方法求取；

步骤2：用户通过移动终端将查询请求发送至可信服务器，查询请求即用户自身的准确 位置；

步骤3：可信服务器将用户自身的准确位置利用空间k匿名处理方法处理为包含用户准 确位置的矩形区域R，并将包含用户准确位置的矩形区域R发送至LBS服务器；

步骤4：LBS服务器根据包含用户准确位置的矩形区域R利用QO-tree索引结构，进行矩 形区域R内障碍空间最近邻查询，将查询得到的数据点存入区域内部的障碍空间最近邻点查 询结果集Res₁中；

步骤4.1：利用QO-tree索引结构确定矩形区域R所在的子区域；

步骤4.2：利用矩形区域R所在的子区域的叶子节点所指向的R-tree索引结构确定与矩 形区域R叠交的最小边界矩形MBR；

步骤4.3：将与矩形区域R叠交的最小边界矩形MBR中包含的并位于矩形区域R中的数 据点存入区域内部的障碍空间最近邻点查询结果集Res₁中；

步骤5：LBS服务器根据包含用户准确位置的矩形区域R利用QO-tree索引结构，进行 矩形区域R外障碍空间最近邻查询，将查询得到的数据点存入区域外部的障碍空间最近邻点 查询结果集Res₂中；

步骤5.1：将包含用户准确位置的矩形区域R的四个边定义为e_p，p∈(1...4)；

步骤5.2：利用QO-tree索引结构确定边e_p的端点的最近邻数据点，u∈(1、2)；

步骤5.2.1：利用QO-tree索引结构确定边e_p的端点所属的叶子节点；

步骤5.2.2：利用边e_p的端点所在的叶子节点的R-tree结构，确定该端点的最近 邻可见点

步骤5.2.3：判断端点的最近邻可见点是否为障碍物线段端点，若是，则利用其 R-tree结构找到该障碍物线段端点的最近邻数据点将数据点存入区域外部的障碍 空间最近邻点查询结果集Res₂中，否则，直接将可见点存入区域外部的障碍空间最近邻 点查询结果集Res₂中；

步骤6：LBS服务器将区域内部的障碍空间最近邻点查询结果集Res₁和区域外部的障碍空 间最近邻点查询结果集Res₂合并为查询结果集Res；

步骤7：LBS服务器将查询结果集Res发送给可信服务器；

步骤8：可信服务器根据查询结果集Res和用户自身的准确位置，计算出查询结果集Res 中距离用户最近的数据点，并利用移动终端反馈给用户。

本发明的有益效果：本发明所述的支持隐私保护的障碍空间内区域最近邻查询系统及方 法，实现了在障碍空间内，不想泄露自己准确位置的移动用户提出的区域最近邻查询，并利 用新提出的QO-tree索引机制，将障碍最近邻查询转化为欧式距离的最近邻查询，并有效地 过滤掉不满足查询要求的结果，缩短了查询时间，提高了查询效率，同时保证了查询结果的 准确性。

附图说明

图1为本发明具体实施方式中的支持隐私保护的障碍空间内的区域最近邻查询系统的结 构示意图；

图2为本发明具体实施方式中的支持隐私保护的障碍空间内的区域最近邻查询方法的流 程图；

图3为本发明具体实施方式中的构建QO-tree索引结构的流程图；

图4为本发明具体实施方式中的数据点集合与障碍物集合示意图；

图5为本发明具体实施方式中的整个地图划分的子区域示意图；

图6为本发明具体实施方式中的障碍物线段中点为中心构建的QO-tree索引结构示意图；

图7为本发明具体实施方式中的查询请求Q的具体位置示意图；

图8为本发明具体实施方式中的将用户准确位置利用空间k匿名处理方法处理为包含用 户准确位置的矩形区域R的示意图；

图9为本发明具体实施方式中的进行矩形区域R内障碍空间最近邻查询的示意图；

图10为本发明具体实施方式中的进行矩形区域R外障碍空间最近邻查询的示意图；

图11为本发明具体实施方式中的查询结果集Res示意图；

图12为本发明具体实施方式中的发送给用户的距离用户最近的数据点的示意图。

具体实施方式

下面结合附图对本发明的具体实施方式做详细说明。

本发明具体实施方式中，查询目标建筑物是指医院、银行等用户需要查询的兴趣点，障 碍建筑物为围栏、河流等障碍。使用知名的网站http：//www.chorochronos.org中的村庄信息生 成一个数据点集合D，其中的河流信息做障碍物数据集O，为了更好地进行测试，把所有数 据进行归一化，从而满足查询的范围。由于抽取的数据点和障碍物个数太多，为了便于在此 说明，特将其内容进行删减，每个数据集只保存了部分数据。

支持隐私保护的障碍空间内的区域最近邻查询系统，如图1所示，包括移动终端、可信 服务器和LBS(Location-based Service)服务器。

本发明具体实施方式是在在Linux操作系统中，采用C++语言编程实现。

所述的移动终端，用于用户提交查询请求发送至可信服务器，查询请求即用户自身的准 确位置。

移动终端可以选择手机、平板电脑等，本实施方式中，通过PC机数据文件模拟手机发送 请求。

所述的可信服务器，用于将用户自身的准确位置利用空间k匿名处理方法处理为包含用 户准确位置的矩形区域R，并将包含用户准确位置的矩形区域R发送至LBS服务器；同时根 据LBS服务器返回的查询结果集Res和用户自身的准确位置，计算出查询结果集Res中距离 用户最近的数据点，并利用移动终端反馈给用户。

本实施方式中，可信服务器选用CPU为Intel 3.4Ghz、内存8GB RAM、硬盘500G的 计算机。

所述的LBS服务器，用于将实际地图中的查询目标建筑物抽象为数据点，组成数据点集 合，将障碍建筑物抽象为障碍物线段，组成障碍物集合，并基于障碍物线段构建QO-tree索 引结构；对于包含用户准确位置的矩形区域R，利用QO-tree索引结构，进行矩形区域R内 障碍空间最近邻查询，将查询得到的数据点存入区域内部的障碍空间最近邻点查询结果集 Res₁中；对于包含用户准确位置的矩形区域R，利用QO-tree索引结构，进行矩形区域R外障 碍空间最近邻查询，将查询得到的数据点存入区域外部的障碍空间最近邻点查询结果集Res₂中；将区域内部的障碍空间最近邻点查询结果集Res₁和区域外部的障碍空间最近邻点查询结 果集Res₂合并为查询结果集Res，并发送给可信服务器。

本实施方式中，LBS服务器选用CPU为Intel 3.4Ghz、内存为8GB RAM、硬盘为500G 的计算机。

采用支持隐私保护的障碍空间内的区域最近邻查询系统进行区域最近邻查询的方法，如 图2所示，包括以下步骤：

步骤1：LBS服务器将实际地图中的查询目标建筑物抽象为数据点d_i，组成数据点集合D， 将障碍建筑物抽象为障碍物线段o_j，组成障碍物集合O，并基于障碍物构建QO-tree索引结 构，如图3所示。

步骤1.1：将实际地图中的查询目标建筑物抽象为数据点d_i，组成数据点集合D。

步骤1.2：将实际地图中的障碍建筑物抽象为障碍物线段o_j，障碍物线段o_j的端点为M_oj和N_oj，组成障碍物集合O。

本实施方式中，组成的数据点集合与障碍物集合如图4所示，其中，包括障碍物线段o₁、 障碍物线段o₂、数据点d₁…d₁₂。

步骤1.3：根据障碍物线段中点的经纬度坐标确定区域原点坐标：将障碍物线段按照线 段中点的经度坐标排序，并将中间位置的障碍物线段中点的经度坐标作为坐标原点的横坐标； 再将障碍物线段按照线段中点的纬度坐标排序，将中间位置的障碍物线段中点的纬度坐标作 为原点的纵坐标。

步骤1.4：利用距离坐标原点最近的障碍物线段所在直线和与障碍物线段的垂直平分线将 整个地图空间划分为四个子区域。

步骤1.5：将四个子区域中的障碍物线段按照步骤1.3至步骤1.4的过程依次划分出其 子区域，直至子区域内没有障碍物线段为止。

本实施方式中，整个地图划分的子区域示意图如图5所示，障碍物线段o₁将整个空间分 为四个子区域，分别为Reg₁、Reg₂、Reg₃和Reg₄，而子区域Reg₁、Reg₃、Reg₄内不再包含 障碍物，所以不用继续划分，子区域Reg₂被障碍物o₂继续划分，形成4个子区域Reg₂₁、Reg₂₂、 Reg₂₃和Reg₂₄，这些子区域内不再包含障碍物。

步骤1.6：以障碍物线段中点为中心构建QO-tree索引结构：将整个地图空间作为根节 点、包含障碍物的子区域作为孩子节点、无障碍物的子区域作为叶子节点，在每个叶子节点 上构建一棵R-tree，其中，每棵R-tree包含该子区域的所有数据点、该子区域边界的最近 邻数据点和最近邻障碍物线段端点、该子区域边界的最近邻障碍物线段端点的最近邻数据点。

子区域边界的最近邻数据点和最近邻障碍物线段端点使用最近邻查询技术中的二分遍历 方法求取，子区域边界的最近邻障碍物线段端点的最近邻数据点使用障碍最近邻查询技术中 的构建可见图方法求取。

本实施方式中，基于障碍物线段构建的QO-tree索引结构如图6所示，root为根节点，子 区域Reg₁、Reg₃、Reg₄、Reg₂₁、Reg₂₂、Reg₂₃和Reg₂₄为叶子节点，子区域Reg₂为孩子节点。 每个孩子节点包含一个数据域和四个指针域，数据域中存储对应的子区域信息，四个指针域 指向该区域的子区域，每个叶子节点上包含一个数据域和一个指针域，数据域中存储对应的 子区域信息，指针域指向一棵R-tree。每棵R-tree中存储着该子区域的所有数据点、该子 区域边界的最近邻数据点和最近邻障碍物线段端点、该子区域边界的最近邻障碍物线段端点 的最近邻数据点。

步骤2：用户通过移动终端将查询请求Q发送至可信服务器，查询请求Q即用户自身的 准确位置。

本实施方式中，查询请求Q的具体位置如图7所示。

步骤3：可信服务器将用户自身的准确位置利用空间k匿名处理方法处理为包含用户准 确位置的矩形区域R，并将包含用户准确位置的矩形区域R发送至LBS服务器。

本实施方式中，将用户准确位置利用空间k匿名处理方法处理为包含用户准确位置的矩 形区域R的示意图如图8所示。

步骤4：LBS服务器根据包含用户准确位置的矩形区域R利用QO-tree索引结构，进行 矩形区域R内障碍空间最近邻查询，将查询得到的数据点存入区域内部的障碍空间最近邻点 查询结果集Res₁中。

本实施方式中，进行矩形区域R内障碍空间最近邻查询的示意图如图9所示。

步骤4.1：利用QO-tree索引结构确定矩形区域R所在的子区域。

本实施方式中，区域R所在的子区域是Reg₂₄和Reg₃。

步骤4.2：利用矩形区域R所在的子区域的叶子节点所指向的R-tree索引结构确定与矩 形区域R叠交的最小边界矩形MBR(Minimum Boundary Rectangle)。

步骤4.3：将与矩形区域R叠交的最小边界矩形MBR中包含的并位于矩形区域R中的数 据点存入区域内部的障碍空间最近邻点查询结果集Res₁中。

本实施方式中，通过访问这两个子区域叶子节点的R-tree，可以获得所有候选的数据点 {d₁，d₂，d₃，d₄，d₅，d₇，d₈，d₉，d₁₀，d₁₁，d₁₂}，通过基于R-tree索引技术的范围查询计算 方法过滤掉MBR₁、MBR₂和MBR₄的数据点，只对MBR₃中的数据点{d₅，d₂，d₇}和MBR₅的 数据点{d₅}一一验证是否在区域R中，最后得到查询区域R的内部最近邻数据点d₅，所以区 域内部的障碍空间最近邻点查询结果集Res₁＝{d₅}。

步骤5：LBS服务器根据包含用户准确位置的矩形区域R利用QO-tree索引结构，进行 矩形区域R外障碍空间最近邻查询，将查询得到的数据点存入区域外部的障碍空间最近邻点 查询结果集Res₂中。

本实施方式中，进行矩形区域R外障碍空间最近邻查询的示意图如图10所示。

步骤5.1：将包含用户准确位置的矩形区域R的四个边定义为e_p，p∈(1...4)。

步骤5.2：利用QO-tree索引结构确定边e_p的端点的最近邻数据点，u∈(1、2)。

步骤5.2.1：利用QO-tree索引结构确定边e_p的端点所属的叶子节点。

步骤5.2.2：利用边e_p的端点所在的叶子节点的R-tree结构，确定该端点的最近邻 可见点

本实施方式中，确定端点的最近邻可见点的方法为：

若端点与其最近邻点在同一个子区域，说明它们之间没有障碍物，也就是一定为可见 点，若端点与其最近邻点不在同一个子区域，则需要判断端点与最近邻点的连线是否 和分割它们之间的障碍物相交，如果相交则不可见，否则为可见点。

步骤5.2.3：判断端点的最近邻可见点是否为障碍物线段端点，若是，则利用其 R-tree结构找到该障碍物线段端点的最近邻数据点将数据点存入区域外部的障碍 空间最近邻点查询结果集Res₂中，否则，直接将可见点存入区域外部的障碍空间最近邻 点查询结果集Res₂中。

本实施方式中，区域外部的障碍空间最近邻点查询结果集为Res₂＝{d₂，d₇}。

步骤6：LBS服务器将区域内部的障碍空间最近邻点查询结果集Res₁和区域外部的障碍 空间最近邻点查询结果集Res₂合并为查询结果集Res。

本实施方式中，查询结果集Res示意图如图11所示，查询结果集Res＝{d₅，d₂，d₇}。

步骤7：LBS服务器将查询结果集Res发送给可信服务器。

本实施方式中，LBS服务器将查询结果集Res＝{d₅，d₂，d₇}返回给可信服务器。

步骤8：可信服务器接根据查询结果集Res和用户自身的准确位置，计算出查询结果集 Res中距离用户最近的数据点，并利用移动终端反馈给用户。

本实施方式中，发送给用户的距离用户最近的数据点的示意图如图12所示，可信服务器 距离用户最近的查询结果{d₂}反馈给用户。