暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / VLDB 2022 | Hu-Fu: 基于数据联邦的高效空间查询系统

VLDB 2022 | Hu-Fu: 基于数据联邦的高效空间查询系统

时空实验室 2023-01-30
601
数据隔离已成为扩展大数据查询处理的障碍。出于安全考虑，数据所有者之间共享原始数据通常是禁止的。一个有前景的解决方案是利用安全多方计算(SMC) 技术对多个数据所有者联邦执行安全查询，最近对关系数据的联邦工作证明了这一点。然而，由于用于查询处理的安全距离操作过多以及它们使用通用SMC 库来实现安全操作，现有解决方案在空间查询上效率非常低。本次为大家带来数据库领域顶级会议VLDB的论文：《Hu-Fu: Efficient and Secure Spatial Queries over Data Federation》。
一．背景
高效处理大规模数据的空间查询对于大量智慧城市应用至关重要，包括出租车、物流规划、地图服务和接触者追踪等。尽管空间数据的数据量在不断增长，但由于数据隔离问题(又名孤立数据)，这些应用越来越难以充分利用大规模空间数据。由于法律法规或商业原因，城市或国家级规模的空间数据集通常由多方私人分别拥有。
解决数据隔离问题的一个有前景的方案是在数据联邦上执行安全查询，一般来说，数据联邦的安全查询处理可以通过多方安全计算(SMC) 等众所周知的技术来解决。然而，直到最近，诸如SMCQL和Conclave之类的先驱研究才迈出了在SMC库上针对(关系)数据联邦进行高效查询的第一步。不出所料，越来越多的应用程序正在构建在空间数据所有者的联邦之上。例如：在COVID-19期间，几家移动网络运营商(如中国移动和中国电信) 合作组成空间数据联邦，通过其空间数据识别谁去过感染地区。通过空间数据联邦执行空间查询(如范围查询或距离连接)可以帮助跨多个组织的空间数据识别传染区域中的联系人，而不会泄露隐私。然而，将最先进的数据联邦解决方案直接应用于空间数据可能效率不高。
为此，文章提出了一种高效、安全地处理联邦空间查询的系统Hu-Fu。它通过两个模块解决了联邦空间查询处理效率低下的问题: (i) 一种新颖的查询重写器，将联邦空间查询分解为明文和安全算子，前者在每个筒仓（silo）内执行，后者跨筒仓执行。文章定义了两个明文算子(明文范围查询和范围计数)和三个安全算子(安全求和、比较和集合联邦)作为基本算子，在此基础上设计了新颖的执行方案, 将主流的联邦空间查询(联邦范围查询、范围计数、kNN查询、距离联接和kNN联接)分解为这些基本算子; (ii)将这些算子实现为明文的驱动程序，Hu-Fu的驱动程序将查询重写器中定义的基本算子实现为高效的基元,可以适应后端的异构空间数据库。每个算子都由特定的原语实现。具体来说，安全算子是作为具有专用优化的安全基元实现的。支持各种系统，例如PostGIS、SpatiaLite、MySQL、GeoMesa、Simba和SpatialHadoop。Hu-Fu 还包含一个透明的查询接口，以支持用本机SQL编写的联邦空间查询。充分的实验评估表明Hu-Fu 在效率方面通常优于现有技术。与从SMCQL和Conclave扩展到空间查询的两个强大的基线SMCQL-GIS 和Conclave-GIS 相比，Hu-Fu分别快了4个数量级和5个数量级，在通信成本方面比同等安全级别的SMCQL-GIS和Conclave-GIS低。
二．方法介绍
2.1总体框架
图1为论文提出的Hu-Fu框架的结构，它由三个模块组成：查询接口、查询重写器和驱动程序。从功能角度来看，查询重写器和驱动程序优化了联邦空间查询的效率,查询接口提高了Hu-Fu的可用性。
图1
图2显示了用户查询n个筒仓的数据联邦时的Hu-Fu 工作流程。查询接口和查询重写器部署在用户计算机上，为空间服务提供门户。每个筒仓都运行一个Hu-Fu 驱动程序实例，以与其基础空间数据库进行交互。假设用户的空间服务发出用SQL 编写的联邦空间查询。当联邦空间查询传入时，它首先由查询接口进行分析。然后，查询重写器将查询转换并优化为一系列明文和安全算子。然后，这些算子将作为明文和安全基元发送到驱动程序执行。首先，在每个筒仓的基础空间数据库上执行明文基元，以获得本地结果。然后，收集本地结果以执行最终查询结果的安全基元，该结果由查询接口返回给用户。
图2
2.2查询重写器模块
Hu-Fu的查询重写器将联邦空间查询分解为多个基本算子，我们将五个联邦空间查询分为半径已知查询和半径未知查询，并解释其分解策略如下（表1）。
表1
（1）基本算子：我们的加速策略是将查询分解为基本算子，以便以明文形式限制与距离相关的操作，只留下跨筒仓的安全操作。我们提出了明文和安全两类基本算子。（i）我们定义了两个明文算子：明文范围查询和明文范围计数。这些运算符在每个筒仓Fi中执行。因此，它们可以以明文形式进行，而不会影响安全性。对于筒仓Fi，给定查询范围R，明文范围查询PRQ Fi (R)以明文形式返回R内Fi中的空间对象，而计算PRQ Fi (R)的明文范围进一步返回此类对象的数量。明文算子可以涉及空间查询中必不可少的与距离相关的操作。因为返回的结果可以在没有安全距离操作的情况下安全地收集，几乎所有空间数据库都支持它们。这些算子在Hu-Fu驱动程序中作为明文基元实现。 (ii) 基于多方安全计算技术，我们定义了三个安全算子：安全求和、安全比较和安全集合联邦。这些算子跨筒仓执行，负责从明文算子返回的本地查询结果中安全地收集结果。安全求和表示对于一个联邦F = {F1,…, Fn}，其中每个筒仓Fi包含一个数字𝛽i，该算子进行计算总和，同时避免泄漏𝛽i到Fj (𝑗≠𝑖)。
安全比较表示对于一个联邦F = {F1…, Fn}，其中每个筒仓Fi保存一个数字𝛽i和一个值𝑘，该算子比较与k，不泄露或𝛽i到任意Fj (𝑗≠𝑖)。
安全集联邦表示对于联邦F = {F1,…, Fn}，其中每个筒仓Fi包含一组空间对像， 该算子计算所有筒仓的空间对象的并集，不暴露每个o∈Si的所有权给Fj(𝑗≠𝑖)。
（2）分解半径已知查询：在五个联邦空间查询中，范围查询、范围计数和距离连接属于半径已知查询。分解计划：联邦范围查询可以分解为半径为𝑟的𝑛明文范围查询，其中每个明文范围查询从每个𝑛筒仓检索本地结果。类似地，联邦范围计数可以分解为𝑛个明文范围计数。观察一个距离连接可以被视为|𝑅||次不同查询点但半径相同的范围查询，联邦距离连接分解为半径为r的|𝑅| ×𝑛明文范围查询。对于跨筒仓的结果收集，联邦计算范围需要一个安全的总和来聚合计数，而不暴露任何筒仓的计数。对于联邦范围查询，它需要一个安全的集合联邦来组装结果，而不暴露对象的所有权。对于联邦距离连接，它首先将明文范围查询的结果在每个筒仓中进行组合，然后跨筒仓只执行一次安全集合联邦。
（3）分解半径未知查询：联邦kNN查询和kNN连接是半径未知查询,联邦kNN连接可以被视为|R|独立的联邦kNN查询。因此,我们主要解释如何分解联邦kNN查询。算法1演示了如何分解联邦kNN查询，我们初始化半径的下界(𝑙= 0)和上界(𝑢=𝑣0)，其中𝑣0可设置为区域直径或由用户自定义。然后，我们执行二分搜索，其中𝜖0是距离的精度下界，可以将其设置为位置坐标的精度。在每个迭代中,thres设置为(𝑙+𝑢)/ 2，对于当前半径thres，我们对每个筒仓执行明文范围计数，并在每个筒仓的计数之和（𝛽i）和整数𝑘之间进行安全比较。然后调整搜索半径的边界，如果总数小于𝑘，当前半径太短，我们将𝑙更新为thres, 作为新的下界。如果总数大于𝑘，这意味着有足够的点在thres中，我们将上界𝑢更新为thres。二分查找保证thres足够接近𝑘𝑡ℎ最近的距离。接着，一个明文范围查询PRQ𝐹i(𝑐𝑖𝑟𝑐𝑙𝑒(𝑝，thres))在每个筒仓上执行，我们使用安全的集合并集来获得最终结果。
图3中演示了查询点(4,4)和𝑘= 4的联邦kNN查询的执行过程，在3个筒仓中，用相同颜色标记的对象属于相同的筒仓。查询重写器将查询分解为多轮半径已知的查询。在第一轮中，以中心为(4,4)和半径为4的明文范围计数被发送到每个筒仓，并跨筒仓执行与𝑘的安全比较。得到9个比𝑘大的对象。因此在第2轮时，半径减小到2，并重新发送到筒仓进行明文范围计数和安全比较。有2个对象比𝑘小。因此，在第3轮中，半径增加到3，程序继续进行，其中范围计数结果等于𝑘，搜索结束。最后，以中心为(4,4)、半径为3的明文范围查询加上安全集合并，得到4个对象。
图3
2.3驱动程序模块
Hu-Fu的驱动程序在孤岛空间数据库之上提供接口和实现，以实现统一和高效执行查询重写器生成的分解计划。由明文基元和安全基元组成的驱动程序部署在每个筒仓上。收到分解计划后，首先在每个筒仓上执行明文算子，然后通过安全基元执行安全算子以进行结果组装。
（1）明文基元：明文基元实现明文范围查询和明文范围计数。它们作为基础空间 数据库之上的接口实现，以实现可移植性，并利用现有的范围查询和范围计数实现。明文基元的实现取决于基础空间数据库。
对于提供范围查询和范围计数的数据库,例如Simba和PostGIS, 我们直接调用相应的函数进行明文范围查询或计数。例如，在PostGIS中，可以通过调用下面的SQL来实现在筒仓Fi上中心为p、半径为r的明文范围计数
对于没有这种查询的数据库，驱动程序提供了范围查询和范围计数的默认实现。例如，GeoMesa仅提供了一个范围查询接口。因此，我们通过首先运行一个范围查询，然后计算返回集合的基数来实现范围计数。
（2）安全基元：安全基元实现安全求和、比较和集合并集，它们独立于基础空间数据库。
（3）安全求和的实现：首先，所有𝑛筒仓接受𝑛不同的公共参数𝑈={u1，u2，···，un}。然后，每个筒仓Fi选择一个随机𝑛−1多项式和计算𝑛个值的多项式,ti(u1)…,ti(un)，其中aik为筒仓Fi独立产生的随机系数，vi为筒仓Fi的局部计数结果。这些变量仅保存在Fi中，对其他人不可见。之后，每个筒仓Fi将多项式tj(uj)的值发送给所有其他Fi (i≠j)。当任何筒仓Fi从其他筒仓接收所有{ tj(uj)|i≠j}时：
（4）安全比较的实现：其主要思想是计算而不是，其中𝑋是一个随机的正实数，因为后者的结果暴露了的值。因此，我们将安全比较简化为经典的安全乘法，采用现有的安全乘法协议来保证安全性。安全乘法协议需要两个乘数𝑥和𝑦都分为𝑛股，，每一股分配到筒仓，例如:xi和yi的筒仓为Fi。该协议可以保护𝑋，𝑌，xi，yi的值免受所有𝑛筒仓中的攻击者的攻击。在我们的简化中，Y = ，于每个筒仓已经知道其本地结果，所以用户只向所有筒仓发送𝑘𝑛。之后，每个筒仓随机生成一个正实数xi，计算
然后将𝑋𝑌返回给用户。最后，用户通过𝑋𝑌的符号获得安全比较的最终结果，而不会泄露任何敏感信息。
（5）安全集联邦的实现：我们将该原语实现为基于随机份额的两阶段联邦方法。每个筒仓在第一阶段将其结果和一些假记录添加到一个全局集合中，在第二阶段将它们从集合中删除。利用差分隐私保护来减少虚假记录的数量，从而降低通信成本。观察到添加和删除假记录可以独立完成，我们将全局集合划分为允许并行执行的批。然后每个筒仓可以独立地从每个批次中添加和删除噪声数据，从而缩短延迟。
2.4查询接口模块
为了方便使用，该接口为用户提供了统一的联邦视图，并支持SQL中的联邦空间查询。
（1）统一联邦视图：Hu-Fu的查询界面为查询用户提供了联邦视图，而筒仓的详细信息是隐藏的。这使用户可以发送查询而无需关心筒仓组织，还可以保护各个筒仓的数据安全。
（2）SQL中的联邦空间查询：Hu-Fu查询接口通过扩展Calcite的SQL解析器，支持基于统一联邦视图的SQL联邦空间查询。我们添加了两个关键字:DWithin和kNN。例如，对以点𝑝为中心，半径为𝑟的圆形范围上计算联邦范围，可以用SQL编写为
SELECT COUNT (*) FROM F WHERE DWithin(p, F.location , r);
其中DWithin(𝑝，𝐹.𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛，𝑟)返回𝑝与对象𝑜∈𝐹之间的距离是否小于𝑟。对数据集𝑅和联邦𝐹与𝑘的kNN连接可以用SQL编写为
SELECT R.id, F.id FROM R JOIN F ON kNN(R.location , F.location , k);
三．实验
3.1实验设置
（1）数据集：采用了基于两个真实世界的数据集，即北京多公司空间数据、开放街道地图，其中每个空间对象都有一个位置和一个唯一的ID。
（2）评估指标：使用时间复杂度（Running time）和通信成本（Communication cost）作为评估度量。
（3）基线：本文将提出的模型与以下最先进的方法进行了比较：Public、SMCQL-GIS & SMCQL-GISext、Conclave-GIS & Conclave-GISext。
3.2实验结果
图4和表2的比较结果表明，总体而言，Hu-Fu比SMCQL-GIS和Conclave-GIS速度提高了15,814.2倍，通信开销降低了5个数量级。Hu-Fu在联邦kNN查询、kNN连接和范围计数等方面的性能比Conclave-GIS快2.4倍以上，通信开销少4.9×lower。SMCQL-GIS和Conclave-GIS在联邦范围查询和数据连接方面具有更高的效率，因为这些基线是公开的，不需要真正的代理进行安全操作。对于联邦范围查询和距离连接，Hu-Fu的效率与SMCQL-GISext和Conclave-GISext(SMCQL-GIS和Conclave-GIS的变体)相同。
图4
表2
四．总结
本文介绍了Hu-Fu，一个通过数据联邦进行高效、安全的空间查询的系统。主要使用一种新颖的查询重写器，将空间查询分解为尽可能多的明文算子和尽可能少的安全算子。特别是，我们的安全算子不涉及距离操作，并且具有比通用SMC库更快的专用实现。此外，Hu-Fu支持异构空间数据库(如PostGIS、Simba、GeoMesa和SpatialHadoop)，并支持原生SQL的查询输入。最后，通过大量实验验证了Hu-Fu算法的有效性比最先进的技术快4个数量级，通信成本低5个数量级。在未来的研究中，我们计划在Hu-Fu中支持更多的空间查询和分析，例如空间关键词搜索。
-End-

本文作者

唐永昕

重庆大学START团队成员。主要研究方向：流式轨迹数据管理。
时空艺术团队（START，Spatio-Temporal Art）来自重庆大学时空实验室，旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有2~3名研究生名额，欢迎计算机、GIS等相关专业的学生报考！

空间数据fuknn
文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论