An Efficient Data Structure for Organizing Multidimensional Data

An Efficient Data Structure for Organizing Multidimensional Data

Guang-Ho Cha, Chin-Wan Chung
Copyright: © 1997 |Pages: 13
DOI: 10.4018/jdm.1997100101
OnDemand:
(Individual Articles)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

We propose an efficient data structure called the HG-tree (or Hilbert Grid tree) for organizing multidimensional data which are typically points in some domain space. The data structure is developed by extending the concept of the B*-tree to the multidimensional data, so that it guarantees the worst-case storage utilization to have more than 66.7% (2/3) of full capacity. It also maintains compactly the area covered by the directory regions of the data structure, so that it reduces the empty space of the directory region; therefore, the search cost is reduced. We present the design of our data structure and associated algorithms and demonstrate that it is possible to run various range queries and nearest neighbor queries efficiently using this structure. A comparison with the buddy-tree, which is one of the most successful data structures for multidimensional space, is carried out and the advantages of the HG-tree over it are discussed.

Complete Article List

Search this Journal:
Reset
Volume 35: 1 Issue (2024)
Volume 34: 3 Issues (2023)
Volume 33: 5 Issues (2022): 4 Released, 1 Forthcoming
Volume 32: 4 Issues (2021)
Volume 31: 4 Issues (2020)
Volume 30: 4 Issues (2019)
Volume 29: 4 Issues (2018)
Volume 28: 4 Issues (2017)
Volume 27: 4 Issues (2016)
Volume 26: 4 Issues (2015)
Volume 25: 4 Issues (2014)
Volume 24: 4 Issues (2013)
Volume 23: 4 Issues (2012)
Volume 22: 4 Issues (2011)
Volume 21: 4 Issues (2010)
Volume 20: 4 Issues (2009)
Volume 19: 4 Issues (2008)
Volume 18: 4 Issues (2007)
Volume 17: 4 Issues (2006)
Volume 16: 4 Issues (2005)
Volume 15: 4 Issues (2004)
Volume 14: 4 Issues (2003)
Volume 13: 4 Issues (2002)
Volume 12: 4 Issues (2001)
Volume 11: 4 Issues (2000)
Volume 10: 4 Issues (1999)
Volume 9: 4 Issues (1998)
Volume 8: 4 Issues (1997)
Volume 7: 4 Issues (1996)
Volume 6: 4 Issues (1995)
Volume 5: 4 Issues (1994)
Volume 4: 4 Issues (1993)
Volume 3: 4 Issues (1992)
Volume 2: 4 Issues (1991)
Volume 1: 2 Issues (1990)
View Complete Journal Contents Listing