System and method for creation, representation, and delivery of document corpus entity co-occurrence information

• US 20070276830A1
• Filed: 05/26/2006
• Published: 11/29/2007
• Est. Priority Date: 05/26/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation, ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Gruhl, Daniel Frederick, Meredith, Daniel Norin
• Granted Patent: US 7,593,940 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

To respond to queries that relate to co-occurring entities on the Web, a compact sparse matrix representing entity co-occurrences is generated and then accessed to satisfy queries. The sparse matrix has groups of sub-rows, with each group corresponding to an entity in a document corpus. The groups are sorted from most occurring entity to least occurring entity. Each sub-row within a group corresponds to an entity that co-occurs in the document corpus, within a co-occurrence criterion, with the entity represented by the group, and to facilitate query response the sub-rows within a group are sorted from most occurring co-occurrence to least occurring co-occurrence.

Claims

1. A computer programmed to execute logic comprising:

receiving a query;

in response to the query, accessing at least one sparse matrix containing information representing co-occurrences of entities in a document corpus; and

returning information obtained in the accessing act as a response to the query.

2. The computer of claim 1, wherein the sparse matrix has groups of sub-rows, each group corresponding to an entity in the document corpus, the groups being sorted in the sparse matrix from most occurring entity to least occurring entity, each sub-row of a group corresponding to an entity co-occurring in the document corpus, within at least one co-occurrence criterion, with the entity represented by the group, the sub-rows within a group being sorted from most occurring co-occurrence to least occurring co-occurrence.

3. The computer of claim 1, wherein the logic further includes, in response to the query, accessing a row index that points to a starting position of a group of sub-rows in the sparse matrix.

4. The computer of claim 1, wherein the logic further includes, in response to the query, accessing a header including at least two bytes, the first of which indicates a file version and the second byte of which indicates a number of bytes used for at least one cardinality representing a corresponding number of entity co-occurrences.

5. The computer of claim 4, wherein the cardinality is expressed exactly.

6. The computer of claim 4, wherein the cardinality is expressed using a two-byte approximation.

7. The computer of claim 1, wherein the logic further comprises accessing a string table including an index and a corresponding data string.

8. The computer of claim 7, wherein the index is a concatenated list of integers representing offsets of entity-representing strings in the data string.

9. The computer of claim 8, wherein the entity-representing strings in the data string are listed in descending order of frequency of occurrence in the document corpus.

10. The computer of claim 1, wherein the document corpus is the World Wide Web.

13. The service of claim 10, wherein the entity representations are groups of sub-rows in the sparse matrix, the groups are sorted from most occurring entity to least occurring entity, with each sub-row of a group corresponding to an entity co-occurring in the document corpus with the entity represented by the group, the sub-rows within a group being sorted from most occurring co-occurrence to least occurring co-occurrence.

11. A service, comprising:

receiving a query for information contained in the World Wide Web; and

returning a response to the query at least in part by accessing a data structure including a sparse matrix.

12. The service of claim 11, wherein the sparse matrix comprises entity representations representing entities in a document corpus, the entity representations being sorted by frequency of entity occurrence within the corpus and, within an entity representation, information being sorted by frequency of co-occurrence of other entities with the entity corresponding to the entity representation.

14. The service of claim 11, wherein the data structure includes a row index that points to a starting position of a group of sub-rows in the sparse matrix.

15. The service of claim 11, wherein the data structure includes a header including at least two bytes, the first of which indicates a file version and the second byte of which indicates a number of bytes used for at least one cardinality representing a corresponding number of entity co-occurrences.

16. The service of claim 11, wherein the data structure includes a string table.

17. The service of claim 16, wherein the string table includes an index and a corresponding data string.

18. The service of claim 17, wherein the index is a concatenated list of integers representing offsets of entity-representing strings in the data string.

19. The service of claim 18, wherein the entity-representing strings in the data string are listed in descending order of frequency of occurrence in the document corpus.

20. A method for responding to queries for information in a document corpus, comprising:

receiving the query;

using at least a portion of the query as an entering argument to access a sparse matrix; and

returning a response to the query at least in part based on the access of the sparse matrix.

21. The method of claim 20, wherein the document corpus includes the World Wide Web and the sparse matrix includes entity representations that are respective groups of sub-rows in the sparse matrix, wherein the groups are sorted from most occurring entity to least occurring entity, with each sub-row of a group corresponding to an entity co-occurring in the document corpus with the entity represented by the group, the sub-rows within a group being sorted from most occurring co-occurrence to least occurring co-occurrence.