公开(公告)号：US09330199B2

公开(公告)日：2016-05-03

申请号：US14336363

申请日：2014-07-21

Applicant: Facebook, Inc.

Inventor： Deepayan Chakrabarti ,  Jonathan Chang ,  Avery Li Kuang Ching ,  Maja Kabiljo

IPC: G06F9/46 ,  G06F17/30 ,  H04L12/911 ,  H04L29/06 ,  H04L12/26

CPC classification number: G06F17/30958 ,  G06F17/30336 ,  G06F17/30377 ,  G06Q50/01 ,  H04L47/70 ,  H04L65/403 ,  H04L67/1097

Abstract: Embodiments are disclosed for striping a directed graph, e.g., a social graph, so as to efficiently perform an operation to each node in the directed graph. At least some of the embodiments can select first and second sets of nodes from the directed graph to form first and second stripes. The first and second sets of nodes are selected, for example, based on available computing resources. First and second intermediate results can be generated by performing the operation to each node of the first and the second stripes, respectively. The operation iteratively performs a superstep. The first and the second intermediate results are combined to form a collective result as an output of the superstep.

Abstract translation: 公开了用于条带化有向图（例如，社交图）的实施例，以有效地对有向图中的每个节点执行操作。 至少一些实施例可以从有向图中选择第一和第二组节点以形成第一和第二条带。 例如，基于可用的计算资源来选择第一和第二组节点。 可以通过分别对第一和第二条纹的每个节点执行操作来生成第一和第二中间结果。 该操作迭代地执行一个超级步骤。 第一和第二中间结果被组合以形成作为超级步骤的输出的集合结果。

公开(公告)号：US20160019313A1

公开(公告)日：2016-01-21

申请号：US14336363

申请日：2014-07-21

Applicant: Facebook, Inc.

Inventor： Deepayan Chakrabarti ,  Jonathan Chang ,  Avery Li Kuang Ching ,  Maja Kabiljo

IPC: G06F17/30 ,  H04L29/06 ,  H04L12/26 ,  H04L12/911

CPC classification number: G06F17/30958 ,  G06F17/30336 ,  G06F17/30377 ,  G06Q50/01 ,  H04L47/70 ,  H04L65/403 ,  H04L67/1097

Abstract: Embodiments are disclosed for striping a directed graph, e.g., a social graph, so as to efficiently perform an operation to each node in the directed graph. At least some of the embodiments can select first and second sets of nodes from the directed graph to form first and second stripes. The first and second sets of nodes are selected, for example, based on available computing resources. First and second intermediate results can be generated by performing the operation to each node of the first and the second stripes, respectively. The operation iteratively performs a superstep. The first and the second intermediate results are combined to form a collective result as an output of the superstep.

Abstract translation: 公开了用于条带化有向图（例如，社交图）的实施例，以有效地对有向图中的每个节点执行操作。 至少一些实施例可以从有向图中选择第一和第二组节点以形成第一和第二条带。 例如，基于可用的计算资源来选择第一和第二组节点。 可以通过分别对第一和第二条纹的每个节点执行操作来生成第一和第二中间结果。 该操作迭代地执行一个超级步骤。 第一和第二中间结果被组合以形成作为超级步骤的输出的集合结果。

公开(公告)号：US20160203235A1

公开(公告)日：2016-07-14

申请号：US15077852

申请日：2016-03-22

Applicant: Facebook, Inc.

Inventor： Deepayan Chakrabarti ,  Jonathan Chang ,  Avery Li Kuang Ching ,  Maja Kabiljo

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30336 ,  G06F17/30377 ,  G06Q50/01 ,  H04L47/70 ,  H04L65/403 ,  H04L67/1097

Abstract: Embodiments are disclosed for striping a directed graph, e.g., a social graph, so as to efficiently perform an operation to each node in the directed graph. At least some of the embodiments can select first and second sets of nodes from the directed graph to form first and second stripes. The first and second sets of nodes are selected, for example, based on available computing resources. First and second intermediate results can be generated by performing the operation to each node of the first and the second stripes, respectively. The operation iteratively performs a superstep. The first and the second intermediate results are combined to form a collective result as an output of the superstep.

