函數(shù)依賴是重要的元數(shù)據(jù),用于描述數(shù)據(jù)集中列之間的關(guān)系,可以被用于很多任務(wù)中,例如范式結(jié)構(gòu)標(biāo)準(zhǔn)化,數(shù)據(jù)清洗等。很多單機(jī)和并行函數(shù)依賴發(fā)現(xiàn)算法已經(jīng)被提出。之前的單機(jī)算法在數(shù)據(jù)集較小且單機(jī)存儲(chǔ)的時(shí)候很高效,但是缺乏并行能力;另一方面,現(xiàn)存的并行算法存在很大的通信開銷,導(dǎo)致其表現(xiàn)不佳。為了解決這個(gè)問題,本文做了如下三方面的工作:首先是提出FD-Combine算法解決了“如何推導(dǎo)”的問題�，F(xiàn)存并行算法最大問題是通信開銷,我們嘗試通過數(shù)據(jù)并行模式的并行來避免大量的通信開銷,而數(shù)據(jù)并行模式的并行的首要問題就是”如何將部分?jǐn)?shù)據(jù)上成立的函數(shù)依賴推導(dǎo)得到全體數(shù)據(jù)的函數(shù)依賴”,即“如何推導(dǎo)”的問題。為此,我們構(gòu)建了BL代數(shù)系統(tǒng)和基礎(chǔ)項(xiàng)表達(dá),形式化了函數(shù)依賴、非函數(shù)依賴、部分函數(shù)依賴的性質(zhì)與運(yùn)算關(guān)系。在BL代數(shù)系統(tǒng)內(nèi),我們提出FD-Combine算法,在每部分?jǐn)?shù)據(jù)集即數(shù)據(jù)塊滿足一定條件時(shí),可以將部分函數(shù)依賴推導(dǎo)得到全體數(shù)據(jù)上的函數(shù)依賴。我們對(duì)比FD-Combine算法與之前非函數(shù)依賴的推導(dǎo)算法,得到進(jìn)一步理解,并給出FD-Combine算法的不同實(shí)現(xiàn)方式和相應(yīng)的時(shí)間復(fù)雜度。然后,改造并選擇了仿射平面區(qū)組設(shè)計(jì)算... 

【文章來源】：中國科學(xué)技術(shù)大學(xué)安徽省 211工程院校 985工程院校

【文章頁數(shù)】：69 頁

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
abstract
第1章 緒論
    1.1 研究背景
    1.2 國內(nèi)外研究現(xiàn)狀
        1.2.1 國外研究現(xiàn)狀
        1.2.2 國內(nèi)研究現(xiàn)狀
        1.2.3 發(fā)展動(dòng)態(tài)分析
    1.3 本文主要工作
    1.4 本文組織結(jié)構(gòu)
第2章 函數(shù)依賴發(fā)現(xiàn)算法概述
    2.1 定義
    2.2 三類發(fā)現(xiàn)算法
        2.2.1 單機(jī)算法過去的實(shí)驗(yàn)對(duì)比
        2.2.2 模式驅(qū)動(dòng)類算法
        2.2.3 數(shù)據(jù)驅(qū)動(dòng)類算法
        2.2.4 混合類算法
    2.3 發(fā)現(xiàn)算法中的四種技術(shù)
        2.3.1 驗(yàn)證技術(shù)
        2.3.2 搜索剪枝技術(shù)
        2.3.3 推導(dǎo)技術(shù)
        2.3.4 重復(fù)檢測(cè)技術(shù)
        2.3.5 分布式環(huán)境下四種技術(shù)
    2.4 分布式環(huán)境下的發(fā)現(xiàn)算法
        2.4.1 三種類型的通信開銷
        2.4.2 幾種并行算法的設(shè)計(jì)
第3章 部分?jǐn)?shù)據(jù)函數(shù)依賴到全體數(shù)據(jù)函數(shù)依賴的推導(dǎo)
    3.1 問題的背景分析
        3.1.1 分布式環(huán)境下的通信開銷分析
        3.1.2 并行模式的分析
    3.2 問題的形式化
L代數(shù)系統(tǒng)與FD-Combine推導(dǎo)算法">    3.3 B_L代數(shù)系統(tǒng)與FD-Combine推導(dǎo)算法
L代數(shù)系統(tǒng)定義與性質(zhì)">        3.3.1 B_L代數(shù)系統(tǒng)定義與性質(zhì)
        3.3.2 基礎(chǔ)項(xiàng)及基礎(chǔ)項(xiàng)計(jì)算規(guī)則
        3.3.3 FD-Combine推導(dǎo)算法
    3.4 FD-Combine推導(dǎo)算法的進(jìn)一步探索
        3.4.1 FD-Combine算法與其他推導(dǎo)算法的關(guān)系
        3.4.2 FD-Combine的算法實(shí)現(xiàn)方式和復(fù)雜度分析
    3.5 本章小結(jié)
