在地理系統中，最近鄰查詢是最常遇見的查詢。它是不同於點查詢(Point Queries)和範圍查詢的另一類查詢方法 ，用來找出空間中距離一給定點最近的對象即最近鄰，最近鄰的數目可以是1個，也可以是多個，即k-NN查詢。例如，在地理信息系統對一個特定的位置或者目標,要求系統查找並返回5個離它最近的對象。
基本介紹
- 中文名：最近鄰查詢
- 外文名：(the Nearest Neighbor,NN
- 領域：計算機科學
- 同種算法：範圍查詢
- 簡介：找出空間中距離最近的對象
- 套用：地理系統
簡介,K個點的NN查詢,K個區域對象的NN查詢,
簡介
我們知道，物體的重心是在某些情況下對其施加作用力最有效的點，下面介紹的內容就是基於這個原理的，將多個對象接合成一個統一體，然後找出它們的重心點。這裡以二維空間為例，K個對象的NN查詢可分為2種情況:K個點和K個區域對象的NN查詢。
K個點的NN查詢
設二維空間K個點，它們的坐標分別是P1(x1，y1), P2(x2, y2),⋯ ,Pk(xk，yk)。由這K個點組成平面圖形，我們考慮各個查詢點權重都是一樣的，不一樣的情況可以利用加權來擴展，因為外形規則密度均勻物體的重心就是它的幾何中心，則定義這K個點的重心為O，而且O的每維上的坐標為K個點的對應維上的坐標的平均值，即:O=(x，y)。由此，定義K個點的NN為它們的重心點O的NN，這樣，給定K個點對它進行NN查詢也就轉化為對一個點的NN查詢。
K個區域對象的NN查詢
在R樹中存儲的是高維區域對象的最小邊界框，這裡所指的也是這樣的區域對象，不論它是什麼形狀，都用它的MBR表示，即K個MBR來表示K個區域對象。我們的思想是，首先，計算出每個MBR的中心點坐標O1 ，O2 ，⋯，Ok，其中Oi=((xilow+xihigh)/2，(yilow+yihigh)/2) (1≤i≤k)然後以中心點代表每個MBR，求出所有K箇中心點的重心坐標，如上所述，即把K個區域對象轉化為K個點，然後實施上面的查詢方法。可以看出，K個點的NN查詢是K個區域對象NN查詢的特例,即它們的中心點就是該點本身。TPR樹和靜態環境中基本的最近鄰查詢算法,並提出了影響時間這一概念,將其運用到最近鄰查詢算法中,可以完成移動對象的連續最近鄰查詢。
生物網路、社會網路、交際網路 等複雜的網路被廣泛的研究,由於數據抽出時引入的噪聲和錯誤使這些數據具有不確定性,因此可以對這些套用使用不確定圖模型建模,k最近鄰查詢問題是查詢一 個圖上的距離某個特定點最近的k個鄰居節點的問題,它是不確定圖上的一個基礎問題.設計了一個解決不確定圖上最近鄰問題的框架,首先定義了一種新穎的不確 定圖上的k最近鄰查詢,然後提出了針對該查詢的一般處理算法,同時對該算法進行了最佳化,使算法效率得到極大提高.理論分析和實驗結果表明提出的算法能夠高 效地處理不確定圖上的k最近鄰查詢。
