1. A method, implemented by one or more computer processors, comprising: providing an entity reference string r e that is associated with an entity; providing a set of candidate strings S e , comprising at least one candidate string s e ; generating, using query log data, similarity score information for respective pairs of individual candidate strings of the set of candidate strings S e and the entity reference string r e using at least two similarity analysis functions; and determining, using the similarity score information, whether the individual candidate strings are valid synonyms of the entity reference string r e , where a valid synonym refers to the entity and satisfies a core set of synonym-related properties jointly provided by said at least two similarity analysis functions.