本文關(guān)鍵詞：高維空間的K最近鄰查詢及連接問(wèn)題研究，由筆耕文化傳播整理發(fā)布。

【摘要】：多年來(lái)，相當(dāng)數(shù)量的研究工作集中在索引多維數(shù)據(jù)。相比于一維的情況下，設(shè)計(jì)多維存取方法是困難的，因?yàn)闆](méi)有保留空間的局部性的總序。對(duì)于一個(gè)給定的多維空間數(shù)據(jù)庫(kù)，一旦我們找到了一個(gè)總的序，我們可以利用簡(jiǎn)單的眾所周知的一維的訪問(wèn)方法，例如B+樹(shù)，可以達(dá)到良好的查詢性能。一個(gè)映射的解決方案是通過(guò)空間填充曲線�？臻g填充曲線已被用于在各種領(lǐng)域，包括數(shù)據(jù)庫(kù)系統(tǒng)，科學(xué)計(jì)算，地理信息系統(tǒng)和圖像處理。它們給出點(diǎn)的坐標(biāo)和在曲線上的點(diǎn)的一維的序列號(hào)之間的一一對(duì)應(yīng)的關(guān)系。在大多數(shù)情況下，應(yīng)用一直局限于Z曲線。然而，大多數(shù)以前的工作從理論上表明， Hilbert曲線相比其它曲線表現(xiàn)優(yōu)異的數(shù)據(jù)聚類的性能。為了減少額外的尋道時(shí)間，它更有效地獲取一組連續(xù)的磁盤塊，而不是一個(gè)隨機(jī)的分散設(shè)置。因此，這是可取的，在多維屬性空間接近的物體也是在一維的磁盤空間接近。在一維序列磁盤塊上的多維數(shù)據(jù)點(diǎn)的好的聚類性質(zhì)可以減少對(duì)于范圍查詢所需的磁盤訪問(wèn)次數(shù)。本文基于空間填充曲線的Hilbert曲線，采用隨機(jī)移位的方法解決K近鄰查詢和K近鄰連接問(wèn)題。在數(shù)據(jù)挖掘和數(shù)據(jù)分析中廣泛用到K近鄰查詢和K近鄰連接，尤其是K近鄰連接是K近鄰查詢和連接操作的聯(lián)合，比較復(fù)雜。MapReduce是在一簇計(jì)算節(jié)點(diǎn)之間利用并行機(jī)制處理大規(guī)模數(shù)據(jù)集的編程模型，由于其簡(jiǎn)單、靈活、容錯(cuò)性等優(yōu)點(diǎn)在出現(xiàn)之后得到廣泛流行，，現(xiàn)在商業(yè)和科學(xué)計(jì)算中廣泛應(yīng)用。我們也進(jìn)一步討論了MapReduce編程模型中K近鄰連接問(wèn)題的解決方案。本文對(duì)于數(shù)據(jù)挖據(jù)領(lǐng)域中的許多應(yīng)用具有一定的借鑒意義。下面介紹本文的主要研究工作。 使用Hilbert曲線，可以將多維空間中的點(diǎn)映射到一維空間。對(duì)于一個(gè)查詢點(diǎn)，可以將KNN搜索轉(zhuǎn)換為該點(diǎn)的Hilbert值的范圍搜索。Hilbert曲線不能始終保持空間局部性，它會(huì)導(dǎo)致最終的答案可能出現(xiàn)潛在錯(cuò)誤。首先，我們使用隨機(jī)變換方法，獨(dú)立生成輸入數(shù)據(jù)集的隨機(jī)變換的版本，在每個(gè)隨機(jī)變換的復(fù)本上，重復(fù)執(zhí)行KNN搜索。在實(shí)驗(yàn)中只需要O（1）的轉(zhuǎn)變，可以發(fā)現(xiàn)對(duì)于KNN查詢實(shí)驗(yàn)中給出很好的近似質(zhì)量。這種方法可以降低錯(cuò)誤發(fā)生的概率。此外，Hilbert曲線表現(xiàn)優(yōu)異的數(shù)據(jù)聚類性能，從而減少額外的尋道時(shí)間。最后，只創(chuàng)建一次隨機(jī)轉(zhuǎn)移表，可用于多次不同的查詢。HKNN方法也是較好的選擇。 K近鄰連接是k近鄰查詢和連接操作的組合，K近鄰連接作為一個(gè)基本操作，在許多數(shù)據(jù)挖掘中應(yīng)用。近年來(lái)，研究人員對(duì)于高維數(shù)據(jù)的K近鄰連接十分感興趣。通過(guò)Hilbert曲線的方式，可以映射多維空間中的點(diǎn)到一維空間。然而，有時(shí)Hilbert曲線可能會(huì)存在潛在的錯(cuò)誤，不能始終保持空間局部性。本文獨(dú)立制作輸入數(shù)據(jù)集的隨機(jī)變換版本，通過(guò)隨機(jī)移位操作，我們把數(shù)據(jù)變換幾次。對(duì)于每個(gè)隨機(jī)變換的副本，執(zhí)行K近鄰連接操作，我們更傾向于通過(guò)看每個(gè)轉(zhuǎn)移列表的查詢點(diǎn)的Hilbert的前驅(qū)和后繼者，找到真正的最近鄰。檢查一個(gè)以上的前驅(qū)和后繼者，可以提高近似的質(zhì)量，取得更好的結(jié)果。雖然HKNNJ算法并沒(méi)有zχ-kNNJ算法速度快，但是它具有較好的聚類性能和實(shí)際應(yīng)用價(jià)值。因此它也是一個(gè)更好的選擇。 在許多數(shù)據(jù)挖掘應(yīng)用中廣泛使用K近鄰連接，它是一個(gè)基本操作，對(duì)一個(gè)數(shù)據(jù)集R中的每一條記錄，它可以從另一個(gè)數(shù)據(jù)集S中找到它的k最近鄰。這個(gè)操作的難度很大，執(zhí)行起來(lái)也很耗時(shí)。隨著維數(shù)的增加，對(duì)于大多數(shù)的數(shù)據(jù)集最近和最遠(yuǎn)的鄰居的距離迅速下降很快，這也就是所謂的維數(shù)災(zāi)難。在大型集群中，MapReduce是一種有效的、故障容錯(cuò)、負(fù)載分布均衡的框架，在本文中，我們研究如何利用Hilbert曲線在MapReduce中實(shí)現(xiàn)K近鄰連接操作。我們提出了一個(gè)三階段的方法并考察了每個(gè)階段。對(duì)于我們提出的算法，我們?cè)贖adoop上實(shí)現(xiàn)，并在真實(shí)數(shù)據(jù)集上分析其性能特征。 本文最后，我們?cè)贛apReduce框架繼續(xù)研究了KNN連接問(wèn)題。解決K近鄰連接的一種直接的方法就是采用塊嵌套循環(huán)的方法。其主要思想是劃分R和S到若干大小相等的塊，對(duì)每一個(gè)可能的塊（一個(gè)來(lái)自R，另一個(gè)來(lái)自S）被劃分到一個(gè)桶。使用嵌套循環(huán)，在那個(gè)桶里能找到在本地塊R的每個(gè)記錄的在本地塊S中的K最近鄰。桶加載R樹(shù)是高效的，在R樹(shù)實(shí)現(xiàn)K近鄰搜索也是高效的。在這基礎(chǔ)上，我們?yōu)橥皟?nèi)局部的S塊建立Hilbert R樹(shù)索引，來(lái)幫助找到相同桶內(nèi)的K近鄰。大量的實(shí)驗(yàn)表明，我們提出的方法是有效的和可擴(kuò)展的。
【關(guān)鍵詞】：K近鄰 Hilbert曲線 空間填充曲線 K近鄰連接 MapReduce Hilbert R樹(shù)
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP311.13
【目錄】：

