空間網(wǎng)絡(luò)數(shù)據(jù)庫(kù)中最近鄰查詢技術(shù)的研究.pdf

1、最近鄰(NN)查詢技術(shù)是空間數(shù)據(jù)庫(kù)領(lǐng)域中一個(gè)重要的研究課題。k-NN查詢計(jì)算距離一個(gè)給定的查詢點(diǎn)最近的k個(gè)對(duì)象。由于定位裝置的廣泛應(yīng)用和定位服務(wù)的增加，對(duì)空間網(wǎng)絡(luò)數(shù)據(jù)庫(kù)中靜態(tài)k-NN查詢、移動(dòng)數(shù)據(jù)的連續(xù)k-NN監(jiān)視技術(shù)的研究已經(jīng)成為空間數(shù)據(jù)庫(kù)領(lǐng)域的熱點(diǎn)課題。 本文首先介紹了現(xiàn)有的空間數(shù)據(jù)索引技術(shù)，對(duì)k-NN查詢及監(jiān)視技術(shù)的研究現(xiàn)狀進(jìn)行了分析。 其次，提出了一個(gè)空間網(wǎng)絡(luò)數(shù)據(jù)兩層存儲(chǔ)模式，將網(wǎng)絡(luò)與興趣數(shù)據(jù)集分開存儲(chǔ)，并討論了

2、其各個(gè)組件，對(duì)其易于擴(kuò)展性進(jìn)行了分析。 再次，提出了增量k-NN查詢算法(IkNNQA)，實(shí)現(xiàn)了查詢結(jié)果的真正增量輸出。更進(jìn)一步，為了提高查詢速度，提出了基于“預(yù)計(jì)算”的k-NN查詢算法(PkNNQA)。它們共同解決了空間網(wǎng)絡(luò)數(shù)據(jù)庫(kù)中靜態(tài)的k-NN查詢問題。 然后，對(duì)空間網(wǎng)絡(luò)數(shù)據(jù)庫(kù)中動(dòng)態(tài)的k-NN監(jiān)視問題進(jìn)行了深入研究，提出了增量監(jiān)視算法(IkNNMA)和群組監(jiān)視算法(GkNNMA)。IkNNMA以擴(kuò)展樹的形式存儲(chǔ)在NN

3、搜索期間遇到的網(wǎng)絡(luò)節(jié)點(diǎn)的最短路徑，只更新使查詢q的NN集發(fā)生改變的落在擴(kuò)展樹之內(nèi)的對(duì)象和邊的更新，不相關(guān)的更新被忽略；另一方面，當(dāng)更新影響到q的結(jié)果或者當(dāng)q移動(dòng)到一個(gè)新的位置時(shí)，IkNNMA保持?jǐn)U展樹的有效部分并加以利用來加速q的新的NNs的計(jì)算。而GkNNMA采用共享策略減少處理時(shí)間，它將落在網(wǎng)絡(luò)兩個(gè)連續(xù)的交叉點(diǎn)間的路徑上的查詢聚集起來，通過監(jiān)視這些交叉點(diǎn)的NN集來生成結(jié)果，從而將監(jiān)視移動(dòng)查詢轉(zhuǎn)化為監(jiān)視靜態(tài)的網(wǎng)絡(luò)節(jié)點(diǎn)，精簡(jiǎn)了問題。