技术摘要：
本发明涉及一种构建加密倒序矩形树的方法，包括所有进行数据共享的数据拥有者协商确定安全系数；数据拥有者根据安全系数，将属于自己的IR树中的每一个叶子节点加密，将所有叶子节点的加密消息发送至其他数据拥有者共享。本发明实现了所有进行数据共享的数据拥有者安全  全部
背景技术：
近年来，随着基于位置的服务(Location-Based-Service，简称LBS)日益繁荣，政 府、公司乃至个人可能收集到大量基于位置的数据，我们将它们称之为数据拥有者，将这些 基于位置的数据称为兴趣点(Point-Of-Interest，简称POI)。 对于这些数据拥有者来说，随着数据规模的不断增加，对数据进行管理和储存的 难度也随之增加，而为此建立专门用来储存管理数据的系统将会消耗大量的资源。云服务 就可以解决这类问题，云服务提供商通常有专业的数据管理与存储技术，并且拥有大量计 算资源用来完成海量数据中的计算，提供大量空间资源存储海量资源。数据拥有者将数据 外包至云服务提供商，这使得数据拥有者能将更多精力与资源投入至运用数据产生价值 上，而数据的存储和管理由云服务提供商承担。这也节约了数据拥有者的数据管理存储成 本。 然而随着云计算的普及，数据拥有者的敏感信息越来越向云服务提供商上集中。 为了保护数据隐私，数据拥有者必须在外包之前加密敏感数据，之后才能进行上传。而这使 得云计算如何有效利用加密数据成为一项非常具有挑战性的任务。而如何支持多个数据拥 有者之间安全地共享彼此的数据，并且保证数据的隐私安全成为目前亟需解决的技术问 题。
技术实现要素：
本发明所要解决的技术问题是针对现有技术的不足，提供一种构建加密倒序矩形 树方法、一种空间关键词查询方法。 本发明解决上述技术问题的技术方案如下： 一种构建加密倒序矩形树的方法，包括以下步骤： 所有进行数据共享的数据拥有者协商确定安全系数，所述安全系数包括公钥PK和 通用随机数； 所述数据拥有者根据所述安全系数，将属于自己的IR树中的每一个叶子节点加 密，且为所述每一个叶子节点构建一组加密消息Mi， Mi＝{(Ni1，Ni2，Ni3，Ni4)，E(IFLi)，{E(pi1)，…，E(pik)}}，且将所有叶子节点的加密 消息发送至其他数据拥有者共享，其中Mi是第i个叶子节点，Ni1、Ni2、Ni3和Ni4分别是覆盖第i 个叶子节点MBR的最小边界矩形的四个顶点，E(IFLi)是第i个叶子节点的倒排索引文件，E (pi1)，…，E(pik)是所述第i个叶子节点的第1至k个兴趣点的加密信息，i和k均是正整数； 所述所有需进行数据共享的数据拥有者分别根据接收到的所述加密消息和自己 的POI信息，重构其他数据拥有者的IR树中的叶子节点的最小边界矩形，并重新划分最小边 4 CN 111597582 A 说　明　书 2/8 页 界矩形，为自己的IR树中的叶子节点关联加密的倒排索引文件，合并自己的IR树中的孩子 节点的倒排索引文件，生成中间节点的倒排索引文件，得到加密倒序矩形树。 本发明的有益效果是：通过所有进行数据共享的数据拥有者协商安全系数，并根 据自己的IR树构建，得到加密倒序矩形树，实现了所有进行数据共享的数据拥有者安全地 共享各自的原始数据，在保护数据隐私安全的同时，为用户提供了更多的备选结果，有效地 提升了服务质量，创造了更大的商业价值。 在上述技术方案的基础上，本发明还可以做如下改进。 进一步地，所述所有进行共享数据数据拥有者协商确定安全系数，具体包括以下 步骤： 每一个数据拥有者生成公私钥对(pki，ski)，并对外发布通用公钥PK，其中PK＝∏ pki； 根据所述通用公钥PK，其中一个数据拥有者随机选择一个随机数ε，且 所述随机数ε是用于加密POI所携带的文本描述信息时，所有 进行数据共享的数据拥有者共同使用的随机数，其中q是大于2的正整数。 采用上述进一步方案的有益效果是：通过所有进行数据共享的数据拥有者协商安 全系数，实现了数据拥有者可安全地共享各自的原始数据。 进一步地，所述加密倒叙矩形树包括以下特征； 所述加密倒序矩形树中的每个叶子节点包含至少一个兴趣点； 所述每一个兴趣点包括空间位置信息和文本描述信息，所述空间位置信息和所述 文本描述信息都是加密的信息； 所述第j个兴趣点E(pj)＝{E(λj)，E(ψj)}，其中E(λj)是所述空间位置信息且E(λj) ＝{E(gxi)，E(gyi)}，其中，j是正整数； E(ψj)是所述文本描述信息，所述文本描述消息包括n组加密的关键词消息，每一 组加密的关键词消息E(ψjn)，E(ψSjn1)，...，E(ψSjnk)包括加密时使用通用公钥PK和通过分布 式ElGamal生成的关键词的密文及为所述关键词的所有子字符串的密文，即 E(ψj)＝{[E(ψj1)，E(ψSj11)，...，E(ψSj1k)]，...[E(ψjn)，E(ψSjn1)，...，E(ψSjnk)]}， 其中n和j是大于1的正整数； 所述加密倒序矩形树中每一个叶子节点包括一个指向倒排索引文件IFL的指针和 一个覆盖所有兴趣点的第一最小边界矩形MBR； 所述每一个叶子节点的倒排文件中包括叶子节点覆盖的所有兴趣点的文本描述 文件，所述文本描述文件包括所有关键词以及对应子字符串的密文； 所述加密倒序矩形树中每一个非叶子节点包括一个指向倒排索引文件IFL的指针 和一个覆盖所有孩子节点MBR的第二最小边界矩形MBR，所述每一个非叶子节点的倒排文件 中包括所述非叶子节点覆盖的所有孩子节点的倒排索引文件之和，所述倒排文件包括所覆 盖兴趣点关键词以及对应子字符串的密文，其中，所述倒排文件IFL＝{E(ψ11)，E(ψ S11)，...，E(ψS1n)}。 采用上述进一步方案的有益效果是：基于IR树的结构创建了加密倒序矩形树结 构，实现了支持多个数据拥有者之间安全地共享彼此的数据，同时还保证了数据的隐私安 全。 5 CN 111597582 A 说　明　书 3/8 页 进一步地，所述加密倒叙矩形树还包括以下特征： 所述第一最小边界矩形MBR的四个顶点分别为{N1，N2，N3，N4}，所述第一最小边界 矩形MBR的顶点的空间位置由经纬度表示，并且四个顶点的空间位置信息均以明文形式储 存； 所述第二最小边界矩形MBR的四个顶点分别为{N’1，N’2，N’3，N’4}，所述第二最小 边界矩形MBR的顶点的空间位置由经纬度表示，并且四个顶点的空间位置信息均以明文形 式储存。 本发明解决上述技术问题的另一种技术方案如下： 一种空间关键词查询方法，基于如上述技术方案中任一项所述的构建加密倒序矩 形树的方法构建的加密倒序矩形树，包括以下步骤： S1、将最小堆H初始化，并将所述加密倒序矩形树的根节点放入所述最小堆H中； S2、当满足弹出条件时，将所述最小堆H中的顶端最小元素e弹出并维持最小堆H， 其中所述满足弹出条件是当查询条件Q中的关键词个数是预设个数时，所述最小堆H中的元 素个数不为空，或当查询条件Q中的关键词个数大于所述预设个数时，查询条件Q中未被覆 盖的关键词个数不为空且所述最小堆H中的元素个数不为空； S3、判断所述顶端最小元素e的类型； 若所述顶端最小元素e是节点，则计算所述最小元素e对应的代价函数； 若所述顶端最小元素e是兴趣点POI，则放入结果集中，且当所述查询条件Q中的关 键词个数大于所述预设个数时，更新所述查询条件Q中的未被覆盖的关键词； S4、重复执行步骤S2-S4，直到所述结果集中的兴趣点POI个数达到预设个数，输出 所述结果集。 本发明的有益效果是：提供了一种空间关键词查询方法，支持多个数据拥有者之 间安全地共享彼此的数据，保证数据的隐私安全，查询条件的隐私安全以及查询结果的隐 私安全，实现了在云计算以及数据外包的情景，服务提供商能够在保护原始数据、查询条件 以及查询结果的隐私安全的前提下，快速响应授权客户端对于空间关键词查询的需求。 在上述技术方案的基础上，本发明还可以做如下改进。 进一步地，所述计算所述最小元素e对应的代价函数，包括以下步骤： 计算所述加密倒序矩形树中的叶子节点的欧氏距离； 计算所述e与查询条件Q中的每一个关键词的最大Jaccard系数。 本发明还提供一种计算机可读存储介质，包括指令，当所述指令在计算机上运行 时，使所述计算机执行根据上述技术方案中任一项所述的构建加密倒序矩形树的方法的步 骤。 本发明还提供一种计算机设备，包括存储器、处理器及存储在所述存储器上的并 可在所述处理器上运行的计算机程序，所述处理器执行所述程序时实现如上述技术方案中 任一项所述的构建加密倒序矩形树的方法的步骤。 本发明还提供一种计算机可读存储介质，包括指令，当所述指令在计算机上运行 时，使所述计算机执行根据上述技术方案中任一项所述的空间关键词查询方法的步骤。 本发明还提供一种计算机设备，包括存储器、处理器及存储在所述存储器上的并 可在所述处理器上运行的计算机程序，所述处理器执行所述程序时实现如上述技术方案中 6 CN 111597582 A 说　明　书 4/8 页 任一项所述的空间关键词查询方法的步骤。 本发明附加的方面的优点将在下面的描述中部分给出，部分将从下面的描述中变 得明显，或通过本发明实践了解到。 附图说明 为了更清楚地说明本发明实施例的技术方案，下面将对本发明实施例或现有技术 描述中所需要使用的附图作简单地介绍，显而易见地，下面所描述的附图仅仅是本发明的 一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这 些附图获得其他的附图。 图1为本发明实施例提供的一种构建加密倒序矩形树的方法的示意性流程图； 图2为本发明另一实施例提供的一种加密倒序矩形树的结构图。 图3为本发明实施例提供的一种加密倒序矩形树的结构图； 图4为本发明另一实施例提供的一种空间关键词查询方法的示意性流程图。