圖形重新排序中的攤銷成本：BFS Ordering 分析 | Publication

Publications-Theses

Article View/Open

pdf(3)

Publication Export

Google Scholar^TM

題名	圖形重新排序中的攤銷成本：BFS Ordering 分析 Amortized Cost in Graph Reordering: Analysis of BFS Ordering
作者	李尚霖 Li, Shang-Lin
貢獻者	郭桐惟 Kuo, Tung-Wei 李尚霖 Li, Shang-Lin
關鍵詞	圖形重新排序圖形理論演算法 Graph Reordering Graph Theory Algorithm
日期	2025
上傳時間	4-Aug-2025 13:57:45 (UTC+8)
摘要	圖形重新排序透過調整節點的排列方式來提升資料存取效率，但尋找最佳排序方式是一個 NP-困難問題。為了解決此問題，研究人員提出多種啟發式方法，包括能提升效能的 Gorder，以及能降低重新排序開銷的基於度數的 DBG。本研究以攤銷成本（amortized cost）評估圖形重新排序的實用性，衡量圖形應用需執行多少次，才能攤銷重新排序所帶來的時間成本。過往研究多著重於比較 Gorder 與 RCM 的加速效能，卻忽略了與 BFS Ordering 相關的攤銷成本分析。本研究以 12 個真實世界圖形與 5 種常見圖形應用進行實驗，結果顯示 BFS Ordering 在加速效果與重新排序時間之間達成良好平衡。此外，我們亦透過隨機圖模型，分析不同圖形參數如何影響 BFS Ordering 的表現。 Graph reordering improves data access efficiency by adjusting vertex arrangements, but finding the optimal ordering is NP-hard. To address this, researchers have proposed several heuristic methods. One is Gorder, which boosts performance, and another is degree-based DBG ordering, which minimizes reordering overhead. This study evaluates the practical applicability of graph reordering using amortized cost. Measures how many times a graph application needs to run to offset the cost of reordering. Previous studies mainly compared acceleration performance with Gorder and RCM but overlooked amortized cost in relation to BFS ordering. We evaluate our approach using 12 real-world graphs and five common graph applications, showing that BFS ordering strikes a good balance between acceleration and reordering time. Additionally, we use random graph models to analyze how various graph parameters affect BFS ordering performance.
參考文獻	[1] M. Valiyev, “Graph storage: How good is csr really?,” dated Dec, vol. 10, p. 8, 2017. [2] E. Cuthill and J. McKee, “Reducing the bandwidth of sparse symmetric matrices,” in Proceedings of the 1969 24th national conference, pp. 157–172, 1969. [3] A. George and J. W. Liu, Computer solution of large sparse positive definite. Prentice Hall Professional Technical Reference, 1981. [4] H. Wei, J. X. Yu, C. Lu, and X. Lin, “Speedup graph processing by graph ordering,” in Proceedings of the 2016 International Conference on Management of Data, pp. 1813–1828, 2016. [5] V. Balaji and B. Lucia, “When is graph reordering an optimization? Studying the effect of lightweight graph reordering across applications and input graphs,” in 2018 IEEE International Symposium on Workload Characterization (IISWC), pp. 203–214, IEEE, 2018. [6] Y. Zhang, V. Kiriansky, C. Mendis, M. Zaharia, and S. Amarasinghe, “Optimizing cache performance for graph analytics,” arXiv preprint arXiv:1608.01362, 2016. [7] P. Faldu, J. Diamond, and B. Grot, “A closer look at lightweight graph reordering,” in 2019 IEEE International Symposium on Workload Characterization (IISWC), pp. 1–13, IEEE, 2019. [8] J. Kunegis, “KONECT – The Koblenz Network Collection,” in Proc. Int. Conf. on World Wide Web Companion, pp. 1343–1350, 2013. [9] J. Shun and G. E. Blelloch, “Ligra: A lightweight graph processing framework for shared memory,” in Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 135–146, 2013. [10] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998. [11] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. [12] P. Holme and B. J. Kim, “Growing scale-free networks with tunable clustering,” Physical Review E, vol. 65, no. 2, p. 026107, 2002. [13] P. Erdős and A. Rényi, “On random graphs I,” Publ. Math. Debrecen, vol. 6, pp. 290–297, 1959. [14] E. N. Gilbert, “Random graphs,” The Annals of Mathematical Statistics, vol. 30, no. 4, pp. 1141–1144, 1959. [15] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, no. 1, p. 47, 2002. [16] NetworkX, "https://networkx.org", 2025. [17] M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew, “Optimistic parallelism requires abstractions,” in Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 211–222, 2007. [18] Y. Zhang, V. Kiriansky, C. Mendis, S. Amarasinghe, and M. Zaharia, “Making caches work for graph analytics,” in 2017 IEEE International Conference on Big Data (Big Data), pp. 293–302, IEEE, 2017. [19] Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein, “GraphLab: A new parallel framework for machine learning,” in Conference on Uncertainty in Artificial Intelligence (UAI), vol. 20, 2010. [20] J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin, “PowerGraph: Distributed Graph-Parallel computation on natural graphs,” in 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), pp. 17–30, 2012. [21] A. Kyrola, G. Blelloch, and C. Guestrin, “GraphChi: Large-Scale graph computation on just a PC,” in 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), pp. 31–46, 2012. [22] D. Nguyen, A. Lenharth, and K. Pingali, “A lightweight infrastructure for graph analytics,” in Proceedings of the 24th ACM Symposium on Operating Systems Principles, pp. 456–471, 2013. [23] N. Sundaram, N. R. Satish, M. M. A. Patwary, S. R. Dulloor, S. G. Vadlamudi, D. Das, and P. Dubey, “GraphMat: High performance graph analytics made productive,” arXiv preprint arXiv:1503.07241, 2015. [24] G. Karypis and V. Kumar, “Multilevel k-way partitioning scheme for irregular graphs,” Journal of Parallel and Distributed Computing, vol. 48, no. 1, pp. 96–129, 1998. [25] I. Stanton and G. Kliot, “Streaming graph partitioning for large distributed graphs,” in Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1222–1230, 2012. [26] G. Karypis and V. Kumar, “Multilevel graph partitioning schemes,” in ICPP (3), pp. 113–122, 1995. [27] J. Banerjee, W. Kim, S.-J. Kim, and J. F. Garza, “Clustering a DAG for CAD databases,” IEEE Transactions on Software Engineering, vol. 14, no. 11, pp. 1684–1699, 1988. [28] Y. Lim, U. Kang, and C. Faloutsos, “SlashBurn: Graph compression and mining beyond caveman communities,” IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 12, pp. 3077–3089, 2014. [29] K. I. Karantasis, A. Lenharth, D. Nguyen, M. J. Garzaran, and K. Pingali, “Parallelization of reordering algorithms for bandwidth and wavefront reduction,” in SC’14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 921–932, IEEE, 2014. [30] J. Arai, H. Shiokawa, T. Yamamuro, M. Onizuka, and S. Iwamura, “Rabbit Order: Just-in-time parallel reordering for fast graph analysis,” in 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 22–31, IEEE, 2016. [31] K. Lakhotia, S. Singapura, R. Kannan, and V. Prasanna, “RECALL: Reordered cache-aware locality-based graph processing,” in 2017 IEEE 24th International Conference on High Performance Computing (HiPC), pp. 273–282, IEEE, 2017. [32] Q. Lyu, M. Sha, B. Gong, and K. Lyu, “Accelerating depth-first traversal by graph ordering,” in Proceedings of the 33rd International Conference on Scientific and Statistical Database Management, pp. 13–24, 2021. [33] M. Drescher, M. A. Awad, S. D. Porumbescu, and J. D. Owens, “BOBA: A parallel lightweight graph reordering algorithm with heavyweight implications,” arXiv preprint arXiv:2306.10410, 2023. [34] K. Wang, X. Lin, L. Qin, W. Zhang, and Y. Zhang, “Vertex priority based butterfly counting for large-scale bipartite networks,” PVLDB, 2019. [35] E. Lee, J. Kim, K. Lim, S. H. Noh, and J. Seo, “Pre-Select static caching and neighborhood ordering for BFS-like algorithms on disk-based graph engines,” in 2019 USENIX Annual Technical Conference (USENIX ATC 19), pp. 459–474, 2019. [36] B. Coleman, S. Segarra, A. J. Smola, and A. Shrivastava, “Graph reordering for cache-efficient near neighbor search,” Advances in Neural Information Processing Systems, vol. 35, pp. 38488–38500, 2022. [37] O. Green, “Inverse-deletion BFS: Revisiting static graph BFS traversals with dynamic graph operations,” in 2021 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–7, 2021. [38] F. Ziche, N. Bombieri, F. Busato, and R. Giugno, “GPU-accelerated BFS for dynamic networks,” in European Conference on Parallel Processing, pp. 74–87, Springer, 2024.
描述	碩士國立政治大學資訊科學系 111753165
資料來源	http://thesis.lib.nccu.edu.tw/record/#G0111753165
資料類型	thesis

