Abstract
Flash-based SSDs have become well established in the storage market, replacing magnetic disks in both enterprise and consumer computer systems. The performance characteristics of these new devices have prompted a considerable amount of research that aims at developing efficient data access methods. Early works attempted to reduce the expensive random writes, exploiting logging and batch write techniques, while more recent ones addressed query processing, taking advantage of the high internal parallelism of SSDs. 3D XPoint is a new nonvolatile memory technology that has emerged recently, featuring smaller access times and higher durability compared with flash. It is available both as block addressable secondary storage and as byte addressable persistent main memory. However, the high cost of 3D XPoint prevents, for the moment, its adoption in large scales. This renders hybrid storage systems utilizing NAND flash and 3D XPoint a sufficient alternative. In this work, we propose HyR-tree, a hybrid variant of R-tree that persists a part of the tree in the high performing 3D XPoint storage. HyR-tree identifies repeated access pattern to the data and uses these patterns to locate the most important nodes. The importance of a node is determined by the performance gain that derives from its placement within a 3D XPoint-based device. We experimentally evaluated HyR-tree using real devices and four different datasets. The acquired results show that our proposal achieves significant performance gains up to 40% in tree construction and up to 56% in range queries.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Afshani P, Arge L, Larsen KD (2009) Orthogonal range reporting in three and higher dimensions. In: Proceedings of the 50th annual IEEE symposium on foundations of computer science, pp 149–158
Beckmann N, Kriegel HP, Schneider R, Seeger B (1990) The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD international conference on management of data, pp 322–331
Bozanis P, Nanopoulos A, Manolopoulos Y (2003) LR-tree: a logarithmic decomposable spatial index method. Comput J 46(3):319–331
Canim M, Mihaila GA, Bhattacharjee B, Ross KA, Lang CA (2009) An object placement advisor for DB2 using solid state storage. Proc VLDB Endow 2(2):1318–1329
Canim M, Mihaila GA, Bhattacharjee B, Ross KA, Lang CA (2010) SSD bufferpool extensions for database systems. Proc VLDB Endow 3(1–2):1435–1446
Carniel AC, Ciferri RR, Ciferri CD (2018) A generic and efficient framework for flash-aware spatial indexing. Inf Syst 52:102–120
Chen F, Hou B, Lee R (2016) Internal parallelism of flash memory-based solid-state drives. ACM Trans Storage 12(3):13
Fevgas A, Akritidis L, Alamaniotis M, Tsompanopoulou P, Bozanis P (2019) A study of R-tree performance in hybrid Flash/3D XPoint storage. In: Proceedings of the 10th international conference on information, intelligence, systems and applications (IISA), pp 1–6
Fevgas A, Akritidis L, Bozanis P, Manolopoulos Y (2020) Indexing in flash storage devices: a survey on challenges, current approaches, and future trends. VLDB J 29(1):273–311
Fevgas A, Bozanis P (2019) LB-Grid: an SSD efficient grid file. Data Knowl Eng 121:18–41. https://doi.org/10.1016/j.datak.2019.04.002
Fevgas A, Bozanis P (2019) A spatial index for hybrid storage. In: Proceedings of the 23rd international database applications and engineering symposium, pp 1–8
Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD international conference on management of data, pp 47–57
Hady FT, Foong A, Veal B, Williams D (2017) Platform storage performance with 3D XPoint technology. Proc IEEE 105(9):1822–1833
Hu Y, Jiang H, Feng D, Tian L, Luo H, Zhang S (2011) Performance impact and interplay of SSD parallelism through advanced commands, allocation strategy and data granularity. In: Proceedings of the 25th international conference on supercomputing, pp 96–107
Izraelevitz J, Yang J, Zhang L, Kim J, Liu X, Memaripour A, Soh YJ, Wang Z, Xu Y, Dulloor SR, et al (2019) Basic performance measurements of the intel optane DC persistent memory module. arXiv:1903.05714
Jin P, Yang P, Yue L (2015) Optimizing B+-Tree for hybrid storage systems. Distrib Parallel Databases 33(3):449–475
Kamel I, Faloutsos C (1994) Hilbert R-tree: an improved R-tree using fractals. In: Proceedings of the 20th international conference on very large data bases, pp 500–509
Koltsidas I, Hsu V (2017) IBM storage and NVM express revolution. Technical reports, IBM
Korda N, Szorenyi B, Li S (2016) Distributed clustering of linear bandits in peer to peer networks. In: Proceedings of The 33rd international conference on machine learning, pp 1301–1309
Kourtis K, Ioannou N, Koltsidas I (2019) Reaping the performance of fast NVM storage with uDepot. In: Proceedings of the 17th USENIX conference on file and storage technologies, pp 1–15. Boston, MA
Li S (2016) The art of clustering bandits. Ph.D. Thesis, Università degli Studi dell’Insubria
Li S, Karatzoglou A, Gentile C (2016) Collaborative filtering bandits. In: Proceedings of the 39th international ACM SIGIR conference on research and development in information retrieval, pp 539–548
Lin S, Zeinalipour-Yazti D, Kalogeraki V, Gunopulos D, Najjar WA (2006) Efficient indexing data structures for flash-based sensor devices. ACM Trans Storage 2(4):468–503
Liu X, Salem K (2013) Hybrid storage management for database systems. Proc VLDB Endow 6(8):541–552
Mahadik K, Wu Q, Li S, Sabne A (2020) Fast distributed bandits for online recommendation systems. In: Proceedings of the 34th ACM international conference on supercomputing, pp 1–13
Manolopoulos Y, Nanopoulos A, Papadopoulos AN, Theodoridis Y (2010) R-trees: theory and applications. Springer, Berlin
Micheloni R (2016) 3D flash memories. Springer, Berlin
Niu J, Xu J, Xie L (2018) Hybrid storage systems: a survey of architectures and algorithms. IEEE Access 6:13385–13406
Roh H, Park S, Kim S, Shin M, Lee SW (2011) B+-tree index optimization by exploiting internal parallelism of flash-based solid state drives. Proc VLDB Endow 5(4):286–297
Roh H, Park S, Shin M, Lee SW (2014) MPSearch: multi-path search for tree-based indexes to exploit internal parallelism of flash SSDs. IEEE Data Eng Bull 37(2):3–11
Roumelis G, Vassilakopoulos M, Corral A, Fevgas A, Manolopoulos Y (2018) Spatial batch-queries processing using xBR+-trees in solid-state drives. In: Proceedings of the 8th international conference on model and data engineering, pp 301–317
Roussopoulos N, Kotidis Y, Roussopoulos M (1997) Cubetree: organization of and bulk incremental updates on the data cube. ACM SIGMOD Record 26(2):89–99
Samet H (1990) Applications of spatial data structures: Computer graphics, image processing, and GIS. Addison-Wesley Longman Publishing Co., Inc., USA
Schubert E, Zimek A, Kriegel HP (2013) Geodetic distance queries on R-trees for indexing geographic data. In: Proceedings of the 16th international symposium on spatial and temporal databases, pp 146–164
Sellis T, Roussopoulos N, Faloutsos C (1987) The R+-tree: a dynamic index for multi-dimensional objects. In: Proceedings of the 13th VLDB conference, pp 507–518
Tao Y, Papadias D (2001) Efficient historical R-trees. In: Proceedings of the 13th international conference on scientific and statistical database management, pp 223–232
Vengroff DE, Vitter JS (1996) Efficient 3-D range searching in external memory. In: Proceedings of the 28th annual ACM symposium on theory of computing, pp 192–201
Vietri G, Rodriguez LV, Martinez WA, Lyons S, Liu J, Rangaswami R, Zhao M, Narasimhan G (2018) Driving cache replacement with ml-based lecar. In: 10th \(\{\)USENIX\(\}\) workshop on hot topics in storage and file systems (HotStorage 18)
Wu CH, Chang LP, Kuo TW (2003) An efficient R-tree implementation over flash-memory storage systems. In: Proceedings of the 11th ACM international symposium on advances in geographic information systems, pp 17–24
Wu CH, Huang CW, Chang CY (2019) A data management method for databases using hybrid storage systems. ACM SIGAPP Appl Comput Rev 19(1):34–47
Wu CH, Kuo TW, Chang LP (2007) An efficient B-tree layer implementation for flash-memory storage systems. ACM Trans Embed Comput Syst 6(3):19
Wu Y, Park K, Sen R, Kroth B, Do J (2020) Lessons learned from the early performance evaluation of intel optane dc persistent memory in dbms. In: Proceedings of the 16th international workshop on data management on new hardware, DaMoN ’20. Association for Computing Machinery, New York. https://doi.org/10.1145/3399666.3399898
Xu J, Swanson S (2016) NOVA: a log-structured file system for hybrid volatile/non-volatile main memories. In: 14th USENIX conference on file and storage technologies (FAST 16). USENIX Association, Santa Clara, pp 323–338. https://www.usenix.org/conference/fast16/technical-sessions/presentation/xu
Yang J, Lilja DJ (2018) Reducing relational database performance bottlenecks using 3D XPoint storage technology. In: Proceedings of the 17th IEEE international conference on trust, security and privacy in computing and communications and 12th IEEE international conference on big data science and engineering, pp 1804–1808
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Fevgas, A., Akritidis, L., Alamaniotis, M. et al. HyR-tree: a spatial index for hybrid flash/3D XPoint storage. Neural Comput & Applic 35, 133–145 (2023). https://doi.org/10.1007/s00521-021-05804-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00521-021-05804-2