Publication Type

Journal Article

Version

publishedVersion

Publication Date

11-2004

Abstract

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.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

16

Issue

12

First Page

1526

Last Page

1542

ISSN

1041-4347

Identifier

10.1109/TKDE.2004.97

Publisher

IEEE

Additional URL

https://doi.org/10.1109/TKDE.2004.97

Download

Share

COinS