[發(fā)明專利]一種圖數(shù)據(jù)的分區(qū)方法、裝置以及設(shè)備

有效

• 申請(qǐng)?zhí)枺?/td>: 202010057861.9
• 申請(qǐng)日: 2020-01-16
• 公開(kāi)（公告）號(hào): CN111241353B
• 公開(kāi)（公告）日: 2023-08-22
• 發(fā)明（設(shè)計(jì)）人: 唐德榮
• 申請(qǐng)（專利權(quán)）人: 支付寶（杭州）信息技術(shù)有限公司
• 主分類號(hào): G06F16/901
• 分類號(hào): G06F16/901;G06F16/906
• 代理公司: 北京晉德允升知識(shí)產(chǎn)權(quán)代理有限公司 11623
• 代理人: 王戈

本說(shuō)明書(shū)實(shí)施例公開(kāi)了一種圖數(shù)據(jù)的分區(qū)方法、裝置以及設(shè)備。所述方法包括：獲取待處理的圖數(shù)據(jù)；對(duì)所述待處理的圖數(shù)據(jù)的節(jié)點(diǎn)數(shù)據(jù)進(jìn)行打散處理，獲得所述待處理的圖數(shù)據(jù)的第一分區(qū)結(jié)果；基于所述第一分區(qū)結(jié)果，對(duì)所述第一分區(qū)結(jié)果中對(duì)應(yīng)的各個(gè)節(jié)點(diǎn)進(jìn)行聚類分析，獲得所述待處理的圖數(shù)據(jù)的第二分區(qū)結(jié)果，以使所述第二分區(qū)結(jié)果中相鄰連通圖的頂點(diǎn)數(shù)據(jù)和/或邊數(shù)據(jù)存儲(chǔ)在同一個(gè)分區(qū)中，所述第二分區(qū)結(jié)果為所述待處理的圖數(shù)據(jù)的最終分區(qū)結(jié)果。采用本說(shuō)明書(shū)實(shí)施例提供的圖數(shù)據(jù)的分區(qū)方法，能夠?qū)崿F(xiàn)圖數(shù)據(jù)的存儲(chǔ)負(fù)載均勻，避免熱點(diǎn)問(wèn)題，且能夠提升圖數(shù)據(jù)的計(jì)算效率。

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

本說(shuō)明書(shū)涉及計(jì)算機(jī)技術(shù)領(lǐng)域，尤其涉及一種圖數(shù)據(jù)的分區(qū)方法、裝置以及設(shè)備。

背景技術(shù)

圖在生活中無(wú)處不在，社交媒體、科學(xué)中分子結(jié)構(gòu)關(guān)系、電商平臺(tái)的廣告推薦、網(wǎng)頁(yè)信息等等，都能夠以圖數(shù)據(jù)的形式進(jìn)行表達(dá)。圖能夠?qū)⑷恕a(chǎn)品、想法、事實(shí)、興趣愛(ài)好之間的關(guān)系全部轉(zhuǎn)換存儲(chǔ)。各種場(chǎng)景下的信息都能轉(zhuǎn)成圖來(lái)表示，同時(shí)我們可以利用圖來(lái)進(jìn)行數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)，比如識(shí)別出有影響力的人和信息、社區(qū)發(fā)現(xiàn)、尋找產(chǎn)品和廣告的投放用戶、給有依賴關(guān)系的復(fù)雜數(shù)據(jù)構(gòu)建模型、分類標(biāo)簽等等這些都可以使用圖來(lái)完成。隨著互聯(lián)網(wǎng)的飛速發(fā)展，會(huì)產(chǎn)生海量的圖數(shù)據(jù)，圖分布式存儲(chǔ)分區(qū)算法(圖分區(qū))應(yīng)運(yùn)而生，以滿足海量圖數(shù)據(jù)的分區(qū)。

