Distributed Join Query Method for Large-Scale Spatial Data Streams

LI Zuolin; XIANG Longgang; YU Liebing; WU Huayi; GUAN Xuefeng

doi:10.13203/j.whugis20230040

您当前的位置：

首页 >

文章列表页 >

Distributed Join Query Method for Large-Scale Spatial Data Streams

Cartography and GIS | 更新时间：2026-11-05

- Distributed Join Query Method for Large-Scale Spatial Data Streams
- Geomatics and Information Science of Wuhan University Vol. 50, Issue 5, Pages: 1017-1028(2025)
- 作者机构：
  
  武汉大学测绘遥感信息工程全国重点实验室，湖北武汉，430079
- 作者简介：
- 基金信息：
- DOI：10.13203/j.whugis20230040
  CLC： P208
- Received：02 August 2023，
  
  Published：05 May 2025
- 稿件说明：
移动端阅览
李柞霖,向隆刚,余列冰，等.面向大规模空间数据流的分布式连接查询方法[J].武汉大学学报（信息科学版）,2025,50(5):1017-1028.

LI Zuolin,XIANG Longgang,YU Liebing,et al.Distributed Join Query Method for Large-Scale Spatial Data Streams[J].Geomatics and Information Science of Wuhan University,2025,50(5):1017-1028.
李柞霖,向隆刚,余列冰，等.面向大规模空间数据流的分布式连接查询方法[J].武汉大学学报（信息科学版）,2025,50(5):1017-1028. DOI：10.13203/j.whugis20230040

LI Zuolin,XIANG Longgang,YU Liebing,et al.Distributed Join Query Method for Large-Scale Spatial Data Streams[J].Geomatics and Information Science of Wuhan University,2025,50(5):1017-1028. DOI：10.13203/j.whugis20230040

摘要

空间连接查询是处理和分析空间数据的基础操作之一。随着空间数据的爆发式增长，针对海量空间数据的连接查询技术备受瞩目。面向大规模历史数据的空间连接查询已被广泛研究，而受限于数据流的高速接入率与连接的实时性需求，目前面向数据流的分布式空间连接查询仍充满挑战。为此，面向大规模空间数据流设计了一种分布式连接查询处理框架。首先形式化定义了针对空间数据流连接查询处理问题，按照参与连接的数据形态细分为“流-表”和“流-流”两类连接，然后分析了分布式连接场景的共性问题，设计了全局网格分区-局部空间索引的两层处理框架，以支持空间流的分布式连接。在此基础上，针对不同连接场景分别设计了适应的连接策略：对于“流-表”连接，提出了基于两级R-tree拓扑关系判断优化算法；对于“流-流”连接，设计了一种顾及分区边界的数据冗余路由算法，以保证分区边界数据的正确连接。此外，针对间隔时间语义的缓存需求，提出了兼顾状态管理与检索效率的BinR-tree结构。大量实验结果表明，所提出的空间数据连接方法具有良好的线性加速比，且相对于基线方法，连接查询效率得到了显著提升。

Abstract

Objectives

Spatial join query is one of the basic operations for processing and analyzing spatial data. With the explosive growth of spatial data

join query technology for massive spatial data has attracted much attention. Although the existing research work has explored the join query of spatial data streams

it is still in its infancy. The processing of join query processing of spatial data streams is still insufficient in terms of systematization and universality. It is urgent to explore how to define general spatial data streams connect query problems and provide systematic solutions.

Methods

After fully excavating the common real-time spatial data processing problems behind various practical application scenarios

this paper refers to the processing theory and methods of spatial data in the batch processing field

and considers the characteristics of long-term continuous operation of stream processing

and formalizes the problem of spatial data stream connection. Two types of connection operators are defined

including “stream-table” connection and “stream-stream” connection. On this basis

a two-layer data index structure of global grid partition and local spatial index is proposed to support spatial stream supports distributed connection. For the “stream-table” connection

this paper proposes two physical realization methods of spatial dimension tables

and designs a two-level R-tree-based topology relationship judgment optimization for the memory-based storage algorithm. For “stream-stream” connection

We propose a partition boundary data redundancy algorithm to correctly implement cross-partition joins of partition boundary data. In addition

for the caching requirements of interval time semantics

a BinR-tree result that takes into account both management and retrieval efficiency is proposed.

Results

(1) The “stream-table” spatial connection implemented in this paper can achieve a throughput of more than 60 000 under a single degree of parallelism

and the average overall delay is about 90 milliseconds. Compared with the native method