• 摘要5-7
• Abstract7-13
• 第1章 緒論13-19
• 1.1 研究背景13-16
• 1.1.1 多維數(shù)據(jù)13
• 1.1.2 多維索引方法13-15
• 1.1.3 空間填充曲線方法15-16
• 1.2 研究意義16
• 1.3 本文主要工作16-17
• 1.4 本文組織結(jié)構(gòu)17-19
• 第2章 基礎(chǔ)知識(shí)19-33
• 2.1 空間多維曲線19-23
• 2.2 Hilbert 曲線23-29
• 2.2.1 Hilbert 曲線背景23
• 2.2.2 Hilbert 曲線相關(guān)工作23-28
• 2.2.3 Hilbert 曲線的繪制方式28-29
• 2.3 OpenStreetMap 數(shù)據(jù)集29-32
• 2.4 本章小結(jié)32-33
• 第3章 基于 Hilbert 曲線的 KNN 查詢33-45
• 3.1 引言33
• 3.2 k 近鄰定義及性質(zhì)33-39
• 3.2.1 符號(hào)與特性33-35
• 3.2.2 形式化定義35-36
• 3.2.3 k 近鄰性質(zhì)36-39
• 3.3 利用隨機(jī)位移的近似 KNN 算法39-41
• 3.4 實(shí)驗(yàn)結(jié)果與分析41-44
• 3.4.1 實(shí)驗(yàn)設(shè)置和數(shù)據(jù)集41
• 3.4.2 實(shí)驗(yàn)結(jié)果41-44
• 3.5 本章小結(jié)44-45
• 第4章 基于 Hilbert 曲線的 KNN 連接45-55
• 4.1 引言45
• 4.2 相關(guān)工作45-46
• 4.3 K 近鄰連接定義及性質(zhì)46
• 4.4 蠻力算法46-48
• 4.5 隨機(jī)變換處理 KNN 連接48-50
• 4.5.1 隨機(jī)變換48-49
• 4.5.2 KNN 連接的過(guò)程49-50
• 4.6 實(shí)驗(yàn)結(jié)果與分析50-53
• 4.6.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集50-51
• 4.6.2 實(shí)驗(yàn)結(jié)果51-53
• 4.7 本章小結(jié)53-55
• 第5章 基于 MapReduce 的 KNN 連接55-65
• 5.1 引言55-56
• 5.2 相關(guān)工作56
• 5.3 MapReduce 框架56-59
• 5.4 KNN 連接過(guò)程59-61
• 5.4.1 劃分值59-60
• 5.4.2 本地的 KNN60-61
• 5.4.3 全局 KNN61
• 5.5 實(shí)驗(yàn)結(jié)果與分析61-63
• 5.5.1 實(shí)驗(yàn)設(shè)置和數(shù)據(jù)集61
• 5.5.2 實(shí)驗(yàn)結(jié)果61-63
• 5.6 本章小結(jié)63-65
• 第6章 基于 Hilbert R 樹(shù)的 KNN 連接65-75
• 6.1 引言65
• 6.2 相關(guān)工作65-66
• 6.3 Hilbert R 樹(shù)66-67
• 6.4 并行塊嵌套循環(huán)的 KNN 連接67-69
• 6.5 基于 Hilbert R 樹(shù)的 KNN 連接69-70
• 6.6 實(shí)驗(yàn)結(jié)果與分析70-73
• 6.6.1 實(shí)驗(yàn)設(shè)置和數(shù)據(jù)集70
• 6.6.2 實(shí)驗(yàn)結(jié)果70-73
• 6.7 本章小結(jié)73-75
• 第7章 結(jié)論與展望75-77
• 7.1 本文的工作75-76
• 7.2 未來(lái)工作展望76-77
• 參考文獻(xiàn)77-85
• 作者簡(jiǎn)介及在學(xué)期間所取得的科研成果85-86
• 致謝86

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 徐紅波;郝忠孝;;一種基于Z曲線近似k-最近對(duì)查詢算法[J];計(jì)算機(jī)研究與發(fā)展;2008年02期

