Expansion of database search queries

• US 20070203929A1
• Filed: 02/28/2006
• Published: 08/30/2007
• Est. Priority Date: 02/28/2006
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: eBay Inc.
• Inventors: Bolivar, Alvaro
• Granted Patent: US 8,195,683 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

In some embodiments, a method includes receiving a token that is usable in search queries for data in a database. The database includes items of data that are represented by data strings. The method also includes determining a synonym candidate for the token. The method includes adding the synonym candidate as a synonym for the token into an expansion dictionary in response to a determination that the number of data strings having the synonym candidate exceeds a threshold.

Claims

1. A method comprising:

receiving a token that is usable in search queries for data in a database, the database including items of data that are represented by data strings;

determining a synonym candidate for the token; and

adding the synonym candidate as a synonym for the token into an expansion dictionary in response to a determination that the number of data strings having the synonym candidate exceeds a threshold.

2. The method of claim 1, further comprising:

receiving a search query having the token for data in the database from a requester;

expanding the search query to include the synonym to form an expanded search query;

performing the search, using the expanded search query, for data in the database; and

returning a result of the search to the requester.

3. The method of claim 2, further comprising:

returning the expanded search query to the requester; and

receiving an approval of the expanded search query from the requester, prior to performing the search using the expanded search query.

4. The method of claim 1, wherein adding the synonym candidate as the synonym for the token into the expansion dictionary is in response to a determination that a number of search queries into the database having the synonym candidate exceeds a threshold.

5. The method of claim 1, wherein determining the synonym candidate for the token comprises determining a different form of the token based on a role in a sentence for the different form in comparison to the role of the token in the sentence.

6. The method of claim 1, wherein determining the synonym candidate for the token comprises determining a plural form of a singular form of the token.

7. The method of claim 1, wherein the threshold is 15.

36. A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations of claim 1.

8. A method comprising:

receiving a token that is usable in search queries for data in a database, the database including items of data stored in a tree hierarchy of categories;

determining a synonym candidate for the token; and

adding the synonym candidate as a synonym for the token into an expansion dictionary in response to a determination that the token and the synonym candidate are in a same category for a level of the tree hierarchy.

9. The method of claim 8, wherein the database includes items of data that are represented by data strings and wherein adding the synonym candidate as the synonym for the token into the expansion dictionary comprises adding the synonym candidate as a synonym for the token into the expansion dictionary in response to a determination that the number of data strings having the synonym candidate exceeds a threshold.

10. The method of claim 8, further comprising:

receiving a search query having the token for data in the database from a requester;

expanding the search query to include the synonym to form an expanded search query;

performing the search, using the expanded search query, for data in the database; and

returning a result of the search to the requester.

11. The method of claim 10, further comprising:

returning the expanded search query to the requester; and

receiving an approval of the expanded search query from the requester, prior to performing the search using the expanded search query.

12. The method of claim 10, wherein the database is a database of items for sale in an online auction, wherein the requester includes a buyer or seller of the items for sale.

13. The method of claim 8, wherein the level is one level below a root of the tree hierarchy.

37. A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations of claim 8.

14. A method comprising:

receiving a token that is usable in search queries for data in a database, the database including items of data stored in a tree hierarchy of categories;

determining a synonym candidate for the token;

determining a probability distribution across leaf categories in the tree hierarchy for the token;

determining a probability distribution across leaf categories in the tree hierarchy for the synonym candidate; and

adding the synonym candidate as a synonym for the token into an expansion dictionary in response to a determination that a similarity between the probability distribution for the token and the probability for the synonym candidate is above a predetermined level.

15. The method of claim 14, wherein the database includes items of data that are represented by data strings and wherein adding the synonym candidate as the synonym for the token into the expansion dictionary comprises adding the synonym candidate as a synonym for the token into the expansion dictionary in response to a determination that the number of data strings having the synonym candidate exceeds a threshold.

16. The method of claim 15, wherein adding the synonym candidate as the synonym for the token into the expansion dictionary comprises adding the synonym candidate as a synonym for the token into the expansion dictionary in response to a determination that the token and the synonym candidate are in a same category for a level of the tree hierarchy.

17. The method of claim 14, further comprising:

receiving a search query having the token for data in the database from a requester;

expanding the search query to include the synonym to form an expanded search query;

performing the search, using the expanded search query, for data in the database; and

returning a result of the search to the requester.

18. The method of claim 17, further comprising:

returning the expanded search query to the requester; and

receiving an approval of the expanded search query from the requester, prior to performing the search using the expanded search query.

19. The method of claim 14, wherein the database is a database of items for sale in an online auction, wherein the requester includes a buyer or seller of the items for sale.

38. A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations of claim 14.

20. A method comprising:

