時(shí)空數(shù)據(jù)庫(kù)新理論文摘

時(shí)間：2023-04-01 00:26:02 | 來(lái)源：營(yíng)銷百科

時(shí)間：2023-04-01 00:26:02 來(lái)源：營(yíng)銷百科

時(shí)空數(shù)據(jù)庫(kù)新理論文摘：版權(quán)頁(yè)：



插圖：



第2章 空間數(shù)據(jù)庫(kù)幾種查詢方法
2.1基于R—樹(shù)的最近鄰查詢理論基礎(chǔ)
空間數(shù)據(jù)庫(kù)系統(tǒng)是描述、存儲(chǔ)和處理空間數(shù)據(jù)及其屬性數(shù)據(jù)的數(shù)據(jù)庫(kù)系統(tǒng)?？臻g數(shù)據(jù)庫(kù)基本功能包括三個(gè)方面：①對(duì)空間數(shù)據(jù)的存儲(chǔ)；②對(duì)空間數(shù)據(jù)查詢的支持；③對(duì)空間數(shù)據(jù)分析推理。
最近鄰查詢?cè)诂F(xiàn)實(shí)中有著廣泛的應(yīng)用價(jià)值。最近鄰查詢主要有：最近鄰查詢、k最近鄰查詢、近似最近鄰查詢、最近對(duì)查詢、組最近鄰查詢、反向最近鄰查詢、約束最近鄰查詢、全部最近鄰查詢等。
空間數(shù)據(jù)庫(kù)的最近鄰查詢是用來(lái)找出空間中距離一個(gè)給定點(diǎn)最近的對(duì)象即最近鄰，最近鄰的個(gè)數(shù)可以是一個(gè)，即NN查詢；也可以是k個(gè)，即kNN查詢。
空間操作的算法有三個(gè)必須考慮的要點(diǎn)：算法的正確性、CPU的代價(jià)、I／O代價(jià)。這就促使算法的設(shè)計(jì)過(guò)程比關(guān)系數(shù)據(jù)庫(kù)中的算法設(shè)計(jì)過(guò)程更為復(fù)雜。而在關(guān)系數(shù)據(jù)庫(kù)中，通常只考慮算法的時(shí)間復(fù)雜度。
最近鄰查詢?cè)趯?shí)際應(yīng)用中，尤其是在空間數(shù)據(jù)庫(kù)中，已經(jīng)變得越來(lái)越重要。而且對(duì)最近鄰查詢概念的擴(kuò)展，即對(duì)象的相似性查詢也具有非常廣泛的應(yīng)用前景。由于利用定點(diǎn)查詢、范圍查詢已不能很好地解決最近鄰查詢的問(wèn)題，人們提出了針對(duì)最近鄰查詢的多種方法。其中包括基于R—樹(shù)的深度優(yōu)先遍歷R—樹(shù)的DF算法和順序遍歷R—樹(shù)的BF算法。
2.1.1最近鄰查詢的定義
最近鄰查詢是區(qū)別于點(diǎn)的定點(diǎn)查詢和范圍查詢的新的查詢類型。
在給出最近鄰查詢的形式化定義之前，先介紹相關(guān)的符號(hào)表示，任意兩點(diǎn)P和q之間的距離用D（p，q）表示，而用C（q，r）表示以q為圓心，r為半徑的圓。如果T是某數(shù)據(jù)空間的子集，D（q，T）表示q到T中任意一點(diǎn)的距離的最小值。
最近鄰查詢問(wèn)題的解決方案還與數(shù)據(jù)空間S和距離函數(shù)D的選擇相關(guān)，下面的選擇是在n維歐氏空間Rn上進(jìn)行的，而且Rn上的距離函數(shù)也是歐氏距離L2。同樣，后面也使用這種選擇。下面給出最近鄰查詢的形式化定義。