PCR*-tree: PCM-aware R*-tree

Elkhan Jabarov; Myong Soon Park; Byung Won On; Gyu Sang Choi

doi:10.6688/JISE.2017.33.5.15

PCR-tree: PCM-aware R-tree

Elkhan Jabarov, Myong Soon Park, Byung Won On, Gyu Sang Choi

* Honorary professors

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

Phase change memory (PCM) is a byte-addressable type of non-volatile memory. Compared to other volatile and non-volatile memories, PCM is two to four times denser than dynamic random access memory (DRAM). It has better read latency than NAND flash memory. Even though the write endurance of PCM is 10 times better than NAND flash memory, it is still limited to 10⁶ times per PCM cell. Decreasing and balancing the number of writes among PCM cells can solve the endurance problem and, where possible, keep PCM cells usable. Our objective is to design a PCR*-tree – a novel PCM-aware R*-tree that can store spatial data. Initially, we examine how R*-tree causes endurance problems in PCM, and then, we optimize it for PCM. Furthermore, the performance of R*-tree is very poor, especially for insertion, which needs to be solved since it will be used for in-memory databases. According to our experimental results, when the benchmark dataset is used, PCR*-tree dramatically reduced the number of write operations to PCM in average 30 times and also improve the performance in terms of processing time. These results suggest our new method outperforms existing ones for the PCM endurance problem, as well as in its performance.

Original language	English
Pages (from-to)	1359-1374
Number of pages	16
Journal	Journal of Information Science and Engineering
Volume	33
Issue number	5
DOIs	https://doi.org/10.6688/JISE.2017.33.5.15
Publication status	Published - 2017 Sept

Bibliographical note

Funding Information:
This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT, and Future Planning (2013-012524) for the third author (Byung-Won On) and supported by the Ministry of Trade, Industry and Energy (MOTIE, Korea) under Industrial Technology Innovation Program No. 10063130 and by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2016R1A2B4007498) for the fourth author (Gyu Sang Choi).

Publisher Copyright:
© 2017 Institute of Information Science. All Rights Reserved.

Keywords

Endurance
In-memory databases
PCM
R*-tree
R-tree
Spatial tree

ASJC Scopus subject areas

Software
Human-Computer Interaction
Hardware and Architecture
Library and Information Sciences
Computational Theory and Mathematics

Access to Document

10.6688/JISE.2017.33.5.15

Cite this

@article{9c4179754dfe46b9a156876f867d7756,

title = "PCR*-tree: PCM-aware R*-tree",

abstract = "Phase change memory (PCM) is a byte-addressable type of non-volatile memory. Compared to other volatile and non-volatile memories, PCM is two to four times denser than dynamic random access memory (DRAM). It has better read latency than NAND flash memory. Even though the write endurance of PCM is 10 times better than NAND flash memory, it is still limited to 106 times per PCM cell. Decreasing and balancing the number of writes among PCM cells can solve the endurance problem and, where possible, keep PCM cells usable. Our objective is to design a PCR*-tree – a novel PCM-aware R*-tree that can store spatial data. Initially, we examine how R*-tree causes endurance problems in PCM, and then, we optimize it for PCM. Furthermore, the performance of R*-tree is very poor, especially for insertion, which needs to be solved since it will be used for in-memory databases. According to our experimental results, when the benchmark dataset is used, PCR*-tree dramatically reduced the number of write operations to PCM in average 30 times and also improve the performance in terms of processing time. These results suggest our new method outperforms existing ones for the PCM endurance problem, as well as in its performance.",

keywords = "Endurance, In-memory databases, PCM, R*-tree, R-tree, Spatial tree",

author = "Elkhan Jabarov and Park, {Myong Soon} and On, {Byung Won} and Choi, {Gyu Sang}",

note = "Funding Information: This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT, and Future Planning (2013-012524) for the third author (Byung-Won On) and supported by the Ministry of Trade, Industry and Energy (MOTIE, Korea) under Industrial Technology Innovation Program No. 10063130 and by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2016R1A2B4007498) for the fourth author (Gyu Sang Choi). Publisher Copyright: {\textcopyright} 2017 Institute of Information Science. All Rights Reserved.",

year = "2017",

month = sep,

doi = "10.6688/JISE.2017.33.5.15",

language = "English",

volume = "33",

pages = "1359--1374",

journal = "Journal of Information Science and Engineering",

issn = "1016-2364",

publisher = "Institute of Information Science",

number = "5",

}

TY - JOUR

T1 - PCR*-tree

T2 - PCM-aware R*-tree

AU - Jabarov, Elkhan

AU - Park, Myong Soon

AU - On, Byung Won

AU - Choi, Gyu Sang

N1 - Funding Information: This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT, and Future Planning (2013-012524) for the third author (Byung-Won On) and supported by the Ministry of Trade, Industry and Energy (MOTIE, Korea) under Industrial Technology Innovation Program No. 10063130 and by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2016R1A2B4007498) for the fourth author (Gyu Sang Choi). Publisher Copyright: © 2017 Institute of Information Science. All Rights Reserved.

PY - 2017/9

Y1 - 2017/9

N2 - Phase change memory (PCM) is a byte-addressable type of non-volatile memory. Compared to other volatile and non-volatile memories, PCM is two to four times denser than dynamic random access memory (DRAM). It has better read latency than NAND flash memory. Even though the write endurance of PCM is 10 times better than NAND flash memory, it is still limited to 106 times per PCM cell. Decreasing and balancing the number of writes among PCM cells can solve the endurance problem and, where possible, keep PCM cells usable. Our objective is to design a PCR*-tree – a novel PCM-aware R*-tree that can store spatial data. Initially, we examine how R*-tree causes endurance problems in PCM, and then, we optimize it for PCM. Furthermore, the performance of R*-tree is very poor, especially for insertion, which needs to be solved since it will be used for in-memory databases. According to our experimental results, when the benchmark dataset is used, PCR*-tree dramatically reduced the number of write operations to PCM in average 30 times and also improve the performance in terms of processing time. These results suggest our new method outperforms existing ones for the PCM endurance problem, as well as in its performance.

AB - Phase change memory (PCM) is a byte-addressable type of non-volatile memory. Compared to other volatile and non-volatile memories, PCM is two to four times denser than dynamic random access memory (DRAM). It has better read latency than NAND flash memory. Even though the write endurance of PCM is 10 times better than NAND flash memory, it is still limited to 106 times per PCM cell. Decreasing and balancing the number of writes among PCM cells can solve the endurance problem and, where possible, keep PCM cells usable. Our objective is to design a PCR*-tree – a novel PCM-aware R*-tree that can store spatial data. Initially, we examine how R*-tree causes endurance problems in PCM, and then, we optimize it for PCM. Furthermore, the performance of R*-tree is very poor, especially for insertion, which needs to be solved since it will be used for in-memory databases. According to our experimental results, when the benchmark dataset is used, PCR*-tree dramatically reduced the number of write operations to PCM in average 30 times and also improve the performance in terms of processing time. These results suggest our new method outperforms existing ones for the PCM endurance problem, as well as in its performance.

KW - Endurance

KW - In-memory databases

KW - PCM

KW - R-tree

KW - Spatial tree

UR - http://www.scopus.com/inward/record.url?scp=85049908473&partnerID=8YFLogxK

U2 - 10.6688/JISE.2017.33.5.15

DO - 10.6688/JISE.2017.33.5.15

M3 - Article

AN - SCOPUS:85049908473

SN - 1016-2364

VL - 33

SP - 1359

EP - 1374

JO - Journal of Information Science and Engineering

JF - Journal of Information Science and Engineering

IS - 5

ER -