2025/07/17 by Xiaolong Wan, Xixian Han, Wan, Xiaolong +1
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2507.12925
openalex publication_date 2025/07/17 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
Breadth-first search (BFS) is known as a basic search strategy for learning graph properties. As the scales of graph databases have increased tremendously in recent years, large-scale graphs G are often disk-resident. Obtaining the BFS results of G in semi-external memory model is inevitable, because the in-memory BFS algorithm has to maintain the entire G in the main memory, and external BFS algorithms consume high computational costs. As a good trade-off between the internal and external memory models, semi-external memory model assumes that the main memory can at least reside a spanning tree of G. Nevertheless, the semi-external BFS problem is still an open issue due to its difficulty. Therefore, this paper presents a comprehensive study for processing BFS in semi-external memory model. After discussing the naive solutions based on the basic framework of semi-external graph algorithms, this paper presents an efficient algorithm, named EP-BFS, with a small minimum memory space requirement, which is an important factor for evaluating semi-external algorithms. Extensive experiments are conducted on both real and synthetic large-scale graphs, where graph WDC-2014 contains over 1.7 billion nodes, and graph eu-2015 has over 91 billion edges. Experimental results confirm that EP-BFS can achieve up to 10 times faster.