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

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

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

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

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