2 崔杰;李陶深;蘭紅星;;基于Hadoop的海量數(shù)據(jù)存儲(chǔ)平臺(tái)設(shè)計(jì)與開(kāi)發(fā)[J];計(jì)算機(jī)研究與發(fā)展;2012年S1期

3 徐紅波;郝忠孝;;基于空間填充曲線網(wǎng)格劃分的最近鄰查詢算法[J];計(jì)算機(jī)科學(xué);2010年01期

4 徐紅波;郝忠孝;;基于Hilbert曲線的高維k-最近對(duì)查詢算法[J];計(jì)算機(jī)工程;2008年02期

5 徐紅波;郝忠孝;;基于Hilbert曲線的近似k-最近鄰查詢算法[J];計(jì)算機(jī)工程;2008年12期

6 何小苑;閔華清;;基于聚類的Hilbert R-樹(shù)空間索引算法[J];計(jì)算機(jī)工程;2009年09期

7 徐紅波;;空間填充曲線映射算法研究[J];科技信息(科學(xué)教研);2007年35期

8 劉俊嶺;孫煥良;;多維度量空間中發(fā)現(xiàn)相互kNN(英文)[J];計(jì)算機(jī)科學(xué)與探索;2010年10期

9 楊景濤;吳立德;;帶聚類的Hilbert R-樹(shù)建樹(shù)算法[J];模式識(shí)別與人工智能;2001年01期

10 林偉偉;劉波;;基于動(dòng)態(tài)帶寬分配的Hadoop數(shù)據(jù)負(fù)載均衡方法[J];華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年09期

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前2條

1 徐紅波;基于空間填充曲線高維空間查詢算法研究[D];哈爾濱理工大學(xué);2010年

2 袁培森;基于LSH的Web數(shù)據(jù)相似性查詢研究[D];復(fù)旦大學(xué);2011年

  本文關(guān)鍵詞：高維空間的K最近鄰查詢及連接問(wèn)題研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：283291