Main memory evaluation of monitoring queries over moving objects

被引：71

作者：

Kalashnikov, DV ^{[1
]}

Prabhakar, S ^{[1
]}

Hambrusch, SE ^{[1
]}

机构：

[1] Purdue Univ, Dept Comp Sci, W Lafayette, IN 47907 USA

来源：

DISTRIBUTED AND PARALLEL DATABASES | 2004年 / 15卷 / 02期

基金：

美国国家科学基金会;

关键词：

query indexing; moving objects; continuous queries; main memory; index structures;

D O I：

10.1023/B:DAPD.0000013068.25976.88

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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

页数：19