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

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

【參考文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號：283291