Patent Document ID: 9110973
Application ID: 13273569
Patent Status: 1

Claim One:
1. A method of processing a query, the method comprising: generating, from a query string, an effective string set comprising a plurality of partial strings which have a variety of lengths; generating a plurality of subsets of the effective string set, each respective subset comprising one or more of the partial strings; determining a reference number of partial strings; determining, based on access costs of the plurality of subsets for a database in which information about a plurality of documents is stored, a candidate set comprising a subset from the plurality of subsets that has an access cost that is less than a reference value; and searching for a document comprising the query string from the information stored in the database using the candidate set, wherein when a number of the partial strings in the effective string set is less than the reference number of partial strings, determining the candidate set comprises arranging the plurality of subsets in a tree structure, selecting a subset from among the plurality of subsets using a depth first search in the tree structure, calculating, for each of the partial strings in the selected subset, a portion of the access cost that comprises a cost used to access and read a posting list of the partial strings, when the portion of the access cost is less than the reference value, calculating the access cost of the selected subset, when the access cost of the selected subset is less than or equal to the reference value, predicting the selected subset as a predicted candidate set, and when there are no additional subsets among the plurality of subsets to be selected using the depth first search, determining the candidate set to comprise the predicted candidate set, and wherein when the number of the partial strings in the effective string set is greater than the reference number of partial strings, determining the candidate set comprises selecting first subsets that have a same number of partial strings from among the plurality of subsets, calculating the access costs for each of the first subsets, predicting a subset among the first subsets that has a minimum access cost as the predicted candidate set, selecting second subsets, in which a partial string is added to the predicted candidate set, from among the plurality of subsets, and when the access costs for each of the second subsets are greater than the access cost of the predicted candidate set, determining the candidate set to comprise the predicted candidate set.