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

• US 7,747,629 B2
• Filed: 08/23/2006
• Issued: 06/29/2010
• Est. Priority Date: 08/23/2006
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Ramaswamy, Ganesh N., Iyengar, Giridharan
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Casanova; Jorge A
• Application Number:
  US11/508,642
• Publication Number:
  US 20080059488A1
• Time in Patent Office: 1,406 Days
• Field of Search: 707/3, 707/102, 707/741, 707/769, 715/721, 715/764
• US Class Current: 707/741
• 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 advancing within a video clip of a multimedia document, the method comprising:

searching first entries of an inverted index for a first annotation matching a query, each first entry having a unique first annotation and a list of document identifiers of multimedia documents having the unique first annotation;

upon determining the matching first annotation, searching second entries of a positional representation corresponding to one of the document identifiers for a second annotation matching the query, each second entry having a unique second annotation and occurrence positions of the unique second annotation within a multimedia document;

upon determining the matching second annotation, deriving a time within the video clip of the multimedia document corresponding to the one document identifier from an occurrence position of the second annotation, and advancing presentation of the video clip to the derived time,

wherein the method is executed by a processor.

2. The method of claim 1, wherein the video clip is advanced to the derived time after a start of the video clip.

3. The method of claim 1, wherein the query specifies a proper name.

4. The method of claim 1, wherein the annotation is text displayed upon request.

5. The method of claim 1, wherein the positional representation includes third entries, each third entry including a unique term of always visible text and occurrence positions of the unique term within a multimedia document.

6. The method of claim 5, wherein the inverted index includes fourth entries, each fourth entry having a corresponding one of the unique terms and list of document identifiers of multimedia documents having the unique term.

7. A method of generating an inverted index for a collection of multimedia documents, the method comprising:

generating a positional representation of each multimedia document, at least one entry of the positional representation including a unique annotation and at least one occurrence position within its corresponding multimedia document, wherein times within a video clip of the corresponding multimedia document are derivable from the occurrence position;

determining for each unique annotation among the generated positional representations, the positional representations that contain the annotation; and

creating an entry in the inverted index for each unique annotation among the generated positional representations including the annotation and document identifiers of the multimedia documents of the positional representations that contain the annotation,

wherein the method is executed by a processor.

8. The method of claim 7, wherein at least one of the times is after the start of the video clip.

9. The method of claim 7, wherein the unique annotation for at least one of the positional representations corresponds to a proper name and at least one of the times corresponds to a time within the video clip in which a subject corresponding to the proper name appears.

10. The method of claim 7, wherein the annotation is text displayed upon request.

11. The method of claim 10, further comprising adding fourth entries to the inverted index, each fourth entry including a corresponding one of the unique terms and list of document identifiers of multimedia documents having the unique term.

12. The method of claim 7, further comprising adding third entries to each of the positional representations, each third entry including a unique term of always visible text and occurrence positions of the unique term in its corresponding multimedia document.