移動(dòng)對(duì)象查詢(xún)(數(shù)據(jù)庫(kù))

時(shí)間：2022-12-04 06:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-12-04 06:30:01 來(lái)源：信息時(shí)代

    移動(dòng)對(duì)象查詢(xún) : 針對(duì)移動(dòng)對(duì)象的一種查詢(xún)技術(shù)。移動(dòng)對(duì)象包含了空間和時(shí)間兩方面的屬性,因此對(duì)移動(dòng)對(duì)象的查詢(xún)是指指明時(shí)空謂詞,搜索滿(mǎn)足這些謂詞的移動(dòng)對(duì)象?？臻g謂詞通常指定一個(gè)空間點(diǎn)或是空間范圍;而時(shí)間謂詞通常包含一個(gè)時(shí)間點(diǎn)或是時(shí)間范圍。
根據(jù)查詢(xún)謂詞的不同,可以將移動(dòng)對(duì)象的查詢(xún)劃分為下面的幾種類(lèi)型:
(1)范圍查詢(xún): 查找在某一時(shí)刻(或時(shí)間段)在給定區(qū)域內(nèi)的所有對(duì)象。范圍查詢(xún)是最基本的、應(yīng)用最廣泛的查詢(xún)類(lèi)型,可以作為其他復(fù)雜查詢(xún)的基礎(chǔ)和組成部分,大部分移動(dòng)對(duì)象索引都支持移動(dòng)對(duì)象的范圍查詢(xún)處理。
(2)最鄰近查詢(xún): 查找某一時(shí)刻(或時(shí)間段)哪些對(duì)象距離給定點(diǎn)最近。鄰近查詢(xún)中最通常的類(lèi)型是K鄰近查詢(xún)(KNN),即查找最靠近查詢(xún)點(diǎn)的K個(gè)對(duì)象。鄰近查詢(xún)中的另一種查詢(xún)?yōu)槟孀罱彶樵?xún)(RNN)。這種查詢(xún)查找其最近鄰是查詢(xún)點(diǎn)的移動(dòng)對(duì)象,即對(duì)于查詢(xún)結(jié)果中的每一個(gè)點(diǎn),距它最近的點(diǎn)是查詢(xún)點(diǎn)。例如: 一個(gè)行人可能想知道距自己最近的出租車(chē),而對(duì)于出租車(chē),他想知道對(duì)于哪些行人,自己是距其最近的出租車(chē),這些行人就是出租車(chē)的逆最近鄰查詢(xún)結(jié)果。
(3)聚集查詢(xún): 查找在某一時(shí)刻(或時(shí)間段),有多少對(duì)象通過(guò)了區(qū)域R,如聚集最近鄰查詢(xún)(ANN)。ANN查詢(xún)查找距離給定查詢(xún)點(diǎn)集合的聚集距離最小的對(duì)象集合。這是一類(lèi)多查詢(xún)點(diǎn)多對(duì)象的查詢(xún)類(lèi)型。這種查詢(xún)的目的是找出綜合評(píng)估最優(yōu)的位置。例如,利用一個(gè)求和函數(shù),可以查找出飯店的最優(yōu)位置,這個(gè)位置距離所有居民區(qū)的距離和最小; 或者利用一個(gè)最大值函數(shù),可以確定約會(huì)的最佳地點(diǎn),使得最后一個(gè)人到達(dá)的時(shí)間最短。
(4)多處理查詢(xún): 同時(shí)處理多個(gè)查詢(xún)。可以將這些查詢(xún)分類(lèi),有些查詢(xún)可共享同一個(gè)查詢(xún)結(jié)果或其查詢(xún)結(jié)果的超集,而有些查詢(xún)不必交給服務(wù)器終端處理,只需對(duì)某類(lèi)中的幾個(gè)查詢(xún)進(jìn)行計(jì)算和處理。這樣大大減少了服務(wù)器的工作量,提高了計(jì)算效率。例如,多處理單范圍查詢(xún)和多處理單KNN查詢(xún)。
(5)連續(xù)查詢(xún):在某個(gè)時(shí)間區(qū)域內(nèi)持續(xù)有效的查詢(xún)。在給定時(shí)間區(qū)域內(nèi),由于移動(dòng)對(duì)象位置的改變,查詢(xún)的結(jié)果也在不斷變化,系統(tǒng)需要隨時(shí)將查詢(xún)結(jié)果的變化信息傳遞給查詢(xún)用戶(hù),使得用戶(hù)能夠?qū)崟r(shí)地監(jiān)控最新的查詢(xún)結(jié)果。例如,在高速公路上行進(jìn)的救護(hù)車(chē)可以提交一個(gè)持續(xù)查詢(xún): “在未來(lái)20min之內(nèi)隨時(shí)查詢(xún)距離最近的醫(yī)院”,這個(gè)查詢(xún)將在未來(lái)20min的行進(jìn)過(guò)程中不斷地動(dòng)態(tài)返回離救護(hù)車(chē)最近的醫(yī)院。
連續(xù)查詢(xún)跟一般查詢(xún)最重要的區(qū)別是對(duì)象的動(dòng)態(tài)性或者查詢(xún)本身的動(dòng)態(tài)性(查詢(xún)窗口的運(yùn)動(dòng))使得查詢(xún)結(jié)果與時(shí)間屬性相關(guān)。對(duì)于數(shù)據(jù)的每一次更新或者查詢(xún)點(diǎn)的連續(xù)變化,所有連續(xù)查詢(xún)的結(jié)果都要重新考慮。在這里,查詢(xún)成為了“數(shù)據(jù)”被索引,而數(shù)據(jù)更新成為了“查詢(xún)”。連續(xù)時(shí)空查詢(xún)?cè)u(píng)價(jià)方法大概包括四種:
(1)無(wú)效查詢(xún)的重復(fù)評(píng)價(jià)。查詢(xún)結(jié)果有一個(gè)附加參數(shù),用于確認(rèn)查詢(xún)結(jié)果的有效性。這個(gè)參數(shù)或者是關(guān)于時(shí)間的(例如,有效時(shí)間,即查詢(xún)結(jié)果在多長(zhǎng)時(shí)間內(nèi)有效,在多長(zhǎng)時(shí)間后將改變),或者是關(guān)于空間的(例如,有效區(qū)域,即查詢(xún)點(diǎn)在怎樣的區(qū)域內(nèi)會(huì)保持查詢(xún)結(jié)果不變,而離開(kāi)這個(gè)區(qū)域查詢(xún)結(jié)果將發(fā)生改變; 或者安全區(qū)域,即被查詢(xún)的數(shù)據(jù)點(diǎn)在怎樣的區(qū)域內(nèi)可以保證所有查詢(xún)點(diǎn)的查詢(xún)結(jié)果均有效,當(dāng)數(shù)據(jù)點(diǎn)在這樣的有效區(qū)域內(nèi)運(yùn)動(dòng)時(shí),每一個(gè)查詢(xún)點(diǎn)的查詢(xún)結(jié)果保持不變)。如果查詢(xún)結(jié)果不在有效參數(shù)范圍內(nèi),那么這個(gè)查詢(xún)需要重新提交并評(píng)價(jià)。
(2)緩存結(jié)果。先前的查詢(xún)結(jié)果為后續(xù)查詢(xún)剪枝搜索空間。為了利用先前的查詢(xún)結(jié)果來(lái)縮小后續(xù)查詢(xún)的范圍、縮小查詢(xún)空間,有必要將查詢(xún)結(jié)果緩存起來(lái)。結(jié)果或者緩存在服務(wù)器端,這將要額外花費(fèi)從服務(wù)器讀取數(shù)據(jù)的時(shí)間; 或者在客戶(hù)端有存儲(chǔ)和計(jì)算能力的情況下,把結(jié)果緩存在客戶(hù)端,然而大量的重復(fù)信息將導(dǎo)致較多的空間浪費(fèi)。
(3)在已知查詢(xún)軌跡情況下,預(yù)計(jì)算查詢(xún)結(jié)果。只要查詢(xún)軌跡不發(fā)生變化,通過(guò)利用靜態(tài)對(duì)象的可計(jì)算幾何信息或者移動(dòng)對(duì)象的速度信息來(lái)識(shí)別查詢(xún)結(jié)果集。根據(jù)每個(gè)對(duì)象的速度、移動(dòng)方向信息預(yù)測(cè)它在一定時(shí)間后的位置,進(jìn)而計(jì)算當(dāng)時(shí)的查詢(xún)結(jié)果。
(4)增量式評(píng)價(jià)。當(dāng)有更新出現(xiàn)時(shí),不是重新評(píng)價(jià)查詢(xún)和產(chǎn)生整個(gè)查詢(xún)結(jié)果,而是查詢(xún)執(zhí)行器輸出前一查詢(xún)結(jié)果的正和負(fù)更新。一個(gè)正更新指一個(gè)新對(duì)象被加入到查詢(xún)結(jié)果中,而一個(gè)負(fù)更新指明一個(gè)老對(duì)象移出查詢(xún)結(jié)果。通過(guò)分析這些更新,可以知道查詢(xún)結(jié)果的個(gè)數(shù)的變化,即查詢(xún)結(jié)果的范圍是增大了還是減小了,從而確定是否需要擴(kuò)大查詢(xún)空間。