Large-Scale Data Retrieve in Road Networks With Optimized $k$-Retriever Routing

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 (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-DRP), which aims to minimize the traversal length of the longest walk by a set of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> data 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.