Main Memory Evaluation of Monitoring Queries Over Moving Objects

被引:0
作者
Dmitri V. Kalashnikov
Sunil Prabhakar
Susanne E. Hambrusch
机构
[1] Purdue University,Department of Computer Sciences
来源
Distributed and Parallel Databases | 2004年 / 15卷
关键词
query indexing; moving objects; continuous queries; main memory; index structures;
D O I
暂无
中图分类号
学科分类号
摘要
In this paper we evaluate several in-memory algorithms for efficient and scalable processing of continuous range queries over collections of moving objects. Constant updates to the index are avoided by query indexing. No constraints are imposed on the speed or path of moving objects or fraction of objects that move at any moment in time. We present a detailed analysis of a grid approach which shows the best results for both skewed and uniform data. A sorting based optimization is developed for significantly improving the cache hit-rate. Experimental evaluation establishes that indexing queries using the grid index yields orders of magnitude better performance than other index structures such as R*-trees.
引用
收藏
页码:117 / 135
页数:18
相关论文
共 23 条
[1]  
Becker B.(1996)An asymptotically optimal multiversion B-tree The VLDB Journal 5 264-275
[2]  
Gschwind S.(1998)The asilomar report on database research SIGMOD Record 27 74-80
[3]  
Ohler T.(2000)Personal locator services emerge IEEE Spectrum 37 41-48
[4]  
Seeger B.(1998)Designing access methods for bitemporal databases IEEE Transactions on Knowledge and Data Engineering (TKDE) 10 1-20
[5]  
Widmayer P.(2002)Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects IEEE Transactions on Computers 51 1124-1140
[6]  
Bernstein P.(1998)A quadtree-based dynamic attribute indexing method The Computer Journal 41 185-200
[7]  
Koshima H.(1999)Updating and querying databases that track mobile units Distributed and Parallel Databases 7 257-387
[8]  
Hoshen J.(undefined)undefined undefined undefined undefined-undefined
[9]  
Kumar A.(undefined)undefined undefined undefined undefined-undefined
[10]  
Tsotras V.J.(undefined)undefined undefined undefined undefined-undefined