現(xiàn)有技術(shù)中，邊分割(Edge-Cut)和點(diǎn)分割(Vertex-Cut)為重要的圖分區(qū)方法。邊分割能夠節(jié)省存儲(chǔ)空間，但是會(huì)產(chǎn)生額外的邊數(shù)據(jù)，需要跨機(jī)器通信傳輸數(shù)據(jù)，內(nèi)網(wǎng)通信流量大。點(diǎn)分割具有較好的性能，但是會(huì)產(chǎn)生額外的節(jié)點(diǎn)數(shù)據(jù)，冗余較大，會(huì)增加存儲(chǔ)開(kāi)銷。

因此，需要一種更為便捷、高效的圖數(shù)據(jù)的分區(qū)方法。

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

本說(shuō)明書(shū)實(shí)施例提供一種圖數(shù)據(jù)的分區(qū)方法、裝置以及設(shè)備，用于解決以下技術(shù)問(wèn)題：邊分割會(huì)產(chǎn)生額外的邊數(shù)據(jù)，內(nèi)網(wǎng)通信流量大和/或邊分割會(huì)產(chǎn)生額外的節(jié)點(diǎn)數(shù)據(jù)，冗余較大，會(huì)增加存儲(chǔ)開(kāi)銷。

為解決上述技術(shù)問(wèn)題，本說(shuō)明書(shū)實(shí)施例是這樣實(shí)現(xiàn)的：

本說(shuō)明書(shū)實(shí)施例提供的一種圖數(shù)據(jù)的分區(qū)方法，包括：

獲取待處理的圖數(shù)據(jù)；

對(duì)所述待處理的圖數(shù)據(jù)的節(jié)點(diǎn)數(shù)據(jù)進(jìn)行打散處理，獲得所述待處理的圖數(shù)據(jù)的第一分區(qū)結(jié)果；

基于所述第一分區(qū)結(jié)果，對(duì)所述第一分區(qū)結(jié)果中對(duì)應(yīng)的各個(gè)節(jié)點(diǎn)進(jìn)行聚類分析，獲得所述待處理的圖數(shù)據(jù)的第二分區(qū)結(jié)果，以使所述第二分區(qū)結(jié)果中相鄰連通圖的頂點(diǎn)數(shù)據(jù)和/或邊數(shù)據(jù)存儲(chǔ)在同一個(gè)分區(qū)中，所述第二分區(qū)結(jié)果為所述待處理的圖數(shù)據(jù)的最終分區(qū)結(jié)果。

本說(shuō)明書(shū)實(shí)施例提供的一種圖數(shù)據(jù)的分區(qū)裝置，包括：

獲取模塊，獲取待處理的圖數(shù)據(jù)；

第一分區(qū)模塊，對(duì)所述待處理的圖數(shù)據(jù)的節(jié)點(diǎn)數(shù)據(jù)進(jìn)行打散處理，獲得所述待處理的圖數(shù)據(jù)的第一分區(qū)結(jié)果；

第二分區(qū)模塊，基于所述第一分區(qū)結(jié)果，對(duì)所述第一分區(qū)結(jié)果中對(duì)應(yīng)的各個(gè)節(jié)點(diǎn)進(jìn)行聚類分析，獲得所述待處理的圖數(shù)據(jù)的第二分區(qū)結(jié)果，以使所述第二分區(qū)結(jié)果中相鄰連通圖的頂點(diǎn)數(shù)據(jù)和/或邊數(shù)據(jù)存儲(chǔ)在同一個(gè)分區(qū)中，所述第二分區(qū)結(jié)果為所述待處理的圖數(shù)據(jù)的最終分區(qū)結(jié)果。

本說(shuō)明書(shū)實(shí)施例還提供一種電子設(shè)備，包括：

至少一個(gè)處理器；以及，

與所述至少一個(gè)處理器通信連接的存儲(chǔ)器；其中，

所述存儲(chǔ)器存儲(chǔ)有可被所述至少一個(gè)處理器執(zhí)行的指令，所述指令被所述至少一個(gè)處理器執(zhí)行，以使所述至少一個(gè)處理器能夠：

獲取待處理的圖數(shù)據(jù)；

對(duì)所述待處理的圖數(shù)據(jù)的節(jié)點(diǎn)數(shù)據(jù)進(jìn)行打散處理，獲得所述待處理的圖數(shù)據(jù)的第一分區(qū)結(jié)果；