[發(fā)明專(zhuān)利]一種大規(guī)模分布式函數(shù)依賴(lài)發(fā)現(xiàn)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810367758.7
• 申請(qǐng)日: 2018-04-23
• 公開(kāi)（公告）號(hào): CN108595624A
• 公開(kāi)（公告）日: 2018-09-28
• 發(fā)明（設(shè)計(jì)）人: 顧榮;黃宜華;朱光輝;王千;袁春風(fēng)
• 申請(qǐng)（專(zhuān)利權(quán)）人: 南京大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 蘇州威世朋知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 32235
• 代理人: 楊林潔

本發(fā)明公開(kāi)了一種大規(guī)模分布式函數(shù)依賴(lài)發(fā)現(xiàn)方法，包括以下步驟：第一步，并行地獲取數(shù)據(jù)集的統(tǒng)計(jì)信息、對(duì)屬性進(jìn)行排序和對(duì)數(shù)據(jù)進(jìn)行分布式編碼；第二步，依次選取屬性，將在該屬性上取值相同的數(shù)據(jù)發(fā)送到同一個(gè)節(jié)點(diǎn)上；第三步，在每個(gè)節(jié)點(diǎn)上進(jìn)行候選函數(shù)依賴(lài)發(fā)現(xiàn)。該過(guò)程可以分為以下兩步：第一步，并行地進(jìn)行采樣，利用采樣結(jié)果對(duì)候選集進(jìn)行剪枝和生成；第二步，并行地對(duì)候選集進(jìn)行驗(yàn)證，利用驗(yàn)證結(jié)果對(duì)候選集進(jìn)行剪枝和生成。每輪采樣和驗(yàn)證結(jié)束后均需根據(jù)其效率來(lái)決定是否進(jìn)行采樣和驗(yàn)證的切換。第四步，生成函數(shù)依賴(lài)結(jié)果。本發(fā)明可高效地實(shí)現(xiàn)分布式函數(shù)依賴(lài)發(fā)現(xiàn)，解決現(xiàn)有函數(shù)依賴(lài)求解方法計(jì)算量大、內(nèi)存占用多、無(wú)法處理大規(guī)模數(shù)據(jù)集等問(wèn)題。

技術(shù)領(lǐng)域

本發(fā)明涉及函數(shù)依賴(lài)發(fā)現(xiàn)與并行計(jì)算技術(shù)領(lǐng)域，尤其涉及一種大規(guī)模分布式函數(shù)依賴(lài)發(fā)現(xiàn)方法。

背景技術(shù)

函數(shù)依賴(lài)是一種重要的元數(shù)據(jù)信息，在數(shù)據(jù)清理、知識(shí)發(fā)現(xiàn)、數(shù)據(jù)集成和模式規(guī)范化等領(lǐng)域都有著廣泛的應(yīng)用。但是函數(shù)依賴(lài)發(fā)現(xiàn)的計(jì)算復(fù)雜度非常高，相關(guān)的工作中并沒(méi)有太多并行化的分布式函數(shù)依賴(lài)發(fā)現(xiàn)方法，人們更側(cè)重于研究單機(jī)的函數(shù)依賴(lài)發(fā)現(xiàn)方法。前人提出的最優(yōu)單機(jī)函數(shù)依賴(lài)發(fā)現(xiàn)方法HyFD，雖然其性能基本上超越了所有其他單機(jī)算法，但事實(shí)證明，該方法在執(zhí)行過(guò)程中需要消耗大量的計(jì)算資源，主要是面向小規(guī)模、集中式存儲(chǔ)數(shù)據(jù)進(jìn)行函數(shù)依賴(lài)發(fā)現(xiàn)，無(wú)法對(duì)大規(guī)模、分布式數(shù)據(jù)。在大數(shù)據(jù)的時(shí)代背景下，數(shù)據(jù)規(guī)模不斷增大，數(shù)據(jù)往往被分布存儲(chǔ)在多個(gè)節(jié)點(diǎn)上。此時(shí)，在多個(gè)節(jié)點(diǎn)并行地運(yùn)行單機(jī)算法無(wú)法保證函數(shù)依賴(lài)發(fā)現(xiàn)的正確性。面對(duì)大數(shù)據(jù)的挑戰(zhàn)，有人提出了將所有數(shù)據(jù)傳輸?shù)絾蝹€(gè)節(jié)點(diǎn)進(jìn)行函數(shù)依賴(lài)發(fā)現(xiàn)的方法，但該方法無(wú)法高效地利用計(jì)算資源，也不能進(jìn)行計(jì)算和存儲(chǔ)的水平擴(kuò)展。也有人提出了分布式大數(shù)據(jù)函數(shù)依賴(lài)發(fā)現(xiàn)的方法，旨在解決上述方法的擴(kuò)展性問(wèn)題，但是沒(méi)有一種能夠在行和列上擁有較好擴(kuò)展性的解決方案。因此，如何設(shè)計(jì)一個(gè)面向大規(guī)模數(shù)據(jù)的、高效的、行和列擴(kuò)展性好的函數(shù)依賴(lài)發(fā)現(xiàn)方法就成為了并行化方法設(shè)計(jì)的挑戰(zhàn)。

