面向移動(dòng)對(duì)象實(shí)時(shí)跟蹤的查詢優(yōu)化算法的研究.pdf

1、近些年來無線通信網(wǎng)絡(luò)高速發(fā)展，智能移動(dòng)終端設(shè)備也迅速普及，提供基于位置的服務(wù)也逐漸成為這些移動(dòng)設(shè)備的基本功能之一。通過移動(dòng)終端查找最近鄰目標(biāo)，即最近鄰查詢，逐漸成為位置服務(wù)中一項(xiàng)重要的應(yīng)用，對(duì)該領(lǐng)域應(yīng)用的研究具有很高的科研與實(shí)用價(jià)值。正是由于位置服務(wù)的大量普及，空間數(shù)據(jù)越來越具有海量性和復(fù)雜性，傳統(tǒng)的針對(duì)靜態(tài)環(huán)境的最近鄰查詢已經(jīng)不能很好地適用于這種情況。因此，如何提高空間數(shù)據(jù)的最近鄰查詢技術(shù)，已經(jīng)成為位置服務(wù)領(lǐng)域的研究焦點(diǎn)。針對(duì)動(dòng)態(tài)環(huán)境

2、下的最近鄰查詢，已經(jīng)存在一些比較好的解決方法，比如YPK?CNN算法， SEA?CNN算法和CPM算法，其中CPM算法是其中公認(rèn)的最優(yōu)秀的算法，但是其中大量的歐氏距離計(jì)算是阻止算法效率進(jìn)一步提高的瓶頸。另外，在實(shí)際應(yīng)用中，大多數(shù)移動(dòng)對(duì)象是移動(dòng)軌跡無法預(yù)測(cè)的非確定對(duì)象，采用一般的最近鄰查詢算法勢(shì)必會(huì)有一定的局限性，并且國(guó)內(nèi)外在該領(lǐng)域的研究成果相對(duì)較少，因此本文提出了一種針對(duì)非確定對(duì)象的最近鄰查詢思路。
　　本文基于CPM算法中概念分

3、割的模型，通過分析總結(jié)當(dāng)前最近鄰查詢研究的相關(guān)成果，采用樹型結(jié)構(gòu)對(duì)平面網(wǎng)格結(jié)構(gòu)中的格室進(jìn)行索引，用簡(jiǎn)單的數(shù)學(xué)運(yùn)算代替復(fù)雜的乘方開放運(yùn)算，破除了原始CPM算法中性能提升的瓶頸，同時(shí)使用數(shù)據(jù)流系統(tǒng)中的滑動(dòng)窗口模型對(duì)算法進(jìn)行進(jìn)一步的改進(jìn)，并最終提升了算法的執(zhí)行效率。另外，在此基礎(chǔ)上，又提出了期望距離的概念，將最近鄰查詢算法擴(kuò)展到非確定對(duì)象領(lǐng)域，并提出了空間數(shù)據(jù)中非確定對(duì)象的最近鄰查詢方法。主要內(nèi)容包括：⑴使用數(shù)據(jù)流技術(shù)中的滑動(dòng)窗口模型對(duì)連續(xù)的

4、最近鄰查詢進(jìn)行優(yōu)化，并提高了連續(xù)最近鄰查詢的效率；⑵用簡(jiǎn)單的數(shù)學(xué)運(yùn)算代替復(fù)雜的乘方開方運(yùn)算，減少最近鄰查詢算法中大量復(fù)雜的歐氏距離計(jì)算；⑶采用樹形結(jié)構(gòu)對(duì)格室進(jìn)行索引，使算法能夠盡早淘汰掉對(duì)查詢結(jié)果不產(chǎn)生影響的格室，降低算法的處理代價(jià)；⑷提出了針對(duì)非確定對(duì)象的最近鄰查詢方法，使算法更加適用于實(shí)際場(chǎng)景；⑸設(shè)計(jì)并實(shí)現(xiàn)了基于位置服務(wù)的最近鄰查詢?cè)拖到y(tǒng)，并對(duì)其中移動(dòng)對(duì)象組件、位置服務(wù)器和顯示終端的設(shè)計(jì)與實(shí)現(xiàn)方法進(jìn)行詳細(xì)介紹。整個(gè)原型系統(tǒng)主要用于