第4章 數(shù)據(jù)集在各個(gè)計(jì)算節(jié)點(diǎn)上的分割問題
    4.1 問題的背景分析與目標(biāo)
        4.1.1 FD-Combine推導(dǎo)條件的滿足
        4.1.2 分割算法的高效性
        4.1.3 分割結(jié)果的質(zhì)量
    4.2 問題的轉(zhuǎn)化及形式化表達(dá)
    4.3 區(qū)組設(shè)計(jì)與評(píng)估指標(biāo)設(shè)計(jì)
        4.3.1 區(qū)組設(shè)計(jì)與條件放松
        4.3.2 評(píng)價(jià)指標(biāo)定義與性質(zhì)
    4.4 仿射平面區(qū)組設(shè)計(jì)算法設(shè)計(jì)與分析
        4.4.1 仿射平面區(qū)組設(shè)計(jì)算法流程
        4.4.2 算法的時(shí)間復(fù)雜度分析與結(jié)果分析
    4.5 本章小結(jié)
第5章 函數(shù)依賴發(fā)現(xiàn)算法的通用并行策略與實(shí)驗(yàn)
    5.1 數(shù)據(jù)并行模式的通用并行策略
        5.1.1 通用并行策略的介紹與例子
        5.1.2 策略的復(fù)雜度分析和加速比
    5.2 通用并行策略的實(shí)驗(yàn)
        5.2.1 實(shí)驗(yàn)設(shè)置
        5.2.2 小數(shù)據(jù)集上的實(shí)驗(yàn)
        5.2.3 大數(shù)據(jù)集上的實(shí)驗(yàn)
    5.3 本章小結(jié)
第6章 總結(jié)與展望
    6.1 工作總結(jié)
    6.2 未來展望
參考文獻(xiàn)
致謝
在讀期間發(fā)表的學(xué)術(shù)論文與取得的研究成果


【參考文獻(xiàn)】：
期刊論文
[1]分布式大數(shù)據(jù)多函數(shù)依賴沖突檢測(cè)[J]. 李衛(wèi)榜,李戰(zhàn)懷,姜濤.  計(jì)算機(jī)學(xué)報(bào). 2017(01)
[2]關(guān)系數(shù)據(jù)中函數(shù)依賴檢測(cè)方法[J]. 鐘評(píng),李戰(zhàn)懷,陳群.  計(jì)算機(jī)學(xué)報(bào). 2017(01)
[3]基于函數(shù)依賴與條件約束的數(shù)據(jù)修復(fù)方法[J]. 金澈清,劉輝平,周傲英.  軟件學(xué)報(bào). 2016(07)
[4]基于可能世界模型的關(guān)系數(shù)據(jù)不一致性的修復(fù)[J]. 徐耀麗,李戰(zhàn)懷,陳群,鐘評(píng).  軟件學(xué)報(bào). 2016(07)
[5]分布式大數(shù)據(jù)不一致性檢測(cè)[J]. 李衛(wèi)榜,李戰(zhàn)懷,陳群,楊婧穎,姜濤.  軟件學(xué)報(bào). 2016(08)
[6]分布式大數(shù)據(jù)函數(shù)依賴發(fā)現(xiàn)[J]. 李衛(wèi)榜,李戰(zhàn)懷,陳群,姜濤,劉海龍,潘巍.  計(jì)算機(jī)研究與發(fā)展. 2015(02)
[7]基于函數(shù)依賴的結(jié)構(gòu)匹配方法[J]. 李國徽,杜小坤,胡方曉,楊兵,唐向紅.  軟件學(xué)報(bào). 2009(10)
[8]時(shí)態(tài)函數(shù)依賴多值依賴混合集的成員籍問題研究[J]. 郝忠孝,李艷娟.  計(jì)算機(jī)研究與發(fā)展. 2006(07)
[9]具有多時(shí)間粒度的時(shí)態(tài)數(shù)據(jù)庫初等關(guān)鍵字、簡單范式分解問題研究[J]. 郝忠孝,李艷娟.  計(jì)算機(jī)研究與發(fā)展. 2005(09)
[10]函數(shù)依賴和規(guī)范化在關(guān)系和XML間的傳播[J]. 談子敬,施伯樂.  軟件學(xué)報(bào). 2005(04)



本文編號(hào)：3159451