[發(fā)明專利]一種實(shí)時(shí)移動空間關(guān)鍵字近似Top-k查詢方法

無效

• 申請?zhí)枺?/td>: 201310011084.4
• 申請日: 2013-01-11
• 公開（公告）號: CN103020319A
• 公開（公告）日: 2013-04-03
• 發(fā)明（設(shè)計(jì)）人: 鄒志文;寇愛軍;陳繼明
• 申請（專利權(quán)）人: 江蘇大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京知識律師事務(wù)所 32207
• 代理人: 盧亞麗

一．技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)庫技術(shù)領(lǐng)域，具體涉及一種實(shí)時(shí)移動空間關(guān)鍵字近似Top-k查詢方法。

二．背景技術(shù)

無線通信及移動計(jì)算技術(shù)的發(fā)展激發(fā)了越來越多的移動通信業(yè)務(wù)，移動對象的連續(xù)查詢是近年來移動對象數(shù)據(jù)庫領(lǐng)域的研究熱點(diǎn)?？臻g關(guān)鍵字查詢處理方法將查詢對象的位置與關(guān)鍵字集合作為參數(shù)，返回相匹配的信息。在很多實(shí)際應(yīng)用中，人們并不需要精確的Top-k查詢結(jié)果，并且不同的用戶具有不同的查詢精度要求。因此，研究多精度或任意精度的移動空間Top-k查詢處理方法是十分有必要的，已有的方法很難確保未來任意時(shí)刻結(jié)果的正確性。為此該發(fā)明研究當(dāng)查詢位置持續(xù)移動時(shí)具有任意精度的空間關(guān)鍵字近似Top-k查詢問題。

現(xiàn)有的相關(guān)研究主要分成兩類：

（1）移動查詢

移動對象查詢是空間數(shù)據(jù)庫領(lǐng)域的重要問題，根據(jù)不同的應(yīng)用需求，產(chǎn)生了很多帶限制條件的以及具有復(fù)雜語義的查詢。目前該領(lǐng)域研究的熱點(diǎn)主要是移動k近鄰查詢和道路網(wǎng)中移動對象的k近鄰查詢。連續(xù)k近鄰查詢是指從提交查詢時(shí)刻開始，不斷地給出隨著查詢位置或者移動對象位置信息變化的k近鄰查詢結(jié)果。Hseuh等進(jìn)一步假設(shè)客戶端具有一定的計(jì)算能力，通過維護(hù)位置信息表來減少更新。Mouratidis?M等研究了道路網(wǎng)中的移動對象多用戶k近鄰查詢問題，通過利用空間網(wǎng)絡(luò)的相關(guān)屬性和移動對象運(yùn)動受限這一性質(zhì)，減少連續(xù)查詢的重復(fù)計(jì)算。目前典型的道路網(wǎng)中移動對象連續(xù)k近鄰查詢處理方法有IMA/GMA算法和ER2CkNN算法。IMA/GMA算法從查詢所在的位置開始，遍歷周圍的邊及其上的移動對象，根據(jù)到移動對象的網(wǎng)絡(luò)距離不斷地更新查詢結(jié)果集。IMA/GMA算法的不足：(1)當(dāng)數(shù)據(jù)頻繁更新時(shí)，絕大多數(shù)查詢都需要重計(jì)算，性能急劇下降；(2)當(dāng)?shù)缆肪W(wǎng)規(guī)模較大，時(shí)，其基本的網(wǎng)絡(luò)擴(kuò)張算法性能下降。ER2CkNN算法提出了預(yù)計(jì)算思想，能夠快速計(jì)算給定兩點(diǎn)的最短路徑，還采用了歐氏距離限制的思想，即快速找到候選結(jié)果集，而后利用歐氏范圍查詢不斷對結(jié)果集精煉得到最終結(jié)果。其不足之處為：當(dāng)移動對象數(shù)據(jù)頻繁更新時(shí)，性能急劇下降。國防科大的趙亮等針對移動對象的多用戶連續(xù)K近鄰查詢處理問題，結(jié)合多核多線程技術(shù)，提出了一種基于兩階段多用戶連續(xù)K近鄰查詢處理框架和移動對象內(nèi)存網(wǎng)格索引結(jié)構(gòu)的K近鄰查詢處理算法。該算法的優(yōu)點(diǎn)是充分結(jié)合了多線程和cache優(yōu)化技術(shù)，在性能上有較大提高。該算法的缺陷是：引入了查詢緩沖區(qū)和移動對象緩沖區(qū)機(jī)制，增加了空間消耗。現(xiàn)有的研究其算法不夠靈活，無法適應(yīng)現(xiàn)實(shí)應(yīng)用中不同用戶具有不同精度要求問題。

（2）近似查詢

由于設(shè)備誤差、隱私保護(hù)以及通信限制等,數(shù)據(jù)的不確定性在空間數(shù)據(jù)庫領(lǐng)域廣泛存在。使得很多研究工作致力于近似數(shù)據(jù)管理技術(shù)。在近似查詢方面的研究中，主要研究熱點(diǎn)為：（1）不同應(yīng)用環(huán)境的近似查詢方法研究；(2)帶有概率保證的近似查詢方法研究及近似度誤差界分析。RONALD?F等基于TA算法的思想，提出θ-近似Top-k查詢處理問題。算法返回滿足用戶精度要求的近似結(jié)果，其中θ為相對誤差界。ARAI?B等提出了帶有概率保證的近似Top-k查詢算法。在P2P環(huán)境下，SEBASTIAN?M等提出了一種帶有固定概率保證的近似Top-k查詢結(jié)果；然而當(dāng)k值調(diào)整時(shí)這種方法不夠靈活，尤其當(dāng)k值較大時(shí)往往需要重新設(shè)置閾值。LIU?Y等提出了一種傳感器網(wǎng)絡(luò)中的近似查詢算法，它可以為用戶遞增地精煉事前收集的近似數(shù)據(jù)，使得誤差任意小。現(xiàn)有研究沒有提出對無效空間對象進(jìn)行剪枝的方法，較難適應(yīng)高速移動空間對象查詢問題。

與本發(fā)明最接近的現(xiàn)有技術(shù)是D.Wu等學(xué)者基于安全區(qū)域理論，提出了兩種動態(tài)計(jì)算安全區(qū)域的方法，確保在動態(tài)安全區(qū)域內(nèi)獲取到正確結(jié)果，并且利用剪切規(guī)則降低了客戶端和服務(wù)器端之間的通信開銷。該現(xiàn)有技術(shù)沒有考慮用戶要求多樣化的問題，并且其剪切規(guī)則基礎(chǔ)是空間對象間的權(quán)重支配關(guān)系，該種方法靈活性差，各個(gè)數(shù)據(jù)對象之間的支配關(guān)系要逐一判斷，效率較低。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種實(shí)時(shí)移動空間關(guān)鍵字近似Top-k查詢方法，以解決實(shí)時(shí)變速移動空間關(guān)鍵字查詢面臨“查詢位置持續(xù)變動”及“用戶對查詢精度要求趨于多樣化”的難題。

為了解決以上技術(shù)問題，本發(fā)明采用以下技術(shù)方案。

一種實(shí)時(shí)移動空間關(guān)鍵字近似Top-k查詢方法，其特征在于包括以下步驟：

Step1查詢點(diǎn)q發(fā)送查詢關(guān)鍵字、ε,δ給服務(wù)器，服務(wù)器執(zhí)行剪枝方法，獲得候選集合CR；