基于Hibert曲線的查詢方法研究.pdf

1、空間填充曲線有很多種，如Sierpinski曲線、Lebesgue曲線、Schoenberg空間填充曲線、具有正Lebesgue測(cè)度的Jordan曲線等.在眾多空間填充曲線中最常用的是Hilbert曲線，Z曲線以及Gray曲線，它們的主要區(qū)別在于映射的方法不同.近些年來，空間填充曲線因其特有的降低維度特性和數(shù)據(jù)聚類特性而被用于空間數(shù)據(jù)庫的索引及查詢之中.在空間填充曲線被應(yīng)用于空間數(shù)據(jù)庫以前，最常用的索引方法是基于R樹及其變形樹的索引結(jié)構(gòu)

2、.在二維空間中基于R樹的最近鄰查詢算法和順序掃描算法具有較高的查詢效率.隨著空間維度的增加，數(shù)據(jù)信息量呈幾何級(jí)數(shù)增加，此時(shí)以上兩種算法的查詢效率急劇下降.因此，可以利用Hilbert曲線的降維和聚類特性，將高維空間中的點(diǎn)映射一一映射到一維空間中，這樣不僅不影響點(diǎn)與點(diǎn)之間的距離比較，而且對(duì)最近鄰查詢及其他查詢有較高的查詢效率.
　　本文首先引入Hilbert曲線、分析Hilbert曲線性質(zhì)及特性、重點(diǎn)總結(jié)降維及聚類特性.
　　

3、其次提出一種基于Hilbert曲線網(wǎng)格劃分的最近鄰查詢算法.該算法首先將數(shù)據(jù)空間分成不重疊且相等的網(wǎng)格，然后把網(wǎng)格中的點(diǎn)進(jìn)行線性排序，最后當(dāng)要獲取最近鄰時(shí)，只需訪問查詢點(diǎn)所在網(wǎng)格中的點(diǎn)以及其周邊臨近網(wǎng)格中的點(diǎn)即可.
　　最后提出一種基于Hilbert曲線的最優(yōu)位置查詢算法.該算法首先將空間中的點(diǎn)利用Hilbert曲線的降維特性映射到一維空間，然后分別利用基于R樹的范圍查詢算法，將所有的數(shù)據(jù)對(duì)象和目標(biāo)對(duì)象保存在兩個(gè)隊(duì)列中，最后從目標(biāo)