最近鄰查詢

最近鄰查詢

在地理系統中,最近鄰查詢是最常遇見的查詢。它是不同於點查詢(Point Queries)和範圍查詢的另一類查詢方法 ,用來找出空間中距離一給定點最近的對象即最近鄰,最近鄰的數目可以是1個,也可以是多個,即k-NN查詢。例如,在地理信息系統對一個特定的位置或者目標,要求系統查找並返回5個離它最近的對象。

簡介

我們知道,物體的重心是在某些情況下對其施加作用力最有效的點,下面介紹的內容就是基於這個原理的,將多個對象接合成一個統一體,然後找出它們的重心點。這裡以二維空間為例,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最近鄰查詢。

相關詞條

熱門詞條

聯絡我們