Efficient approximate range aggregation over large-scale spatial data federation
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...
Saved in:
Main Authors: | , , , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2023
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/6383 https://ink.library.smu.edu.sg/context/sis_research/article/7386/viewcontent/tkde21_shi__1_.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-7386 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-73862024-03-06T01:58:13Z Efficient approximate range aggregation over large-scale spatial data federation SHI, Yexuan TONG, Yongxin ZENG, Yuxiang ZHOU, Zimu DING, Bolin CHEN, Lei 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%. 2023-01-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/6383 info:doi/10.1109/TKDE.2021.3084141 https://ink.library.smu.edu.sg/context/sis_research/article/7386/viewcontent/tkde21_shi__1_.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Spatial Data Federation Range Aggregation Sampling Databases and Information Systems Numerical Analysis and Scientific Computing |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Spatial Data Federation Range Aggregation Sampling Databases and Information Systems Numerical Analysis and Scientific Computing |
spellingShingle |
Spatial Data Federation Range Aggregation Sampling Databases and Information Systems Numerical Analysis and Scientific Computing SHI, Yexuan TONG, Yongxin ZENG, Yuxiang ZHOU, Zimu DING, Bolin CHEN, Lei Efficient approximate range aggregation over large-scale spatial data federation |
description |
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%. |
format |
text |
author |
SHI, Yexuan TONG, Yongxin ZENG, Yuxiang ZHOU, Zimu DING, Bolin CHEN, Lei |
author_facet |
SHI, Yexuan TONG, Yongxin ZENG, Yuxiang ZHOU, Zimu DING, Bolin CHEN, Lei |
author_sort |
SHI, Yexuan |
title |
Efficient approximate range aggregation over large-scale spatial data federation |
title_short |
Efficient approximate range aggregation over large-scale spatial data federation |
title_full |
Efficient approximate range aggregation over large-scale spatial data federation |
title_fullStr |
Efficient approximate range aggregation over large-scale spatial data federation |
title_full_unstemmed |
Efficient approximate range aggregation over large-scale spatial data federation |
title_sort |
efficient approximate range aggregation over large-scale spatial data federation |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2023 |
url |
https://ink.library.smu.edu.sg/sis_research/6383 https://ink.library.smu.edu.sg/context/sis_research/article/7386/viewcontent/tkde21_shi__1_.pdf |
_version_ |
1794549747878461440 |