The D-tree: An index structure for planar point queries location-based wireless services
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...
Saved in:
Main Authors: | , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2004
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/1092 https://ink.library.smu.edu.sg/context/sis_research/article/2091/viewcontent/The_D_tree_An_index_structure_for_planar_point_queries_location_based_wireless_services.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-2091 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-20912019-04-01T09:06:14Z The D-tree: An index structure for planar point queries location-based wireless services XU, Jianliang ZHENG, Baihua LEE, Wang-chien LEE, Dik Lun 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. 2004-11-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/1092 info:doi/10.1109/TKDE.2004.97 https://ink.library.smu.edu.sg/context/sis_research/article/2091/viewcontent/The_D_tree_An_index_structure_for_planar_point_queries_location_based_wireless_services.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Databases and Information Systems Numerical Analysis and Scientific Computing |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Databases and Information Systems Numerical Analysis and Scientific Computing |
spellingShingle |
Databases and Information Systems Numerical Analysis and Scientific Computing XU, Jianliang ZHENG, Baihua LEE, Wang-chien LEE, Dik Lun The D-tree: An index structure for planar point queries location-based wireless services |
description |
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. |
format |
text |
author |
XU, Jianliang ZHENG, Baihua LEE, Wang-chien LEE, Dik Lun |
author_facet |
XU, Jianliang ZHENG, Baihua LEE, Wang-chien LEE, Dik Lun |
author_sort |
XU, Jianliang |
title |
The D-tree: An index structure for planar point queries location-based wireless services |
title_short |
The D-tree: An index structure for planar point queries location-based wireless services |
title_full |
The D-tree: An index structure for planar point queries location-based wireless services |
title_fullStr |
The D-tree: An index structure for planar point queries location-based wireless services |
title_full_unstemmed |
The D-tree: An index structure for planar point queries location-based wireless services |
title_sort |
d-tree: an index structure for planar point queries location-based wireless services |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2004 |
url |
https://ink.library.smu.edu.sg/sis_research/1092 https://ink.library.smu.edu.sg/context/sis_research/article/2091/viewcontent/The_D_tree_An_index_structure_for_planar_point_queries_location_based_wireless_services.pdf |
_version_ |
1770570851626778624 |