Incremental Processing of Continual Range Queries over Moving Objects

Efficient processing of continual range queries over moving objects is critically important in providing location-aware services and applications. A set of continual range queries, each defining the geographical region of interest, can be periodically (re)evaluated to locate moving objects that are...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2006-11, Vol.18 (11), p.1560-1575
Main Authors: Wu, K.-L., Chen, S.-K., Yu, P.S.
Format: Article
Language:English
Subjects:
Applied sciences
Boundaries
Computer applications
Computer science
control theory
systems
Construction
Containment
continual range queries
Decomposition
Encoding
Exact sciences and technology
Global Positioning System
Indexing
Information systems. Data bases
location-aware applications
Memory organisation. Data processing
Mobile computing
Monitoring
moving objects
Personal digital assistants
Queries
Query indexing
Radiofrequency identification
Search engines
Searching
Software
Stores
Vehicles
Virtual colonoscopy
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Efficient processing of continual range queries over moving objects is critically important in providing location-aware services and applications. A set of continual range queries, each defining the geographical region of interest, can be periodically (re)evaluated to locate moving objects that are currently within individual query boundaries. We study a new query indexing method, called CES-based indexing, for incremental processing of continual range queries over moving objects. A set of containment-encoded squares (CES) are predefined, each with a unique ID. CESs are virtual constructs (VC) used to decompose query regions and to store indirectly precomputed search results. Compared with a prior VC-based approach, the number of VCs visited in a search operation is reduced from (4L 2 -1)/3 to log(L)+1, where L is the maximal side length of a VC. Search time is hence significantly lowered. Moreover, containment encoding among the CESs makes it easy to identify all those VCs that need not be visited during an incremental query (re)evaluation. We study the performance of CES-based indexing and compare it with a prior VC-based approach
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2006.176