Methods and apparatus for generating a data dictionary

1. An ecommerce system having a database comprising multiple data items, wherein the data items represent products sold in the ecommerce system, the system comprising:

a processor;

a processor-implemented candidate list generator module to:

generate a list of keywords from search query information;

generate a set of token pairs including a keyword from the list of keywords and a token,

the token being a synonym of the keyword;

receive demand information and supply information, wherein the demand information is information retrieved from query logs maintained for user-provided query entries stored in the database and the supply information is seller-provided descriptor information for the data items stored in the database; and

apply candidate selection rules to token pairs across a plurality of categories of data items in the database using the demand information and the supply information, generating a set of candidate token pairs;

a processor-implemented validation module to:

calculate a divergence value for each candidate token pair across the plurality of categories, wherein calculation of the divergence value comprises:

performing a search using a keyword of a candidate token pair as a search criteria;

determining a first distribution (P) of search results for the keyword, the first distribution over the plurality of categories;

performing a search using a token of the candidate token pair as a search criteria;

determining a second distribution (Q) of search results for the token, the second distribution over the plurality of categories;

calculating the divergence measure as an Information Radius (IRad) value as:

IRad=0.5[ D ( P ∥avg( P,Q ))+ D ( Q ∥avg( P,Q ))],

wherein D is Kullback-Liebler divergence calculated as:

D ( P∥Q )=Σ P ( i )log( P ( i )/ Q ( i )),

wherein avg (P,Q) is an average of the first distribution and the second distribution, and

wherein an index i=1, 2, . . . N, and N is the number of categories in the plurality of categories; and

validate the candidate token pairs based on the divergence value, wherein the candidate token pairs having divergence values exceeding a divergence threshold are valid token pairs; and

a processor-implemented data dictionary module to:

receive the validated token pairs as entries in a vocabulary, and provide the validated token pairs in response to a search query containing a keyword corresponding to at least one entry in the vocabulary.

2. The system of claim 1 , wherein the candidate list generator module comprises candidate selection rules, including vocabulary generation rules for processing search query terms to identify keywords, and token generation rules for generating synonyms of the keywords.

3. The system of claim 1 , wherein the candidate list generator module is further to generate a set of token pairs resulting in a plurality of token pairs having a same keyword.

4. The system of claim 1 , wherein the candidate list generator module is further to apply at least one token generation rule to the validated token pairs to identify invalid token pairs.

5. The system of claim 4 , wherein an invalid token pair is one resulting in a large number of data items in unrelated categories as a result from search.

6. The system of claim 1 , wherein the candidate list generator module is further to compare the search query information to the seller-provided descriptor information for data items stored in the database.

7. The system of claim 1 , wherein the vocabulary is a stemming and transliteration vocabulary.

8. A method, comprising:

receiving search query inputs to search a database of data items, the database having a plurality of categories and an associated data dictionary of terms to add to the search query inputs for searching the database;

using at least one processor, identifying demand information that is retrieved from query logs maintained for the search query inputs stored in the database, and supply information comprising seller-provided descriptor information for the data items stored in the database;

generating a set of token pairs based on the search query inputs, each token pair comprising a keyword from at least one search query input and a token, the token being a synonym of the keyword;

applying candidate selection rules to token pairs across the plurality of categories of data items in the database using the demand information and the supply information, generating a set of candidate token pairs;

validating the set of candidate token pairs by calculating a divergence measure for each of the candidate token pairs, wherein the candidate token pairs having divergence values exceeding a divergence threshold are valid token pairs wherein calculation of the divergence value comprises:

performing a search using a keyword of a candidate token pair as a search criteria;

determining a first distribution (P) of search results for the keyword, the first distribution over the plurality of categories;

performing a search using a token of the candidate token pair as a search criteria;

determining a second distribution (Q) of search results for the token, the second distribution over the plurality of categories;

calculating the divergence measure as an Information Radius (IRad) value as:

IRad=0.5[ D ( P ∥avg( P,Q ))+ D ( Q ∥avg( P,Q ))],

wherein D is Kullback-Liebler divergence calculated as:

D ( P∥Q )=Σ P ( i )log( P ( i )/ Q ( i )),

wherein avg (P,Q) is an average of the first distribution and the second distribution, and

wherein an index i=1, 2, . . . N, and N is the number of categories in the plurality of categories; and

entering the validated token pairs into the data dictionary to form an updated data dictionary; and

providing the validated token pairs in the updated data dictionary in response to a search query containing a keyword corresponding to at least one entry in the updated data dictionary.

9. The method of claim 8 , wherein the candidate selection rules are applied across multiple categories in the database using the demand information.

10. The method of claim 8 , further comprising:

receiving supply information wherein the supply information is seller-provided descriptor information for the data items stored in the database; and

comparing the search query inputs to the seller-provided descriptor information for data items stored in the database.

11. The method of claim 8 , wherein generating a set of token pairs includes generating a set of token pairs resulting in a plurality of token pairs having a same keyword.

12. A non-transitory machine-readable medium including instructions which, when read by the machine, cause the machine to perform the operations of:

receiving search query inputs to search a database of data items, the database having a plurality of categories and an associated data dictionary of terms to add to the search query inputs for searching the database;

identifying demand information that is retrieved from query logs maintained for the search query inputs stored in the database, and supply information comprising seller-provided descriptor information for the data items stored in the database;

generating a set of token pairs based on the search query inputs, each token pair comprising a keyword from at least one search query input and a token, the token being a synonym of the keyword;

applying candidate selection rules to token pairs across the plurality of categories of data items in the database using the demand information and the supply information, generating a set of candidate token pairs;

validating the set of candidate token pairs by calculating a divergence measure for each of the candidate token pairs, wherein the candidate token pairs having divergence values exceeding a divergence threshold are valid token pairs wherein calculation of the divergence value comprises:

performing a search using a keyword of a candidate token pair as a search criteria;

determining a first distribution (P) of search results for the keyword, the first distribution over the plurality of categories;

performing a search using a token of the candidate token pair as a search criteria;

determining a second distribution (Q) of search results for the token, the second distribution over the plurality of categories;

calculating the divergence measure as an Information Radius (IRad) value as:

IRad=0.5[ D ( P ∥avg( P,Q ))+ D ( Q ∥avg( P,Q ))],

wherein D is Kullback-Liebler divergence calculated as:

D ( P∥Q )=Σ P ( i )log( P ( i )/ Q ( i )),

wherein avg (P,Q) is an average of the first distribution and the second distribution, and

wherein an index i=1, 2, . . . N, and N is the number of categories in the plurality of categories; and

entering the validated token pairs into the data dictionary to form an updated data dictionary; and

providing the validated token pairs in the updated data dictionary in response to a search query containing a keyword corresponding to at least one entry in the updated data dictionary.