Expansion of database search queries

• US 8,195,683 B2
• Filed: 02/28/2006
• Issued: 06/05/2012
• Est. Priority Date: 02/28/2006
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: eBay Inc.
• Inventors: Bolivar, Alvaro
• Primary Examiner(s): Wu, Yicun
• Application Number:
  US11/363,679
• Publication Number:
  US 20070203929A1
• Time in Patent Office: 2,289 Days
• Field of Search: 707 1- 6, 707/10, 707/740, 707748-749, 707/688, 707/780, 707/736, 707/713, 707765-769, 706/45, 714/47, 704/270, 704/257
• US Class Current: 707/765
• 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:

executing instructions stored on a machine-readable medium readable by a processor which when executed cause the processor to perform operations comprising;

receiving a search query including a token, the search query to be performed on data in a database stored on the machine-readable medium or a different machine-readable medium, the database including items of data that are represented by data strings;

determining a synonym candidate for the token;

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 and a determination that the synonym candidate and the token are in a same category for a level of a tree hierarchy in the database, the tree hierarchy including a plurality of nodes having parent-child relationships;

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

performing a search, using the expanded search query, for data in the database.

2. The method of claim 1, wherein the operations comprise:

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

returning a result of the search to the requester.

3. The method of claim 2, wherein the operations comprise:

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.

8. A machine-readable medium including instructions, which when executed by a machine cause the machine to perform operations comprising:

receiving a search query including a token, the search query to be performed on data in a database stored on the machine-readable medium or a different machine-readable medium, the database including items of data that are represented by data strings;

determining a synonym candidate for the token;

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 and a determination that the synonym candidate and the token are in a same category for a level of a tree hierarchy in the database, the tree hierarchy including a plurality of nodes having parent-child relationships;

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

performing a search, using the expanded search query, for data in the database.

9. The machine-readable medium of claim 8, further comprising:

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

returning a result of the search to the requester.

10. The machine-readable medium of claim 9, 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.

11. The machine-readable medium of claim 8, 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.

12. The machine-readable medium of claim 8, 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.

13. The machine-readable medium of claim 8, wherein determining the synonym candidate for the token comprises determining a plural form of a singular form of the token.

14. The machine-readable medium of claim 8, wherein the threshold is 15.