一種高效的GNN查詢算法的研究

黃 凱

（福建省特種設(shè)備檢驗(yàn)研究院泉州分院，福建 泉州 362000）

一種高效的GNN查詢算法的研究

黃 凱

（福建省特種設(shè)備檢驗(yàn)研究院泉州分院，福建 泉州 362000）

給定集合P和Q，則GNN查詢返回的是P中的對(duì)象p，p滿足到Q中所有對(duì)象的距離的集合函數(shù)f最小。求GNN的方法有多種，文章提出了vp-GNN算法，其特點(diǎn)在于不采用任何索引的情況下，也能高效地對(duì)空間數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行裁剪，縮小查詢區(qū)域、提高GNN的查詢效率。

空間數(shù)據(jù)庫(kù)；最近鄰；集合最近鄰

1 背景

數(shù)據(jù)挖掘（Data Mining）是指從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際應(yīng)用中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識(shí)的過(guò)程。它實(shí)質(zhì)是一種知識(shí)發(fā)現(xiàn)的過(guò)程。[1]

在數(shù)據(jù)挖掘中，相關(guān)性查詢是一種極為重要的查詢問(wèn)題。通常情況下，人們?cè)谘芯績(jī)蓚€(gè)對(duì)象之間的相關(guān)性時(shí)，都用對(duì)象之間的距離來(lái)衡量。在大量的數(shù)據(jù)中，尤其是在空間數(shù)據(jù)庫(kù)中，最近鄰查詢就經(jīng)常被用于求兩個(gè)對(duì)象之間的相關(guān)性。然而要在整個(gè)空間數(shù)據(jù)庫(kù)中求最近鄰并不是一件容易的事，它需要花費(fèi)大量的時(shí)間和空間。因此為了減少查詢所需要的時(shí)間以及縮小查詢的空間范圍，人們引進(jìn)了各種各樣的空間索引[2]，如：R-tree、R*-tree等。

集合最近鄰查詢[3]是空間數(shù)據(jù)庫(kù)中一種新的查詢方法，其實(shí)質(zhì)是從最近鄰查詢方法中演變而來(lái)的。但是因?yàn)榧献罱彶樵兊牟樵凕c(diǎn)是多個(gè)而不像最近鄰查詢那樣查詢點(diǎn)只有一個(gè)，因此它比最近鄰查詢要復(fù)雜得多。常見(jiàn)的GNN[4]方法有MQM、SPM、MBM[5]等，它們基本能夠很好的解決低維空間數(shù)據(jù)庫(kù)的GNN查詢問(wèn)題。不過(guò)，它們基本都是通過(guò)借助“索引”來(lái)對(duì)空間數(shù)據(jù)庫(kù)進(jìn)行裁剪，這往往會(huì)因?yàn)樗饕旧淼臉O限性而影響GNN算法的效率。

2 vp-GNN算法

在接下來(lái)的討論中，假設(shè)空間數(shù)據(jù)庫(kù)為二維的；假設(shè)對(duì)象之間的距離用歐氏距離表示，不考慮對(duì)象本身可能帶有的權(quán)值；并且假設(shè)集合函數(shù)f為求和函數(shù)sum。不過(guò)，這不能就說(shuō)明接下來(lái)討論的方法就只適合滿足上述假設(shè)條件的查詢，它們同樣適用于多維空間數(shù)據(jù)庫(kù)和f是其它單調(diào)遞增的集合函數(shù)。

2.1 算法的基本思想

圖1 最小包圍矩形的外接圓

這種方法在集合P和Q都均勻分布在歐氏空間的情況下，一般都能找到正確結(jié)果，但是并不能證明落在區(qū)域內(nèi)的候選點(diǎn)一定就是GNN查詢的結(jié)果，也可能存在某一點(diǎn)，其中，但滿足，也即雖然 落在裁剪區(qū)域之外，卻為GNN查詢的結(jié)果。因此就有必要將裁剪所得的區(qū)域進(jìn)行放大，這在更新的vp-GNN算法中將進(jìn)行了討論。

另外，在vp-GNN方法中需要求查詢集合Q的質(zhì)心q_center。質(zhì)心的求解公式如下：

不過(guò)，雖然公式（1）和公式（2）求解的質(zhì)心精確度很高，但它只適合于當(dāng)?shù)目臻g數(shù)據(jù)，當(dāng)n＞2時(shí)，它就不再是一個(gè)好的方法了。為了解決n＞2時(shí)高效的求Q的質(zhì)心的問(wèn)題，人們引入了一種通過(guò)降低質(zhì)心的精確度，來(lái)降低計(jì)算的復(fù)雜度的方法。引入的求質(zhì)心的新公式如下：

2 . 2 算法流程

（2）求查詢集合Q的質(zhì)心q_center；

（3）求q_center在被查詢集合P中的最近鄰vp；

（5）求MBR的外接圓的圓心；

（6）求MBR的外接圓的半徑；

（8）在裁剪區(qū)域R中求GNN的結(jié)果。

2.3 算法的復(fù)雜度

