Abstract
In the past a number of I/O-efficient algorithms were designed to solve a problem on a static data set. However, many data sets like social networks or web graphs change their shape frequently. We provide experimental results of the first external-memory dynamic breadth-first search (BFS) implementation based on earlier theoretical work [13] that crucially relies on a randomized clustering. We refine this approach using a new I/O-efficient deterministic clustering, which groups vertices in a level-aligned hierarchy and facilitates easy access to clusters of changing sizes during the BFS updates. In most cases the new external memory dynamic BFS implementation is significantly faster than recomputing the BFS levels after an edge insertion from scratch.
Partially supported by the DFG grant ME 3250/1-3, and by MADALGO – Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. Communications of the ACM 31(9), 1116–1127 (1988)
Ajwani, D.: Traversing large graphs in realistic setting. PhD thesis, Saarland University (2008)
Ajwani, D., Meyer, U.: Design and engineering of external memory traversal algorithms for general graphs. In: Lerner, J., Wagner, D., Zweig, K.A. (eds.) Algorithmics. LNCS, vol. 5515, pp. 1–33. Springer, Heidelberg (2009)
Ajwani, D., Meyer, U., Osipov, V.: Improved external memory BFS implementation. In: Proc. 9th ALENEX, pp. 3–12 (2007)
Arge, L.: The buffer tree: A technique for designing batched external data structures. Algorithmica 37(1), 1–24 (2003)
Arge, L., Brodal, G., Toma, L.: On external-memory MST, SSSP and multi-way planar graph separation. J. Algorithms 53(2), 186–206 (2004)
Atallah, M., Vishkin, U.: Finding euler tours in parallel. Journal of Computer and System Sciences 29(30), 330–337 (1984)
Chiang, Y.J., Goodrich, M.T., Grove, E.F., Tamasia, R., Vengroff, D.E., Vitter, J.S.: External memory graph algorithms. In: Proceedings of the 6th Annual Symposium on Discrete Algorithms (SODA), pp. 139–149. ACM-SIAM (1995)
Crescenzi, P., Grossi, R., Imbrenda, C., Lanzi, L., Marino, A.: Finding the diameter in real-world graphs – experimentally turning a lower bound into an upper bound. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol. 6346, pp. 302–313. Springer, Heidelberg (2010)
Dementiev, R., Sanders, P.: Asynchronous parallel disk sorting. In: Proc. 15th SPAA, pp. 138–148. ACM (2003)
Eppstein, D., Galil, Z., Italiano, G.: Dynamic graph algorithms. In: Atallah, M.J. (ed.) Algorithms and Theory of Computation Handbook, ch. 8. CRC Press (1999)
Mehlhorn, K., Meyer, U.: External-memory Breadth-First Search with sublinear I/O. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 723–735. Springer, Heidelberg (2002)
Meyer, U.: On dynamic Breadth-First Search in external-memory. In: 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 551–560 (2008)
Munagala, K., Ranade, A.: I/O-complexity of graph algorithms. In: Proceedings of the 10th Annual Symposium on Discrete Algorithms (SODA), pp. 687–694. ACM-SIAM (1999)
Roditty, L.: Dynamic and static algorithms for path problems in graphs. PhD thesis, Tel Aviv University (2006)
Vitter, J.S.: Algorithms and data structures for external memory. Foundations and Trends in Theoretical Computer Science 2(4), 305–474 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beckmann, A., Meyer, U., Veith, D. (2013). An Implementation of I/O-Efficient Dynamic Breadth-First Search Using Level-Aligned Hierarchical Clustering. In: Bodlaender, H.L., Italiano, G.F. (eds) Algorithms – ESA 2013. ESA 2013. Lecture Notes in Computer Science, vol 8125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40450-4_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-40450-4_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40449-8
Online ISBN: 978-3-642-40450-4
eBook Packages: Computer ScienceComputer Science (R0)