The B-dual-tree: indexing moving objects by space filling curves in the dual space
Publication in refereed journal


引用次數
替代計量分析
.

其它資訊
摘要Existing spatiotemporal indexes suffer from either large update cost or poor query performance, except for the B-x-tree (the state-of-the-art), which consists of multiple B+-trees indexing the 1D values transformed from the (multi-dimensional) moving objects based on a space filling curve (Hilbert, in particular). This curve, however, does not consider object velocities, and as a result, query processing with a B-x-tree retrieves a large number of false hits, which seriously compromises its efficiency. It is natural to wonder "can we obtain better performance by capturing also the velocity information, using a Hilbert curve of a higher dimensionality?". This paper provides a positive answer by developing the B-dual-tree, a novel spatiotemporal access method leveraging pure relational methodology. We show, with theoretical evidence, that the B-dual-tree indeed outperforms the B-x-tree in most circumstances. Furthermore, our technique can effectively answer progressive spatiotemporal queries, which are poorly supported by B-x-trees.
著者Yiu ML, Tao YF, Mamoulis N
期刊名稱VLDB Journal
出版年份2008
月份5
日期1
卷號17
期次3
出版社Springer Verlag (Germany)
頁次379 - 400
國際標準期刊號1066-8888
電子國際標準期刊號0949-877X
語言英式英語
關鍵詞access method; space filling curve; spatiotemporal
Web of Science 學科類別Computer Science; Computer Science, Hardware & Architecture; COMPUTER SCIENCE, HARDWARE & ARCHITECTURE; Computer Science, Information Systems; COMPUTER SCIENCE, INFORMATION SYSTEMS

上次更新時間 2021-03-03 於 00:02