Patent ID: 8631044

Claim:
A non-transitory computer readable medium having software instructions stored thereon for matching an advertisement with a phrase, the software instructions, when executed by a processor, cause the processor to perform operations comprising: receiving a first graph data structure, a first weight matrix and degree distribution data as input, the first graph data structure having a first group of advertisement nodes each representing an advertisement and a second group of phrase nodes each representing a phrase, the first weight matrix including weight values, each representing a bid value for each connection between an advertisement node of the first group and a phrase node of the second group in the first graph data structure; generating a second graph data structure including nodes corresponding to the first graph data structure and additional dummy nodes; generating a second weight matrix including the first weight matrix and additional weight values each associated with one of the advertisement nodes in the first graph data structure and one of the additional dummy nodes, the additional weight values in the second weight matrix being determined based on the degree distribution data and the second weight matrix also including a group of zero weight values; constraining the nodes in the second graph data structure that correspond to the first graph data structure to a predetermined degree value and not constraining the additional dummy nodes in the second graph data structure; determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value to generate an intermediate graph data structure having binary weight values; truncating the intermediate graph data structure to yield a truncated portion; and generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output.