Document cache replacement policy for automatically generating groups of documents based on similarity of content

• US 6,842,876 B2
• Filed: 04/14/1998
• Issued: 01/11/2005
• Est. Priority Date: 04/14/1998
• Status: Expired due to Fees

• Current Assignee: Majandro LLC (IP Edge LLC)
• Original Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Schilit, William Noah, Price, Morgan N., Golovchinsky, Gene
• Primary Examiner(s): Paula, Cesar B
• Application Number:
  US09/059,335
• Publication Number:
  US 20020052898A1
• Time in Patent Office: 2,464 Days
• Field of Search: 707/500, 707/532, 707/531, 707/4, 707/7, 707/530, 715/500, 715/532, 715/530, 715/531
• US Class Current: 715/256
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

A document storage management system and method that manages the storage of documents based upon the similarity of the content of the documents. Groups of documents are created based upon the similarity of the contents of the documents. Those groups are displayed to the user in a ranked list of selectable groups to permit selection of a group or document. The storage of the selected group or document is then managed by, for example, deleting, compressing, or copying. The displayed list may be ranked based upon a least recently used policy, the relevance to a predetermined topic, the size of the group, the radius of the group based upon the maximum distance of any document from the group centroid, the number of documents in the group and any other combination of parameters.

Claims

1. A cache management system communicating with a document storage device, a plurality of documents stored on the document storage device, the system defining a replacement policy of a cache memory and comprising:

a group generator that automatically identifies a plurality of groups of documents from the plurality of documents in the cache memory based on a similarity of a content of the plurality of documents without a user input;

a display for displaying an ordered list of groups, each group in the list being ranked based on at least one or more of a least recently used metric of that group, a relevance metric of that group, a size of that group, a radius of that group, and a total number of documents in that group;

a selector that the user uses to select at least one of the groups of documents displayed in the ordered list; and

an operation command input device that accepts an operation command input by the user that instructs a cache manager to free up space in the cache memory;

wherein

the cache manager manages storage of the selected at least one group of documents to free up space in the cache memory based on the selection made by the selector and the operation command by acting on the selected at least one group of documents.

2. The system of claim 1, wherein the group generator generates at least one group of documents based further on at least one attribute of each of the plurality of documents.

3. The system of claim 1, wherein the operation command instructs the cache manager to delete the selected group of documents from the cache memory.

4. The system of claim 1, wherein the operation command instructs the cache manager to compress the selected group of documents in the cache memory.

5. The system of claim 1, further comprising a presentation device that presents a list of at least one selectable group identifier that corresponds to the at least one group of documents.

6. The system of claim 1, wherein the group generator orders the plurality of groups based on at least one group characteristic.

7. The system of claim 6, wherein the group generator comprises a keyword generator that generates a set of keywords for each group and the at least one group characteristic for each group is the corresponding set of keywords.

8. The system of claim 6, wherein the group generator comprises a group score calculator that determines a group score for each group.

9. The system of claim 8, wherein the group score for each group is the sum of at least one of:

a product of a first variable and a least-recently-used metric of that group;

a product of a second variable and a relevance metric of that group;

a product of a third variable and a size of that group;

a product of a fourth variable and a radius of that group; and

a product of a fifth variable and a total number of documents in that group.

10. The system of claim 9, wherein the relevance metric for each group is based on the relevance of that group to at least one predetermined topic.

11. The system of claim 9, wherein the radius for each group is based on a maximum distance of the documents from a group centroid.

12. The system of claim 8, wherein the at least one group characteristic is the group score.

13. The system of claim 1, further comprising a group filter that identifies groups that have at least one group attribute that satisfies at least one predetermined criterion.

14. The system of claim 13, wherein said group filter removes the identified groups from the list of groups.

41. The system of claim 1, wherein the document storage device is the cache memory.

15. A method for managing a replacement policy in a cache memory in a document storage system, comprising:

automatically grouping a plurality of documents stored in a cache memory of a document storage device into a plurality of groups based on a similarity of a content of the plurality of documents without a user input;

displaying an ordered list of the plurality of groups, each group in the list being ranked based on at least one or more of a least recently used metric of that group, a relevance metric of that group, a size of that group, a radius of that group, and a total number of documents in that group;

selecting using user input at least one of the plurality of groups of documents in the ordered list;

accepting an operation command input by the user to free up space in the cache memory; and

