LaGRange: Locality-aware Graph with Range Maintenance

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：122

、訪客IP：3.140.188.250

姓名

徐裕翔(Yu-Hsiang Hsu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(LaGRange: Locality-aware Graph with Range Maintenance)

相關論文

★ 重新思考虛擬記憶體管理的方式以開放通道式固態硬碟最大限度地減少深度學習推薦系統演算法的讀寫流量	★ 開啟製程相似檢查方法在組裝超級塊上以最小化額外的寫入延遲
★ LaDy: Enabling Locality-aware Deduplication Technology on Shingled Magnetic Recording Drives	★ On Minimizing Writing Overhead to Establish a Low-latency LSM-tree on Skyrmion-based Racetrack Memory
★ WABE: Rethinking B-epsilon-tree to Minimize Write-amplification on NAND Flash Memory	★ Rethinking Bϵ tree Indexing Structure over NVM with the Support of Multi-write Modes
★ Prophet’s Insight: Unleashing Deduplication System Performance in Multi-tier Storage Systems	★ Freeing the Power of High Parallelism: Accelerating the Bϵ-Tree Indexing Scheme Performance on Open-Channel SSD
★ Applying Content-Defined Chunking to OCSSD-based Deduplication Systems	★ GraLoc: Preserving Graph Locality to Minimize Read and Write Amplification on NAND Flash Memory
★ On Minimizing Writing Overhead to Establish a Low-latency LSM-tree on Skyrmion-based Racetrack Memory	★ Planting a Forest in Sky: Harnessing Parallelism in Skyrmion Racetrack Memory for Efficient Random Forest Data Placement
★ Precision versusPerformance: Optimizing Swapping Mechanisms in Multi-Mode NVM

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2027-6-1以後開放)

摘要(中)

隨著圖神經網絡（GNNs）的興起與其強大的解釋能力，對於高效存取圖
結構資料的需求重新變的重要。然而圖結構資料不規則且複雜的特性加劇了
寫入放大和讀取的延遲。儘管如此，現階段的針對圖儲存相關的研究主要集
中在靜態圖上。雖然一些研究涉及動態圖，它們討論的是在不同的時間戳下
保持該時間點下的圖，而非真正的去維護一個會隨時間而變動的單一圖資料
結構。
因此，本項研究提出了一個關注單一圖結構資料隨時間演變的局部感知
圖快閃記憶體－LaGRange的全面設計。它能夠更有效地管理圖的更新，同時
減輕寫入放大和讀取延遲。

摘要(英)

With the rise of Graph Neural Networks (GNNs), the need for efficient graph storage
has resurfaced. While retrieving data from external storage, the irregular pattern of
graph data exacerbates both write amplification and read latency. Despite this, current
research on graphs predominantly focuses on static graphs. Although some studies
address dynamic graphs, it maintains multiple versions of a graph at different
timestamps rather than a single graph evolving over time.
The study proposes Locality-aware Graph SSD with Range(LaGRange) maintenance
which focuses on a single graph that evolves over time. It’s a comprehensive design to
manage graph updates effectively, mitigating write amplification and read latency
simultaneously.

關鍵字(中)

★ 圖存取
★ 圖神經網路
★ 快閃記憶體
★ 寫入放大

關鍵字(英)

★ Graph storage
★ GNNs
★ Flash memory
★ Write amplification

論文目次

Contents
1 Introduction 1
2 Technical Background & Motivation 3
2.1 Graph Data Representation 3
2.2 Flash Translation Layer(FTL) 4
2.3 Related Work 5
2.4 Motivation 6
3 Locality-aware Graph with Range Maintenance 8
3.1 LaGRange Overview 8
3.2 Detailed Components 10
3.2.1 Update Buffer 10
3.2.2 Locality-aware Page Table 11
3.2.3 Mapping Merger 13
3.2.4 Garbage Collector 14
3.3 Overhead Analysis 15
4 Experiments 16
4.1 Environmental Settings 16
4.1.1 Graph Update 17
4.2 Evaluation Results 17
4.2.1 Write Amplification 17
4.2.2 Read Amplification 18
5 Concluding Remarks 21
Bibliography 22

