Expansion of database search queries

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.

1 . 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   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.   
     
     
         2 . The method of  claim 1 , wherein identifying the synonym candidate as a synonym for the token further comprises adding the synonym candidate as the synonym for the token into an expansion dictionary. 
     
     
         3 . The method of  claim 1 , wherein the database includes items of data that are represented by data strings and wherein identifying the synonym candidate as the synonym for the token comprises a determination that the number of data strings having the synonym candidate exceeds a threshold. 
     
     
         4 . 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.   
     
     
         5 . The method of  claim 4 , 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.   
     
     
         6 . The method of  claim 4 , 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. 
     
     
         7 . The method of  claim 1 , wherein the level is one level below a root of the tree hierarchy. 
     
     
         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;   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   identifying the synonym candidate as a synonym for the token 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, and 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 identifying the synonym candidate as a synonym for the token further comprises adding the synonym candidate as the synonym for the token into an expansion dictionary. 
     
     
         10 . The method of  claim 8 , wherein the database includes items of data that are represented by data strings and wherein identifying the synonym candidate as the synonym for the token comprises a determination that the number of data strings having the synonym candidate exceeds a threshold. 
     
     
         11 . 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.   
     
     
         12 . The method of  claim 11 , 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.   
     
     
         13 . The method of  claim 7 , 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. 
     
     
         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;   determining a cross entropy for the probability distribution for the token and the probability for the synonym candidate; and   identifying the synonym candidate as a synonym for the token in response to a determination that a cross entropy is above a predetermined level, and in response to a determination that the token and the synonym candidate are in a same category for a level of the tree hierarchy.   
     
     
         15 . The method of  claim 14 , wherein identifying the synonym candidate as a synonym for the token further comprises adding the synonym candidate as the synonym for the token into an expansion dictionary. 
     
     
         16 . The method of  claim 14 , wherein the database includes items of data that are represented by data strings and wherein identifying the synonym candidate as the synonym for the token comprises a determination that the number of data strings having the synonym candidate exceeds a threshold. 
     
     
         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 . 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   identifying the synonym candidate as a synonym for the token in response to a determination that the KL-divergence is below a threshold, and a determination that the token and the synonym candidate are in a same category for a level of the tree hierarchy.   
     
     
         20 . The method of  claim 19 , wherein identifying the synonym candidate as a synonym for the token further comprises adding the synonym candidate as the synonym for the token into an expansion dictionary. 
     
     
         21 . The method of  claim 19 , wherein the threshold is five. 
     
     
         22 . The method of  claim 19 , wherein the database includes items of data that are represented by data strings and wherein identifying the synonym candidate as the synonym for the token comprises a determination that the number of data strings having the synonym candidate exceeds a threshold. 
     
     
         23 . The method of  claim 22 , 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.   
     
     
         25 . 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 are stored in a tree hierarchy of categories; 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 identify the synonym candidate as a synonym for the token in response to a determination that the number of data strings having the synonym candidate exceeds a threshold, and in response to a determination that the token and the synonym candidate are in a same category for a level of the tree hierarchy.   
     
     
         26 . The system of  claim 25 , wherein the expansion module is further to add the synonym candidate as the 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 in response to a determination that the token and the synonym candidate are in a same category for a level of the tree hierarchy. 
     
     
         27 . The system of  claim 25 , 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 perform 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.   
     
     
         28 . The system of  claim 25 , wherein the expansion module is to add the synonym candidate as the synonym for the token into an expansion dictionary in response to a determination that a number of search queries into the online auction database having the synonym candidate exceeds a threshold. 
     
     
         29 . The system of  claim 25 , 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 identify the synonym candidate as a synonym for the token 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. 
     
     
         30 . A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations of  claim 1 . 
     
     
         31 . A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations of  claim 8 . 
     
     
         32 . A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations of  claim 14 . 
     
     
         33 . A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations of  claim 19 .