Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
Final published version
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.
Original language | English |
---|---|
Title of host publication | Proceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM '21) |
Number of pages | 5 |
Place of publication | New York |
Publisher | Association for Computing Machinery |
Publication year | Oct 2021 |
Pages | 3083-3087 |
ISBN (electronic) | 9781450384469 |
DOIs | |
Publication status | Published - Oct 2021 |
Event | 30th ACM International Conference on Information and Knowledge Management, CIKM 2021 - Virtual, Online, Australia Duration: 1 Nov 2021 → 5 Nov 2021 |
Conference | 30th ACM International Conference on Information and Knowledge Management, CIKM 2021 |
---|---|
Land | Australia |
By | Virtual, Online |
Periode | 01/11/2021 → 05/11/2021 |
Sponsor | ACM SIGIR, ACM SIGWEB |
Publisher Copyright:
© 2021 ACM.
See relations at Aarhus University Citationformats
ID: 226898167