以往的相關(guān)工作中，有以HyFD算法為代表的單機(jī)函數(shù)依賴(lài)發(fā)現(xiàn)方法。首先,該方法對(duì)數(shù)據(jù)集進(jìn)行定制化的采樣，減少待處理數(shù)據(jù)的行數(shù)，并利用采樣數(shù)據(jù)和列高效的算法對(duì)候選函數(shù)依賴(lài)進(jìn)行剪枝和生成。然后，將剩余的候選函數(shù)依賴(lài)在所有數(shù)據(jù)上進(jìn)行驗(yàn)證。這種方法的優(yōu)勢(shì)在于利用列高效的算法降低了候選函數(shù)依賴(lài)的數(shù)量，從而降低了行高效算法的驗(yàn)證時(shí)間。但該方法要求所有的輸入數(shù)據(jù)都存儲(chǔ)在單個(gè)節(jié)點(diǎn)上，且計(jì)算過(guò)程中生成的中間數(shù)據(jù)結(jié)構(gòu)能夠完全放入主存中，而單機(jī)的主存往往有限，所以該方法無(wú)法對(duì)大規(guī)模分布式數(shù)據(jù)進(jìn)行函數(shù)依賴(lài)發(fā)現(xiàn)。

目前較好的分布式函數(shù)依賴(lài)發(fā)現(xiàn)算法是HFDD，該方法基于數(shù)據(jù)重分布進(jìn)行函數(shù)依賴(lài)發(fā)現(xiàn)，每次重分布將某個(gè)屬性取值相同的數(shù)據(jù)發(fā)送到同一個(gè)節(jié)點(diǎn)上，然后進(jìn)行驗(yàn)證。但該方法有以下不足：一是沒(méi)有考慮節(jié)點(diǎn)的負(fù)載均衡，如果取值較少的屬性被優(yōu)先用來(lái)重分布，該方法將無(wú)法充分利用集群資源，效率也會(huì)變得十分低下；二是沒(méi)有解決候選函數(shù)依賴(lài)過(guò)多的問(wèn)題；三是沒(méi)有高效的分布式驗(yàn)證方法。

發(fā)明內(nèi)容

發(fā)明目的：針對(duì)上述現(xiàn)有技術(shù)存在的問(wèn)題和不足，本發(fā)明的目的是提供一種在大規(guī)模、分布存儲(chǔ)數(shù)據(jù)上進(jìn)行函數(shù)依賴(lài)發(fā)現(xiàn)的方法，解決了現(xiàn)有方法資源利用率低、計(jì)算性能差和擴(kuò)展性較差等問(wèn)題。

技術(shù)方案：為實(shí)現(xiàn)上述發(fā)明目的，本發(fā)明采用的技術(shù)方案為一種大規(guī)模分布式函數(shù)依賴(lài)發(fā)現(xiàn)方法，包括以下步驟：

(1)并行地獲取輸入數(shù)據(jù)的統(tǒng)計(jì)信息，根據(jù)統(tǒng)計(jì)信息對(duì)屬性進(jìn)行排序，根據(jù)統(tǒng)計(jì)信息和屬性排序結(jié)果對(duì)數(shù)據(jù)進(jìn)行分布式編碼；

(2)根據(jù)步驟(1)中的結(jié)果，分多輪執(zhí)行步驟(3)到步驟(4)；

(3)根據(jù)步驟(1)的屬性排序結(jié)果，每次選取一個(gè)屬性并對(duì)步驟(1)中得到的編碼數(shù)據(jù)進(jìn)行重分布；

(4)根據(jù)步驟(3)的結(jié)果，分多輪執(zhí)行步驟(5)到步驟(6)，每一輪對(duì)左部中包含被選屬性的所有候選函數(shù)依賴(lài)進(jìn)行發(fā)現(xiàn)，直到左部包含該屬性的所有候選函數(shù)依賴(lài)被排除或者被驗(yàn)證；