參考文獻

[1] Savannah Thais et al. “Graph neural networks in particle physics: Implementa-
tions, innovations, and challenges”. In: arXiv preprint arXiv:2203.12852 (2022).
[2] Chang Li and Dan Goldwasser. “Encoding social information with graph con-
volutional networks forpolitical perspective detection in news media”. In: Pro-
ceedings of the 57th annual meeting of the association for computational linguistics.
2019, pp. 2594–2604.
[3] Aditya Pal et al. “Pinnersage: Multi-modal user embedding framework for rec-
ommendations at pinterest”. In: Proceedings of the 26th ACM SIGKDD Interna-
tional Conference on Knowledge Discovery & Data Mining. 2020, pp. 2311–2320.
[4] Rex Ying et al. “Graph convolutional neural networks for web-scale recom-
mender systems”. In: Proceedings of the 24th ACM SIGKDD international confer-
ence on knowledge discovery & data mining. 2018, pp. 974–983.
[5] Shengxiang Hu et al. “Large Language Model Meets Graph Neural Network in
Knowledge Distillation”. In: arXiv preprint arXiv:2402.05894 (2024).
[6] Thomas N Kipf and Max Welling. “Semi-supervised classification with graph
convolutional networks”. In: arXiv preprint arXiv:1609.02907 (2016).
[7] Will Hamilton, Zhitao Ying, and Jure Leskovec. “Inductive representation learn-
ing on large graphs”. In: Advances in neural information processing systems 30
(2017).
[8] Amber Huffman. NVM Express Base Specification. 2013.
[9] Kiran Kumar Matam et al. “GraphSSD: graph semantics aware SSD”. In: Pro-
ceedings of the 46th international symposium on computer architecture. 2019, pp. 116–
128.
[10] Peter Macko et al. “Llama: Efficient graph analytics using large multiversioned
arrays”. In: 2015 IEEE 31st International Conference on Data Engineering. IEEE.
2015, pp. 363–374.
[11] Miryeong Kwon et al. “{Hardware/Software}{Co-Programmable} framework
for computational {SSDs} to accelerate deep learning service on {Large-Scale}
graphs”. In: 20th USENIX Conference on File and Storage Technologies (FAST 22).
2022, pp. 147–164.
[12] Hannu Reittu and Ilkka Norros. “On the power-law random graph model of
massive data networks”. In: Performance Evaluation 55.1-2 (2004), pp. 3–23.
[13] Ryan A. Rossi and Nesreen K. Ahmed. “The Network Data Repository with
Interactive Graph Analytics and Visualization”. In: AAAI. 2015. URL: https:
//networkrepository.com.
[14] Ryan A. Rossi and Nesreen K. Ahmed. “The Network Data Repository with
Interactive Graph Analytics and Visualization”. In: AAAI. 2015. URL: https:
//networkrepository.com.
[15] Srijan Kumar et al. “Edge weight prediction in weighted signed networks”.
In: 2016 IEEE 16th international conference on data mining (ICDM). IEEE. 2016,
pp. 221–230.
[16] Srijan Kumar et al. “Rev2: Fraudulent user prediction in rating platforms”. In:
Proceedings of the Eleventh ACM International Conference on Web Search and Data
Mining. 2018, pp. 333–341.
[17] Ryan A. Rossi and Nesreen K. Ahmed. “The Network Data Repository with
Interactive Graph Analytics and Visualization”. In: AAAI. 2015. URL: https:
//networkrepository.com.
[18] Pietro Panzarasa, Tore Opsahl, and Kathleen M Carley. “Patterns and dynam-
ics of users’ behavior and interaction: Network analysis of an online commu-
nity”. In: Journal of the American Society for Information Science and Technology 60.5
(2009), pp. 911–932.

指導教授

陳增益(Tseng-Yi Chen)

審核日期

2024-7-26

推文