Distributed kNN query authentication

Cheng Xu*, Jianliang Xu, Koon Kau Choi

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

5 Citations (Scopus)
37 Downloads (Pure)


With the prevalence of location-based services and geo-functioned devices, the trend of spatial data outsourcing is rising. In the data outsourcing scenario, result integrity must be ensured by means of a query authentication scheme. However, most of the existing studies are confined to a centralized environment. In this paper, we investigate the query authentication problem in distributed environments and focus on the k nearest neighbor (kNN) query, which is widely used in spatial data analytics. We design a new distributed spatial authenticated data structure (ADS), distributed MR-tree, to facilitate efficient kNN processing. Furthermore, we propose a basic algorithm to process authenticated kNN queries based on the new ADS. Apart from the results, some verification objects are generated to guarantee the results' integrity. We also design two optimized algorithms to reduce the size of verification objects as well as the verification cost. Our experiments validate the good performance of the proposed techniques in terms of query cost, communication overhead, and verification time.

Original languageEnglish
Title of host publicationProceedings - 2018 IEEE 19th International Conference on Mobile Data Management, MDM 2018
Number of pages10
ISBN (Electronic)9781538641330
Publication statusPublished - 13 Jul 2018
Event19th IEEE International Conference on Mobile Data Management, MDM 2018 - Aalborg, Denmark
Duration: 26 Jun 201828 Jun 2018

Publication series

NameProceedings - IEEE International Conference on Mobile Data Management
ISSN (Print)1551-6245


Conference19th IEEE International Conference on Mobile Data Management, MDM 2018
Internet address

Scopus Subject Areas

  • Engineering(all)

User-Defined Keywords

  • Distributed Systems
  • kNN
  • Query Authentication


Dive into the research topics of 'Distributed kNN query authentication'. Together they form a unique fingerprint.

Cite this