一種高效的移動(dòng)對(duì)象位置索引機(jī)制的研究.pdf

1、隨著3G時(shí)代的到來和眾多具有定位功能的無線手持設(shè)備的大量普及，促使一類基于位置的服務(wù)，稱為位置相關(guān)服務(wù)(location based service,LBS)成為可能。相應(yīng)的移動(dòng)對(duì)象的位置追蹤也變得越來越可行和必需，這就需要有一種高效的索引結(jié)構(gòu)來定位移動(dòng)對(duì)象的位置。然而傳統(tǒng)的移動(dòng)對(duì)象時(shí)空索引技術(shù)不能同時(shí)有效地支持對(duì)移動(dòng)對(duì)象的過去、現(xiàn)在和將來位置的查詢，這是由空間數(shù)據(jù)的復(fù)雜性和移動(dòng)對(duì)象的動(dòng)態(tài)易變屬性造成的。 本文提出的TEBm<'

2、x>(Time Entropy B<'x>)混合索引結(jié)構(gòu)，在B<'x>樹索引結(jié)構(gòu)的基礎(chǔ)上進(jìn)行了改進(jìn)，并且增加了建立在葉結(jié)點(diǎn)之上的hash輔助索引表來支持對(duì)象的頻繁更新操作，能夠有效地解決上述問題。它簡化了索引關(guān)鍵字來增大索引的時(shí)間跨度，通過使用線性時(shí)間函數(shù)來表征移動(dòng)對(duì)象的位置，可以索引移動(dòng)對(duì)象從過去到將來的位置；該索引結(jié)構(gòu)同時(shí)引入時(shí)間熵，用來表征數(shù)據(jù)庫中移動(dòng)對(duì)象的位置信息隨時(shí)間增長的衰減度量，故能定期剪除那些存儲(chǔ)超過一定期限的對(duì)象信息，

3、維持索引結(jié)構(gòu)處于某個(gè)穩(wěn)定的規(guī)模以提高系統(tǒng)的索引效率。 該索引結(jié)構(gòu)將移動(dòng)對(duì)象的位置存儲(chǔ)在一個(gè)B<'x>樹森林中，它可以有效地支持對(duì)移動(dòng)對(duì)象的過去、現(xiàn)在和將來位置的查詢；同時(shí)它也有效地支持時(shí)間跨度較大的時(shí)空范圍查詢和基于時(shí)間地點(diǎn)受限的集合查詢，例如查詢那些在一個(gè)時(shí)間間隔集合內(nèi)都位于一個(gè)特定的空間區(qū)域內(nèi)的移動(dòng)對(duì)象；并且與B<'x>樹索引結(jié)構(gòu)相比，由于TEB<'x>混合索引結(jié)構(gòu)引入的hash輔助索引表能夠有效地支持自底向上的局部更新策略