nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Grid-File: Towards to a Flash Efficient Multi-dimensional Index

verfasst von : Athanasios Fevgas, Panayiotis Bozanis

Erschienen in: Database and Expert Systems Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Spatial indexes are of great importance for multidimensional query processing. Traditional data structures have been optimized for magnetic disks in the storage layer. In the recent years flash solid disks are widely utilized, as a result of their exceptional features. However, the specifics of flash memory (asymmetric read/write speeds erase before update, wear out) introduce new challenges. Algorithms and data structures designed for magnetic disks experience reduced performance in flash. Most research efforts for flash-aware spatial indexes concern R-tree and its variants. Distinguishing from previous works we investigate the performance of Grid File in flash and enlighten constrains and opportunities towards a flash efficient Grid File. We conducted experiments on mainstream and high performance SSD devices and Grid File outperforms R\(^*\)-tree in all cases.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel XQuery Testing from XML Schema Based Random Test Cases

Nächstes Kapitel Supporting Fluctuating Transactional Workload

Bouganim, L., Jónsson, B., Bonnet, P.: uFLIP: understanding flash IO patterns (2009). arXiv preprint arXiv:0909.1780

Wu, C.H., Chang, L.P., Kuo, T.W.: An efficient R-tree implementation over flash-memory storage systems. In: Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems, GIS 2003, pp. 17–24. ACM, New York (2003)

Wu, C.H., Kuo, T.W., Chang, L.P.: An efficient B-tree layer implementation for flash-memory storage systems. ACM Trans. Embed. Comput. Syst. (TECS) 6(3), 19 (2007)CrossRef

Pawlik, M., Macyna, W.: Implementation of the aggregated R-tree over flash memory. In: Yu, H., Yu, G., Hsu, W., Moon, Y.-S., Unland, R., Yoo, J. (eds.) DASFAA Workshops 2012. LNCS, vol. 7240, pp. 65–72. Springer, Heidelberg (2012) CrossRef

Roh, H., Kim, S., Lee, D., Park, S.: As B-tree: a study of an efficient B+-tree for SSDs. J. Inf. Sci. Eng. 30(1), 85–106 (2014)MATH

Agrawal, D., Ganesan, D., Sitaraman, R., Diao, Y., Singh, S.: Lazy-adaptive tree: an optimized index structure for flash devices. Proc. VLDB Endow. 2(1), 361–372 (2009)CrossRef

Roh, H., Park, S., Kim, S., Shin, M., Lee, S.W.: B+-tree index optimization by exploiting internal parallelism of flash-based solid state drives. Proc. VLDB Endow. 5(4), 286–297 (2011)CrossRef

Wang, N., Jin, P., Wan, S., Zhang, Y., Yue, L.: OR-tree: an optimized spatial tree index for flash-memory storage systems. In: Xiang, Y., Pathan, M., Tao, X., Wang, H. (eds.) ICDKE 2012. LNCS, vol. 7696, pp. 1–14. Springer, Heidelberg (2012) CrossRef

Jin, P., Xie, X., Wang, N., Yue, L.: Optimizing R-tree for flash memory. Expert Syst. Appl. 42, 4676–4686 (2015)CrossRef

10.

Lv, Y., Li, J., Cui, B., Chen, X.: Log-compact R-tree: an efficient spatial index for SSD. In: Xu, J., Yu, G., Zhou, S., Unland, R. (eds.) DASFAA Workshops 2011. LNCS, vol. 6637, pp. 202–213. Springer, Heidelberg (2011) CrossRef

11.

Li, G., Zhao, P., Yuan, L., Gao, S.: Efficient implementation of a multi-dimensional index structure over flash memory storage systems. J. Supercomput. 64(3), 1055–1074 (2013)CrossRef

12.

Athanassoulis, M., Ailamaki, A.: BF-tree: approximate tree indexing. In: Proceedings of the 40th International Conference on Very Large Databases. Number EPFL-CONF-201942 (2014)

13.

Guttman, A.: R-trees: a dynamic index structure for spatial searching, vol. 14. ACM (1984)

14.

Nievergelt, J., Hinterberger, H., Sevcik, K.C.: The grid file: an adaptable, symmetric multikey file structure. ACM Trans. Database Syst. (TODS) 9(1), 38–71 (1984)CrossRef

15.

Papadopoulos, A.N., Manolopoulos, Y., Theodoridis, Y., Tsotras, V.: Grid file (and family). In: Liu, L., Özsu, M.T. (eds.) Encyclopedia of Database Systems, pp. 1279–1282. Springer, New York (2009)

16.

Eldawy, A., Mokbel, M.F.: A demonstration of spatialhadoop: an efficient mapreduce framework for spatial data. Proc. VLDB Endow. 6(12), 1230–1233 (2013)CrossRef

17.

Liu, Y., Hu, S., Rabl, T., Liu, W., Jacobsen, H.A., Wu, K., Chen, J.: DGFindex for smart grid: enhancing hive with a cost-effective multidimensional range index (2014). arXiv preprint arXiv:1404.5686

18.

Park, K.: Location-based grid-index for spatial query processing. Expert Syst. Appl. 41(4), 1294–1300 (2014)CrossRef

19.

Robinson, J.T.: The KDB-tree: a search structure for large multidimensional dynamic indexes. In: Proceedings of the 1981 ACM SIGMOD INTERNATIONAL CONFERENCE on Management of DATA, pp. 10–18. ACM (1981)

20.

Sarwat, M., Mokbel, M.F., Zhou, X., Nath, S.: FAST: a generic framework for flash-aware spatial trees. In: Pfoser, D., Tao, Y., Mouratidis, K., Nascimento, M.A., Mokbel, M., Shekhar, S., Huang, Y. (eds.) SSTD 2011. LNCS, vol. 6849, pp. 149–167. Springer, Heidelberg (2011) CrossRef

21.

Koltsidas, I., Viglas, S.D.: Spatial Data management over flash memory. In: Pfoser, D., Tao, Y., Mouratidis, K., Nascimento, M.A., Mokbel, M., Shekhar, S., Huang, Y. (eds.) SSTD 2011. LNCS, vol. 6849, pp. 449–453. Springer, Heidelberg (2011) CrossRef

22.

Park, S.y., Jung, D., Kang, J.u., Kim, J.s., Lee, J.: CFLRU: a replacement algorithm for flash memory. In: Proceedings of the 2006 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, pp. 234–241. ACM (2006)

23.

Jin, P., Ou, Y., Harder, T., Li, Z.: AD-LRU: an efficient buffer replacement algorithm for flash-based databases. Data Knowl. Eng. 72, 83–102 (2012)CrossRef

24.

Hinrichs, K.: Implementation of the grid file: design concepts and experience. BIT Numer. Math. 25(4), 569–592 (1985)MathSciNetCrossRefMATH

25.

Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The R*-tree: an efficient and robust access method for points and rectangles, vol. 19. ACM (1990)

26.

Hadjieleftheriou, M.: libspatialindex 1.8.5 (2015). http://libspatialindex.github.io/. Accessed 20 Feb 2015

Titel: Grid-File: Towards to a Flash Efficient Multi-dimensional Index
verfasst von: Athanasios Fevgas
Panayiotis Bozanis
Verlag: Springer International Publishing
Buch: Database and Expert Systems Applications
Print ISBN: 978-3-319-22851-8

Electronic ISBN: 978-3-319-22852-5

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-22852-5_24

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"