System and method for generation of computer index files

• US 8,250,075 B2
• Filed: 12/22/2006
• Issued: 08/21/2012
• Est. Priority Date: 12/22/2006
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Cheslow, Robert D.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Chang, Jeffrey
• Application Number:
  US11/644,039
• Publication Number:
  US 20080154938A1
• Time in Patent Office: 2,069 Days
• Field of Search: 707/742, 707/7, 707/103.Z
• US Class Current: 707/742
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures

Abstract

Methods and systems for the generation of computer readable indexes or other ordered lists are provided. A corpus of electronic documents or other electronic information is parsed into postings that include key and reference pairs. An inversion buffer in memory is explicitly or implicitly formatted to receive the postings in a predetermined order by key. Each key is assigned a space in the inversion buffer that is subsequently filled with references associated with the key during an inversion method. In an embodiment, an index file is generated directly from the inversion buffer, or in the case of large inversions, from a plurality of inversion buffer segments.

Claims

1. A computer-implemented method for generating an ordered data set, comprising:

providing a data set of tuples, each tuple comprising a key and a corresponding reference;

determining the number of corresponding references in the data set of tuples that include each key;

allocating an inversion buffer in a memory;

allocating a key space in the inversion buffer for each key in the data set of tuples to be included in an ordered data set of tuples and associating that key with the key space;

allocating a variable number of reference spaces in the key spaces, wherein one of the reference spaces in each key space is allocated for each reference that corresponds to the key associated with the key space from the determined number of corresponding references that include each key;

associating the corresponding reference with the reference space allocated for that corresponding reference; and

generating the ordered data set of the tuples based upon the positional relationship of the key spaces and the reference spaces.

2. The method of claim 1, further comprising ordering the key spaces in the inversion buffer according to a desired sort order.

3. The method of claim 2, further comprising associating each key space with a unique key.

4. The method of claim 2, further comprising saving the inversion buffer as an index file.

5. The method of claim 2, further comprising:

combining a plurality of inversion buffer segments into the ordered data set of tuples; and

ordering the plurality of inversion buffer segments according to the desired sort order.

6. The method of claim 5, further comprising sequentially processing the inversion buffer segments in the desired sort order and appending each inversion buffer segment to the ordered data set of tuples in the desired sort order.

7. A computer-readable media comprising program instructions implementing the method of claim 1.

8. A computer system including for generating an inverted index, the system comprising:

a posting component that provides a plurality of postings parsed from a document corpus, each posting comprising a term reference and an associated document reference;

a document reference frequency component that determines the number of postings in the plurality of postings that include the term reference;

an inversion component, comprising;

an inversion buffer allocation component that maps an inversion buffer in a memory to receive the plurality of postings in a pre-defined sort order;

a posting sort component that associates each posting with the mapped location in the inversion buffer for that posting; and

a document reference space allocation component that allocates a variable number of reference spaces, wherein one of the reference spaces in the mapped location is allocated for each of the number of postings associated with the term reference as determined by the document reference frequency component; and

an index generation component that generates the inverted index from the mapping of the inversion buffer.

9. The system of claim 8, wherein the inversion buffer allocation component maps in the inversion buffer a term reference area associated with each term reference from the plurality of postings.

10. The system of claim 9, wherein the inversion buffer allocation component maps, in each term reference area, a document reference area for each document reference associated with the term reference that is associated with the term reference area by way of at least one posting.

11. The system of claim 10, wherein the inversion buffer allocation component maps the term reference area for only term references that are unique in the plurality of postings.

12. The system of claim 11, wherein the index generation component generates the inverted index by sequentially reading the inversion buffer as allocated by the inversion buffer allocation component and appending the read of the inversion buffer to the inverted index.

13. The system of claim 10, wherein:

the inversion buffer allocation component maps a single document reference area in the term reference area for each unique instance of a document reference associated with the term reference; and

the posting sort component associates only a single instance of a document reference with the single document reference area in the term reference area that is associated with the term reference with which the document reference is associated.

14. The system of claim 13, wherein the index generation component generates the inverted index by sequentially reading the inversion buffer as allocated by the inversion buffer allocation component and appending the read of the inversion buffer to the inverted index.

15. A computer-implemented method for inverting an index, the computer comprising a processor and a memory, the method comprising:

providing a plurality of postings to be indexed, each posting comprising a term identification and a document identification;

determining a set of unique term identifications present in the plurality of postings;

for each unique term identification in the set of unique term identifications, determining from the plurality of postings the number of document identifications that are associated with that unique term identification;

allocating an inversion buffer in memory;

allocating, in a predefined order, a term space in memory associated with the inversion buffer for each unique term identification;

allocating a variable number reference spaces in memory, wherein each reference space is associated with the term space for each document identification that is associated with the unique term identification that is associated with the term space based on the determined number of document identifications that are associated with the unique term identification;

for each posting in the set of postings, associating the document identification from that posting with one of the document spaces that is associated with the term space associated with the term identification of that posting; and

generating the index from the spatial relationships of the term spaces associated with the inversion buffer.

16. The method of claim 15, wherein generating the index from the spatial relationships of the term spaces associated with the inversion buffer comprises writing the key spaces to the index file as ordered in the inversion buffer.

17. The method of claim 16, further comprising writing a plurality of inversion buffer segments to the index file in a predefined order.

18. The method of claim 17, wherein at least one inversion buffer segment written to the index file is generated by another computer in a distributed computer environment.

19. A computer-readable media comprising program instructions implementing the method of claim 15.

20. A computer system for generating a computer-readable index, comprising:

a document corpus parsing component, comprising;

a posting component that adds a posting to a set of postings when a document in a corpus of documents contains a term, each posting comprising a term identifier and a document identifier associated with the document containing the term;

a document frequency component that determines the number of postings in the set of postings that include the term identifier;

a term lexicon component that administers a set of term identifiers;

an inversion buffer component, comprising;

an inversion buffer allocating component that allocates an inversion area in memory for inversion of a subset of postings from the set of postings;

a term space allocating component that allocates a term space for each term identifier in a subset of terms identifiers from the term lexicon such that the term spaces are arranged by a pre-defined sort order;

a reference space allocating component that allocates a variable number of reference spaces in the term spaces, wherein the reference spaces in each term space is allocated for the number of postings associated with the term identifier as determined by the document frequency component;

an inversion component, comprising;

a posting processing component that retrieves each posting and assigns the document identifier associated with that posting to one of the reference spaces associated with the term space that is associated with the term identifier associated with that posting;

an index generating component, comprising;

an inversion buffer conversion component that sequentially returns each term space in order and appends a term record to the index, each record associating the term identifier that is associated with the term space with the reference identifiers that have been assigned to the reference spaces associated with that term space.

21. The system of claim 20, further comprising:

a inversion buffer paging component that;

initializes an inversion buffer segment for a subset of lexicon terms;

retrieves a subset of term identifiers determined to fit in the inversion buffer segment;

processes each inversion buffer segment as recited in the preceding claim;

wherein the index generating component orders each inversion buffer segment in the index according to the pre-defined sort order.

22. The system of claim 21, wherein the subset of term identifiers are selected in the pre-defined sort order and the index file is assembled by sequentially appending the inversion buffer segment to the index file.

23. The system of claim 21, wherein at least one inversion buffer segment is processed on a different computer in a distributed network and that inversion buffer segment is combined into the index file.