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, comprising:
 a processor receiving a query and accessing at least one data structure to return a response thereto, the data structure including:   at least one sparse matrix having groups of sub-rows, each group corresponding to an entity in a 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.   
   
   
       2 . The computer of  claim 1 , wherein the data structure includes a row index that points to a starting position of a group of sub-rows in the sparse matrix. 
   
   
       3 . The computer of  claim 1 , 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. 
   
   
       4 . The computer of  claim 3 , wherein the cardinality is expressed exactly. 
   
   
       5 . The computer of  claim 3 , wherein the cardinality is expressed using a two-byte approximation. 
   
   
       6 . The computer of  claim 1 , wherein the data structure includes a string table. 
   
   
       7 . The computer of  claim 6 , wherein the string table includes 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 . A data storage medium engageable with a computer for access by a processor to respond to queries, the data storage medium containing a sparse matrix representing the co-occurrence, in a document corpus, of entity pairs. 
   
   
       11 . The data storage medium of  claim 10 , 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 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. 
   
   
       12 . The data storage medium of  claim 11 , wherein the data structure includes a string table including a data string listing entities in descending order of frequency of occurrence in the document corpus. 
   
   
       13 . A method for establishing a data structure identifying the co-occurrence of entities in a plurality of electronic documents comprising:
 for each of at least some of the documents, classifying annotations in the document that correspond to the entities into annotation vectors for the document;   for each of at least some of the documents, inverting the annotation vectors into a table of unique annotations and a list of the unique annotations for the document;   defining an inner set of entities of primary interest comprising inner entities;   setting an outer set of entities of interest comprising outer entities for determining if a relationship exists between one of the outer entities and one of the inner entities;   retrieving the lists of the unique annotations for each of the documents;   determining pairs of inner entities and outer entities which occur within a proximity boundary;   if a pair occurs within the proximity boundary, comparing the unique annotations for the corresponding locations of the inner entity and the outer entity of the pair;   producing a table of all unique pairs which occurred and the number of times the pairs occurred; and   deriving a sparse matrix from the table.   
   
   
       14 . The method of  claim 13 , wherein the classifying comprises relating annotations that refer to people to a people class of entities. 
   
   
       15 . The method of  claim 13 , wherein the classifying comprises relating annotations that refer to organizations to an organization class of entities. 
   
   
       16 . The method of  claim 13 , wherein the classifying comprises relating annotations that refer to products to a product class of entities. 
   
   
       17 . The method of  claim 13 , wherein the inverting comprises recording the location, span, and unique identifiers for each of the unique annotations. 
   
   
       18 . The method of  claim 13 , wherein if a particular annotation has occurred more than once in the document, structuring the locations of the annotations as the list of annotations, sorted by the order in which the individual annotations occurred in the document. 
   
   
       19 . The method of  claim 13 , wherein the defining comprises setting the inner set as the set of all entities. 
   
   
       20 . The method of  claim 13 , wherein the setting comprises making the outer set the set of all entities. 
   
   
       21 . The method  claim 13 , wherein the determining comprises using a boundary of the same sentence. 
   
   
       22 . The method  claim 13 , wherein the determining comprises using a boundary of the same paragraph. 
   
   
       23 . The method  claim 13 , wherein the determining comprises using a boundary of the same document. 
   
   
       24 . The method  claim 13 , wherein the determining comprises using a boundary of a fixed number of tokens. 
   
   
       25 . The method of  claim 13 , wherein the comparing comprises, if the inner entity and the outer entity are unique, appending the pair a list of all pairs which have been discovered. 
   
   
       26 . The method of  claim 13 , wherein the inverting comprises merging the table and the list. 
   
   
       27 . The method of  claim 26 , wherein the merging comprises producing a final index comprising all the unique annotations and lists of annotations. 
   
   
       28 . A method for generating a data structure useful in responding to queries about co-occurrences of entities in a document corpus, comprising:
 accessing the corpus to determine entities and their locations to thereby establish annotation vectors;   inverting the annotation vectors such that for at least one document in the corpus, a table of unique annotations is produced and the locations on the document where the annotation occurred are recorded;   merging the table of unique annotations with lists of annotations to produce a document table;   producing a final index containing all the unique annotations and lists of the documents in which they have occurred;   defining a set of inner entities and a set of outer entities;   accessing document locations for inner and outer entities;   determining all pairs of inner and outer entities which occur within a proximity boundary;   if a unique pair is determined to be within the proximity boundary, adding the pair to a list of all pairs;   using the list of all pairs, establishing a table of unique pairs and the number of times each pair occurred;   sorting the table of unique pairs into a sparse matrix.   
   
   
       29 . The method of  claim 28 , comprising using the sparse matrix to respond to a query. 
   
   
       30 . The method of  claim 28 , comprising establishing a string table using the list of all pairs. 
   
   
       31 . The method of  claim 28 , comprising establishing a hierarchical structure of entity classes. 
   
   
       32 . The method of  claim 28 , comprising accessing the corpus to determine a number of tokens associated with each entity. 
   
   
       33 . The method of  claim 28 , wherein annotation vectors are established at least in part by:
 annotating raw documents having at least document ID and content, an annotated document indicating entities in the document; and   producing annotation vectors from annotated documents, an annotation vector indicating, for each entity, the documents in which the entity appears.   
   
   
       34 . The method of  claim 28 , comprising recording a location, span and unique entity identifier for each entity location.