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

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.

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. 
   
   
       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. 
   
   
       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. 
   
   
       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.