Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
GeoInformatica
Published in: GeoInformatica 1/2022

13-12-2021

Porting disk-based spatial index structures to flash-based solid state drives

Authors: Anderson Chaves Carniel, George Roumelis, Ricardo R. Ciferri, Michael Vassilakopoulos, Antonio Corral, Cristina D. Aguiar

Published in: GeoInformatica | Issue 1/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Indexing data on flash-based Solid State Drives (SSDs) is an important paradigm recently applied in spatial data management. During last years, the design of new spatial access methods for SSDs, named flash-aware spatial indices, has attracted the attention of many researchers, mainly to exploit the advantages of SSDs in spatial query processing. eFIND is a generic framework for transforming a disk-based spatial index into a flash-aware one, taking into account the intrinsic characteristics of SSDs. In this article, we present a systematic approach for porting disk-based data-driven and space-driven access methods to SSDs, through the eFIND framework. We also present the actual porting of representatives data-driven (R-trees, R*-trees, and Hilbert R-trees) and space-driven (xBR+-trees) access methods through this framework. Moreover, we present an extensive experimental evaluation that compares the performance of these ported indices when inserting and querying synthetic and real point datasets. The main conclusions of this experimental study are that the eFIND R-tree excels in insertions, the eFIND xBR+-tree is the fastest for different types of spatial queries, and the eFIND Hilbert R-tree is efficient for processing intersection range queries.
previous article Temporal aggregation bias and Gerrymandering urban time series

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Gaede V, Günther O (1998) Multidimensional access methods. ACM Comp Surveys 30(2):170–231CrossRef
2.
Rigaux P, Scholl M, Voisard A (2001) Spatial databases: with application to GIS, 1st edn. Morgan Kaufmann, Burlington
3.
Oosterom PVaN (2005) Spatial Access Methods. In: Longley PA, Goodchild MF, Maguire DJ, Rhind DW (eds) Geographical Information Systems: Principles, Techniques, Management and Applications. 2nd edn., pp 385–400
4.
Guttman A (1984) R-trees: A dynamic index structure for spatial searching. In: ACM SIGMOD Int. Conf. on Management of Data, pp 47–57
5.
Beckmann N, Kriegel H-P, Schneider R, Seeger B (1990) The R*-tree: An efficient and robust access method for points and rectangles. In: ACM SIGMOD Int. Conf. on Management of Data, pp 322–331
6.
Kamel I, Faloutsos C (1994) Hilbert R-tree: An improved R-tree using fractals. In: In: Int. Conf. on Very Large Databases, pp 500–509
7.
8.
Roumelis G, Vassilakopoulos M, Loukopoulos T, Corral A, Manolopoulos Y (2015) The xBR+-tree: an efficient access method for points. In: Int. Conf. on Database and Expert Systems Applications, pp 43–58
9.
Brayner Ax, Monteiro Filho JM (2016) Hardware-aware database systems: A new era for database technology is coming - vision paper. In: Brazilian Symp. on Databases, pp 187–192
10.
Mittal S, Vetter JS (2016) A survey of software techniques for using non-volatile memories for storage and main memory systems. IEEE Trans Parallel Distrib Syst 27(5):1537–1550CrossRef
11.
Fevgas A, Akritidis L, Bozanis P, Manolopoulos Y (2019) Indexing in flash storage devices: a survey on challenges, current approaches, and future trends. VLDB J:1–39
12.
Emrich T, Graf F, Kriegel H-P, Schubert M, Thoma M (2010) On the impact of flash SSDs on spatial indexing. In: Int. Workshop on Data Management on New Hardware, pp 3–8
13.
Koltsidas I, Viglas SD (2011) Spatial data management over flash memory. In: Int. Conf. on Advances in Spatial and Temporal Databases, pp 449–453
14.
Carniel AC, Ciferri RR, Ciferri CDA (2016) The performance relation of spatial indexing on hard disk drives and solid state drives. In: Brazilian Symp. on GeoInformatics, pp 263–274
15.
Carniel AC, Ciferri RR, Ciferri CDA (2017) Analyzing the performance of spatial indices on hard disk drives and flash-based solid state drives. J Inf Data Manag 8(1):34–49
16.
Agrawal N, Prabhakaran V, Wobber T, Davis JD, Manasse M, Panigrahy R (2008) Design tradeoffs for SSD performance. In: USENIX 2008 Annual Technical Conf., pp 57–70
17.
Bouganim L, Jónsson B, Bonnet P (2009) uFLIP: Understanding flash IO patterns. In: Fourth biennial conf. on innovative data systems research
18.
Chen F, Koufaty DA, Zhang X (2009) Understanding intrinsic characteristics and system implications of flash memory based solid state drives. In: ACM SIGMETRICS Int. Conf. on Measurement and Modeling of Computer Systems, pp 181–192
19.
Jung M, Kandemir M (2013) Revisiting widely held SSD expectations and rethinking system-level implications. In: ACM SIGMETRICS Int. Conf. on Measurement and Modeling of Computer Systems, pp 203–216
20.
Chen F, Hou B, Lee R (2016) Internal parallelism of flash memory-based solid-state drives. ACM Trans Storage 12(3):13:1–13:39CrossRef
21.
Carniel AC, Ciferri RR, Ciferri CDA (2017) A generic and efficient framework for spatial indexing on flash-based solid state drives. In: Inf Syst, pp 229–243
22.
Carniel AC, Ciferri RR, Ciferri CDA (2019) A generic and efficient framework for flash-aware spatial indexing. Inf Syst 82:102–120CrossRef
23.
Hellerstein JM, Naughton JF, Pfeffer A (1995) Generalized search trees for database systems. In: Int. Conf. on Very Large Databases, pp 562–573
24.
Kornacker M (1999) High-performance extensible indexing. In: Int. Conf. on Very Large Databases, pp 699–708
25.
Aref WG, Ilyas IF (2001) SP-GiST: An extensible database index for supporting space partitioning trees. J Intell Inf Syst 17:215–240CrossRef
26.
Cormer D (1979) Ubiquitous B-tree. IEEE Trans Softw Eng 11 (2):121–137
27.
Agrawal D, Ganesan D, Sitaraman R, Diao Y, Singh S (2009) Lazy-adaptive tree: An optimized index structure for flash devices. VLDB Endow 2(1):361–372CrossRef
28.
Wu C-H, Kuo T-W, Chang L-P (2007) An efficient B-tree layer implementation for flash-memory storage systems. ACM Trans Embedded Comput Syst 6(3)
29.
Kwon SJ, Ranjitkar A, Ko Y-B, Chung T-S (2011) FTL algorithms for NAND-type flash memories. Des Autom Embedded Syst 15(3-4):191–224CrossRef
30.
Li Y, He B, Yang RJ, Luo Q, Yi K (2010) Tree indexing on solid state drives. VLDB Endow 3(1-2):1195–1206CrossRef
31.
Thonangi R, Babu S, Yang J (2012) A practical concurrent index for solid-state drives. In: ACM Int. Conf. on Information and Knowledge Management, pp 1332–1341
32.
Jin P, Yang C, Jensen CS, Yang P, Yue L (2016) Read/write-optimized tree indexing for solid-state drives. VLDB J 25(5):695–717CrossRef
33.
Wu C-H, Chang L-P, Kuo T-W (2003) An efficient R-tree implementation over flash-memory storage systems. In: ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems, pp 17–24
34.
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–503CrossRef
35.
Nievergelt J, Hinterberger H, Sevcik KC (1984) The grid file: An adaptable, symmetric multikey file structure. ACM Trans Database Syst 9(1):38–71CrossRef
36.
Lv Y, Li J, Cui B, Chen X (2011) Log-Compact R-tree: An efficient spatial index for SSD. In: Int. Conf. on Database Systems for Advanced Applications, pp 202–213
37.
Li G, Zhao P, Yuan L, Gao S (2013) Efficient implementation of a multi-dimensional index structure over flash memory storage systems. J Supercomput 64(3):1055–1074CrossRef
38.
Robinson JT (1981) The K-D-B-tree: a search structure for large multidimensional dynamic indexes. In: ACM SIGMOD Int. Conf. on Management of Data, pp 10–18
39.
Jin P, Xie X, Wang N, Yue L (2015) Optimizing R-tree for flash memory. Expert Syst Appl 42(10):4676–4686CrossRef
40.
Fevgas A, Bozanis P (2015) Grid-file: Towards to a flash efficient multi-dimensional index. In: Int. Conf. on Database and Expert Systems Applications, pp 285–294
41.
Fevgas A, Bozanis P (2019) LB-Grid: An SSD efficient grid file. Data Knowl Eng 121:18–41CrossRef
42.
Denning PJ (1980) Working sets past and present. TSE SE-6 (1):64–84
43.
Roumelis G, Vassilakopoulos M, Corral A, Fevgas A, Manolopoulos Y (2018) Spatial batch-queries processing using xbr+-trees in solid-state drives. In: Int. Conf. on Model and Data Engineering, pp 301–317
44.
Roumelis G, Fevgas A, Vassilakopoulos M, Corral A, Bozanis P, Manolopoulos Y (2019) Bulk-loading and bulk-insertion algorithms for xBR+-trees in solid state drives. Computing:1–25
45.
Carniel AC, Roumelis G, Ciferri RR, Vassilakopoulos M, Corral A, Ciferri CDA (2018) An efficient flash-aware spatial index for points. In: Brazilian Symp. on GeoInformatics, pp 68–79
46.
Carniel AC, Roumelis G, Ciferri RR, Vassilakopoulos M, Corral A, Ciferri CDA (2019) Indexing points on flash-based solid state drives using the xBR+-tree. J Inf Data Manag 10(1):35–48
47.
Sarwat M, Mokbel MF, Zhou X, Nath S (2013) Generic and efficient framework for search trees on flash memory storage systems. GeoInformatica 17 (3):417–448CrossRef
48.
49.
Effelsberg W, Haerder T (1984) Principles of database buffer management. ACM Trans on Database Systems 9(4):560–595CrossRef
50.
Johnson T, Shasha D (1994) 2Q: A low overhead high performance buffer management replacement algorithm. In: Int. Conf. on Very Large Databases, pp 439–450
51.
Graefe G (2012) A survey of b-tree logging and recovery techniques. ACM Trans Database Syst 37(1)
52.
Proietti G, Faloutsos C (1999) I/O complexity for range queries on region data stored using an r-tree. In: Int. Conf. on Data Engineering, pp 628–635
53.
Arge L, De Berg M, Haverkort H, Yi Ke (2008) The Priority R-tree: A practically efficient and worst-case optimal r-tree. ACM Trans Algorithms 4(1)
54.
Mehlhorn K, Sanders P (2008) Algorithms and data structures: The basic toolbox. Springer
55.
Roumelis G, Vassilakopoulos M, Corral A, Manolopoulos Y (2017) Efficient query processing on large spatial databases: A performance study. J Syst Softw 132:165–185CrossRef
56.
Folk MJ, Zoellick B, Riccardi G (1997) File structures: An object-oriented approach with C++, 3rd edn. Addison Wesley, Boston
57.
58.
Carniel AC, Ciferri RR, Ciferri CDA (2017) Spatial datasets for conducting experimental evaluations of spatial indices. In: Satellite events of the brazilian symp. on databases - dataset showcase workshop, pp 286–295
59.
Carniel AC, Silva TB, Bonicenha KLS, Ciferri RR, Ciferri CDA (2017) Analyzing the performance of spatial indices on flash memories using a flash simulator. In: Brazilian Symp. on Databases, pp 40–51
60.
Carniel AC, Ciferri RR, Ciferri CDA (2020) FESTIval: A versatile framework for conducting experimental evaluations of spatial indices. MethodsX 7:1–19CrossRef
61.
Sellis T, Roussopoulos N, Faloutsos C (1987) The R+-tree: A dynamic index for multi-dimensional objects. In: Int. Conf. on Very Large Databases, pp 507–518
62.
Berchtold S, Keim DA, Kriegel H-P (1996) The X-Tree: An index structure for high-dimensional data. In: In: Int. Conf. on Very Large Databases, pp 28–39
63.
64.
Su X, Jin P, Xiang X, Cui K, Yue L (2009) Flash-DBSim: A simulation tool for evaluating flash-based database algorithms. In: IEEE Int. Conf. on Computer Science and Information Technology, pp 185–189
65.
Zhang Y, Swanson S (2015) A study of application performance with non-volatile main memory. In: Symp. on Mass Storage Systems and Technologies, pp 1–10
Metadata
Title
Porting disk-based spatial index structures to flash-based solid state drives
Authors
Anderson Chaves Carniel
George Roumelis
Ricardo R. Ciferri
Michael Vassilakopoulos
Antonio Corral
Cristina D. Aguiar
Publication date
13-12-2021
Publisher
Springer US
Published in
GeoInformatica / Issue 1/2022
Print ISSN: 1384-6175
Electronic ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-021-00455-w

Other articles of this Issue 1/2022

GeoInformatica 1/2022 Go to the issue

OriginalPaper

Reverse keyword-based location search on road networks

OriginalPaper

Contextual location recommendation for location-based social networks by learning user intentions and contextual triggers

OriginalPaper

On discovering motifs and frequent patterns in spatial trajectories with discrete Fréchet distance

OriginalPaper

Efficient computation of map algebra over raster data stored in the k2-acc compact data structure

OriginalPaper

CIME: Context-aware geolocation of emergency-related posts

OriginalPaper

Temporal aggregation bias and Gerrymandering urban time series