Thesis
PM-RTREE: A HIGH-EFFICIENT CRASH-CONSISTENT R-TREE FOR PERSISTENT MEMORY
Washington State University
Master of Science (MS), Washington State University
01/2022
DOI:
https://doi.org/10.7273/000004489
Handle:
https://hdl.handle.net/2376/124521
Abstract
Persistent R-trees are important data structures for indexing large-scale spatial datasetsusing persistent memory (e.g., Intel Optane DIMMs). Existing persistent R-trees (e.g., FBR-tree) suffer from four major issues. (1) Node updates cause unnecessary writes to persistent memory, leading to high latency. (2) The locking overhead is high under high thread concurrency. (3) They support a limited number of maximum bounding rectangles on each node. (4) The persistent overhead of managing its bitmaps in persistent memory is high for repeatedly cache line reflushing. In this paper, we propose a novel data structure Persistent Merged R-tree (PM-Rtree) for high-efficient insert, delete, and search operations for high-dimensional datasets using persistent memory. It is a partitioned data structure where its non-leaf nodes are stored in DRAM and leaf nodes are stored in persistent memory. In addition, we use an interleaved mapping approach to reduce cache line reflushes. Finally, it supports lock-free insertion using persistent multi-word compare and swap operations to eliminate locking overhead. Our experimental results show that PM-Rtree reduces the latency of insertion and search compared to the state-of-the-art persistent R-trees while maintaining crash consistency.
Metrics
4 File views/ downloads
34 Record Views
Details
- Title
- PM-RTREE
- Creators
- Brandon Lavinsky
- Contributors
- Xuechen Zhang (Advisor)Xinghui Zhao (Committee Member)Benjamin McCamish (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Engineering and Computer Science (VANC), School of
- Theses and Dissertations
- Master of Science (MS), Washington State University
- Publisher
- Washington State University
- Number of pages
- 50
- Identifiers
- 99900882139301842
- Language
- English
- Resource Type
- Thesis