Method and apparatus for incremental computation of the accuracy of a categorization-by-example system

A computer-implemented method of incrementally updating precision and recall curves in a k nearest neighbor database, said database including original documents, categories, category assignments for the original documents, and category scores for the original documents, the method including:

• retaining for the original documents a list of their m nearest neighbors and corresponding similarity scores, wherein m>k;
• adding or deleting one or more category assignments to one or more original documents;
• updating category scores of the documents influenced by the adding or deleting of one or more category assignments, for at least the categories to which the category assignments were added or deleted;
• and
• computing precision and recall curves for the categories having updated category scores.

A computer-implemented method of incrementally adding category assignments to particular original documents in a k nearest neighbor database, said database including original documents, categories, category assignments for the original documents, and category scores for the original documents, the method including:

• retaining for the original documents a first list of their k nearest neighbors and corresponding similarity scores;
• retaining for the original documents a second list of m–k additional nearest neighbors and corresponding similarity scores;
• adding one or more category assignments for one or more particular original documents;
• computing category scores for the particular original documents and a predetermined number of nearest neighbors of the particular original documents, for those categories to which the category assignments are added, based on the retained similarity scores;
• and
• computing precision and recall curves for the categories to which the category assignments are added.

A computer-implemented method of incrementally adding one or more documents to a k nearest neighbor database, said database including original documents, categories, category assignments for the original documents, and category scores for the original documents, the method including:

• retaining for the original documents a first list of their k nearest neighbors and corresponding similarity scores;
• retaining for the original documents a second list of m–k additional nearest neighbors and corresponding similarity scores;
• adding one or more documents;
• calculating similarity scores between the added documents, and the added and original documents;
• modifying the retained first and second nearest neighbor lists for a predetermined number of nearest neighbors of the added documents;
• adding category assignments for the added documents;
• computing one or more category scores for the added documents and the predetermined number of nearest neighbors of the added documents, based on the retained and calculated similarity scores;
• and
• computing precision and recall curves for the categories to which the category assignments are added.

A computer-implemented method of incrementally deleting category assignments from particular documents in a k nearest neighbor database, said database including original documents, categories, category assignments for the original documents, and category scores for the original documents, the method including:

• retaining for the original documents a first list of their k nearest neighbors and corresponding similarity scores;
• retaining for the original documents a second list of m–k additional nearest neighbors and corresponding similarity scores;
• deleting one or more of the category assignments for one or more particular original documents;
• computing category scores for the particular original documents and a predetermined number of nearest neighbors of the particular original documents, for those categories from which the category assignments are deleted, based on the retained similarity scores;
• and
• computing precision and recall curves for the categories from which the category assignments are deleted.

A computer-implemented method of incrementally deleting documents from a k nearest neighbor database, said database including original documents, categories, category assignments for the original documents, and category scores for the original documents, the method including:

• retaining for the original documents a first list of their k nearest neighbors and corresponding similarity scores;
• retaining for the original documents a second list of m–k additional nearest neighbors and corresponding similarity scores;
• deleting one or more of the original documents and corresponding category assignments from the database;
• deleting the deleted documents from the retained first and second nearest neighbor lists for a predetermined number of nearest neighbors of the deleted documents;
• computing one or more category scores for a predetermined number of nearest neighbors of the deleted documents, based on the retained similarity scores;
• and
• computing precision and recall curves for the categories in which the deleted documents had category assignments.

A computer-implemented method of incrementally adding category assignments to particular original documents in a k nearest neighbor database, said database including original documents, categories, category assignments for the original documents, and category scores for the original documents, the method including:

• retaining for the original documents a first list of their k nearest neighbors and corresponding similarity scores;
• creating an influence list of original documents having a particular original document among their k nearest neighbors;
• adding one or more category assignments for one or more particular original documents;
• identifying influenced original documents from the influence list for the particular original documents to which the category assignments are added;
• computing category scores of the influenced original documents and of the particular original documents, for those categories to which the category assignments are added, based on the retained similarity scores;
• and
• computing precision and recall curves for the categories to which the category assignments are added.

A computer-implemented method of incrementally adding one or more documents to a k nearest neighbor database, said database including original documents, categories, category assignments for the original documents, and category scores for the original documents, the method including:

• retaining for the original documents a first list of their k nearest neighbors and corresponding similarity scores;
• creating an influence list of those original documents having certain original documents among their k nearest neighbors;
• adding one or more documents to the database;
• calculating similarity scores between the added documents, and the added and original documents;
• updating the retained first list of k nearest neighbors to include the added documents;
• updating the influence list to include the added documents;
• adding category assignments for the added documents;
• computing one or more category scores of the added and original documents influenced by the category assignments, based on the retained and calculated similarity scores;
• and
• computing precision and recall curves for the categories to which the category-assignments are added.

A computer-implemented method of incrementally deleting category assignments from particular documents in a k nearest neighbor database, said database including original documents, categories, category assignments for the original documents, and category scores for the original documents, the method including:

• retaining for the original documents a first list of their k nearest neighbors and corresponding similarity scores;
• creating an influence list of those original documents having certain original documents among their k nearest neighbors;
• deleting one or more category assignments for one or more particular original documents;
• identifying influenced original documents from the influence list for the particular original documents from which the category assignments are deleted;
• computing category scores of the influenced original documents and of the particular original documents for those categories from which the category assignments are deleted, based on the retained similarity scores;
• and
• computing precision and recall curves for the categories from which the category assignments are deleted.

A computer-implemented method of incrementally deleting one or more documents to a k nearest neighbor database, said database including original documents, categories, category assignments for the original documents, and category scores for the original documents, the method including:

• retaining for the original documents a first list of their k nearest neighbors and corresponding similarity scores;
• retaining for the original documents a second list of m–k additional nearest neighbors and corresponding similarity scores;
• creating an influence list of those original documents having certain original documents among their k nearest neighbors;
• deleting one or more documents from the database and corresponding category assignments;
• updating the retained first and second lists of m nearest neighbors to delete the deleted documents;
• updating the influence list to delete the deleted documents;
• computing one or more category scores of the original documents influenced by the deleted documents, based on the retained similarity scores;
• and
• computing precision and recall curves for the categories in which the deleted documents had category assignments.