the average throughput is 9 times Boost

latency is reduced by an average of 20 milliseconds. (2) Same as the “stream-table” connection

the performance of the “stream-stream” connection method in this paper improves steadily with the increase of parallelism

and has good horizontal scalability. (3) In the experimental comparison between window connection and interval connection

with the window increases

the connection latency increases

much higher than the stream interval connection. This part of the experiment also shows that the stream interval connection without bounded time semantics is more suitable for stream processing logic. (4) Mesh division has little effect on throughput

and its main function is to balance the load and ensure the spatial proximity of data. (5) When the bin size is smaller than the window size

the query will span multiple BinR-tree

which will affect the query efficiency. Properly increasing the bin size will improve the query efficiency; when the bin size is greater than or equal to the time interval

the query efficiency will not be greatly improved.

Conclusions

A large number of experimental results show that the spatial data connection method proposed in this paper has a good linear speedup ratio

and compared with the baseline method

the connection query efficiency has been significantly improved.

关键词

Keywords

references

孙大为，张广艳，郑纬民 . 大数据流式计算：关键技术及系统实例［J］. 软件学报， 2014 ， 25 （ 4 ）： 839 - 862 .

SUN Dawei ， ZHANG Guangyan ， ZHENG Weimin . Big Data Stream Computing： Technologies and Instances ［J］. Journal of Software ， 2014 ， 25 （ 4 ）： 839 - 862 .

朱建军，宋迎春，胡俊，等 . 测绘大数据时代数据处理理论面临的挑战与发展［J］. 武汉大学学报（信息科学版）， 2021 ， 46 （ 7 ）： 1025 - 1031 .

ZHU Jianjun ， SONG Yingchun ， HU Jun ， et al . Challenges and Development of Data Processing Theory in the Era of Surveying and Mapping Big Data ［J］. Geomatics and Information Science of Wuhan University ， 2021 ， 46 （ 7 ）： 1025 - 1031 .

李军，刘举庆，赵学胜，等 . 地理格网模型支持下的轨迹数据管理与分析框架：方法与应用［J］. 武汉大学学报（信息科学版）， 2021 ， 46 （ 5 ）： 640 - 649 .

LI Jun ， LIU Juqing ， ZHAO Xuesheng ， et al . Trajectory Data Management and Analysis Framework Based on Geographical Grid Model： Method and Application ［J］. Geomatics and Information Science of Wuhan University ， 2021 ， 46 （ 5 ）： 640 - 649 .

陈栋，张翔，陈能成 . 智慧城市感知基站：未来智慧城市的综合感知基础设施［J］. 武汉大学学报（信息科学版）， 2022 ， 47 （ 2 ）： 159 - 180 .

CHEN Dong ， ZHANG Xiang ， CHEN Nengcheng . Smart City Awareness Base Station： A Prospective Integrated Sensing Infrastructure for Future Cities ［J］. Geomatics and Information Science of Wuhan University ， 2022 ， 47 （ 2 ）： 159 - 180 .

仇阿根 . 基于分布式内存计算的空间数据近似查询处理方法［D］. 武汉：武汉大学， 2017 .

QIU Agen . In-Memory Distributed Computing Based Approximate Query Processing on Spatial Data ［D］. Wuhan ： Wuhan University ， 2017 .

盛宇裕，毕硕本，范京津，等 . 运用交通运行状况指标分析交通热点时空模式［J］. 武汉大学学报（信息科学版）， 2021 ， 46 （ 5 ）： 746 - 754 .

SHENG Yuyu ， BI Shuoben ， FAN Jingjin ， et al . Analyzing Spatiotemporal Patterns of Traffic Hotspots Using Traffic Operation Indicators ［J］. Geomatics and Information Science of Wuhan University ， 2021 ， 46 （ 5 ）： 746 - 754 .

TAYLOR R W ， SHAPIRO L D . Join Processing in Database Systems with Large Main Memories ［J］. ACM Transactions on Database Systems ， 1986 ， 11 （ 3 ）： 239 - 264 .

AJI A ， WANG F S ， VO H ， et al . Hadoop-GIS： A High Performance Spatial Data Warehousing System over MapReduce ［J］. Proceedings of the VLDB Endowment International Conference on Very Large Data Bases ， 2013 ， 6 （ 11 ）： 1009 .

ELDAWY A ， MOKBEL M F . SpatialHadoop： A MapReduce Framework for Spatial Data ［C］// IEEE 31st International Conference on Data Engineering ， Seoul， Republic of Korea ， 2015 .

