Expansion of database search queries

• US 9,916,349 B2
• Filed: 02/17/2016
• Issued: 03/13/2018
• Est. Priority Date: 02/28/2006
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Inventors: Bolivar, Alvaro
• Primary Examiner(s): Wu, Yicun
• Application Number:
  US15/045,777
• Publication Number:
  US 20160162545A1
• Time in Patent Office: 755 Days
• 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

Systems and methods are provided for expanding database search queries. In one embodiment, a method comprises 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. The method further comprises determining a synonym candidate for the token, and identifying the synonym candidate as a synonym for the token in response to a determination that the token and the synonym candidate are in a same category for a level of the tree hierarchy.

Claims

1. A method comprising:

identifying a token that is usable in search queries for items of data in a database having a hierarchical tree structure and having categories at a plurality of levels in the hierarchical tree structure;

determining a synonym candidate for the token;

determining whether a number of items of data in the database having the synonym candidate exceeds a threshold, and if so, for a level in the hierarchical tree structure;

identifying a first category of the level of the hierarchal tree structure based on the first category having the most items of data in the database with the token,

identifying a second category of the level of the hierarchal tree based on the second category having the most items of data in the database with the synonym candidate, and

determining that the first category and the second category are the same;

adding the synonym candidate as a synonym for the token into an expansion dictionary in response to the determination that the number of items of data in the database having the synonym candidate exceeds the threshold and the determination that the first category and the second category are the same, the adding of the synonym candidate as a synonym for the token into the expansion dictionary including updating a data structure in the database to be associated the synonym candidate with the token;

receiving a search query that includes the token;

determining that the search query is expandable based on the expansion dictionary including the synonym candidate as a synonym for the token;

expanding the search query to include the synonym candidate 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 level is one level below a root of the hierarchical tree structure.

3. The method of claim 1, further comprising returning a result of the search to a requester.

4. 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.

5. 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.

6. The method of claim 3, wherein the database is a database of items for sale, and wherein the requester includes a buyer or seller of the items for sale.

7. A system comprising:

a memory to store items of data in a database having a hierarchical tree structure and having categories at a plurality of levels in the hierarchical tree structure; and

one or more processors, configured to cause the system to perform operations, the operations comprising;

identify a token;

determine a synonym candidate for the token;

determine whether a number of items of data in the database having the synonym candidate exceeds a threshold, and if so, for a level in the hierarchical tree structure;

identify a first category of the level of the hierarchal tree structure based on the first category having the most items of data in the database with the token,

a second category of the level of the hierarchal tree based on the second category having the most items of data in the database with the synonym candidate, and

determine that the first category and the second category are the same;

add the synonym candidate as a synonym for the token into an expansion dictionary in response to the determination that the number of items of data in the database having the synonym candidate exceeds the threshold and the determination that the first category and the second category are the same;

receive a search query that includes the token;

determine that the search query is expandable based on the expansion dictionary including the synonym candidate as a synonym for the token;

expand the search query to include the synonym candidate to form an expanded search query; and

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

8. The system of claim 7, wherein the level is one level below a root of the hierarchical tree structure.

9. The system of claim 7, wherein the operations further comprise return a result of the search to a requester.

10. The system of claim 7, wherein the operations further comprise add the synonym candidate as the synonym for the token into the expansion dictionary in response to a determination that a number of search queries into the database having the synonym candidate exceeds a threshold.

11. The system of claim 7, wherein the adding of the synonym candidate as a synonym for the token into the expansion dictionary includes updating a data structure in the database to be associated the synonym candidate with the token.

12. A machine-readable medium carrying instructions which, in response to being executed by a system, cause the system to perform operations including:

identifying a token that is usable in search queries for items of data in a database having a hierarchical tree structure and having categories at a plurality of levels in the hierarchical tree structure;

determining a synonym candidate for the token;

determining whether a number of items of data in the database having the synonym candidate exceeds a threshold, and if so, for a level in the hierarchical tree structure;

identifying a first category of the level of the hierarchal tree structure based on the first category having the most items of data in the database with the token,

identifying a second category of the level of the hierarchal tree based on the second category having the most items of data in the database with the synonym candidate, and

determining that the first category and the second category are the same; and

adding the synonym candidate as a synonym for the token into an expansion dictionary in response to the determination that the number of items of data in the database having the synonym candidate exceeds the threshold and the determination that the first category and the second category are the same.

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

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

15. The machine-readable medium of claim 12, wherein the adding of the synonym candidate as a synonym for the token into the expansion dictionary includes updating a data structure in the database to be associated the synonym candidate with the token.

16. The machine-readable medium of claim 12, wherein the operations further comprise:

receiving a search query that includes the token;

determining that the search query is expandable based on the expansion dictionary including the synonym candidate as a synonym for the token;

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

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