Publication Type

Journal Article

Version

acceptedVersion

Publication Date

1-2023

Abstract

Range aggregation is a primitive operation in spatial data applications and there is a growing demand to support such operations over a data federation, where the entire spatial data are separately held by multiple data providers (a.k.a., data silos). Data federations notably increase the amount of data available for data-intensive applications such as smart mobility planning and public health emergency responses. Yet they also challenge the conventional implementation of range aggregation queries because the raw data cannot be shared within the federation and the data partition at each data silo is fixed during query processing. These constraints limit the design space of distributed range aggregation query processing. In this work, we propose approximate algorithms for efficient range aggregation over spatial data federation. We devise novel single-silo sampling algorithms that process queries in parallel and design a level sampling based algorithm which reduces the time complexity of local queries at each data silo to O(log 1/), where is the approximation ratio of the accuracy guarantee. Extensive evaluations with real-world data show that compared with state-of-the-arts, our solutions reduce the time cost and communication cost by up to 85.1x and 5.5x respectively, with average approximate errors of below 2.8%.

Keywords

Spatial Data Federation, Range Aggregation, Sampling

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Software and Cyber-Physical Systems

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

35

Issue

1

First Page

418

Last Page

430

ISSN

1041-4347

Identifier

10.1109/TKDE.2021.3084141

Publisher

Institute of Electrical and Electronics Engineers

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/TKDE.2021.3084141

Download

Share

COinS