Centerpoint Query Authentication
Centerpoint Query Authentication
复制标题
中心点查询认证
DOI：
10.1145/3459637.3482072
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Panagiotis Karras
中科院分区：
文献类型：
--
作者：
Magnus Haxen;Morten Raeburn;P. Afshani;Panagiotis Karras
在线地图服务的兴起促使数据所有者将空间数据外包给可能不受信任的数据库提供商。查询结果沿着允许确认其真实性的验证对象。这样的认证方案已被提出了几个空间和几何查询，以及在一个维度的中位数查询。然而，到目前为止，没有认证机制存在的中心点查询，返回一个点躺在中间的其他点在多维空间。在本文中，我们提出了一个认证方案的中心点查询，接地上的有限平面点集和认证的聚合R-树和伴随认证的聚合查询的中心点查询的算法。我们还提供了用于找到完整数据集的子集的中心点的方法，并实现了基于范围的方法。我们的解决方案有一个最坏情况下的时间复杂度为O（n log n）和空间复杂度为O（n）。我们的实验研究证实了这些说法。
The rise of online map services drives data owners to outsource spatial data to potentially untrusted database providers. Query results are provided along with verification objects that allow confirming their authenticity. Such authentication schemes have been proposed for several spatial and geometric queries, as well as for median queries in one dimension. However, to date, no authentication mechanism exists for centerpoint queries, which return a point lying in the middle of other points in multidimensional space. In this paper, we propose an authentication scheme for centerpoint queries, grounded on the algorithm for centerpoint queries on a finite planar set of points and authenticated aggregation R-trees and accompanying authenticated aggregation queries. We also provide methods for finding the centerpoint of a subset of the complete data set, and implement a range-based method. Our solution has a worst-case time-complexity of O(n log n) and space-complexity of O(n). Our experimental study confirms these claims.