Microsoft Technology Licensing, LLC

Dong Xin

Kaushik Chakrabarti

Venkatesh Ganti

Surajit J Chaudhuri

Tao Cheng

Yeye He

Bahman Bahmani

Surajt Chaudhuri

Embodiments for identifying an entity synonym of an entity are described. A query log is stored in a database located on at least one computing device. A candidate generation module can select a candidate query in the query log that shares a click on a URL with the entity. A correlated tag module can generate a set of phrase-tag pairs for the entity and the candidate query and measure a mutual information value for each phrase-tag pair. A candidate filtering module can determine a click similarity value between the candidate query and the entity based on a set of URLs selected in the search engine results and a tag similarity value based on the mutual information values. A candidate query is selected as an entity synonym if the click similarity value and the tag similarity value are greater than predetermined thresholds respectively.

Identifying entity synonyms

A personalized page rank computation system is described herein that provides a fast MapReduce method for Monte Carlo approximation of personalized PageRank vectors of all the nodes in a graph. The method presented is both faster and less computationally intensive than existing methods, allowing a broader scope of problems to be solved by existing computing hardware. The system adopts the Monte Carlo approach and provides a method to compute single random walks of a given length for all nodes in a graph that it is superior in terms of the number of map-reduce iterations among a broad class of methods. The resulting solution reduces the I/O cost and outperforms the state-of-the-art FPPR approximation methods, in terms of efficiency and approximation error. Thus, the system can very efficiently perform single random walks of a given length starting at each node in the graph and can very efficiently approximate all the personalized PageRank vectors.

Fast personalized page rank on map reduce

A similarity analysis framework is described herein which leverages two or more similarity analysis functions to generate synonyms for an entity reference string r. The functions are selected such that the synonyms that are generated by the framework satisfy a core set of synonym-related properties. The functions operate by leveraging query log data. One similarity analysis function takes into consideration the strength of similarity between a particular candidate string sand an entity reference string reven in the presence of sparse query log data, while another function takes into account the classes of sand r. The framework also provides indexing mechanisms that expedite its computations. The framework also provides a reduction module for converting long entity reference strings into shorter strings, where each shorter string (if found) contains a subset of the terms in its longer counterpart.

Robust discovery of entity synonyms using query logs

A set expansion system is described herein that uses general-purpose web data to expand a set of seed entities. The system includes a simple yet effective quality metric to measure the expanded set, and includes two iterative thresholding processes to rank candidate entities. The system models web data sources and integrates relevance and coherence measurements to evaluate potential set candidates using an iterative process. The system uses general-purpose web data that is not specific to the given seeds. The system defines quality of the result set as the sum of two component scores: the relevance of a set of entities that measures their similarity with the given seeds, and the coherence of the set of entities produced which is how closely the entities in the set are related to each other. Based on this quality measure, the system develops a class of iterative set expansion processes.

Iterative set expansion using samples

Identifying synonyms of entities using a collection of documents is disclosed herein. In some aspects, a document from a collection of documents may be analyzed to identify hit sequences that include one or more tokens (e.g., words, number, etc.). The hit sequences may then be used to generate discriminating token sets (DTS's) that are subsets of both the hit sequences and the entity names. The DTS's are matched with corresponding entity names, and then used to create DTS phrases by selecting adjacent text in the document that is proximate to the DTS. The DTS phrases may be analyzed to determine whether the corresponding DTS is synonyms of the entity name. In various aspects, the tokens of an associated entity name that are present in the DTS phrases are used to generate a score for the DTS. When the score at least reaches a threshold, the DTS may be designated as a synonym. A list of synonyms may be generated for each entity name.

Identifying synonyms of entities using a document collection

The described implementations relate to data analysis, such as membership checking. One technique identifies candidate matches between document sub-strings and database members utilizing signatures. The technique further verifies that the candidate matches are true matches.

Membership checking of digital text

The subject disclosure pertains to a class of object finder queries that return the best target objects that match a set of given keywords. Mechanisms are provided that facilitate identification of target objects related to search objects that match a set of query keywords. Scoring mechanisms/functions are also disclosed that compute relevance scores of target objects. Further, efficient early termination techniques are provided to compute the top K target objects based on a scoring function.

Growing community of inventors

Redmond, WA, United States of America

Dong Xin