The D-tree: An index structure for planar point queries in location-based wireless services

Jianliang XU*, Baihua Zheng, Wang Chien Lee, Dik Lun Lee

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

56 Citations (Scopus)


Location-based services (LBSs), considered as a killer application in the wireless data market, provide information based on locations specified in the queries. In this paper, we examine the indexing issue for querying location-dependent data in wireless LBSs; in particular, we focus on an important class of queries, planar point queries. To address the issues of responsiveness, energy consumption, and bandwidth contention in wireless communications, an index has to minimize the search time and maintain a small storage overhead. It is shown that the traditional point-location algorithms and spatial index structures fail to achieve either objective or both. This paper proposes a new index structure, called D-tree, which indexes spatial regions based on the divisions that form the boundaries of the regions. We describe how to construct a binary D-tree index, how to process queries based on the D-tree, and how to page the binary D-tree. Moreover, two parameterized methods for partitioning the original space, called fixed grid assignment (FGA) and adaptive grid assignment (AGA), are proposed to enhance the D-tree. The performance of the D-tree is evaluated using both synthetic and real data sets. Experimental results show that the proposed D-tree outperforms the well-known indexes such as the R*-tree, and that both the FGA and AGA approaches can achieve different performance trade-offs between the index search time and storage overhead by fine-tuning their algorithmic parameters.

Original languageEnglish
Pages (from-to)1526-1542
Number of pages17
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number12
Publication statusPublished - Dec 2004

Scopus Subject Areas

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

User-Defined Keywords

  • Data broadcast
  • Energy conservation
  • Index structure
  • Location-dependent data
  • Mobile computing
  • Spatial database


Dive into the research topics of 'The D-tree: An index structure for planar point queries in location-based wireless services'. Together they form a unique fingerprint.

Cite this