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

1、隨著3G時代的到來和眾多具有定位功能的無線手持設(shè)備的大量普及，促使一類基于位置的服務(wù)，稱為位置相關(guān)服務(wù)(location based service,LBS)成為可能。相應(yīng)的移動對象的位置追蹤也變得越來越可行和必需，這就需要有一種高效的索引結(jié)構(gòu)來定位移動對象的位置。然而傳統(tǒng)的移動對象時空索引技術(shù)不能同時有效地支持對移動對象的過去、現(xiàn)在和將來位置的查詢，這是由空間數(shù)據(jù)的復(fù)雜性和移動對象的動態(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輔助索引表來支持對象的頻繁更新操作，能夠有效地解決上述問題。它簡化了索引關(guān)鍵字來增大索引的時間跨度，通過使用線性時間函數(shù)來表征移動對象的位置，可以索引移動對象從過去到將來的位置；該索引結(jié)構(gòu)同時引入時間熵，用來表征數(shù)據(jù)庫中移動對象的位置信息隨時間增長的衰減度量，故能定期剪除那些存儲超過一定期限的對象信息，

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