System and method for computerized batching of huge populations of electronic documents

• US 9,002,842 B2
• Filed: 08/08/2012
• Issued: 04/07/2015
• Est. Priority Date: 08/08/2012
• Status: Active Grant

• Current Assignee: Microsoft Israel Research And Development (2002) Ltd (Microsoft Corporation)
• Original Assignee: Equivio Ltd. (Microsoft Corporation)
• Inventors: Ravid, Yiftach
• Primary Examiner(s): Arjomandi, Noosha
• Application Number:
  US13/569,752
• Publication Number:
  US 20140046942A1
• Time in Patent Office: 972 Days
• Field of Search: 707/737, 707/736, 707/740, 707/749
• US Class Current: 707/736
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

A method for computerized batching of huge populations of electronic documents, including computerized assignment of electronic documents into at least one sequence of electronic document batches such that each document is assigned to a batch in the sequence of batches and such that there is no conflict between batching requirements, the following batching requirements being maintained by a suitably programmed processor: a. pre-defined subsets of documents are always kept together in the same batch, b. batches are equal in size, c. the population is partitioned into clusters, and all documents in any given batch belong to a single cluster rather than to two or more clusters.

Claims

1. A method for computerized batching of huge populations of electronic documents, including

computerized assignment of electronic documents into at least one sequence of electronic document batches such that each document is assigned to a batch in the sequence of batches and such that absent conflict between batching requirements, the following batching requirements being maintained by a suitably programmed processor:

a. pre-defined subsets of documents are always kept together in the same batch

b. batches are equal in size

c. the population is partitioned into clusters and all documents in any given batch belong to a single cluster rather than to two or more clusters,

the method also comprising filling batches, separately for each of several clusters, including first using large keep-together sets as batches and then combining keep-together sets other than the large sets into batches and finally ordering the resulting batches into a sequence according to urgency.

2. The method according to claim 1 wherein absent conflict between batching requirements, the following batching requirement is also maintained:

positions of documents within the sequence of batches are determined by the document'"'"'s pre-known urgency for review such that highly urgent documents appear in early batches and less urgent documents appear in later batches.

3. The method according to claim 1 and also comprising computing an urgency score for at least one keep-together set which represents an attribute such as a central tendency of the urgency scores of all documents in the keep-together set.

4. The method according to claim 3 wherein said urgency score of said set comprises a mode (most frequently occurring) urgency score of all documents in the set.

5. The method according to claim 1 and also comprising filling batches, separately for each of several clusters, including first combining keep-together sets other than very small sets into batches and subsequently passing over the batches in an order determined by known urgency and enlarging at least some of the batches by adding the very small sets thereto, in the order determined by known urgency.

6. The method according to claim 5 wherein the very small sets comprise keep-together sets including only a single document.

7. The method according to claim 1 wherein requirement (a) (keep-together) takes precedence over (b) (equal size) such that documents with a uniform keep-together value are assigned to a single batch regardless of resulting size of the batch.

8. The method according to claim 1 wherein requirement (a) (keep-together) takes precedence over requirement (c)—

that each batch include only documents belonging to a single cluster—

in that an artificial intelligence functionality uniformizes the cluster id'"'"'s of all documents having a single keep-together id.

9. The method according to claim 1 wherein due to conflict between requirements (b), (c), there is for at least one cluster, a batch of lesser size than other batches equal in size.

10. The method according to claim 1 wherein, due to conflict between requirements (a), (b), there is at least one batch of greater size than other batches equal in size.

11. A computer program product, comprising a non-transitory tangible computer readable medium having computer readable program code embodied therein, said computer readable program code adapted to be executed to implement the method of claim 1.

12. A method for computerized batching of huge populations of electronic documents, including

computerized assignment of documents into at least one sequence of electronic document batches such that each document is assigned to a batch in the sequence of batches and such that absent conflict between batching requirements, the following batching requirements being maintained by a suitably programmed processor:

a. pre-defined subsets of documents are always kept together in the same batch

b. batches are equal in size

c. positions of documents within the sequence of batches are determined by the document'"'"'s pre-known urgency for review such that highly urgent e.g. highly relevant documents appear in early batches and less urgent e.g. less relevant documents appear in later batches,

