Indexing system using one-way hash for document service

• US 5,742,807 A
• Filed: 05/31/1995
• Issued: 04/21/1998
• Est. Priority Date: 05/31/1995
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Masinter, Larry M.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HO, RUAY L
• Application Number:
  US08/455,605
• Time in Patent Office: 1,056 Days
• Field of Search: 395/600, 395/650, 395/700, 395/800, 395/412, 395/421.06, 380/25, 380/23, 380/4, 364/962.1, 364/962.2, 364/963.3, 364/419.19
• US Class Current: 707/610
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

Systems and methods for managing a plurality of electronically stored documents in an open document repository employ a one-way hash function to compute a hash for the stored documents as an indexing link. A document management index maps an attribute of an original document stored in the repository to the hash and the document. A hash-to-location index maps the hash to an address location of the document in a file system of the repository. The attribute points to the hash which then points to the location for linking the attribute to the location.

Claims

1. An open document repository for electronically storing a plurality of documents comprising:

a file system for electronically storing an original document at an address location;

a document management index comprising a mapping between an attribute of the original document stored in the repository and a hash computed from the original document; and

a hash-to-location index interposed as a key link between the document management index and the file system comprising a mapping between the hash and the address location of the original document in the file system whereby the attribute points to the hash which points to the location for linking the attribute to the location for the documents stored in the repository.

2. The repository as defined in claim 1 wherein the hash comprises a computation from a low probability hash function.

3. The repository as defined in claim 1 wherein the hash comprises a computation from a cryptographically secure hash function.

4. The repository as defined in claim 1 wherein the attribute comprises a user preselected attribute of the original document.

5. The repository as defined in claim 4 wherein the attribute comprises one from a group of title, author and keyword of the original document.

6. The repository as defined in claim 1 wherein the hash-to-location index includes means for linking the hash to a backup system.

7. The repository as defined in claim 1 wherein the hash-to-location index includes means for linking the hash to an archive system.

8. The repository as defined in claim 1 further including means for validating a particular hash associated with a particular location in the hash-to-location index.

9. A document management system for electronically storing a document in a file system comprising:

index means interposed between a management index and the file system for sequentially linking a preselected attribute of the document to a hash computed from the document to a location in the file system where the document is stored.

10. The document management system as claimed in claim 9 wherein the hash is computed from either a low probability hash function or a cryptographically secure hash function.

11. The document management system as claimed in claim 9 wherein the attribute comprises a user selected feature of the document suggestive of an identity of the document.

12. In an open document repository containing a plurality of documents, a method of indexing each of the plurality for archival document service comprising steps of:

identifying an attribute of one of the plurality of documents to be electronically stored in the repository;

computing a hash of the one document;

mapping the hash to the attribute in a document management index;

identifying an address location of the one document in a file system of the repository; and

,

mapping the address location to the hash in a hash-to-location index wherein the hash-to-location is disposed as a security key link between the document management index and the file system and whereby the attribute is used to point to the location through the indexes.

13. A document management method for a document repository containing a plurality of documents in a file system of the repository comprising steps of:

storing an original document in the file system at a location;

computing a hash of the document using a one-way hash function;

storing the hash and the location as an associated mapping in a hash to location index disposed as a security link for an entrance to the file system;

acquiring an attribute of the document; and

,

storing the attribute and the hash in a document management index whereby the attribute points to the hash and the hash points to the location for selective access of the document from the file system.

14. The document management method as claimed in claim 13 further comprising steps for retrieval of the document of:

querying the document management index to identify the hash for the document;

using the hash to identify the location from the hash to location index; and

,

retrieving the document from the location.

15. The document management method as claimed in claim 13, wherein a back up system is also provided and further comprising steps for backup of the repository of:

identifying a particular file system of the repository;

for each directory or file in the particular file system computing a representative hash from the one way hash function;

for each computed representative hash, determining all locations for said each directory or file in the back up and file systems from the hash to location index;

copying said each directory or file to the back up system determined not to be at a back up location; and

,

marking the hash to location index to indicate that the copied directory or files are in the back up system.

16. The document management method as claimed in claim 15 further comprising, when reusing or discarding backup media, identifying and erasing all entries for the media from the hash to location index.

17. The document management method as claimed in claim 15, wherein an archive system is also provided and further comprising steps for archiving of the repository of:

marking one file for archive;

obtaining a hash for the one file;

determining if the hash is in the hash to location index and if the hash is marked as archived or backed up;

marking the hash as wanting archive in the hash to location index.

18. The document management method as claimed in claim 17 further comprising steps of retrieval of the original document of:

obtaining the hash;

identifying a most accessible location of the document from the hash to location index; and

,

retrieving the document from said most accessible location.

19. The document management method as claimed in claim 17 further comprising when reusing backup media, checking if any entry on the backup media that is marked as wanting backup in the hash to location index is actually archived, and if not, copying said entry to archive.

20. An indexing system using a one-way hash for backup/archive document service in a distributed file system including a plurality of processing units each having a plurality of files for selective backup or archive, wherein the plurality of files are intended for communication to and storage in the backup/archive document service, comprising:

means for computing the one-way hash for a one of the files in a one of the processing units; and

,

means for determining if said one-way hash is already included in the backup/archive document service and if not, storing the one file and recording said one-way hash in the backup/archive document service, and if already included, computing another one-way hash for another of the files.

21. The indexing system as defined in claim 20 including a directory of one-way hashes respectively associated with a plurality of files wherein said one processing unit includes means for computing a hash-of-hashes of said directory recursively, and means for storing said hash-of-hashes in the backup/archive document service.

22. A method for synchronizing files between first and second processing units and for replicating files therebetween, comprising:

designating the first processing unit as a file repository having a plurality of files;

designating the second processing unit as a backup service to the file repository;

computing by the second processing unit of a one-way hash of a one of the files in the first repository; and

,

determining if said one-way hash is already stored in the second processing unit, and if not, storing the one file and recording the one-way hash in the second processing unit, and if already included, calling another of the files of the first processing unit for said computing and determining.

23. The method as defined in claim 22 wherein said first processing unit includes a directory of the files stored therein and said second processing unit further selectively computes an other one-way hash of said directory or a directory of files and directories, or a hash-of-hashes of said directory, recursively.