receiving a token that is usable in search queries for data in a database, the database including items of data stored in a tree hierarchy of categories;

determining a synonym candidate for the token;

determining a probability distribution across leaf categories in the tree hierarchy for the token;

determining a probability distribution across leaf categories in the tree hierarchy for the synonym candidate;

determining a cross entropy for the probability distribution for the token and the probability for the synonym candidate; and

adding the synonym candidate as a synonym for the token into an expansion dictionary in response to a determination that a cross entropy is above a predetermined level.

21. The method of claim 20, wherein the database includes items of data that are represented by data strings and wherein adding the synonym candidate as the synonym for the token into the expansion dictionary comprises adding the synonym candidate as a synonym for the token into the expansion dictionary in response to a determination that the number of data strings having the synonym candidate exceeds a threshold.

22. The method of claim 21, wherein adding the synonym candidate as the synonym for the token into the expansion dictionary comprises adding the synonym candidate as a synonym for the token into the expansion dictionary in response to a determination that the token and the synonym candidate are in a same category for a level of the tree hierarchy.

23. The method of claim 20, further comprising:

receiving a search query having the token for data in the database from a requester;

expanding the search query to include the synonym to form an expanded search query;

performing the search, using the expanded search query, for data in the database; and

returning a result of the search to the requester.

24. The method of claim 23, further comprising:

returning the expanded search query to the requester; and

receiving an approval of the expanded search query from the requester, prior to performing the search using the expanded search query.

39. A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations of claim 20.

25. A method comprising:

receiving a token that is usable in search queries for data in a database, the database including items of data stored in a tree hierarchy of categories;

determining a synonym candidate for the token;

determining a probability distribution across leaf categories in the tree hierarchy for the token;

determining a probability distribution across leaf categories in the tree hierarchy for the synonym candidate;

determining a KL-divergence measure of the probability distribution for the token and the probability for the synonym candidate; and

determining a cross entropy for the probability distribution for the token and the probability for the synonym candidate; and

adding the synonym candidate as a synonym for the token into an expansion dictionary in response to a determination that the KL-divergence is below a threshold.

26. The method of claim 25, wherein the threshold is five.

27. The method of claim 25, wherein the database includes items of data that are represented by data strings and wherein adding the synonym candidate as the synonym for the token into the expansion dictionary comprises adding the synonym candidate as a synonym for the token into the expansion dictionary in response to a determination that the number of data strings having the synonym candidate exceeds a threshold.

28. The method of claim 27, wherein adding the synonym candidate as the synonym for the token into the expansion dictionary comprises adding the synonym candidate as a synonym for the token into the expansion dictionary in response to a determination that the token and the synonym candidate are in a same category for a level of the tree hierarchy.

29. The method of claim 25, further comprising:

receiving a search query having the token for data in the database from a requester;

expanding the search query to include the synonym to form an expanded search query;

performing the search, using the expanded search query, for data in the database; and

returning a result of the search to the requester.

30. The method of claim 29, further comprising:

returning the expanded search query to the requester; and

receiving an approval of the expanded search query from the requester, prior to performing the search using the expanded search query.

40. A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations of claim 25.

31. A system comprising:

a data store to store auction items for an online auction database, wherein the auction items are represented by data strings; and

an expansion module to determine a synonym candidate for a token that is usable in search queries for the auction items in the online auction database, wherein the expansion module is to add the synonym candidate as a synonym for the token into an expansion dictionary in response to a determination that the number of data strings having the synonym candidate exceeds a threshold.

32. The system of claim 31, further comprising:

a query controller module to receive a search query having the token for auction items in the online auction database from a requester, wherein the query controller module is to expand the search query to include the synonym to form an expanded search query; and

a search engine to performing the search, using the expanded search query, for online auction items in the online auction database, wherein the query controller module is to return the result of the search to the requester.

33. The system of claim 31, wherein the expansion module is to add the synonym candidate as the synonym for the token into the expansion dictionary is in response to a determination that a number of search queries into the online auction database having the synonym candidate exceeds a threshold.

34. The system of claim 33, wherein the online auction database includes auction items stored in a tree hierarchy of categories wherein the expansion module is to add the synonym candidate as a synonym for the token into an expansion dictionary in response to a determination that the token and the synonym candidate are in a same category for a level of the tree hierarchy.

35. The system of claim 34, wherein the expansion module is to determine a probability distribution across leaf categories in the tree hierarchy for the token, the expansion module to determine a probability distribution across leaf categories in the tree hierarchy for the synonym candidate, and wherein the expansion module is to add the synonym candidate as a synonym for the token into an expansion dictionary in response to a determination that a similarity between the probability distribution for the token and the probability for the synonym candidate is above a predetermined level.