[發(fā)明專利]圖數(shù)據(jù)劃分方法及裝置

有效

• 申請?zhí)枺?/td>: 201610101409.1
• 申請日: 2016-02-24
• 公開（公告）號: CN105787020B
• 公開（公告）日: 2019-05-21
• 發(fā)明（設(shè)計(jì)）人: 武永衛(wèi);章明星;陳康;鄭緯民
• 申請（專利權(quán)）人: 鄞州浙江清華長三角研究院創(chuàng)新中心
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 北京清亦華知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11201
• 代理人: 張大威

本發(fā)明公開了一種圖數(shù)據(jù)劃分方法及裝置，其中，該方法包括根據(jù)圖定義的數(shù)據(jù)和計(jì)算模型UPPS對算法進(jìn)行建模；通過二維數(shù)據(jù)劃分方法對建模中的數(shù)據(jù)進(jìn)行劃分，并獲取劃分后冗余度最小的數(shù)據(jù)；根據(jù)估測公式估測確定最佳的第三維層數(shù)；以及根據(jù)冗余度最小的數(shù)據(jù)對第三維層數(shù)的每一層進(jìn)行劃分，獲得數(shù)據(jù)的分布方式。該方法實(shí)現(xiàn)了通過增加適量的層間通訊量減少每一層內(nèi)數(shù)據(jù)劃分塊數(shù)，減少分布式圖數(shù)據(jù)處理時的通訊量，提升計(jì)算效率。

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

本發(fā)明涉及數(shù)據(jù)處理技術(shù)領(lǐng)域，尤其涉及一種圖數(shù)據(jù)劃分方法及裝置。

背景技術(shù)

隨著圖數(shù)據(jù)在數(shù)據(jù)量和重要性上的不斷增長，分布式的圖數(shù)據(jù)處理引擎逐漸成為一種主流的解決方案。這一需求驅(qū)使著工業(yè)界和學(xué)術(shù)界的許多開發(fā)人員及研究人員研發(fā)了許多多種多樣的圖并行處理框架，包括Pregel、PowerGraph、GraphX等等。由于這些系統(tǒng)提供了一種簡單有效的編程接口使得程序員們可以無縫的將他們的程序擴(kuò)展到多機(jī)環(huán)境，這些原本為了圖計(jì)算設(shè)計(jì)的系統(tǒng)目前不僅僅被用于傳統(tǒng)的圖分析，還被用于許多可以用圖進(jìn)行建模的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘任務(wù)。

例如Collaborative Filtering這一類數(shù)據(jù)挖掘問題的目的在于通過已知的用戶對物品的打分集合來預(yù)測未知的部分。這一問題最早是用矩陣進(jìn)行描述的。如圖1所示，簡單地說，給定一個大小為N*M的稀疏矩陣R，求解的目的為將R分解成兩個低維稠密矩陣P和Q的乘積(P和Q的大小分別為N*D以及M*D，并且R約等于P*Q^T其中D遠(yuǎn)小于N和M)。相對的，同樣可以用圖模型對這一問題進(jìn)行描述，其中P和Q的每一行分別對應(yīng)于一張二分圖中的點(diǎn)。每一個點(diǎn)的屬性都是一個長度為D的向量，而打分矩陣R則對應(yīng)于邊的分?jǐn)?shù)。換句話說用戶u對物品v的打分為Ruv的話，則u和v之間的邊權(quán)值為Ruv。

隨著對機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘任務(wù)中大型圖數(shù)據(jù)進(jìn)行分析這一需求的增長，許多之前未曾被考慮到的問題也隨之出現(xiàn)。根據(jù)近期的一些研究，為了能夠高效地處理圖數(shù)據(jù)，一個關(guān)鍵的研究點(diǎn)就是如何減少圖處理時的通訊量。因此，一個分布式圖處理引擎需要非常小心的選擇他使用的任務(wù)劃分算法。然而，根據(jù)調(diào)查，目前已有的圖處理引擎基本都忽略了機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘任務(wù)的特性而認(rèn)為圖中每一個點(diǎn)的屬性都是不可分的，因此將圖計(jì)算的任務(wù)劃分簡單地等價為了一般的圖劃分問題。可是，正如Collaborative Filtering這一類數(shù)據(jù)挖掘問題那樣，在很多的時候每一個點(diǎn)的屬性實(shí)際上是一個向量。雖然這一向量的長度一般并不大，需要一種新的維度對圖進(jìn)行劃分，解決通訊量問題。

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

本發(fā)明的目的旨在至少在一定程度上解決上述的技術(shù)問題之一。

為此，本發(fā)明的第一個目的在于提出一種圖數(shù)據(jù)劃分方法。該方法實(shí)現(xiàn)了通過增加適量的層間通訊量減少每一層內(nèi)數(shù)據(jù)劃分塊數(shù)，減少分布式圖數(shù)據(jù)處理時的通訊量，提升計(jì)算效率。

本發(fā)明的第二個目的在于提出了一種圖數(shù)據(jù)劃分裝置。

為達(dá)上述目的，本發(fā)明第一方面實(shí)施例的圖數(shù)據(jù)劃分方法，根據(jù)圖定義的數(shù)據(jù)和計(jì)算模型UPPS(Update Push Pull Sink)對算法進(jìn)行建模；通過二維數(shù)據(jù)劃分方法對所述建模中的數(shù)據(jù)進(jìn)行劃分，并獲取劃分后冗余度最小的數(shù)據(jù)；根據(jù)估測公式估測確定最佳的第三維層數(shù)；以及根據(jù)所述冗余度最小的數(shù)據(jù)對所述第三維層數(shù)的每一層進(jìn)行劃分，獲得數(shù)據(jù)的分布方式。

本發(fā)明實(shí)施例的圖數(shù)據(jù)劃分方法，根據(jù)圖定義的數(shù)據(jù)和計(jì)算模型對算法進(jìn)行建模，通過二維數(shù)據(jù)劃分方法對建模中的數(shù)據(jù)進(jìn)行劃分，并獲取劃分后冗余度最小的數(shù)據(jù)，再根據(jù)估測公式估測確定最佳的第三維層數(shù)，最后根據(jù)冗余度最小的數(shù)據(jù)對第三維層數(shù)的每一層進(jìn)行劃分，獲得數(shù)據(jù)的分布方式。該方法實(shí)現(xiàn)了通過增加適量的層間通訊量減少每一層內(nèi)數(shù)據(jù)劃分塊數(shù)，減少分布式圖數(shù)據(jù)處理時的通訊量，提升計(jì)算效率。