Aarhus University Seal

Centerpoint Query Authentication

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


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 languageEnglish
Title of host publicationProceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM '21)
Number of pages5
Place of publicationNew York
PublisherAssociation for Computing Machinery
Publication yearOct 2021
ISBN (electronic)9781450384469
Publication statusPublished - Oct 2021
Event30th ACM International Conference on Information and Knowledge Management, CIKM 2021 - Virtual, Online, Australia
Duration: 1 Nov 20215 Nov 2021


Conference30th ACM International Conference on Information and Knowledge Management, CIKM 2021
ByVirtual, Online

Bibliographical note

Publisher Copyright:
© 2021 ACM.

    Research areas

  • centerpoint query, query authentication

See relations at Aarhus University Citationformats

ID: 226898167