Indexing Points on Flash-based Solid State Drives using the xBR+-tree
DOI:
https://doi.org/10.5753/jidm.2019.1629Keywords:
flash-aware spatial index, flash memory, spatial databases, spatial indexing, xBR -treesAbstract
Spatial database systems and Geographic Information Systems have focused on exploiting the positive characteristics of flash-based Solid State Drives(SSDs) like fast reads and writes. However, designing spatial indices for SSDs, termed flash-aware spatial indices, has been a challenging task because of the intrinsic characteristics of these devices. Among existing works in the literature, FAST and eFIND distinguish themselves by proposing general approaches that can be employed to design flash-aware spatial indices. In this article, we apply these approaches to the xBR+-tree, an efficient spatial index for points. The goal is to understand how they should be adapted in order to deal with the particular properties of the xBR+-tree. As a result, we specify two novel flash-aware spatial indices for points, the eFIND xBR+-tree and the FAST xBR+-tree. We also conduct a performance evaluation to analyze their performance. As main conclusion, we point out that eFIND fits very well with the xBR+-tree, allowed the processing of the index construction to be reduced from 30.8% to 91.4%, and improved the execution of spatial queries from 22.5% to 46%.
Downloads
References
Agrawal, N., Prabhakaran, V., Wobber, T., Davis, J. D., Manasse, M., and Panigrahy, R. Design tradeoffs for SSD performance. In USENIX 2008 Annual Technical Conference. pp. 57–70, 2008.
Beckmann, N., Kriegel, H.-P., Schneider, R., and Seeger, B. The R*-tree: An efficient and robust access method for points and rectangles. In ACM SIGMOD International Conference on Management of Data. pp. 322–331, 1990.
Bouganim, L., Jónsson, B., and Bonnet, P. uFLIP: Understanding flash IO patterns. In Fourth Biennial Conference on Innovative Data Systems Research, 2009.
Brayner, A. and Monteiro Filho, J. M. Hardware-aware database systems: A new era for database technology is coming - vision paper. In Brazilian Symposium on Databases. pp. 187–192, 2016.
Carniel, A. C. Spatial indexing on flash-based solid state drives. In Proceedings of the VLDB 2018 PhD Workshop. pp. 1–4, 2018.
Carniel, A. C., Ciferri, R. R., and Ciferri, C. D. A. The performance relation of spatial indexing on hard disk drives and solid state drives. In Brazilian Symposium on GeoInformatics. pp. 263–274, 2016.
Carniel, A. C., Ciferri, R. R., and Ciferri, C. D. A. Analyzing the performance of spatial indices on hard disk drives and flash-based solid state drives. Journal of Information and Data Management 8 (1): 34–49, 2017a.
Carniel, A. C., Ciferri, R. R., and Ciferri, C. D. A. A generic and efficient framework for spatial indexing on flash-based solid state drives. In European Conference on Advances in Databases and Information Systems. pp. 229–243, 2017b.
Carniel, A. C., Ciferri, R. R., and Ciferri, C. D. A. Spatial datasets for conducting experimental evaluations of spatial indices. In Satellite Events of the Brazilian Symposium on Databases - Dataset Showcase Workshop. pp. 286–295, 2017c.
Carniel, A. C., Ciferri, R. R., and Ciferri, C. D. A. A generic and efficient framework for flash-aware spatial indexing. Information Systems vol. 82, pp. 102–120, 2019.
Carniel, A. C., Roumelis, G., Ciferri, R. R., Vassilakopoulos, M., Corral, A., and Ciferri, C. D. A. An efficient flash-aware spatial index for points. In Brazilian Symposium on GeoInformatics. pp. 68–79, 2018.
Chen, F., Koufaty, D. A., and Zhang, X. Understanding intrinsic characteristics and system implications of flash memory based solid state drives. In ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. pp. 181–192, 2009.
Denning, P. J. Working sets past and present. IEEE Transactions on Software Engineering SE-6 (1): 64–84, 1980.
Emrich, T., Graf, F., Kriegel, H.-P., Schubert, M., and Thoma, M. On the impact of flash SSDs on spatial indexing. In International Workshop on Data Management on New Hardware. pp. 3–8, 2010.
Fevgas, A., Akritidis, L., Bozanis, P., and Manolopoulos, Y. Indexing in flash storage devices: a survey on challenges, current approaches, and future trends. The VLDB Journal, 2019.
Fevgas, A. and Bozanis, P. Grid-file: Towards to a flash efficient multi-dimensional index. In International Conference on Database and Expert Systems Applications. pp. 285–294, 2015.
Folk, M. J., Zoellick, B., and Riccardi, G. File Structures: An Object-Oriented Approach with C++. Addison Wesley, 1997.
Gaede, V. and Günther, O. Multidimensional access methods. ACM Computing Surveys 30 (2): 170–231, 1998.
Hjaltason, G. R. and Samet, H. Ranking in spatial databases. In International Symposium on Spatial Databases. pp. 83–95, 1995.
Jin, P., Xie, X., Wang, N., and Yue, L. Optimizing R-tree for flash memory. Expert Systems with Applications 42 (10): 4676–4686, 2015.
Johnson, T. and Shasha, D. 2Q: A low overhead high performance buffer management replacement algorithm. In International Conference on Very Large Databases. pp. 439–450, 1994.
Jung, M. and Kandemir, M. Revisiting widely held SSD expectations and rethinking system-level implications. In ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. pp. 203–216,
Koltsidas, I. and Viglas, S. D. Data management over flash memory. In ACM SIGMOD International Conference on Management of Data. pp. 1209–1212, 2011a.
Koltsidas, I. and Viglas, S. D. Spatial data management over flash memory. In International Conference on Advances in Spatial and Temporal Databases. pp. 449–453, 2011b.
Li, G., Zhao, P., Yuan, L., and Gao, S. Efficient implementation of a multi-dimensional index structure over flash memory storage systems. The Journal of Supercomputing 64 (3): 1055–1074, 2013.
Lin, S., Zeinalipour-Yazti, D., Kalogeraki, V., Gunopulos, D., and Najjar, W. A. Efficient indexing data structures for flash-based sensor devices. ACM Transactions on Storage 2 (4): 468–503, 2006.
Mittal, S. and Vetter, J. S. A survey of software techniques for using non-volatile memories for storage and main memory systems. IEEE Transactions on Parallel and Distributed Systems 27 (5): 1537–1550, 2016.
Nievergelt, J., Hinterberger, H., and Sevcik, K. C. The grid file: An adaptable, symmetric multikey file structure. ACM Transactions on Database Systems 9 (1): 38–71, 1984.
Oosterom, P. V. a. N. Spatial Access Methods. In Geographical Information Systems: Principles, Techniques, Management and Applications, 2nd Edition ed., P. A. Longley, M. F. Goodchild, D. J. Maguire, and D. W. Rhind (Eds.). pp. 385–400, 2005.
Rigaux, P., Scholl, M., and Voisard, A. Spatial databases: with application to GIS. Morgan Kaufmann, 2001.
Robinson, J. T. The K-D-B-tree: a search structure for large multidimensional dynamic indexes. In ACM SIGMOD International Conference on Management of Data. pp. 10–18, 1981.
Roumelis, G., Fevgas, A., Vassilakopoulos, M., Corral, A., Bozanis, P., and Manolopoulos, Y. Bulk-loading and bulk-insertion algorithms for xBR+-trees in solid state drives. Computing, 2019.
Roumelis, G., Vassilakopoulos, M., Corral, A., Fevgas, A., and Manolopoulos, Y. Spatial batch-queries processing using xBR+-trees in solid-state drives. In International Conference on Model and Data Engineering. pp. 301–317, 2018.
Roumelis, G., Vassilakopoulos, M., Corral, A., and Manolopoulos, Y. Efficient query processing on large spatial databases: A performance study. Journal of Systems and Software vol. 132, pp. 165–185, 2017.
Roumelis, G., Vassilakopoulos, M., Loukopoulos, T., Corral, A., and Manolopoulos, Y. The xBR+-tree: an efficient access method for points. In International Conference on Database and Expert Systems Applications. pp. 43–58, 2015.
Samet, H. The quadtree and related hierarchical data structures. ACM Computing Surveys 16 (2): 187–260, 1984.
Sarwat, M., Mokbel, M. F., Zhou, X., and Nath, S. FAST: A generic framework for flash-aware spatial trees. In International Conference on Advances in Spatial and Temporal Databases. pp. 149–167, 2011.
Sarwat, M., Mokbel, M. F., Zhou, X., and Nath, S. Generic and efficient framework for search trees on flash memory storage systems. GeoInformatica 17 (3): 417–448, 2013.
Sellis, T. K., Roussopoulos, N., and Faloutsos, C. The R+-Tree: A dynamic index for multi-dimensional objects. In International Conference on Very Large Databases. pp. 507–518, 1987.
Silva, F. A., Domingues, A. C. S. A., and Silva, T. R. M. B. Discovering mobile application usage patterns from a large-scale dataset. ACM Transactions on Knowledge Discovery from Data 12 (5): 59:1–59:36, 2018.
Wu, C.-H., Chang, L.-P., and Kuo, T.-W. An efficient R-tree implementation over flash-memory storage systems. In ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. pp. 17–24, 2003.