managing the storage in the cache memory by acting on the selected at least one of the plurality of groups to free up space in the cache memory using the operation command.

16. The method of claim 15, wherein the plurality of documents are grouped further based upon at least one attribute of each of the plurality of documents.

17. The method of claim 15, wherein the step of managing the storage comprises deleting the selected at least one of the plurality of groups from the cache memory.

18. The method of claim 15, wherein the step of managing comprises compressing the selected at least one of the plurality of groups in the cache memory.

19. The method of claim 15, further comprising generating a plurality of group keywords for each of the plurality of groups.

20. The method of claim 15, further comprising displaying a plurality of selectable group identifiers corresponding to the plurality of groups, wherein the step of selecting comprises selecting at least one of the selectable group identifiers corresponding to the selected at least one of the plurality of groups.

21. The method of claim 15, further comprising the step of ranking the plurality of groups according to at least one group characteristic.

22. The method of claim 21, wherein the ranking step comprises determining a group score.

23. The method of claim 22, wherein determining the group score for each group comprises summing at least one of:

a product of a first variable and a least-recently-used metric of each group;

a product of a second variable and a relevance metric of each group;

a product of a third variable and a size of each group;

a product of a fourth variable and a radius of each group; and

a product of a fifth variable and a total number of documents in each group.

24. The method of claim 23, wherein the relevance metric for each group is based on a relevance of that group to at least one topic.

25. The method of claim 23, wherein the radius for each group is based on a maximum distance of the documents in that group from the group centroid.

26. The method of claim 15, further comprising generating set of group keywords for each of the plurality of groups.

27. The method of claim 15, wherein managing the storage comprises deleting the selected at least one of the documents.

28. The method of claim 17, wherein managing the storage comprises compressing the selected at least one of the documents.

29. The method of claim 17, wherein managing the storage comprises copying the selected at least one of the documents.

42. The method of claim 15, wherein the document storage device is the cache memory.

30. A graphical user interface for managing a storage and replacement policy of a plurality of documents in a cache memory, the interface comprising:

a display for displaying to a user an ordered list of groups of documents from a plurality of documents that have been automatically pregrouped based on a similarity of a content of the documents in the cache memory without user input;

at least one selectable group identifier visible on the display, the at least one selectable group identifier representing corresponding groups of documents in the cache memory, the at least one selectable group identifier being ranked based on at least one or more of a least recently used metric of a corresponding group, a relevance metric of the corresponding group, a size of the corresponding group, a radius of the corresponding group, and a total number of documents in the corresponding group, wherein the groups of documents comprise the plurality of documents that are automatically grouped based on the content of the plurality of documents without user input, wherein the at least one selectable group identifier is responsive to a selection of the at least one selectable group identifier by at least a predetermined user input to select a corresponding at least one group of documents; and

a cache manager responsive to an operational command input by a user to perform a storage management function, defining the replacement policy of the cache memory, on the selected at least one group of documents in the cache memory to free up space of the cache memory by acting on the selected at least one group.

31. The interface of claim 30, wherein the plurality of documents are grouped further based on at least one attribute of each of the plurality of documents.

32. The interface of claim 30, wherein the operational command is a command to delete the at least one selected group of documents and the cache manager deletes the selected at least one group of documents from the cache memory.

33. The interface of claim 30, wherein the operational command is a command to compress the at least one selected group of documents and the cache manager compresses the selected at least one group of documents.

34. The interface of claim 30, wherein the at least one selectable group identifier is displayed in a list that is ordered based on at least one group characteristic.

35. The interface of claim 34, wherein the at least one selectable group identifier comprises a set of keywords for each group and the at least one group characteristic for each group is the corresponding set of keywords.

36. The interface of claim 34, wherein the at least one group characteristic is a group score.

37. The interface of claim 36, wherein the group score is the sum of at least one of:

a product of a first variable and a least-recently-used metric of that group;

a product of a second variable and a relevance metric of that group;

a product of a third variable and a size of that group;

a product of a fourth variable and a radius of that group; and

a product of a fifth variable and a total number of documents in that group.

38. The interface of claim 37, wherein the relevance metric for each group is based on the relevance of that group to at least one predetermined topic.

39. The interface of claim 37, wherein the radius for each group is based on a maximum distance of the documents from a group centroid.

40. The interface of claim 30, wherein the at least one selectable group identifier represents a corresponding group of documents that each have a group attribute that satisfies at least one predetermined criterion.