YOU S M ， ZHANG J T ， GRUENWALD L . Large-Scale Spatial Join Query Processing in Cloud ［C］// IEEE 31st International Conference on Data Engineering ， Seoul， Republic of Korea ， 2015 .

YU J ， WU J ， SARWAt M . GeoSpark： A Cluster Computing Framework for Processing Large-Scale Spatial Data ［C］// The 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems ， Seattle，Washington D C，USA， 2015 .

YU J ， ZHANG Z S ， SARWAT M . Spatial Data Management in Apache Spark： The GeoSpark Perspective and Beyond ［J］. GeoInformatica ， 2019 ， 23 （ 1 ）： 37 - 78 .

XIE D ， LI F F ， YAO B ， et al . Simba： Efficient In-Memory Spatial Analytics ［C］// International Conference on Management of Data ， San Francisco， California， USA， 2016 .

TANG M J ， YU Y Y ， MALLUHI Q M ， et al . LocationSpark：A Distributed In-Memory Data Management System for Big Spatial Data ［J］. Proceedings of the VLDB Endowment ， 2016 ， 9 （ 13 ）： 1565 - 1568 .

PANDEY V ， KIPF A ， NEUMANN T ， et al . How Good Are Modern Spatial Analytics Systems？［J］. Proceedings of the VLDB Endowment ， 2018 ， 11 ： 1661 - 1673 .

SHAHVARANI A ， JACOBSEN H A . Distributed Stream K NN Join ［C］// International Conference on Management of Data ， Virtual Event China ， 2021 .

ZHANG F ， ZHENG Y ， XU D P ， et al . Real-Time Spatial Queries for Moving Objects Using Storm Topology ［J］. ISPRS International Journal of Geo-Information ， 2016 ， 5 （ 10 ）： 178 .

GALIĆ Z ， MEŠKOVIĆ E ， OSMANOVIĆ D . Distributed Processing of Big Mobility Data as Spatiotemporal Data Streams ［J］. GeoInformatica ， 2017 ， 21 （ 2 ）： 263 - 291 .

SHAIKH S A ， MARIAM K ， KITAGAWA H ， et al . GeoFlink： A Distributed and Scalable Framework for the Real-Time Processing of Spatial Streams ［C］// The 29th ACM International Conference on Information & Knowledge Management ， Virtual Event Ireland ， 2020 .

SHAIKH S A ， KITAGAWA H ， MATONO A ， et al . GeoFlink： An Efficient and Scalable Spatial Data Stream Management System ［J］. IEEE Access ， 2022 ， 10 ： 24909 - 24935 .

SHEKHAR S ， XIONG H . Encyclopedia of GIS ［M］. USA ： Springer Publishing Company ， 2007 .

KIMBALL R ， ROSS M . The Data Warehouse Toolkit：The Definitive Guide to Dimensional Modeling ［M］. 3rd ed . New York ： Wiley ， 1996 .

TIAN R J ， ZHAI H W ， ZHANG W S ， et al . A Survey of Spatiotemporal Big Data Indexing Methods in Distributed Environment ［J］. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing ， 2022 ， 15 ： 4132 - 4155 .

HUGHES J N ， ANNEX A ， EICHELBERGER C N ， et al . GeoMesa： A Distributed Architecture for Spatio-temporal Fusion ［C］//Geospatial Informatics， Fusion， and Motion Video Analytics V， Baltimore， Maryland， USA ， 2015 .

FOLEY J D ， VAN F D ， VAN Dam A ， et al . Computer Graphics Principles and Practice in C ［M］. Massachusetts ： Addison-Wesley Professional ， 1996 .

YUAN J ， ZHENG Y ， ZHANG C Y ， et al . T-Drive ［C］// The 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems ， San Jose， California， USA， 2010 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

VA-HBase： An Adaptive Distributed Management Scheme for Vector Data

Research Progress in Spatiotemporal Modeling， Analysis， and Prediction of Urban Activity Flows in Built Environment

Development and Prospects of Spaceborne Greenhouse Gas LiDAR Technology

A Framework for Evaluating Geospatial Cognitive Abilities of Multimodal Large Language Models for Brain-Inspired Spatial Intelligence

Three-State Fusion Support Problem of Marine Geographic Information for Ship Navigation

Related Author

SHEN Dannan

GUAN Xuefeng

HAN Linxu

XIANG Longgang

WU Huayi

Related Institution

State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University

AI问答

⁰