Facebook, Inc.

Maja Kabiljo

Jonathan D Chang

Deepayan Chakrabarti

Avery Li Kuang Ching

Aleksandar Ilic

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, &#x201c;relationship among users&#x201d; as &#x201c;edges&#x201d; in the directed graph, and &#x201c;items&#x201d; as &#x201c;worker data&#x201d; that is locally-calculated, stored, and managed in individual worker computers. When a local computing process is completed, the &#x201c;worker data&#x201d; 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.

Collaborative filtering in directed graph

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.

Growing community of inventors

Menlo Park, CA, United States of America

Maja Kabiljo