A related-word registration device comprising: a related-word candidate group generating means configured to generate a related-word candidate group by extracting candidates of a related word if a number of search results from a search query log in which logs regarding a search query are stored is one or more, wherein the search query log stores search queries in association with the number of search results; a receiving means configured to receive a search query of a search word entered by the user; a partial character string generating means configured to generate a partial character string from a character string of the search word; a candidate character string extracting means configured to extract candidate character strings from the related-word candidate group on the basis of the generated partial character string; a score calculating means configured to calculate a suitability score of each candidate character string on the reach basis of similarity between the candidate character string and the search word, the number of use times of the candidate character string, and the number of search results of the search of the candidate character string; a ranking means configured to rank the candidate character strings in order of the scores; a criterion generating means configured to generate a reference line of a suitability score for the ranking as a criterion of determining whether a given candidate character string is to be registered as a related word or not on the basis of its suitability score and ranking; a registration character string extracting means configured to extract, as a registration character string to be registered as a related word, a candidate character string whose suitability score is above the reference line by a preset threshold or larger; and a related-word registering means configured to register the extracted registration character string and the search word as related words into a related-word database, wherein the partial character string generating means is configured to set at least one of length of the partial character string and shift width of the number of characters of a search word at the time of generating the partial character string on the basis of the number of characters of the search word, and generate a partial character string having at least one of the set length and the set shift width, and wherein the criterion generating means is configured to obtain the reference line by an approximate function which approximates relation between the ranking and the suitability score, the reference line being obtained from data of the ranking in a predetermined range. a related-word candidate group generating means configured to generate a related-word candidate group by extracting candidates of a related word if a number of search results from a search query log in which logs regarding a search query are stored is one or more, wherein the search query log stores search queries in association with the number of search results; a receiving means configured to receive a search query of a search word entered by the user; a partial character string generating means configured to generate a partial character string from a character string of the search word; a candidate character string extracting means configured to extract candidate character strings from the related-word candidate group on the basis of the generated partial character string; a score calculating means configured to calculate a suitability score of each candidate character string on the reach basis of similarity between the candidate character string and the search word, the number of use times of the candidate character string, and the number of search results of the search of the candidate character string; a ranking means configured to rank the candidate character strings in order of the scores; a criterion generating means configured to generate a reference line of a suitability score for the ranking as a criterion of determining whether a given candidate character string is to be registered as a related word or not on the basis of its suitability score and ranking; a registration character string extracting means configured to extract, as a registration character string to be registered as a related word, a candidate character string whose suitability score is above the reference line by a preset threshold or larger; and a related-word registering means configured to register the extracted registration character string and the search word as related words into a related-word database, wherein the partial character string generating means is configured to set at least one of length of the partial character string and shift width of the number of characters of a search word at the time of generating the partial character string on the basis of the number of characters of the search word, and generate a partial character string having at least one of the set length and the set shift width, and wherein the criterion generating means is configured to obtain the reference line by an approximate function which approximates relation between the ranking and the suitability score, the reference line being obtained from data of the ranking in a predetermined range.