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

Research output: Contribution to journalArticlepeer-review

51 Scopus citations


This paper describes an efficient data structure called the G-tree (or grid tree) for organizing multidimensional data. The data structure combines the features of grids and B-trees in a novel manner. It also exploits an ordering property that numbers the partitions in such a way that partitions that are spatially close to one another in a multidimensional 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 nonuniform 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 comparision 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.

Original languageEnglish (US)
Pages (from-to)341-347
Number of pages7
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number2
StatePublished - Apr 1994

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'G-Tree: A New Data Structure for Organizing Multidimensional Data'. Together they form a unique fingerprint.

Cite this