首页>
外国专利>
Graph partitioning for massive scale graphs
Graph partitioning for massive scale graphs
展开▼
机译:大规模比例图的图分区
展开▼
页面导航
摘要
著录项
相似文献
摘要
Graph partitioning for massive scale graphs is described, such as for graphs having vertices representing people and edges representing connections between people in a social networking system; or for graphs where the vertices represent other items and the edges represent relationships between the items. In various embodiments a graph data allocator receives a graph vertex and its edges and allocates the vertex to one of a plurality of clusters each associated with one or more computing devices. In various embodiments the allocation is made by optimizing an objective function which takes into account both a cost of edges between clusters and a cost related to sizes of the clusters. In some examples the cost related to sizes of the clusters comprises a convex function applied to each of the cluster sizes. In examples, computations on the graph data are carried out with reduced runtimes and communications cost.
展开▼