Large-Scale Data Retrieve in Road Networks With Optimized $k$-Retriever Routing
Bay-Yuan Hsu, Pin-Yu Chen, Chun Yi Chen · IEEE Transactions on Computational Social Systems · 2025
In recent years, artificial intelligence (AI) has emerged as a significant topic, spurring numerous novel and innovative applications leveraging AI technology. As AI relies on large-scale datasets, the collection of such data is crucial for these applications. However, large-scale data acquisition in the physical world can be both expensive and time-consuming. To address this challenge, we introduce a new computational problem called the k-data retriever problem (k-DRP), which aims to minimize the traversal length of the longest walk by a set ofkdata retrievers within a road network. We establish the NP-hardness of k-DRP and propose a constant-ratio approximation algorithm named collective search walk planning (CSP) to tackle this problem. Additionally, we enhance CSP’s efficiency through GPU acceleration and a pruning strategy. Furthermore, we observe that CSP may result in retrievers traversing more duplicate or unnecessary routes. To address these instances, we propose the weight-balance collective search walk planning (WBCSP) algorithm. Through extensive experimental evaluations, we demonstrate that our proposed CSP and WBCSP algorithms surpass other baseline methods in both solution quality and efficiency.