Yahoo! Inc.

Kevin John Lang

Anirban Dasgupta

Lee Rhodes

Reid Marlow Andersen

Vivek B Tawde

Briefly, embodiments of methods and/or systems of computation via array decomposition are disclosed. For one embodiment, as an example, a system may be capable of implementation of an advertising audience overlap analysis dashboard in which for an audience exceeding 100 million users and exceeding 10,000 user groups. Such a system embodiment, for example, may be capable of computing an exact count of user overlap among the user groups in less than two hours.

Computation through array decomposition

Techniques are provided for improving the speed and accuracy of analytics on big data using theta sketches, by converting fixed-size sketches to theta sketches, and by performing set operations on sketches. In a technique for performing a set operation, two sketches are analyzed to identify the maximum value of each sketch. The maximum values of the two sketches are compared. Based the comparison, one or more values are removed from the sketch whose maximum value is greater. After the removal, a set operation (e.g., union, intersection, or difference) is performed based on the modified sketch and the unmodified sketch. A result of the set operation is a third sketch, which may be used to estimate a cardinality of the larger data sets that are represented by the two input sketches.

System and method for performing set operations with defined sketch accuracy distribution

An improved system and method is provided for identifying web communities from seed sets of web pages. A seed set of web pages may be represented as a set of seed vertices of a graph representing a collection of web pages. An initial probability distribution may be constructed on vertices of the graph by assigning a nonzero value to the vertices belonging to the seed set. Then a sequence of probability distributions may be produced on the vertices of the graph by modifying the probability distribution over a series of one-step walks of the probability distribution over the vertices of the graph. For each probability distribution produced in the sequence, level sets of vertices may be generated, and a level set with minimal conductance may be selected for each probability distribution. The level set with the least conductance may then be output representing a community of web pages.

System and method for identifying web communities from seed sets of web pages

A system and method to identify target node graphs from predetermined seed node subsets are described. A one-sided constrained spectral embedding of a graph using a predetermined set of seed nodes within the graph is computed. Next, a threshold boundary is identified to define a target area for a target subgraph within the embedded graph using predetermined network-flow calculations, the target subgraph including the predetermined set of seed nodes. Finally, the target subgraph is identified based on the calculated threshold boundary.

System and method for identifying target node graphs from predetermined seed node subsets

Methods and apparatus for locating a dense and isolated sub-graph from a weighted graph having multiple nodes and multiple weighted edges are described. Each node in the weighted graph represents an object. Each weighted edge in the weighted graph connects two nodes and represents the relationship between the two objects represented by the two corresponding nodes. To located the sub-graph, first, an auxiliary weighted graph is constructed using the weighted graph and three coefficients: &#x3b1;, &#x3b2;, and &#x3b3;, where &#x3b1;, &#x3b2;, and &#x3b3; are greater than 0, &#x3b1; influences the number of nodes inside the sub-graph, &#x3b2; influences the sum of the weights associated with the edges connecting a node inside the sub-graph and a node outside the sub-graph, and &#x3b3; influences the sum of the weights associated with the edges connecting two nodes both inside the sub-graph, and by adding a source node s and a sink node t. Next, the auxiliary weighted graph is partitioned into two parts using the s-t minimum cut algorithm. The sub-graph is the part associated with the sink node t in its original form, with the original undirected edges and unmodified edge weights and excluding the sink node t and all the new edges added during the construction of the auxiliary weighted graph.

Growing community of inventors

Mountain View, CA, United States of America

Kevin John Lang