# US 2012/0254188 A1 · Cluster-based identification of news stories

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254188 A1
- Document ID: US20120254188A1
- Status: Published application
- Kind: A1
- Application number: 13/434,600
- Filed: 2012-03-29
- Published: 2012-10-04
- Earliest claimed: 2011-03-30
- Assignees: Vcvc III LLC
- Inventors: Krzysztof Koperski; Satish Bhatti; Jisheng Liang; Adrian Klein
- Web page: https://patentgrep.com/patent/US20120254188A1

## CPC

- G06F 16/285: {Clustering or classification}
- G06F 16/3334: {Selection or weighting of terms from queries, including natural language queries}
- G06F 16/335: Filtering based on additional data, e.g. user or group profiles (filtering in web context G06F16/9535, G06F16/9536)
- G06F 16/35: Clustering; Classification
- G06F 16/353: into predefined classes
- G06F 16/355: Creation or modification of classes or clusters
- G06F 16/38: Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06F 16/9538: Presentation of query results
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods, systems, and techniques for cluster-based content recommendation are described. Some embodiments provide a content recommendation system (“CRS”) configured to recommend news stories about events or occurrences. In some embodiments, a news story about an event includes multiple related content items that each include an account of the event and that each reference one or more entities or categories that are represented by the CRS. In one embodiment, the CRS identifies news stories by generating clusters of related content items. Then, in response to a received query that indicates a keyterm, entity, or category, the CRS determines and provides indications of one or more news stories that are relevant to the received query. In some embodiments, at least some of these techniques are employed to implement a news story recommendation facility in an online news service.

## Claims

### Claim 1

A method in a content recommendation system, the method comprising:
identifying a news story about an event, the news story including multiple related content items that each give an account of the event and that each reference multiple entities or categories that are each electronically represented by the content recommendation system, comprising:
processing content items to determine semantic information that includes identified entities and relations between the identified entities;
storing the identified entities and relations in a repository of the content recommendation system;
generating a cluster that includes the multiple related content items, based at least in part on how many entities each of the multiple related content items has in common with one or more other of the multiple related content items; and
storing an indication of the identified news story and the generated cluster.

### Claim 2 (depends on 1)

The method of claim 1 wherein generating the cluster includes:
determining whether a candidate cluster of a plurality of clusters is a suitable cluster for one of the multiple of related content items, based at least in part on one or more of: distances between the one content item and content items of the candidate cluster, a quantity of common keyterms between the one content item and content items of the candidate cluster, and a quantity of content items of the candidate cluster that have a distance to the content item that is below a predetermined threshold;
if the candidate cluster is determined to be a suitable cluster, adding the one content item to the candidate cluster; and
if the candidate cluster is not determined to be a suitable cluster, creating a new cluster that includes the one content item as a seed.

### Claim 3 (depends on 1)

The method of claim 1 wherein generating the cluster includes finding a candidate cluster that is nearest to one of the multiple related content items.

### Claim 4 (depends on 3)

The method of claim 3 wherein finding the candidate cluster that is nearest to one of the multiple related content items includes comparing the one content item to content items of the candidate cluster.

### Claim 5 (depends on 3)

The method of claim 3 wherein finding the candidate cluster that is nearest to one of the multiple related content items includes comparing the one content item to a centroid of the candidate cluster.

### Claim 6 (depends on 3)

The method of claim 3 wherein finding the candidate cluster includes computing a cosine distance between a term vector that represents the one content item and a term vector that represents a content item of the candidate cluster.

### Claim 7 (depends on 3)

The method of claim 3 wherein finding the candidate cluster includes finding a cluster that includes a content item that has a cosine distance to the one content item that is lower than cosine distances between the one content item and other content items of other clusters.

### Claim 8 (depends on 1)

The method of claim 1 wherein identifying the news story includes processing only content items published during a time interval that is about one day in length.

### Claim 9 (depends on 1)

The method of claim 1 wherein identifying the news story includes reassigning content items from clusters that are smaller than a specified size to clusters that are larger than the specified size.

### Claim 10 (depends on 1)

The method of claim 1 wherein identifying the news story includes merging two clusters into a single cluster when distances between centroids of the two clusters are lower than a specified threshold.

### Claim 11 (depends on 1)

The method of claim 1 wherein identifying the news story includes generating two or more sub-clusters of the generated cluster, each sub-cluster including one or more of the multiple related content items.

### Claim 12 (depends on 11)

The method of claim 11 wherein generating the two or more sub-clusters includes decomposing the multiple content items using a k-means process.

### Claim 13 (depends on 11)

The method of claim 11 wherein generating the two or more sub-clusters includes discarding a candidate sub-cluster if a distance measured between a centroid of the generated cluster and a centroid of the candidate sub-cluster is lower than a specified threshold.

