ACM SIGMOD Anthology TKDE dblp.uni-trier.de

G-Tree: A New Data Structure for Organizing Multidimensional Data.

Akhil Kumar: G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994)
@article{DBLP:journals/tkde/Kumar94,
  author    = {Akhil Kumar},
  title     = {G-Tree: A New Data Structure for Organizing Multidimensional
               Data},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {6},
  number    = {2},
  year      = {1994},
  pages     = {341-347},
  ee        = {db/journals/tkde/Kumar94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper describes an efficient data structure called the G-tree (or grid tree) for organizing multi-dimensional data. The data structure combines the features of grids and B-trees in a novel manner. It also exploits an ordering property which numbers the partitions in such a way that partitions that are spatially close to one another in a multi-dimensional space are also close in terms of their partition numbers. This structure adapts well to dynamic data spaces with a high frequency of insertions and deletions, and to non-uniform distributions of data. We demonstrate that it is possible to perform insertion, retrieval and deletion operations, and to run various range queries efficiently using this structure. A comparison with the BD tree, - zkdb tree and the KDB tree is carried out and the advantages of the G-tree over the other structures are discussed. The simulated bucket utilization rates for the G-tree are also reported.

Copyright © 1994 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[2]
Walter A. Burkhard: Interpolation-Based Index Maintenance. BIT 23(3): 274-294(1983) BibTeX
[3]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[4]
...
[5]
Sivarama P. Dandamudi, Paul G. Sorenson: Algorithms for BD Trees. Softw., Pract. Exper. 16(12): 1077-1096(1986) BibTeX
[6]
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
[7]
Klaus Hinrichs: Implementation of the Grid File: Design Concepts and Experience. BIT 25(4): 569-592(1985) BibTeX
[8]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
[9]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 BibTeX
[10]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX
[11]
Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105 BibTeX
[12]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
[13]
James B. Rothnie Jr., Tomas Lozano: Attribute Based File Organization in a Paged Memory Environment. Commun. ACM 17(2): 63-69(1974) BibTeX
[14]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX

Referenced by

  1. Dimitris G. Kapopoulos, Michael Hatzopoulos: The Gr_Tree: The Use of Active Regions in G-Trees. ADBIS 1999: 141-155
  2. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  3. Jong-Hak Lee, Young-Koo Lee, Kyu-Young Whang, Il-Yeol Song: A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations. VLDB 1997: 416-425
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
IEEE Transactions on Data and Knowledge Engineering: Copyright © by IEEE,
Joint ACM SIGMOD / IEEE Computer Society Anthology: Copyright © by ACM (info@acm.org) and IEEE, Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:28:03 2009