Data is often referred to as the new oil of the digital economy, representing a highly valuable and untapped asset. To fully realize the potential of spatial data, various spatial data marketplace platforms have emerged. The existing spatial data marketplaces primarily focus on recommending each dataset individually. There is a lack of consideration for cases where an individual dataset cannot satisfy the buyer’s needs such that a collection of datasets needs to be acquired.
To solve the problems, a research team led by Zhiyong Peng published their new research on 15 March 2026 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
The team proposed a data collection acquisition problem as the Budgeted Maximum Coverage with Connectivity Constraint (BMCC), which aims to find a set of datasets with the maximum spatial coverage under a limited budget while maintaining spatial
connectivity. Two heuristic greedy algorithms with theoretical guarantee, namely Dual-Search Algorithm (DSA) and Dual-Path Search Algorithm (DPSA), are proposed, along with two acceleration strategies.
In the research, they first propose an approximate algorithm DSA with detailed theoretical guarantees and time complexity analysis. The basic idea of DSA is to iteratively pick the dataset, which brings the maximum marginal gain w.r.t. the spatial coverage while maintaining the spatial connectivity. However, the theoretical analysis shows that the approximation ratio of DSA gradually decreases as the budget increases.
In order to address this, they propose DPSA, which iteratively selects paths (i.e., a sequence of nodes connected by edges) with the common node and the maximum marginal gain from the dataset graph. The theoretical analysis shows its better approximation in scenarios involving a larger budget. Furthermore, they also design two acceleration strategies to enhance the efficiency of DPSA significantly.
The experiments are conducted on five real-world spatial dataset collections to verify the efficiency and effectiveness of the proposed algorithms. The experimental results show that compared with the existing research methods, the proposed method can achieve up to at most 68% times larger spatial coverage with 89% times speedups. Future work can focus on exploring fairness-aware spatial data acquisition and integration tasks.
Frontiers of Computer Science
Experimental study
Not applicable
Budgeted spatial data acquisition: when coverage and connectivity matter
15-Mar-2026