（1）從時(shí)間復(fù)雜度方面講，求Q的質(zhì)心q_center的時(shí)間復(fù)雜度為O（n），其中n表示Q中包含的點(diǎn)的個(gè)數(shù)；而在求q_center在P中的最近鄰時(shí)，它的時(shí)間復(fù)雜度為O（N），其中N表示P中包含的點(diǎn)的個(gè)數(shù)；求最小包圍矩形MBR的左上頂點(diǎn)和右上頂點(diǎn)的時(shí)間復(fù)雜度為O（n+1）；在計(jì)算MBR的圓心和半徑的時(shí)間復(fù)雜度都為O（1）；對(duì)集合P的裁剪的時(shí)間復(fù)雜度為O（N）；在裁剪區(qū)域R中求GNN的結(jié)果的時(shí)間復(fù)雜度最大不會(huì)超過(guò)O（N）。又因?yàn)榧螾中具包含大量的數(shù)據(jù)點(diǎn)，一般遠(yuǎn)遠(yuǎn)大于Q的中的點(diǎn)，所以vp-GNN算法的時(shí)間復(fù)雜度為可近似的表示為O（N）。

（2）從空間復(fù)雜度方面講，vp-GNN算法中主要的空間消耗是在于集合P、Q和R。因?yàn)榧蟁一般都會(huì)小于P，最壞情況等于P，而集合Q是會(huì)遠(yuǎn)遠(yuǎn)小于P，因此vp-GNN的空間復(fù)雜度也可近似的用O（N）表示。

3 改進(jìn)的vp-GNN算法

3.1 算法的基本思想

3.2 算法流程

（2）求查詢集合Q的質(zhì)心q_center；

（3）求q_center在被查詢集合P中的最近鄰vp；

（5）求MBR外接圓的圓心和半徑r；

（7）求出新的裁剪區(qū)域C(o,г＇)，并令R= C(o,г＇)；

（8）在裁剪區(qū)域R中求GNN的結(jié)果。

3.3 算法核心代碼

3.4 算法的復(fù)雜度

（1）因?yàn)楦潞蟮膙p-GNN方法只是將vp-GNN方法的裁剪區(qū)域的半徑進(jìn)行放大，并沒(méi)有其他額外的操作，因此它在時(shí)間復(fù)雜度方面與vp-GNN的時(shí)間復(fù)雜度是一致的，即也近似等于O（N）。

（2）另外，由于更新后的vp-GNN方法放大了裁剪區(qū)域的半徑，所以整個(gè)裁剪后的區(qū)域會(huì)比vp-GNN方法裁剪去來(lái)的區(qū)域來(lái)得大，因此更新后的vp-GNN的空間復(fù)雜度會(huì)比vp-GNN的空間復(fù)雜度高些。但是因?yàn)椴眉艉蟮膮^(qū)域R仍然不會(huì)大于集合P，所以同樣可以用O（N）來(lái)表示更新后的vp-GNN的空間復(fù)雜度。

4 結(jié)束語(yǔ)

當(dāng)集合P固定時(shí)，不管是集合Q中點(diǎn)的個(gè)數(shù)、集合Q的區(qū)間大小、還是空間數(shù)據(jù)庫(kù)的維數(shù)的高低都會(huì)影響裁剪區(qū)域中所包含的點(diǎn)的個(gè)數(shù)。并且當(dāng)集合Q中點(diǎn)的個(gè)數(shù)越多、或集合Q的區(qū)間大小越大、或者空間數(shù)據(jù)庫(kù)的維數(shù)越多時(shí)，裁剪出來(lái)的區(qū)域所包含的點(diǎn)的個(gè)數(shù)也就越多。但是從求取GNN所需要的CPU時(shí)間方法來(lái)看，能夠得到不管vp-GNN裁剪出來(lái)的區(qū)域是怎么樣的，它們都比MQM方法所需要的CPU時(shí)間來(lái)得短。

文中提出的改進(jìn)的vp-GNN算法，雖然較傳統(tǒng)算法效率要高，但在衡量?jī)蓚€(gè)對(duì)象之間的相關(guān)度，還簡(jiǎn)限在用歐氏距離來(lái)表示。文章今后的研究方向?qū)⒓尤雽?duì)對(duì)象本身帶有的權(quán)值、對(duì)移動(dòng)對(duì)象的查詢以及對(duì)高維的空間數(shù)據(jù)庫(kù)等方面的考慮，使得該算法能更好地應(yīng)用于工程實(shí)踐。

[1] Jiawei Han, Micheline Kamber著，范明，猛小峰，譯.數(shù)據(jù)挖掘概念與技術(shù)（第二版）[M]，機(jī)械工業(yè)出版社，2007.3.

[2] Z. Song and N. Roussopoulos. K-Nearest Neighbor Search for Moving Object[J]. In VLDB 2001: 287-298.

[3] Papadias, D., Tao, Y., Mouratidis, K., Hui, C.K.: Aggregate Nearest Neighbor Queries in spatial database[J]. ACM Trans. Database Syst. 30(2) 2005: 529-576.

[4] Li, H., Lu, H., Huang, B., Huang, Z.: Two Ellipse-based Pruning Methods for Group Nearest Neighbor Queries[J]. In: GIS 2005: 192-199.

[5] Papadias, D., Shen, Q., Tao, Y., Mouratidis, K.: Group Nearest Neighbor Queries[J]. In: ICDE 2004: 301-312.

Research on an Efficient Method for GNN Query Algorithm

HUANG Kai
( Fujian Special Equipment Inspection and Research Institute,Quanzhou Branch Institute,Quanzhou 362000, Fujian, China)

Given a collection of P and Q, then GNN is returned by the query object p in P, p meets to set function all objects in the Q f the minimum distance. There are several methods for GNN. This paper raises the vp-GNN algorithm, which is characterized in that does not use any index case, also can effectively cut to spatial data in the database, reduce the search area and improve the efficiency of GNN query.

Spatial database; Nearest neighbor; Group nearest neighbor

2014-03-25

黃 凱，男，福建省特種設(shè)備檢驗(yàn)研究院泉州分院，工程師，碩士