dc.contributor.advisor	郭桐惟	zh_TW
dc.contributor.advisor	Kuo, Tung-Wei	en_US
dc.contributor.author (Authors)	李尚霖	zh_TW
dc.contributor.author (Authors)	Li, Shang-Lin	en_US
dc.creator (作者)	李尚霖	zh_TW
dc.creator (作者)	Li, Shang-Lin	en_US
dc.date (日期)	2025	en_US
dc.date.accessioned	4-Aug-2025 13:57:45 (UTC+8)	-
dc.date.available	4-Aug-2025 13:57:45 (UTC+8)	-
dc.date.issued (上傳時間)	4-Aug-2025 13:57:45 (UTC+8)	-
dc.identifier (Other Identifiers)	G0111753165	en_US
dc.identifier.uri (URI)	https://nccur.lib.nccu.edu.tw/handle/140.119/158475	-
dc.description (描述)	碩士	zh_TW
dc.description (描述)	國立政治大學	zh_TW
dc.description (描述)	資訊科學系	zh_TW
dc.description (描述)	111753165	zh_TW
dc.description.abstract (摘要)	圖形重新排序透過調整節點的排列方式來提升資料存取效率，但尋找最佳排序方式是一個 NP-困難問題。為了解決此問題，研究人員提出多種啟發式方法，包括能提升效能的 Gorder，以及能降低重新排序開銷的基於度數的 DBG。本研究以攤銷成本（amortized cost）評估圖形重新排序的實用性，衡量圖形應用需執行多少次，才能攤銷重新排序所帶來的時間成本。過往研究多著重於比較 Gorder 與 RCM 的加速效能，卻忽略了與 BFS Ordering 相關的攤銷成本分析。本研究以 12 個真實世界圖形與 5 種常見圖形應用進行實驗，結果顯示 BFS Ordering 在加速效果與重新排序時間之間達成良好平衡。此外，我們亦透過隨機圖模型，分析不同圖形參數如何影響 BFS Ordering 的表現。	zh_TW
dc.description.abstract (摘要)	Graph reordering improves data access efficiency by adjusting vertex arrangements, but finding the optimal ordering is NP-hard. To address this, researchers have proposed several heuristic methods. One is Gorder, which boosts performance, and another is degree-based DBG ordering, which minimizes reordering overhead. This study evaluates the practical applicability of graph reordering using amortized cost. Measures how many times a graph application needs to run to offset the cost of reordering. Previous studies mainly compared acceleration performance with Gorder and RCM but overlooked amortized cost in relation to BFS ordering. We evaluate our approach using 12 real-world graphs and five common graph applications, showing that BFS ordering strikes a good balance between acceleration and reordering time. Additionally, we use random graph models to analyze how various graph parameters affect BFS ordering performance.	en_US
dc.description.tableofcontents	摘要 i Abstract ii 誌謝 iii Contents iv List of Figures vii List of Tables ix 1 Introduction 1 2 Background 8 2.1 CSR 8 2.2 Previous Graph Reordering Algorithm 9 2.3 Amortized Cost for Graph Reordering 12 2.4 Random Graph Model 13 2.4.1 Watts-Strogatz Model 13 2.4.2 Barabási-Albert Model 14 2.4.3 Powerlaw Cluster Model 14 3 BFS Ordering 16 3.1 Motivation 16 3.1.1 Reordering Time of Gorder is Excessive 16 3.1.2 RCM Involves Redundant Operations 17 3.1.3 Degree-Based Methods Provide Insufficient Acceleration 18 3.2 BFS Ordering 18 3.3 Time Complexity 22 4 Experiments 24 4.1 Experimental Setup 24 4.1.1 Graph Datasets 25 4.1.2 Graph Applications 28 4.1.3 Comparison Methods 31 4.2 Speedup of Graph Reordering on Real Graphs 31 4.2.1 Analysis of Results 31 4.2.2 Speedup Analysis for Connected Components 34 4.2.3 Speedup Analysis for Maximum Independent Set 38 4.3 The Effect of Random Graph Properties on Graph Reordering Speedup 41 4.3.1 Watts-Strogatz Graph Speedup Results 42 4.3.2 Barabási-Albert Graph Speedup Results 45 4.3.3 Powerlaw Cluster Graph Speedup Results 45 4.4 Amortized Cost 49 4.4.1 Reordering Time Cost 49 4.4.2 Amortized Cost for Real Graph 50 4.4.3 Amortized Cost for Random Graph 54 4.5 Summary 54 5 Related Work 57 5.1 Software Frameworks for Graph Applications 57 5.2 Graph Partition 58 5.3 Other Graph Reordering Methods 59 6 Conclusion and Future Work 61 Reference 62	zh_TW
dc.format.extent	1655000 bytes	-
dc.format.mimetype	application/pdf	-
dc.source.uri (資料來源)	http://thesis.lib.nccu.edu.tw/record/#G0111753165	en_US
dc.subject (關鍵詞)	圖形重新排序	zh_TW
dc.subject (關鍵詞)	圖形理論	zh_TW
dc.subject (關鍵詞)	演算法	zh_TW
dc.subject (關鍵詞)	Graph Reordering	en_US
dc.subject (關鍵詞)	Graph Theory	en_US
dc.subject (關鍵詞)	Algorithm	en_US
dc.title (題名)	圖形重新排序中的攤銷成本：BFS Ordering 分析	zh_TW
dc.title (題名)	Amortized Cost in Graph Reordering: Analysis of BFS Ordering	en_US
dc.type (資料類型)	thesis	en_US
dc.relation.reference (參考文獻)	[1] M. Valiyev, “Graph storage: How good is csr really?,” dated Dec, vol. 10, p. 8, 2017. [2] E. Cuthill and J. McKee, “Reducing the bandwidth of sparse symmetric matrices,” in Proceedings of the 1969 24th national conference, pp. 157–172, 1969. [3] A. George and J. W. Liu, Computer solution of large sparse positive definite. Prentice Hall Professional Technical Reference, 1981. [4] H. Wei, J. X. Yu, C. Lu, and X. Lin, “Speedup graph processing by graph ordering,” in Proceedings of the 2016 International Conference on Management of Data, pp. 1813–1828, 2016. [5] V. Balaji and B. Lucia, “When is graph reordering an optimization? Studying the effect of lightweight graph reordering across applications and input graphs,” in 2018 IEEE International Symposium on Workload Characterization (IISWC), pp. 203–214, IEEE, 2018. [6] Y. Zhang, V. Kiriansky, C. Mendis, M. Zaharia, and S. Amarasinghe, “Optimizing cache performance for graph analytics,” arXiv preprint arXiv:1608.01362, 2016. [7] P. Faldu, J. Diamond, and B. Grot, “A closer look at lightweight graph reordering,” in 2019 IEEE International Symposium on Workload Characterization (IISWC), pp. 1–13, IEEE, 2019. [8] J. Kunegis, “KONECT – The Koblenz Network Collection,” in Proc. Int. Conf. on World Wide Web Companion, pp. 1343–1350, 2013. [9] J. Shun and G. E. Blelloch, “Ligra: A lightweight graph processing framework for shared memory,” in Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 135–146, 2013. [10] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998. [11] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. [12] P. Holme and B. J. Kim, “Growing scale-free networks with tunable clustering,” Physical Review E, vol. 65, no. 2, p. 026107, 2002. [13] P. Erdős and A. Rényi, “On random graphs I,” Publ. Math. Debrecen, vol. 6, pp. 290–297, 1959. [14] E. N. Gilbert, “Random graphs,” The Annals of Mathematical Statistics, vol. 30, no. 4, pp. 1141–1144, 1959. [15] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, no. 1, p. 47, 2002. [16] NetworkX, "https://networkx.org", 2025. [17] M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew, “Optimistic parallelism requires abstractions,” in Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 211–222, 2007. [18] Y. Zhang, V. Kiriansky, C. Mendis, S. Amarasinghe, and M. Zaharia, “Making caches work for graph analytics,” in 2017 IEEE International Conference on Big Data (Big Data), pp. 293–302, IEEE, 2017. [19] Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein, “GraphLab: A new parallel framework for machine learning,” in Conference on Uncertainty in Artificial Intelligence (UAI), vol. 20, 2010. [20] J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin, “PowerGraph: Distributed Graph-Parallel computation on natural graphs,” in 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), pp. 17–30, 2012. [21] A. Kyrola, G. Blelloch, and C. Guestrin, “GraphChi: Large-Scale graph computation on just a PC,” in 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), pp. 31–46, 2012. [22] D. Nguyen, A. Lenharth, and K. Pingali, “A lightweight infrastructure for graph analytics,” in Proceedings of the 24th ACM Symposium on Operating Systems Principles, pp. 456–471, 2013. [23] N. Sundaram, N. R. Satish, M. M. A. Patwary, S. R. Dulloor, S. G. Vadlamudi, D. Das, and P. Dubey, “GraphMat: High performance graph analytics made productive,” arXiv preprint arXiv:1503.07241, 2015. [24] G. Karypis and V. Kumar, “Multilevel k-way partitioning scheme for irregular graphs,” Journal of Parallel and Distributed Computing, vol. 48, no. 1, pp. 96–129, 1998. [25] I. Stanton and G. Kliot, “Streaming graph partitioning for large distributed graphs,” in Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1222–1230, 2012. [26] G. Karypis and V. Kumar, “Multilevel graph partitioning schemes,” in ICPP (3), pp. 113–122, 1995. [27] J. Banerjee, W. Kim, S.-J. Kim, and J. F. Garza, “Clustering a DAG for CAD databases,” IEEE Transactions on Software Engineering, vol. 14, no. 11, pp. 1684–1699, 1988. [28] Y. Lim, U. Kang, and C. Faloutsos, “SlashBurn: Graph compression and mining beyond caveman communities,” IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 12, pp. 3077–3089, 2014. [29] K. I. Karantasis, A. Lenharth, D. Nguyen, M. J. Garzaran, and K. Pingali, “Parallelization of reordering algorithms for bandwidth and wavefront reduction,” in SC’14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 921–932, IEEE, 2014. [30] J. Arai, H. Shiokawa, T. Yamamuro, M. Onizuka, and S. Iwamura, “Rabbit Order: Just-in-time parallel reordering for fast graph analysis,” in 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 22–31, IEEE, 2016. [31] K. Lakhotia, S. Singapura, R. Kannan, and V. Prasanna, “RECALL: Reordered cache-aware locality-based graph processing,” in 2017 IEEE 24th International Conference on High Performance Computing (HiPC), pp. 273–282, IEEE, 2017. [32] Q. Lyu, M. Sha, B. Gong, and K. Lyu, “Accelerating depth-first traversal by graph ordering,” in Proceedings of the 33rd International Conference on Scientific and Statistical Database Management, pp. 13–24, 2021. [33] M. Drescher, M. A. Awad, S. D. Porumbescu, and J. D. Owens, “BOBA: A parallel lightweight graph reordering algorithm with heavyweight implications,” arXiv preprint arXiv:2306.10410, 2023. [34] K. Wang, X. Lin, L. Qin, W. Zhang, and Y. Zhang, “Vertex priority based butterfly counting for large-scale bipartite networks,” PVLDB, 2019. [35] E. Lee, J. Kim, K. Lim, S. H. Noh, and J. Seo, “Pre-Select static caching and neighborhood ordering for BFS-like algorithms on disk-based graph engines,” in 2019 USENIX Annual Technical Conference (USENIX ATC 19), pp. 459–474, 2019. [36] B. Coleman, S. Segarra, A. J. Smola, and A. Shrivastava, “Graph reordering for cache-efficient near neighbor search,” Advances in Neural Information Processing Systems, vol. 35, pp. 38488–38500, 2022. [37] O. Green, “Inverse-deletion BFS: Revisiting static graph BFS traversals with dynamic graph operations,” in 2021 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–7, 2021. [38] F. Ziche, N. Bombieri, F. Busato, and R. Giugno, “GPU-accelerated BFS for dynamic networks,” in European Conference on Parallel Processing, pp. 74–87, Springer, 2024.	zh_TW

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

Google Scholar^TM