wherein requirement (a) (keep-together) takes precedence over requirement (c)—

that each batch include only documents belonging to a single cluster—

in that an artificial intelligence functionality uniformizes the cluster id'"'"'s of all documents having a single keep-together id.

13. The method according to claim 12 wherein, due to conflict between requirements (a), (b), there is at least one batch of greater size than other batches equal in size.

14. The method according to claim 12 and also comprising computing an urgency score for at least one keep-together set which represents an attribute such as a central tendency of the urgency scores of all documents in the keep-together set.

15. The method according to claim 14 wherein said urgency score of said set comprises a mode (most frequently occurring) urgency score of all documents in the set.

16. The method according to claim 12 and also comprising filling batches, separately for each of several clusters, including first using large keep-together sets as batches and then combining keep-together sets other than the large sets into batches and finally ordering the resulting batches into a sequence according to urgency.

17. The method according to claim 12 and also comprising filling batches, separately for each of several clusters, including first combining keep-together sets other than very small sets into batches and subsequently passing over the batches in an order determined by known urgency and enlarging at least some of the batches by adding the very small sets thereto, in the order determined by known urgency.

18. The method according to claim 17 wherein the very small sets comprise keep-together sets including only a single document.

19. The method according to claim 12 wherein requirement (a) (keep-together) takes precedence over (b) (equal size) such that documents with a uniform keep-together value are assigned to a single batch regardless of resulting size of the batch.

20. A computer program product, comprising a non-transitory tangible computer readable medium having computer readable program code embodied therein, said computer readable program code adapted to be executed to implement the method of claim 12.

21. A system for computerized batching of huge populations of electronic documents, the system including:

apparatus for computerized assignment of documents into at least one sequence of batches; and

a processor for controlling said computerized assignment such that each document is assigned to a batch in the sequence of batches and such that there is no conflict between batching requirements, the following batching requirements being maintained;

a. pre-defined subsets of documents are always kept together in the same batch

b. batches are equal in size

c. the population is partitioned into clusters and all documents in any given batch belong to a single cluster rather than to two or more clusters,

the processor being operative for filling batches, separately for each of several clusters, including first combining keep-together sets other than very small sets into batches and subsequently passing over the batches in an order determined b known urgency and enlarging at least some of the batches by adding the very small sets thereto, in the order determined by known urgency.

22. A system for computerized batching of huge populations of electronic documents, the system including:

apparatus for computerized assignment of documents into at least one sequence of batches; and

a processor for controlling said computerized assignment such that each document is assigned to a batch in the sequence of batches and such that in the absence of conflict between batching requirements, the following batching requirements are maintained;

a. pre-defined subsets of documents are always kept together in the same batch

b. batches are equal in size

c. positions of documents within the sequence of batches are determined by the document'"'"'s pre-known urgency for review such that highly urgent documents appear in early batches and less urgent e.g. less relevant documents appear in later batches,

the processor being operative for filling batches, separately for each of several clusters, including first combining keep-together sets other than very small sets into batches and subsequently passing over the batches in an order determined by known urgency and enlarging at least some of the batches by adding the very small sets thereto, in the order determined by known urgency.

23. A system for computerized batching of huge populations of electronic documents, the system including:

apparatus for computerized assignment of documents into at least one sequence of batches; and

a processor for controlling said computerized assignment such that each document is assigned to a batch in the sequence of batches and such that there is no conflict between batching requirements, the following batching requirements being maintained;

a. pre-defined subsets of documents are always kept together in the same batch

b. batches are equal in size

c. the population is partitioned into clusters and all documents in any given batch belong to a single cluster rather than to two or more clusters,

the processor being operative for filling batches, separately for each of several clusters, including first using large keep-together sets as batches and then combining keep-together sets other than the large sets into batches and finally ordering the resulting batches into a sequence according to urgency.

24. The system according to claim 23 wherein absent conflict between batching requirements, the following batching requirement are also maintained:

positions of documents within the sequence of batches are determined by the document'"'"'s pre-known urgency for review such that more urgent documents appear in early batches and less urgent documents appear in later batches.