System for incrementally clustering news stories

1. A method of clustering news stories that are to be accessed over a computer network, comprising:

obtaining a plurality of news articles via the computer network;

clustering the news articles into a plurality of initial clusters;

for a subset of the news articles in the initial clusters that are less than a predetermined age limit and any unclustered news articles that are less than the predetermined age limit, determining whether to form one or more new clusters or assign to the initial clusters in an incremental clustering process; and

storing indications of the initial clusters and the one or more new clusters, if any, so as to be accessible for sending a portion of the news articles to users in a clustered format based on the initial clusters and the one or more new clusters, if any;

wherein the news articles that are less than the predetermined age limit are defined as transient articles and the remaining news articles are defined as fixed articles, wherein the incremental clustering is withheld from being performed on the fixed articles so that the fixed articles retain their initial clusters;

wherein the incremental clustering process is performed by:

for each transient article, finding one or more nearest neighbor articles from the entire corpus of articles, including fixed and transient articles;

for each transient article selected from a randomly ordered set, determining whether a ratio of nearest neighbors that are fixed articles to nearest neighbors that are transient articles is greater than a predetermined threshold; and

for each transient article selected from the randomly ordered set and based on the determination as to whether the ratio is greater than the predetermined threshold, adding such transient article and its one or more nearest neighbors that are transient articles to one or more of the initial clusters or forming a new cluster for such transient article and its one or more nearest neighbors that are transient articles.

2. The method of claim 1 , wherein the predetermined age limit is about four hours.

3. The method of claim 1 , wherein one or more nearest neighbors are found for each transient articles using a locality sensitive hashing technique.

4. The method of claim 1 , wherein the incremental clustering process further includes removing each transient article and its nearest neighbors from the randomly ordered set of news articles prior to clustering a next transient article from such randomly ordered set.

5. The method of claim 1 , further comprising recursively reclustering the entire corpus of news articles so as to find a lowest cost clustering after a predetermined time period.

6. The method of claim 1 , further comprising:

forming one or more new clusters including at least a portion of the subset of the news articles in the initial clusters.

7. An apparatus comprising at least a processor and a memory, wherein the processor and/or memory are configured to perform operations, comprising:

obtaining a plurality of news articles via the computer network;

clustering the news articles into a plurality of initial clusters;

for a subset of the news articles in the initial clusters that are less than a predetermined age limit and any unclustered news articles that are less than the predetermined age limit, determining whether to form one or more new clusters or assign to the initial clusters in an incremental clustering process; and

storing indications of the initial clusters and the one or more new clusters, if any, so as to be accessible for sending a portion of the news articles to users in a clustered format based on the initial clusters and the one or more new clusters, if any;

wherein the news articles that are less than the predetermined age limit are defined as transient articles and the remaining news articles are defined as fixed articles, wherein the incremental clustering is withheld from being performed on the fixed articles so that the fixed articles retain their initial clusters;

wherein the incremental clustering process is performed by:

for each transient article, finding one or more nearest neighbor articles from the entire corpus of articles, including fixed and transient articles;

for each transient article selected from a randomly ordered set, determining whether a ratio of nearest neighbors that are fixed articles to nearest neighbors that are transient articles is greater than a predetermined threshold; and

for each transient article selected from the randomly order set and based on the determination as to whether the ratio is greater than the predetermined threshold, adding such transient article and its one or more nearest neighbors that are transient articles to one or more of the initial clusters or forming a new cluster for such transient article and its one or more nearest neighbors that are transient articles.

8. The apparatus of claim 7 , wherein the predetermined age limit is about four hours.

9. The apparatus of claim 7 , wherein one or more nearest neighbors are found for each transient article using a locality sensitive hashing technique.

10. The apparatus of claim 7 , wherein the incremental clustering process further includes removing each transient article and its nearest neighbors from the randomly ordered set of news articles prior to clustering a next transient article from such randomly ordered set.

11. The apparatus of claim 7 , wherein the processor and/or memory are further configured to recursively recluster the entire corpus of news articles so as to find a lowest cost clustering after a predetermined time period.

12. The apparatus of claim 7 , wherein determining whether to form one or more new clusters or assign to the initial clusters in an incremental clustering process comprises:

determining whether to form one or more new clusters including at least a portion of the subset of the news articles in the initial clusters.

13. The apparatus of claim 7 , wherein the processor and/or memory are configured to perform operations, further comprising:

forming one or more new clusters including at least a portion of the subset of the news articles in the initial clusters.

14. At least one non-transitory computer readable storage medium having computer program instructions stored thereon that are arranged to perform operations, comprising:

obtaining a plurality of news articles via the computer network;

clustering the news articles into a plurality of initial clusters;

for a subset of the news articles in the initial clusters that are less than a predetermined age limit and any unclustered news articles that are less than the predetermined age limit, determining whether to form one or more new clusters or assign to the initial clusters in an incremental clustering process; and

storing indications of the initial clusters and the one or more new clusters, if any, so as to be accessible for sending a portion of the news articles to users in a clustered format based on the initial clusters and the one or more new clusters, if any;

wherein the news articles that are less than the predetermined age limit are defined as transient articles and the remaining news articles are defined as fixed articles, wherein the incremental clustering is withheld from being performed on the fixed articles so that the fixed articles retain their initial clusters;

wherein the incremental clustering process is performed by:

for each transient article, finding one or more nearest neighbor articles from the entire corpus of articles, including fixed and transient articles;

for each transient article selected from a randomly ordered set, determining whether a ratio of nearest neighbors that are fixed articles to nearest neighbors that are transient articles is greater than a predetermined threshold; and

for each transient article selected from the randomly order set and based on the determination as to whether the ratio is greater than the predetermined threshold, adding such transient article and its one or more nearest neighbors that are transient articles to one or more of the initial clusters or forming a new cluster for such transient article and its one or more nearest neighbors that are transient articles.

15. The at least one computer readable storage medium of claim 14 , wherein the predetermined age limit is about four hours.

16. The at least one computer readable storage medium of claim 14 , wherein one or more nearest neighbors are found for each transient articles using a locality sensitive hashing technique.

17. The at least one computer readable storage medium of claim 14 , wherein the incremental clustering process further includes removing each transient article and its nearest neighbors from the randomly ordered set of news articles prior to clustering a next transient article from such randomly ordered set.

18. The method of claim 1 , wherein determining whether to form one or more new clusters or assign to the initial clusters in an incremental clustering process comprises:

determining whether to form one or more new clusters including at least a portion of the subset of the news articles in the initial clusters.

19. The at least one computer readable storage medium of claim 14 , wherein determining whether to form one or more new clusters or assign to the initial clusters in an incremental clustering process comprises:

determining whether to form one or more new clusters including at least a portion of the subset of the news articles in the initial clusters.

20. The at least one computer readable storage medium of claim 14 , the computer program instructions stored thereon being arranged to perform operations, further comprising:

forming one or more new clusters including at least a portion of the subset of the news articles in the initial clusters.