Abstract translation: 公开了用于条带化有向图（例如，社交图）的实施例，以有效地对有向图中的每个节点执行操作。 至少一些实施例可以从有向图中选择第一和第二组节点以形成第一和第二条带。 例如，基于可用的计算资源来选择第一和第二组节点。 可以通过分别对第一和第二条纹的每个节点执行操作来生成第一和第二中间结果。 该操作迭代地执行一个超级步骤。 第一和第二中间结果被组合以形成作为超级步骤的输出的集合结果。

公开(公告)号：US10313457B2

公开(公告)日：2019-06-04

申请号：US14718391

申请日：2015-05-21

Applicant: Facebook, Inc.

Inventor： Maja Kabiljo ,  Aleksandar Ilic

IPC: G06N5/00 ,  H04L29/08 ,  G06Q50/00 ,  G06N20/00

Abstract: Embodiments are disclosed for data computation of collaborative filtering in a social network. Collaborative filtering involves predicting a user's behavior or interests based on other users' behavior or interests. To predict a user's interests in an item such as a picture, a system performs an iterative computation to perform an evaluation by solving an objective function. The system characterizes “users” as “vertices” in a directed graph, “relationship among users” as “edges” in the directed graph, and “items” as “worker data” that is locally-calculated, stored, and managed in individual worker computers. When a local computing process is completed, the “worker data” can be transferred to other worker computers so as to complete a whole computing process. The system enhances an overall computing efficiency and enables collaborative filtering across a large data set.

公开(公告)号：US09805140B2

公开(公告)日：2017-10-31

申请号：US15077852

申请日：2016-03-22

Applicant: Facebook, Inc.

Inventor： Deepayan Chakrabarti ,  Jonathan Chang ,  Avery Li Kuang Ching ,  Maja Kabiljo

IPC: G06F9/46 ,  G06F17/30 ,  H04L12/911 ,  H04L29/06

CPC classification number: G06F17/30958 ,  G06F17/30336 ,  G06F17/30377 ,  G06Q50/01 ,  H04L47/70 ,  H04L65/403 ,  H04L67/1097

Abstract: Embodiments are disclosed for striping a directed graph, e.g., a social graph, so as to efficiently perform an operation to each node in the directed graph. At least some of the embodiments can select first and second sets of nodes from the directed graph to form first and second stripes. The first and second sets of nodes are selected, for example, based on available computing resources. First and second intermediate results can be generated by performing the operation to each node of the first and the second stripes, respectively. The operation iteratively performs a superstep. The first and the second intermediate results are combined to form a collective result as an output of the superstep.

公开(公告)号：US20160342899A1

公开(公告)日：2016-11-24

申请号：US14718391

申请日：2015-05-21

Applicant: Facebook, Inc.

Inventor： Maja Kabiljo ,  Aleksandar Ilic

IPC: G06N5/04 ,  G06N7/00 ,  H04L29/08

CPC classification number: H04L67/22 ,  G06N5/003 ,  G06N99/005 ,  G06Q50/01

Abstract: Embodiments are disclosed for data computation of collaborative filtering in a social network. Collaborative filtering involves predicting a user's behavior or interests based on other users' behavior or interests. To predict a user's interests in an item such as a picture, a system performs an iterative computation to perform an evaluation by solving an objective function. The system characterizes “users” as “vertices” in a directed graph, “relationship among users” as “edges” in the directed graph, and “items” as “worker data” that is locally-calculated, stored, and managed in individual worker computers. When a local computing process is completed, the “worker data” can be transferred to other worker computers so as to complete a whole computing process. The system enhances an overall computing efficiency and enables collaborative filtering across a large data set.

Abstract translation: 公开了用于社交网络中协作过滤的数据计算的实施例。 协作过滤涉及基于其他用户的行为或兴趣来预测用户的行为或兴趣。 为了预测用户在诸如图片的项目中的兴趣，系统执行迭代计算以通过求解目标函数来执行评估。 该系统将有向图中的“用户”表示为“顶点”，将有向图中的“用户之间的关系”设为“边缘”，将个体作为“个人数据”作为“个体”进行本地计算，存储和管理的“工作者数据” 工作电脑。 当本地计算过程完成时，可以将“工作人员数据”传输到其他工作计算机，以完成整个计算过程。 该系统增强了整体计算效率，并实现了跨大数据集的协同过滤。