移動對象索引(數(shù)據(jù)庫)

時間：2022-12-04 12:30:01 | 來源：信息時代

時間：2022-12-04 12:30:01 來源：信息時代

    移動對象索引 : 針對移動對象的一種索引技術(shù)。在移動數(shù)據(jù)庫中通常管理著數(shù)量非常龐大的移動對象(如車輛、飛機(jī)、移動用戶等),在查詢處理時,如果逐個掃描所有的移動對象,會降低系統(tǒng)性能。為減少查詢的空間代價、提高查詢效率,必須對數(shù)據(jù)庫中存儲的移動對象進(jìn)行索引。
1. 移動對象索引
移動對象的索引應(yīng)支持:
(1)動態(tài)數(shù)據(jù)的抽象表示:動態(tài)屬性數(shù)據(jù)隨著時間的變化而改變。要既能表示動態(tài)數(shù)據(jù)的當(dāng)前狀態(tài),又能表示它的變化歷史,還能描述數(shù)據(jù)變化的未來趨勢和情況,必須采用動態(tài)數(shù)據(jù)模型。而數(shù)據(jù)模型是索引工作和其他相關(guān)工作的前提。所以,從這個意義上講,動態(tài)數(shù)據(jù)表示也可以認(rèn)為是移動對象索引工作的一部分。
(2)動態(tài)可維護(hù)性: 由于數(shù)據(jù)是動態(tài)變化的,即便在原有的存儲條件下已經(jīng)建立了數(shù)據(jù)的抽象模型,但這種抽象可能發(fā)生變化。因此,移動對象的索引也需要動態(tài)更新或者重建。
(3)可擴(kuò)展性:包括兩層含義:第一,能支持盡可多的查詢類型; 第二,索引的性能應(yīng)該是隨數(shù)據(jù)量增加而近乎線性地下降(不是非線性地下降太快)。
(4)大數(shù)據(jù)量: 通常移動對象的數(shù)據(jù)量都很大,故移動對象索引必須支持巨大的數(shù)據(jù)負(fù)載。
(5)移動對象查詢:支持高效查詢是建立索引最直接和最主要的目的,移動對象的索引當(dāng)然也不例外。另外,移動對象的索引還應(yīng)該支持盡可能多的查詢類型,因為移動對象查詢是多種多樣的。
2.移動對象的索引方法
移動對象索引方法通常借鑒于空間數(shù)據(jù)索引技術(shù),不同之處在于移動對象索引中必有一維是時間。空間數(shù)據(jù)索引方法中有R-樹及其變形(R⁺-樹、R^*-樹等)、Quad-樹、X-樹、LSD-樹、格柵文件等,但它們都難以直接應(yīng)用于移動對象索引。因為這些方法都假定查詢頻率遠(yuǎn)遠(yuǎn)高于更新頻率,它們更多地只考慮查詢效率。而對移動對象索引來說,移動對象的位置更新會引起索引結(jié)構(gòu)的動態(tài)變化,故在查詢負(fù)載之外還有大量的更新負(fù)載,所以移動對象索引除了要考慮查詢效率外,還必須著重考慮更新代價問題。在這種情況下,針對移動數(shù)據(jù)管理,人們提出了一些新的索引技術(shù)和解決方案。
(1)在原有的空間索引中引入時間維。其主要思想就是將時間看作另一個空間維。若原有的參考空間是d維的,則現(xiàn)在將其視為d+1維來處理,于是傳統(tǒng)的空間索引方法就可以應(yīng)用了。如SpatioTemporal R-tree、MV3R-tree等就是這種思想的例子。但該方法存在的問題是生存期較長的對象將被表示為長矩形。
(2)在結(jié)點中加入時間因素,使每個對象都有空間和時間的范圍。當(dāng)移動對象的位置發(fā)生改變時,就插入新的記錄。顯然,維護(hù)這種索引結(jié)構(gòu)的代價是很高的。
(3)分狀態(tài)索引。應(yīng)用傳統(tǒng)空間索引方法來索引每個狀態(tài)下的對象,也就是建立一系列對應(yīng)離散時刻的樹結(jié)構(gòu)。
(4)空間-時間表示。移動對象的軌跡表示為空間-時間坐標(biāo)系里的一條射線(一維的情況下),每條線用一個最小范圍矩形(MBR)近似表示。它的問題是,MBR的范圍要比它對應(yīng)的軌跡大得多。因此,常常采用下面的二元時空變換方法。
(5)二元時空變換。存在很多種變換方法,共同的思想就是降維。例如,Hough-X變換就是將直線y(t)=v^*t+a變?yōu)槠矫嫔系囊粋€點(v,a)。類似的還有Hough-Y變換。這類方法的主要缺點是,當(dāng)維數(shù)為d時,需要將運動分解為d個投影,因此不能很方便地解決三維空間下的移動對象問題。另外,可以利用希爾伯特曲線等空間劃分技術(shù),將高維空間降為低維空間,使更新代價減小,數(shù)據(jù)表示更簡單。
3.移動對象的時空索引
移動對象索引與時空索引方法密切相關(guān),可以分為對移動對象過去位置或者歷史軌跡的索引和對現(xiàn)在與將來位置的索引。
在對移動對象過去位置的索引中,對象的歷史軌跡是隨著時間連續(xù)變化的,但我們不可能記錄下所有更新的位置,因此只能以折線來近似描述移動對象過去的位置變化。移動對象歷史位置信息包含空間與時間兩個方面,即對應(yīng)移動對象在一定時間范圍內(nèi)的空間位置信息。根據(jù)對空間與時間維處理方式的不同,移動對象歷史位置信息索引可以分為三類: 第一類是在已有的空間索引基礎(chǔ)上加入時間維,即將時間看作空間索引中的另外一維而不區(qū)分時間維與空間維; 第二類要區(qū)分空間維與時間維,但主要目標(biāo)是將空間鄰近的移動對象聚集在一起,而時間維處于次要地位。這種作法是為了支持基于軌跡的查詢,目的是高效地獲得同一個移動對象的全部或部分軌跡,而將時間或空間臨近的移動對象聚集在一起放在次要的位置。前兩類查詢處理著眼于基于移動對象坐標(biāo)信息的查詢,即關(guān)注移動對象的位置信息,如點查詢、區(qū)域查詢、最鄰近查詢等;第三類則關(guān)注移動對象的軌跡查詢,即查詢拓?fù)浠蛲茖?dǎo)信息。支持結(jié)合了坐標(biāo)查詢與軌跡查詢的混合型查詢,這通常需要先以一個區(qū)域查詢來得到候選的軌跡集合,然后處理候選集中的軌跡查詢。
移動對象位置更新頻繁,移動對象當(dāng)前與未來位置索引的關(guān)鍵是采用有效的更新算法及預(yù)測模型,其主要目標(biāo)是給定對象當(dāng)前的運動向量,使得能有效地檢索在未來時間滿足某個空間條件的移動對象。對未來信息進(jìn)行索引,根據(jù)對時間維和空間維處理方法的不同,可以分為時間-空間維方法、轉(zhuǎn)換式方法和參數(shù)式方法三種。在時間-空間維方法中,時間被當(dāng)作單獨的一維來處理; 在轉(zhuǎn)化式方法中,時間維被轉(zhuǎn)化到空間維;而在參數(shù)式方法中,將時間作為對空間進(jìn)行描述的參數(shù)。