A Unified Multi-Core Strategy for Optimised Traversal of Large-Scale Structured Data
Abstract
The exponential growth in structured data across scientific, business, and real-time domains demands efficient traversal techniques capable of handling vast, complex datasets. Traditional sequential methods fail to scale, resulting in increased latency and limited throughput. This paper presents a scalable multicore traversal algorithm that leverages fine-grained parallelism combined with topology-aware partitioning and dynamic work-stealing scheduling to evenly distribute workloads while minimising synchronisation overhead and cache inefficiencies. Experiments conducted on diverse real-world datasets, including large social graphs, citation networks, synthetic dense graphs, and hierarchical structures, demonstrate that the proposed approach achieves an over 40% reduction in execution time compared to leading parallel BFS methods. Furthermore, the algorithm exhibits near-linear scalability up to 32 cores, improved load-balancing efficiency (~0.91) over existing methods, and significantly reduced cache miss rates. These results establish the algorithm's practical suitability for both commodity and high-performance computing environments. By integrating architectural awareness into parallel traversal design, this work advances scalable data processing and real-time analytics across multiple domains, including social network analysis, healthcare, and scientific research.
References
D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Boston, MA, USA: Addison-Wesley, 1997.
S. Beamer, K. Asanović, and D. A. Patterson, “Direction-optimizing breadth-first search,” Scientific Programming, vol. 21, nos. 3–4, pp. 137–148, 2012.
J. Kepner and J. Gilbert, Graph Algorithms in the Language of Linear Algebra. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics (SIAM), 2011.
V. Agarwal, A. Buluç, and K. Madduri, “A comparative study of parallel breadth-first search algorithms on distributed memory systems,” in Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), Atlanta, GA, USA, 2010.
J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani, “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,” Internet Mathematics, vol. 6, no. 1, pp. 29–123, 2009.
G. Malewicz et al., “Pregel: A system for large-scale graph processing,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, Indianapolis, IN, USA, 2010, pp. 135–146.
M. Zaharia et al., “Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing,” in Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI), San Jose, CA, USA, 2012.
P. Harish and P. J. Narayanan, “Accelerating large graph algorithms on the GPU using CUDA,” in Proceedings of the International Conference on High Performance Computing (HiPC), Goa, India, 2007.
D. Merrill, M. Garland, and A. Grimshaw, “Scalable GPU graph traversal,” in Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), New Orleans, LA, 2012.
G. Senthilkumar and R. Naveenkumar, “Efficient energy management in wireless sensor networks based on optimized explicit feature interaction aware graph neural network,” Peer-to-Peer Networking and Applications, vol. 18, Art. no. 115, Mar. 2025.
R. Kolikipogu et al., “Improving food safety by IoT-based climate monitoring and control systems for food processing plants,” Remote Sensing in Earth Systems Sciences, Jan. 2025.
S. M. Padmaja et al., “Deep Learning in Remote Sensing for Climate-Induced Disaster Resilience: A Comprehensive Interdisciplinary Approach,” Remote Sensing in Earth Systems Sciences, vol. 8, no. 1, pp. 145–160, Dec. 2024.
N. Kalavani et al., “Evaluating the performance of machine learning models in cancer prediction through ROC and PRC metrics,” Nano NTP, vol. 20, S16, Nov. 2024.
G. Vani et al., “Advancing predictive data analytics in IoT and AI leveraging real-time data for proactive operations and system resilience,” Nano NTP, vol. 20, S16, Nov. 2024.
S. Bhadra, A. Goon, R. Naveenkumar, S. Roy, et al., “Fortifying the Resilience and Integrity of Cyber-Physical Systems through Meticulous Assessment,” Nano NTP, Vol. 20, S16 (2024).
N. Kalavani, R. Naveenkumar, S. Bhattacharjee, R. Sarkar, and N. Kumar, “Evaluating the Performance of Machine Learning Models in Cancer Prediction Through ROC and PRC Metrics,” Nano NTP, Vol. 20, S16, Nov. 2024.
G. Vani, R. Naveenkumar, R. Singha, R. Sarkar, and N. Kumar, “Advancing Predictive Data Analytics in IoT and AI Leveraging Real-time Data for Proactive Operations and System Resilience,” Nano NTP, Vol. 20, S16, Nov. 2024.
R. Naveenkumar, V. Joshi, B. Pramanik, R. Sarkar, “Enhancing the Effectiveness of Zero-R and One-R Algorithms in Data Classification,” Asian Journal of Biological and Life Sciences, Vol. 6, No. 14, pp. 11255–11272, Oct. 2024.
A. Thakuri, S. Visalakshi, C. K, V. H. Krishnan, N. B, R. Naveenkumar, “An Empirical Approach to Fuzzy Logic System in Risk Assessment for Decision-Making,” Asian Journal of Biological and Life Sciences, Vol. 6, No. 12, 2024.
