Query to task mapping

• US 20050262058A1
• Filed: 05/24/2004
• Published: 11/24/2005
• Est. Priority Date: 05/24/2004
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chandrasekar, Raman, Bala, Aravind, Hon, Hsiao-Wuen
• Application Number:
  US10/852,734
• Publication Number:
  US 20050262058A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70

Abstract

Candidate mappings are generated between two sets of short strings. A set of files related to the two sets of strings is chosen. Each string from the two sets of strings is searched for in the set of files. Any two strings that match the same file are presumed to be related, and are mapped together. These candidate mappings may then be checked by annotators/reviewers.

Claims

1. A method for determining relationships between a first set of strings and a second set of strings, comprising:

selecting a set of files;

creating an index from the set of files;

searching the index for files that are related to the first set of strings;

creating a first list comprising an entry for each string from the first set of strings and the files from the set of files that are related to that string;

searching the index for files that are related to the second set of strings;

creating a second list comprising an entry for each string from the second set of strings and the files from the set of files that are related to that string;

generating, from the first list, a third list comprising an entry for each file from the set of files and the strings from the first set of strings that are related to that file; and

generating, from the second list and the third list, a fourth list comprising an entry for each string from the second set of strings and the strings from the first set of strings, if any, that related to the same file from the set of files as the string from the second set of strings.

2. The method of claim 1, further comprising:

determining if an entry in the fourth list represents a valid relationship between a string from the second set of strings and a string from the first set of strings; and

removing any entry from the fourth list that does not represent a valid relationship between a string from the second set of strings and a string from the first set of strings.

3. The method of claim 1, further comprising generating a ranking for each entry in the first list and the second list, and generating a ranking for each entry in the fourth list using the generated rankings from the first list and the second list.

4. The method of claim 3, further comprising determining a minimum rank, and removing any entry from the fourth list that has a rank below the minimum rank.

5. The method of claim 4, further comprising:

determining if an entry in the fourth list represents a valid relationship between a string from the second set of string and a string from the first set of strings; and

removing any entry from the fourth list that does not represent a valid relationship between a string from the second set of string and string from the first set of strings.

6. The method of claim 1, wherein selecting a set of files comprises selecting a set of files in the same domain as the first set of strings and the second set of strings.

7. A system for determining relationships between a first set of strings and a second set of strings, comprising:

a selector component that selects a set of files that are stored in a storage device;

a searcher component that searches for strings from the first set of strings and the second set of strings in the set of files;

a first generator component that generates a first list comprising at least one pair, the pair comprising a string from the first set of strings and a file from the file set that is related to said string;

a second generator component that generates a second list comprising at least one pair, the pair comprising a string from the second set of strings and a file from the file set that is related to said string; and

a third generator component that generates a third list, using the first list and the second list, comprising at least one pair, the pair comprising a string from the first set of strings and a string from the second set of strings, wherein the string from the first set of strings and the string from the second set of strings are mutually related to at least one file from the file set.

8. The system of claim 7, further comprising a reviewer component that verifies pairs in the third list, and removes pairs from the third list that cannot be verified.

9. The system of claim 7, wherein the first list further comprises, for each pair in the first list, a confidence indicator.

10. The system of claim 9, wherein the searcher component determines the confidence indicator for the pair based on the probability that the string from the first set of strings is related to the file from the set of files.

11. The system of claim 10, wherein the first generator component removes a pair from the first list if the confidence indicator is less than a predetermined amount.

12. The system of claim 10, wherein the first generator component removes a pair from the list if the confidence indicator is below the average confidence indicator for the first list.

13. The system of claim 7, wherein the second list further comprises, for each pair in the second list, a confidence indicator.

14. The system of claim 13, wherein the searcher component determines the confidence indicator for the pair based on the probability that the string from the second set of strings is related to the file from the set of files.

15. The system of claim 13, wherein the second generator component removes a pair from the second list if the confidence indicator is less than a predetermined amount.

16. The system of claim 13, wherein the second generator component removes a pair from the second list if the confidence indicator is below the average confidence indicator for the second list.

