Name search using a ranking function

Patent metadata

Field	Value
Publication number	US-9727639-B2
Application number	US-201414171155-A
Country	US
Kind code	B2
Filing date	Feb 3, 2014
Priority date	Jun 18, 2008
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

Abstract

An approach is described for performing a name search using a name search operation and a ranking operation. The name search operation may take text as input and apply a fuzzy matching operation and a lookup operation to generate a collection of candidate names with respective probability scores. In other cases, speech or handwriting recognition may generate the collection of candidate names and probability scores. The ranking operation may then rank these candidate names using a ranking function. The ranking function may rank the candidate names based on the probability scores associated with the names and at least one other factor. One such factor may reflect whether information provided by a user matches profile information associated with a candidate name under consideration. Another factor may reflect an extent of a nexus between the user and a person associated with the candidate name. Other types of factors can be used.

First claim

The invention claimed is:

1. A computer-readable medium for storing computer-readable instructions, the computer-readable instructions providing a ranking module when executed by one or more processing devices, the computer-readable instructions comprising:
logic configured to receive a plurality of identified candidate names from a matching operation between an input name from a query and an index of names of people;
logic configured to generate rank values associated with the respective candidate names using a ranking function, each rank value R for a candidate name being generated based on at least a result D+S+N, where D is a dynamic rank score associated with one or more query-dependent factor values, wherein each query-dependent factor value is associated with input information input by a user, N is a nexus rank score associated with one or more nexus factor values, wherein each nexus factor value is associated with an extent of a nexus between the user who inputs the input information and a person associated with the candidate name, and S is a static rank score associated with one or more static factor values, wherein each static factor value is associated with a determination regarding the candidate name that is independent of an identity of the user who inputs the input information;
logic configured to rank the candidate names based on the rank values; and
logic configured to output the candidate names on a display device as an ordered list according to the rank values.

2. The computer readable medium of claim 1 , wherein the dynamic rank score D is calculated using a BM25-type ranking algorithm.

3. The computer readable medium of claim 1 , wherein the computer-readable instructions further comprising:
logic configured to, for each component name, identify at least one version of the component name and perform said determining and executing with respect to said at least one identified version of the component name.

4. The computer readable medium of claim 1 , wherein at least two versions of a component name map to a same candidate name with respective probability scores associated therewith, further comprising producing a consolidated probability score associated with the same candidate name based on the respective probability scores.

5. The computer readable medium of claim 1 , wherein the computer-readable instructions further comprising: logic configured to form an intersection to identify one or more candidate names that match lookup results associated with plural component names in the input name.

6. The computer readable medium of claim 5 , wherein the computer-readable instructions further comprising: logic configured to determine the probability score of each candidate name by taking a product of fuzzy match scores associated with the component names that correspond to the candidate name.

7. A method for performing a search, the method being performed on electronic data processing equipment, the method comprising:
receiving a plurality of identified candidate names from a matching operation between an input name from a query and an index of names of people;
generating rank values associated with the respective candidate names using a ranking function, each rank value R for a candidate name being generated based on at least a result D+S+N, where D is a dynamic rank score associated with one or more query-dependent factor values, wherein each query-dependent factor value is associated with input information input by a user, N is a nexus rank score associated with one or more nexus factor values, wherein each nexus factor value is associated with an extent of a nexus between the user who inputs the input information and a person associated with the candidate name, and S is a static rank score associated with one or more static factor values, wherein each static factor value is associated with a determination regarding the candidate name that is independent of an identity of the user who inputs the input information;
displaying on a display device the candidate names based on the rank values.

8. The method of claim 7 , wherein the dynamic rank score D is calculated using a BM25-type ranking algorithm.

9. The method of claim 7 further comprising:
receiving input information that includes the input name;
parsing the input name into component names;
for each component name: determining at least one fuzzy match associated with the component name if there is at least one fuzzy match and executing a lookup operation in an index for each fuzzy match to provide at least one lookup result;
providing at least one candidate name based on a scoring analysis of lookup results provided for the component names in the input name, each candidate name having a probability score associated therewith which reflects a level of confidence that the candidate name is an appropriate match for the input name; and
generating a rank value associated with said at least one candidate name using a ranking function.

10. The method of claim 9 , further comprising, for each component name: identifying at least one version of the component name; and performing said determining and executing with respect to said at least one identified version of the component name.

11. The method of claim 10 , wherein said at least one version of the component name is a pronunciation version of the component name.

12. The method of claim 10 , wherein at least two versions of a component name map to a same candidate name with respective probability scores associated therewith, further comprising producing a consolidated probability score associated with the same candidate name based on the respective probability scores.

13. The method of claim 10 , wherein said providing of said at least one candidate name comprises forming an intersection to identify one or more candidate names that match lookup results associated with plural component names in the input name, further comprising determining the probability score of each candidate name by taking a product of fuzzy match scores associated with the component names that correspond to the candidate name.

14. A query module for performing a name search, comprising:
a name search module operative to receive a plurality of identified candidate names from a matching operation between an input name from a query and an index of names of people;
a ranking module operative to generate rank values associated with the respective candidate names using a ranking function, each rank value R for a candidate name being generated based on at least a result D+S+N, where D is a dynamic rank score associated with one or more query-dependent factor values, wherein each query-dependent factor value is associated with input information input by a user, N is a nexus rank score associated with one or more nexus factor values, wherein each nexus factor value is associated with an extent of a nexus between the user who inputs the input information and a person associated with the candidate name, and S is a static rank score associated with one or more static factor values, wherein each static factor value is associated with a determination regarding the candidate name that is independent of an identity of the user who inputs the input information, and rank the candidate names based on the rank values; and
an output module operative to display on a display device a subset of the ranked candidate names that satisfy a prescribed threshold of appropriateness.

15. The query module of claim 14 , wherein the static rank score S is determined at least in part from information that does not pertain to the person who is associated with th

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Groeneveld Dirk H
• Meyerzon Dmitriy
• Mowatt David
• Alspaugh Jessica A

Classifications

• G06F17/30657 Primary

  Physics · mapped topic

• G06F17/30864

  Physics · mapped topic

• G06F16/951 Primary

  Indexing; Web crawling techniques · CPC title

• G06F16/3331 Primary

  Query processing · CPC title