空間數(shù)據(jù)最優(yōu)點(diǎn)查詢算法研究.pdf

1、近年來，隨著互聯(lián)網(wǎng)、移動(dòng)通信以及感知定位技術(shù)的快速發(fā)展與應(yīng)用，各種移動(dòng)終端、圖像視頻采集設(shè)備以及社交平臺(tái)產(chǎn)生了大量的地理位置等低維空間數(shù)據(jù)，和圖像、文本等高維空間數(shù)據(jù)。這些數(shù)據(jù)具有海量、異構(gòu)等特征，因而需要借助高效、準(zhǔn)確的處理模型及算法，來挖掘其內(nèi)在的信息與價(jià)值，從而支持相關(guān)行業(yè)進(jìn)行更好的決策。因此，如何高效、準(zhǔn)確地分析處理空間數(shù)據(jù)并挖掘其內(nèi)在價(jià)值和信息，已成為當(dāng)今計(jì)算機(jī)領(lǐng)域的重大前沿學(xué)術(shù)問題。在該領(lǐng)域問題中，空間數(shù)據(jù)最優(yōu)點(diǎn)查詢是近幾年

2、快速興起的一類子問題。現(xiàn)有的空間數(shù)據(jù)查詢算法在處理復(fù)雜決策分析問題時(shí)會(huì)出現(xiàn)低效和低準(zhǔn)確度等不足，同時(shí)索引和查詢算法還面臨諸多難點(diǎn)和技術(shù)瓶頸。一方面，互聯(lián)網(wǎng)、移動(dòng)設(shè)備等每時(shí)每刻都在產(chǎn)生海量空間數(shù)據(jù)。這些海量數(shù)據(jù)是面向不同決策支持場景的，需要同時(shí)考慮數(shù)據(jù)點(diǎn)的變化特征、維度特征與度量空間特征等諸多因素。然而，目前國內(nèi)外索引技術(shù)大多針對(duì)靜態(tài)數(shù)據(jù)點(diǎn)，很少有考慮時(shí)間維度的索引，同時(shí)現(xiàn)有算法很難做到查詢效率和查詢準(zhǔn)確性的兼顧。另一方面，針對(duì)不同的決策

3、支持場景，最優(yōu)點(diǎn)查詢問題本身是復(fù)雜多變的?，F(xiàn)有的（空間）最優(yōu)點(diǎn)查詢方法大多針對(duì)某一種特定的目標(biāo)方程進(jìn)行算法優(yōu)化，因此擴(kuò)展性差，執(zhí)行效率低，尤其是在處理高維或者路網(wǎng)數(shù)據(jù)集，以及在處理組合最優(yōu)點(diǎn)查詢問題時(shí)，現(xiàn)有算法的準(zhǔn)確性和效率都隨著數(shù)據(jù)集復(fù)雜度的增加而急劇下降。
　　基于上述兩點(diǎn)對(duì)國內(nèi)外研究現(xiàn)狀和趨勢的分析，本文研究并提出了面向不同應(yīng)用背景的高效的最優(yōu)點(diǎn)查詢算法以支持不同的分析與決策場景。主要包括:
　　1.研究提出了歐氏空間

4、下單一最優(yōu)點(diǎn)查詢算法，針對(duì)現(xiàn)有雙色反向最近鄰數(shù)目最大化問題在大數(shù)據(jù)場景下的算法效率低和可擴(kuò)展性差的不足，結(jié)合計(jì)算幾何等領(lǐng)域的經(jīng)典算法，提出了空間掃描策略、空間劃分和上限估計(jì)策略以及基于“弧重疊”的影響值計(jì)算方法。實(shí)驗(yàn)結(jié)果證明，提出的算法相比于已有算法，有更高的效率，更低的內(nèi)存占用率。
　　2.研究提出了三維空間下單一最優(yōu)點(diǎn)查詢算法，首次解決了三維空間下雙色體反向最近鄰最大化問題。針對(duì)問題本身的空間特性和對(duì)索引效率的需求，提出了基于

5、“細(xì)粒度”空間劃分和上限估計(jì)的三維空間最優(yōu)點(diǎn)查詢算法，算法具有高效準(zhǔn)確的特點(diǎn)。并且，證明了提出的算法擴(kuò)展到更高維空間的可行性，對(duì)于空間數(shù)據(jù)最優(yōu)點(diǎn)查詢問題在高維空間下的研究有重要的意義。
　　3.研究提出了考慮服務(wù)設(shè)施點(diǎn)容量限制的空間最優(yōu)點(diǎn)查詢算法，首次解決了服務(wù)點(diǎn)容量受限場景下的空間數(shù)據(jù)最優(yōu)點(diǎn)查詢問題。通過研究空間數(shù)據(jù)庫以及運(yùn)籌學(xué)領(lǐng)域的帶有容量限制的服務(wù)設(shè)施點(diǎn)選址查詢問題，并分析現(xiàn)有算法的應(yīng)用場景局限性，最后提出了基礎(chǔ)搜索算法、基

6、于漸進(jìn)式算法的搜索算法以及基于空間剪枝的搜索算法。實(shí)驗(yàn)證明提出的算法能準(zhǔn)確查詢空間最優(yōu)點(diǎn)，并給出準(zhǔn)確的服務(wù)設(shè)施點(diǎn)和數(shù)據(jù)點(diǎn)之間的分配方案。
　　4.研究提出了歐氏和路網(wǎng)空間中基于聚類算法的組合最優(yōu)點(diǎn)查詢算法。通過研究數(shù)據(jù)挖掘中的各種聚類方法，以及算法導(dǎo)論領(lǐng)域解決組合優(yōu)化問題的各種經(jīng)典近似算法，首次提出了基于聚類算法的組合最優(yōu)點(diǎn)查詢方案。提出的算法可以準(zhǔn)確返回一組最少的最優(yōu)位置點(diǎn)來覆蓋所有數(shù)據(jù)點(diǎn)。相比于傳統(tǒng)的組合最優(yōu)點(diǎn)查詢算法，具有更

7、高的效率及更高的準(zhǔn)確度。同時(shí)，首次將算法擴(kuò)展到了路網(wǎng)數(shù)據(jù)空間，提出了高效的路網(wǎng)空間距離計(jì)算策略。
　　本文研究內(nèi)容主要圍繞空間數(shù)據(jù)最優(yōu)點(diǎn)查詢問題，研究了二維三維歐氏空間中的單個(gè)最優(yōu)點(diǎn)查詢問題，并擴(kuò)展到帶有容量限制的場景，以及歐氏及路網(wǎng)空間中的組合最優(yōu)點(diǎn)查詢問題。提出的算法能夠更高效、更正確地處理市場決策支持等問題。未來的研究方向包括動(dòng)態(tài)場景下及高維空間和度量空間下的最優(yōu)點(diǎn)查詢問題:主要問題是將組合最優(yōu)點(diǎn)問題擴(kuò)展到高維空間（圖片，文