### Claim 14 (depends on 11)

The method of claim 11 wherein generating the two or more sub-clusters includes retaining a candidate sub-cluster if a distance measured between a centroid of the generated cluster and a centroid of the candidate sub-cluster is greater than a specified threshold.

### Claim 15 (depends on 1)

The method of claim 1 wherein identifying the news story includes determining a representative content item for the news story by selecting one of the multiple related content items that is nearest to a centroid of the generated cluster.

### Claim 16 (depends on 1)

The method of claim 1 wherein storing the indication of the identified news story and the generated cluster includes storing an association between a keyterm, entity, or category and the generated cluster, along with an indicator of relevance of the keyterm, entity, or category to the generated cluster.

### Claim 17 (depends on 1)

The method of claim 1 wherein storing the indication of the identified news story and the generated cluster includes storing one or more of: a representative content item for the identified news story; a representative image for the identified news story; a centroid of the generated cluster, the centroid including a vector of keyterms and/or entity identifiers; top categories for the identified news story; two or more sub-clusters for the identified news story; a growth rate of the generated cluster; and a date.

### Claim 18 (depends on 1)

The method of claim 1, further comprising:
receiving a search query that includes an indication of a keyterm, entity or category;
selecting a news story from a plurality of news stories, the selecting based on how many keyterms, entities, or categories are in common between the received search query and the multiple content items of the selected news story; and
transmitting an indication of the selected news story.

### Claim 19 (depends on 18)

The method of claim 18, further comprising:
selecting multiple news stories that are each relevant to the received search query; and
sorting the multiple selected news stories based on one or more of: the number of content items in each news story, a rate of growth of the number of content items in each news story, an importance of the indicated keyterm, entity, or category to content items in each news story, an age of each news story.

### Claim 20

A method in a content recommendation system for recommending a news story about an event, the news story including multiple content items that each give an account of the event, and that each reference multiple entities or categories that are each electronically represented by the content recommendation system, comprising:
receiving a search query that includes an indication of an entity or a category;
selecting the news story from a plurality of news stories, the selecting based on how many entities or categories are in common between the received search query and the multiple content items of the selected news story; and
transmitting an indication of the selected news story.

### Claim 21 (depends on 20)

The method of claim 20, further comprising:
for a plurality of content items in a plurality of news stories about an event,
processing content items to determine semantic information that includes identified entities and relations between the identified entities;
storing the identified entities and relations in a repository of the content recommendation system;
generating a cluster that includes the multiple related content items, based at least in part on how many entities each of the multiple related content items has in common with one or more other of the multiple related content items; and
storing an indication of the identified news story and the generated cluster.

### Claim 22

A computer-readable medium including contents that enable a computing system to recommend content, by performing the method comprising:
identifying a news story about an event, the news story including multiple related content items that each give an account of the event and that each reference multiple entities or categories that are each electronically represented by the content recommendation system, comprising:
processing content items to determine semantic information that includes identified entities and relations between the identified entities;
storing the identified entities and relations in a repository of the content recommendation system;
generating a cluster that includes the multiple related content items, based at least in part on how many entities each of the multiple related content items has in common with one or more other of the multiple related content items; and
storing an indication of the identified news story and the generated cluster.

### Claim 23 (depends on 22)

The computer-readable medium of claim 22 wherein the computer-readable medium is at least one of a memory in a mobile computing device or a data transmission medium transmitting a generated signal containing the contents.

### Claim 24 (depends on 22)

The computer-readable medium of claim 22 wherein the contents are instructions that when executed cause the computing system to perform the method.

### Claim 25

A computing system configured to recommend content, comprising:
a memory;
a module stored on the memory that is configured, when executed, to identify a news story about an event, the news story including multiple related content items that each give an account of the event and that each reference multiple entities or categories that are each electronically represented by the content recommendation system, by:
processing content items to determine semantic information that includes identified entities and relations between the identified entities;
storing the identified entities and relations in a repository of the content recommendation system;
generating a cluster that includes the multiple related content items, based at least in part on how many entities each of the multiple related content items has in common with one or more other of the multiple related content items; and
storing an indication of the identified news story and the generated cluster.

### Claim 26 (depends on 25)

The computing system of claim 25 wherein the module includes software instructions for execution in the memory of the computing system.

### Claim 27 (depends on 25)

The computing system of claim 25 wherein the module is a content recommendation system.

### Claim 28 (depends on 25)

The computing system of claim 25 wherein the computing system is a mobile computing device and the module is a content recommendation module.

### Claim 29 (depends on 25)

The computing system of claim 25 wherein the module is configured to recommend news stories to at least one of a personal digital assistant, a smart phone, a laptop computer, a tablet computer, and/or a third-party application.
