System and method for positional representation of content for efficient indexing, search, retrieval, and compression

• US 20080059488A1
• Filed: 08/23/2006
• Published: 03/06/2008
• Est. Priority Date: 08/23/2006
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Ramaswamy, Ganesh N., Iyengar, Giridharan
• Granted Patent: US 7,747,629 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures

Abstract

A method of generating a positional representation of a document, including identifying each unique term in a document and positions in the document at which the unique term appears, and for the each unique term, storing positional information derived from the positions into a positional representation.

Claims

1. A method of generating a positional representation of a document, comprising:

identifying unique terms in a document and determining positions in the document at which each of the unique terms appear; and

for each of the unique terms, storing positional information derived from the positions into a positional representation.

2. The method of claim 1, further comprising:

identifying annotations in the document and determining annotation positions in the document at which each of the annotations appear; and

for each of the annotations, storing annotation positional information derived from the annotation positions into the positional representation.

3. The method of claim 1, further comprising storing a document identifier which is representative of the document into the positional representation.

4. The method of claim 3, wherein the storing of the positional information comprises:

generating a record having a first unique term of the unique terms and the positions corresponding to the first unique term; and

adding the record to the positional representation.

5. The method of claim 3, wherein the storing of the positional information comprises:

generating a record having a first unique term of the unique terms, a first position of the positions corresponding to the first unique term, and relative offsets of the positions subsequent to the first position; and

adding the record to the positional representation.

6. The method of claim 1, wherein each of the unique terms is made up of one or more words.

7. The method of claim 4, wherein the record further comprises a count of occurrences of the first unique term in the document.

8. The method of claim 5, wherein the record further comprises a count of occurrences of the first unique term in the document.

9. The method of claim 3, further comprising:

for each of the unique terms, generating an entry having a first unique term of the unique terms and the document identifier and adding the entry to an inverted index.

10. The method of claim 9, wherein the entry further comprises the positional information for the first unique term.

11. The method of claim 9, further comprising:

entering a search term;

searching the inverted index for an entry which matches the search term; and

upon determining a match, retrieving the document identifier from the entry and viewing a document corresponding to the document identifier;

12. The method of claim 11, wherein the document is generated by translating the positional representation having the document identifier into the document.

13. The method of claim 11, further comprising:

advancing presentation of the document to a position derived from the positional information in the positional representation.

14. The method of claim 11, further comprising:

advancing presentation of the document to a time derived from the positional information in the positional representation, wherein the document is a multimedia document.

15. A computer readable medium including computer code for generating a positional representation of a document comprising:

computer code for identifying each of the unique terms in a document and determining positions in the document at which each of the unique terms appear; and

for each of the unique terms, computer code for storing positional information derived from the positions into a positional representation.

16. A method of generating an inverted index from a positional representation of a document, comprising:

inputting a positional representation of a document having a document identifier and positional records, wherein the positional records include a term of the document and occurrence positions of the term in the document;

generating an entry for each of the positional records, wherein the entry includes the term and a document record, wherein the document record includes the document identifier and the occurrence positions; and

inserting the entry into an inverted index.

17. The method of claim 16, wherein the positional records include a count of the occurrence positions.

18. The method of claim 16, wherein the term is one or more words.

19. A computer readable medium having program instructions stored thereto for implementing the method claimed in claim 16, when executed in a digital processing device.

20. An apparatus for generating a positional representation of a text document, comprising:

a processor for converting a document to a positional representation by extracting each of the unique terms from the document and their respective occurrence positions in the document, generating entries for each of the unique terms which include a first one of the unique terms and a set of the occurrence positions corresponding to the first one of the unique terms, and adding each of the entries to a positional representation.