Dynamic Hilbert curve-based B+-Tree to manage frequently updated data in big data applications

Dongmin Seo, Sungho Shin, Young min Kim, Hanmin Jung, Sa Kwang Song

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

In big data application sets, the values of the data used change continually in practice. Therefore, applications involving frequently updated data require index structures that can efficiently handle frequent update of data values. Several methods to index the values of frequently updated data have been proposed, and most of them are based on R-tree-like index structures. Research has been conducted to try to improve the update performance of R-trees, and focuses on query performance. Even though these efforts have resulted in improved update performance, the overhead involved and the immaturity of the concurrency control algorithms of R-trees render the proposed methods a less-than-ideal choice for frequently updated data. In this paper, we propose an update-efficient indexing method. The proposed index is based on the B+-tree and the Hilbert curve. We present an advanced Hilbert curve that automatically adjusts the order of the Hilbert curve in sub-regions, according to the data distribution and the number of data items. We show through experiments that our strategy achieves a faster response time and higher throughput than competing strategies.

Original languageEnglish
Article number62
Pages (from-to)454-461
Number of pages8
JournalLife Science Journal
Volume11
Issue number10
StatePublished - 2014 Jan 1

Fingerprint

Concurrency control
Throughput
Reaction Time
Experiments
Research
Big data
Datasets

Keywords

  • Big data
  • Dynamic Hilbert curve
  • Frequently updated data
  • Multi-dimensional data

Cite this

Seo, Dongmin ; Shin, Sungho ; Kim, Young min ; Jung, Hanmin ; Song, Sa Kwang. / Dynamic Hilbert curve-based B+-Tree to manage frequently updated data in big data applications. In: Life Science Journal. 2014 ; Vol. 11, No. 10. pp. 454-461.
@article{4a793009b59a4aafa25a6726f5627d51,
title = "Dynamic Hilbert curve-based B+-Tree to manage frequently updated data in big data applications",
abstract = "In big data application sets, the values of the data used change continually in practice. Therefore, applications involving frequently updated data require index structures that can efficiently handle frequent update of data values. Several methods to index the values of frequently updated data have been proposed, and most of them are based on R-tree-like index structures. Research has been conducted to try to improve the update performance of R-trees, and focuses on query performance. Even though these efforts have resulted in improved update performance, the overhead involved and the immaturity of the concurrency control algorithms of R-trees render the proposed methods a less-than-ideal choice for frequently updated data. In this paper, we propose an update-efficient indexing method. The proposed index is based on the B+-tree and the Hilbert curve. We present an advanced Hilbert curve that automatically adjusts the order of the Hilbert curve in sub-regions, according to the data distribution and the number of data items. We show through experiments that our strategy achieves a faster response time and higher throughput than competing strategies.",
keywords = "Big data, Dynamic Hilbert curve, Frequently updated data, Multi-dimensional data",
author = "Dongmin Seo and Sungho Shin and Kim, {Young min} and Hanmin Jung and Song, {Sa Kwang}",
year = "2014",
month = "1",
day = "1",
language = "English",
volume = "11",
pages = "454--461",
journal = "Life Science Journal",
issn = "1097-8135",
number = "10",

}

Dynamic Hilbert curve-based B+-Tree to manage frequently updated data in big data applications. / Seo, Dongmin; Shin, Sungho; Kim, Young min; Jung, Hanmin; Song, Sa Kwang.

In: Life Science Journal, Vol. 11, No. 10, 62, 01.01.2014, p. 454-461.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Dynamic Hilbert curve-based B+-Tree to manage frequently updated data in big data applications

AU - Seo, Dongmin

AU - Shin, Sungho

AU - Kim, Young min

AU - Jung, Hanmin

AU - Song, Sa Kwang

PY - 2014/1/1

Y1 - 2014/1/1

N2 - In big data application sets, the values of the data used change continually in practice. Therefore, applications involving frequently updated data require index structures that can efficiently handle frequent update of data values. Several methods to index the values of frequently updated data have been proposed, and most of them are based on R-tree-like index structures. Research has been conducted to try to improve the update performance of R-trees, and focuses on query performance. Even though these efforts have resulted in improved update performance, the overhead involved and the immaturity of the concurrency control algorithms of R-trees render the proposed methods a less-than-ideal choice for frequently updated data. In this paper, we propose an update-efficient indexing method. The proposed index is based on the B+-tree and the Hilbert curve. We present an advanced Hilbert curve that automatically adjusts the order of the Hilbert curve in sub-regions, according to the data distribution and the number of data items. We show through experiments that our strategy achieves a faster response time and higher throughput than competing strategies.

AB - In big data application sets, the values of the data used change continually in practice. Therefore, applications involving frequently updated data require index structures that can efficiently handle frequent update of data values. Several methods to index the values of frequently updated data have been proposed, and most of them are based on R-tree-like index structures. Research has been conducted to try to improve the update performance of R-trees, and focuses on query performance. Even though these efforts have resulted in improved update performance, the overhead involved and the immaturity of the concurrency control algorithms of R-trees render the proposed methods a less-than-ideal choice for frequently updated data. In this paper, we propose an update-efficient indexing method. The proposed index is based on the B+-tree and the Hilbert curve. We present an advanced Hilbert curve that automatically adjusts the order of the Hilbert curve in sub-regions, according to the data distribution and the number of data items. We show through experiments that our strategy achieves a faster response time and higher throughput than competing strategies.

KW - Big data

KW - Dynamic Hilbert curve

KW - Frequently updated data

KW - Multi-dimensional data

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

M3 - Article

AN - SCOPUS:84903213906

VL - 11

SP - 454

EP - 461

JO - Life Science Journal

JF - Life Science Journal

SN - 1097-8135

IS - 10

M1 - 62

ER -