DocumentCode :
1455543
Title :
Nine-areas-tree-bit-patterns-based method for continuous range queries over moving objects
Author :
Chen, Hung-Ling ; Chang, Ye-In
Author_Institution :
Dept. of Comput. Sci. & Eng., Nat. Sun Yat-Sen Univ., Kaohsiung, Taiwan
Volume :
5
Issue :
1
fYear :
2011
fDate :
2/1/2011 12:00:00 AM
Firstpage :
54
Lastpage :
69
Abstract :
A continuous range query is defined to periodically re-evaluated to locate moving objects that are currently inside the boundary of the range query and is widely used to support the location-based services. However, the query processing becomes complicated because of frequent locations update of moving objects. The query indexing relies on incremental evaluation, building the index on range queries instead of moving objects and exploiting the relation between locations objects and queries. The cell-based query indexing method has been proved to have the better performance of query processing than that of the R*-tree-based query indexing method with the overlapping problem in internal nodes. However, it takes a lot of space and time for the cell-based method to maintain the index structure, when the number of range queries increases. The nine-areas (NA) tree has been proved to solve the overlapping problem in the R*-tree to minimise the number of disk accesses during a tree search for the range queries. In this study, the authors propose the NA-tree-bit-patterns-based (NABP) query indexing method based on the NA-tree. We use the bit-patterns to denote the regions and to preserve the locality of range queries and moving objects. Therefore our NABP method can incrementally local update the affected range queries over moving objects by bit-patterns operations, especially with the increase of the number of range queries. From their simulation study, the authors show that their NABP method requires less CPU time and storage cost than the cell-based method for large number of range queries update. The authors also show that their NABP method requires less CPU time than the R*-tree-based method for large number of moving objects update.
Keywords :
indexing; mobile computing; query processing; trees (mathematics); visual databases; NA-tree; NABP; R*-tree-based method; cell-based query indexing method; continuous range queries; location-based services; moving objects; nine areas tree bit patterns based method; query processing;
fLanguage :
English
Journal_Title :
Software, IET
Publisher :
iet
ISSN :
1751-8806
Type :
jour
DOI :
10.1049/iet-sen.2009.0085
Filename :
5718213
Link To Document :
بازگشت