US 10,242,090 B1Granted

Method and device for measuring relevancy of a document to a keyword(s)

AssigneeThe United States of America as represented by the Director, National Security Agency

InventorsJon T. Kosloski, John W. Thompson

Life of this patent

Estimating the term…

Abstract

A method is presented for ranking documents identified in a search relative to a keyword. The method utilizes a set of training documents to provide a co-occurrence matrix and a transition matrix. A word pair relevancy measure is calculated for each word of the document to be ranked. These word pair relevancy measures are based upon the co-occurrence and transition matrices obtained from the training set and are utilized to calculate a document relevance measure. Documents identified in a search are ranked utilizing the document relevance measure.

Claims17

Dependent claims

A device for determining a measure of relevancy between a keyword and a live document comprising:

a word identifier for identifying each unique word in a set of training documents as a search word;
a word pair identifier, in communication with said word identifier, for combining the identified search words to define search word pairs;
a unit portioner for portioning the set of training documents into units;
a co-occurrence matrix generator for generating a matrix based upon the number of units in which search word pairs co-occur;
a probability matrix generator in communication with said co-occurrence matrix generator and for generating a probability matrix as a function of the co-occurrence matrix said probability matrix providing a co-occurrence probability associated with each search word pair,
a matrix normalizer in communication with said probability matrix generator for normalizing the probability matrix to form a transition matrix providing a transition probability associated with each search word pair;
a word pair identifier wherein said word pair identifier identifies each word in the live document as a seed word and pairs each seed word with the keyword to define a plurality of live document word pairs;
an expected search distance generator in communication with said probability matrix generator and said matrix normalizer, for calculating an expected search distance for each of said plurality of live document word pairs wherein said expected search distance is defined as the expected number of units traversed to transition from the seed word of the live document to a unit that contains the keyword and is based upon said co-occurrence probability and said transition probability;
a weighted average expected search distance generator in communication with said expected search distance generator, said probability matrix generator, and said matrix normalizer, said weighted average expected search distance generator for determining a weighted average expected search distance, for each of said plurality of live document word pairs;
a calibrator in communication with said expected search distance generator and said weighted average expected search distance generator, wherein said calibrator determines the word pair relevancy measure for each of said plurality of live document word pairs, based upon said expected search distance and said weighted averaged expected search distance and
a document relevancy calculator for calculating a document relevancy, based upon said relevancy measures for said plurality of live document word pairs.

8 more elements

A method for determining a measure of relevancy between a keyword and a live document comprising:

identifying a set of training documents;
identifying search words from said set of training documents;
pairing a first search word and a second search word to define a plurality of search word pairs;
portioning the set of training documents into units;
creating a co-occurrence matrix identifying the number of co-occurrences of the search word pairs in said units;
calculating a co-occurrence probability associated with said search word pair, wherein said co-occurrence probability is based upon said co-occurrence matrix;
calculating a transition probability associated with said search word pair, wherein said transition probability is based upon said co-occurrence matrix;
identifying a live document;
identifying each of the words in the live document as a seed word;
pairing each seed word with the keyword to form a plurality of live document word pairs;
for each live document word pair, calculating an expected search distance based on said co-occurrence probability and said transition probability, wherein said expected search distance is defined as the expected number of units traversed to transition from the seed word of the live document to a unit that contains the keyword;
calculating a word pair relevancy for each live document word pair, based upon said expected search distance, to provide a plurality of live document word pair relevancy measures;
and
calculating a document relevancy measure based on said live document word pair relevancies.

11 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

A device for determining a measure of relevancy between a keyword and a live document comprising:

a word identifier for identifying each unique word in a set of training documents as a search word;
a word pair identifier, in communication with said word identifier, for combining the identified search words to define search word pairs;
a unit portioner for portioning the set of training documents into units;
a co-occurrence matrix generator for generating a matrix based upon the number of units in which search word pairs co-occur;
a probability matrix generator in communication with said co-occurrence matrix generator and for generating a probability matrix as a function of the co-occurrence matrix said probability matrix providing a co-occurrence probability associated with each search word pair,
a matrix normalizer in communication with said probability matrix generator for normalizing the probability matrix to form a transition matrix providing a transition probability associated with each search word pair;
a word pair identifier wherein said word pair identifier identifies each word in the live document as a seed word and pairs each seed word with the keyword to define a plurality of live document word pairs;
an expected search distance generator in communication with said probability matrix generator and said matrix normalizer, for calculating an expected search distance for each of said plurality of live document word pairs wherein said expected search distance is defined as the expected number of units traversed to transition from the seed word of the live document to a unit that contains the keyword and is based upon said co-occurrence probability and said transition probability;
a weighted average expected search distance generator in communication with said expected search distance generator, said probability matrix generator, and said matrix normalizer, said weighted average expected search distance generator for determining a weighted average expected search distance, for each of said plurality of live document word pairs;
a calibrator in communication with said expected search distance generator and said weighted average expected search distance generator, wherein said calibrator determines the word pair relevancy measure for each of said plurality of live document word pairs, based upon said expected search distance and said weighted averaged expected search distance and
a document relevancy calculator for calculating a document relevancy, based upon said relevancy measures for said plurality of live document word pairs.

8 more elements