System and method for indexing type-annotated web documents

• US 20090049035A1
• Filed: 08/14/2007
• Published: 02/19/2009
• Est. Priority Date: 08/14/2007
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: He, Hao, Wang, Haixun, Yu, Philip Shilung
• Application Number:
  US11/891,921
• Publication Number:
  US 20090049035A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Methods and apparatus generate an index for use in a document retrieval system where the index is organized by type and keyword. Redundancy in the index is reduced by organizing type entries in a hierarchy of internal and leaf nodes. Determining whether to generate an inverted list for a type is based on the position of the type in the hierarchy; generally inverted lists are generated only for types corresponding to leaf nodes. Redundancy is further reduced by re-using inverted lists generated for keywords for types when there is an overlap between keywords and types. Search performance using the document retrieval index is improved by adding entries corresponding to combinations of keywords and types. The intersections of inverted lists associated with the keywords and types comprising the combinations are determined and added to the index for use in search operations. Determining whether to add an entry for a keyword-type combination is made on a cost-benefit analysis dependent, at least in part, on the proximity of the keyword to type in documents containing the combination.

Claims

1. A method comprising:

establishing a document retrieval index for use in a document retrieval system

wherein the document retrieval index is organized by type and keyword entries;

organizing type entries by a type hierarchy comprising internal and leaf nodes;

determining whether to generate an inverted list for particular types in the type hierarchy mapping the types to documents including the types in dependence on the position of the types in the type hierarchy; and

generating an inverted list for at least some of the types in the type hierarchy as a result of the determination.

2. The method of claim 1 wherein determining whether to materialize an inverted list for particular types and generating an inverted list for at least some of the types further comprise generating inverted lists only for types corresponding to leaf nodes in the type hierarchy.

3. The method of claim 2 further comprising:

determining overlaps between keywords and types; and

where there is an overlap between a keyword and a type that corresponds to a leaf node, using an inverted list associated with the keyword as the inverted list for the type.

4. The method of claim 1 further comprising:

selecting at least one combination of type and keyword;

for the type and keyword comprising the combination, determining an intersection between an inverted list associated with the type and an inverted list associated with the keyword; and

saving information describing the intersection.

5. The method of claim 1 further comprising:

selecting combinations of types and keywords;

sorting the combinations of types and keywords by a benefit/cost criterion;

determining which combinations of type and keyword exceed a benefit/cost criterion threshold;

for each combination of type and keyword determined to have benefit/cost criterion that exceeds a benefit/cost threshold;

determining an intersection between an inverted list associated with the type and an inverted list associated with the keyword; and

saving information describing the intersection.

6. The method of claim 1 further comprising:

selecting a proximity value, wherein the proximity value corresponds to a predetermined distance between words in a document;

selecting at least one combination of type and keyword;

determining an intersection between an inverted list associated with the type and an inverted list associated with the keyword using the proximity value, where a particular document appearing in inverted lists associated with both the type and keyword is included in the intersection only if the type and keyword appear together in the particular document separated by a distance less than or equal to the proximity value; and

saving information describing the intersection.

7. The method of claim 1 further comprising:

adding an entry in the types entries corresponding to each keyword; and

for each type entry corresponding to a keyword, adding a pointer to the inverted list associated with the keyword.

8. The method of claim 1 further comprising:

selecting a keyword, the keyword having an inverted list;

splitting the inverted list associated with the keyword into a plurality of segments;

associating each segment with a different type entry; and

for each type entry associated with a segment of the inverted list of the keyword, inserting a pointer to the segment.

9. A computer program product tangibly embodying a computer program in a computer readable memory medium, the computer program configured to perform operations involving a document retrieval index when executed by digital processing apparatus, the operations comprising:

establishing the document retrieval index, where the document retrieval index is organized by type and keyword entries;

organizing type entries by a type hierarchy comprised of internal and leaf nodes;

determining whether to generate an inverted list for particular types in the type hierarchy in dependence on the position of the types in the type hierarchy, wherein the inverted list maps the types to documents including the types; and

generating an inverted list for at least some of the types in the type hierarchy as a result of the determination.

10. The computer program product of claim 9 wherein determining whether to materialize an inverted list for particular types and generating an inverted list for at least some of the types further comprise generating inverted lists only for types corresponding to leaf nodes in the type hierarchy.

11. The computer program product of claim 10 wherein the operations further comprise:

determining overlaps between keywords and types; and

where there is an overlap between a keyword and type that corresponds to a leaf node, using an inverted list associated with the keyword as the inverted list for the type.

12. The computer program product of claim 9 wherein the operations further comprise:

selecting at least one combination of type and keyword;

determining an intersection between an inverted list associated with the type and an inverted list associated with the combination; and

saving information describing the intersection.

13. The computer program product of claim 9 wherein the operations further comprise:

selecting combinations of types and keywords;

sorting the combinations of types and keywords by a benefit/cost criterion;

determining which combinations of type and keyword exceed a benefit/cost criterion threshold;

for each combination of type and keyword determined to have a benefit/cost criterion that exceeds a benefit/cost threshold;

determining an intersection between an inverted list associated with the type and an inverted list associated with the keyword; and

saving information describing the intersection.

14. The computer program product of claim 9 wherein the operations further comprise:

selecting a proximity value, wherein the proximity value corresponds to a predetermined distance between words in a document;

selecting at least one combination of type and keyword;

determining an intersection between an inverted list associated with the type and an inverted list associated with the keyword using the proximity value, where a particular document appearing in inverted lists associated with both type and keyword is included in the intersection only if the type and keyword appear together in the particular document separated by a distance less than or equal to the proximity value; and

saving information describing the intersection.

15. The computer program product of claim 9 wherein the operations further comprise:

adding an entry in the type entries corresponding to each keyword; and

for each type entry corresponding to a keyword, adding a pointer to the inverted list associated with the keyword.

16. The computer program product of claim 9 wherein the operations further comprise:

selecting a keyword, the keyword having an inverted list;

splitting the inverted list associated with the keyword into a plurality of segments;

associating each segment with a different type entry; and

for each type entry associated with a segment of the inverted list of the keyword, inserting a pointer to the segment.

17. A system comprising:

at least one computer memory, the at least one computer memory storing a computer program and a document retrieval index, the computer program configured to perform operations involving the document retrieval index when executed; and

processing apparatus coupled to the at least one computer memory, the processing apparatus configured to execute the computer program, wherein when the computer program is executed by the processing apparatus the system is configured to organize the document retrieval index by type and keyword entries;

to organize the type entries by a type hierarchy comprising internal and leaf nodes;

to determine whether to generate an inverted list for particular types depending on the position of the types in the type hierarchy; and

to generate an inverted list for at least some of the types in the type hierarchy as a result of the determination.

18. The system of claim 17 further comprising:

a network interface configured to be coupled a network.

19. The system of claim 18 wherein the at least one computer memory, processing apparatus and network interface together comprise a server, the system further comprising:

a remote database accessible over the network, the remote database configured to store documents, wherein documents stored in the remote database are indexed in the document retrieval index.

20. The system of claim 18 wherein the computer program is further configured to receive type and keyword queries over the network and to use the document retrieval index to respond to the type and keyword queries.