17. The system of claim 7, wherein the selector component selects a set of files that is in the same domain as the first set of strings and the second set of strings.

18. A method for creating a mapping between a first set of strings and a second set of strings, comprising:

maintaining an index of files;

creating a first mapping between the first set of strings and the index of files;

creating a second mapping between the second set of strings and the index of files; and

creating the mapping between the first set of strings and the second set of strings based on the first mapping and the second mapping.

19. The method of claim 18, wherein maintaining the index of files L comprises selecting an index of files that is in the same domain of the first set of strings and the second set of strings.

20. The method of claim 18, wherein creating the first mapping comprises:

searching the index of files for files that are related to at least one of the strings from the first set of strings; and

for each string in the first set of strings that is related to a file from the index of files, making an entry in a first list, the entry comprising the string from the first set of strings, and each file from the index of files that is related to the string from the first set of strings.

21. The method of claim 20, wherein creating the second mapping comprises:

searching the index of files for files that are related to at least one of the strings from the second set of strings; and

for each string in the second set of strings that is related to a file from the index of files, making an entry in a second list, the entry comprising the string from the second set of strings, and each file from the index of files that is related to the string from the second set of strings.

22. The method of claim 21, wherein creating the mapping between the first set of strings and the second set of strings comprises:

generating a third list from the second list, wherein the third list comprises an entry for each file from the index of files that is related to a string from the second set of strings, along with each string from the second set of strings that is related to the file;

generating a fourth list from the third list and the first list, wherein the fourth list comprises an entry for each string from the first set of strings that is related to a file from the index of files, and each string from the second set of strings that is related to the same file as the string from the first set of strings.

23. The method of claim 22, further comprising generating a ranking for each entry in the fourth list.

24. A system for creating a mapping between a first set of strings and a second set of strings, comprising:

a storage device for maintaining an index of files; and

a processor for creating a first mapping between the first set of strings and the index of files;

creating a second mapping between the second set of strings and the index of files; and

creating the mapping between the first set of strings and the second set of strings based on the first mapping and the second mapping.

25. The system of claim 24, further comprising an input device for receiving the first set of strings and the second set of strings.

26. The system of claim 24, wherein the processor creates the first mapping by:

searching the index of files for files that are related to at least one of the strings from the first set of strings; and

for each string in the first set of strings that is related to a file from the index of files, making an entry in a first list, the entry comprising the string from the first set of strings, and each file from the index of files that is related to the string from the first set of strings.

27. The system of claim 26, wherein the processor creates the second mapping by:

searching the index of files for files that are related to at least one of the strings from the second set of strings; and

for each string in the second set of strings that is related to a file from the index of files, making an entry in a second list, the entry comprising the string from the second set of strings, and each file from the index of files that is related to the string from the second set of strings.

28. The system of claim 27, wherein the processor creates the mapping between the first set of strings and the second set of strings by:

generating a third list from the second list, wherein the third list comprises an entry for each file from the index of files that contained a string from the second set of strings, along with each string from the second set of strings that is related to the file; and

generating a fourth list from the third list and the first list, wherein the fourth list comprises an entry for each string from the first set of strings that is related to a file from the index of files, and each string from the second set of strings that is related to the same file as the string from the first set of strings.

29. The system of claim 28, further comprising generating, by the processor, a ranking for each entry in the fourth list.

30. A method for determining relationships between a first set of strings and a second set of strings, comprising:

receiving a generated mapping between a first set of strings and a second set of strings, the mapping comprising a plurality of entries, each entry comprising a string from the first set of strings and a string from the second set of strings;

determining if an entry represents a valid relationship between the string from the first set of strings and the string from the second set of strings; and

removing an entry that does not represent a valid relationship.

31. The method of claim 30, further comprising:

selecting a set of files;

generating an index from the set of files;

generating a first mapping from the first set of strings to the set of files;

generating a second mapping from the second set of strings to the set of files;

generating a third mapping from the first set of strings to the second set of strings, using the first mapping and the second mapping; and

sending the third mapping to a reviewer.