面向移動對象實時跟蹤的查詢優(yōu)化算法的研究.pdf

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

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

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

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