US 2008/0306919 A1Published application

Document search method

AssigneeHitachi, Ltd.

InventorsMakoto Iwayama, Kazutomo Ushijima, Osamu Imaichi, Tomohiro Yasuda

Life of this patent

Estimating the term…

Loading patent…

Abstract

A document search apparatus capable of an index-type search and a scan-type search performs a search in a combination of the two search types while compensating for the disadvantages of the two search types with each other. A search query for index-type search and a search query for scan-type search are constructed based on a search query consisting of a logical formula of keywords. Then, a character 2-gram for performing an index search is set to shorten the whole search time, and the index-type search is performed. Finally, a scan-type search is performed on this search result of the index-type search.

Claims14

Dependent claims

A document search method with which a document search apparatus searches for a document from a document DB in response to an input of a search query consisting of keywords that are combined using a logical formula, the document search apparatus including:

a processor;
the document DB storing documents to be searched;
and an index DB storing an index term included in the documents to be searched, the number of documents including the index term, and a document list of documents including the index term,
the method comprising causing the document search apparatus to execute the steps of:
constructing a search query for index-type search, by replacing each keyword included in the inputted search query with conjunctions of index terms constituting the keyword;
calculating a sum of a required time for an index-type search and a required time for a scan-type search, as an estimated value of a total search time, in a way that the required time for the index-type search and the number of documents to be searched out are estimated for each term in the search query for index-type search, by regarding, as hitting all the documents, another term having a larger number of hits than the each term in reference to the document index DB, and that the required time for the scan-type search, in which the estimated number of documents are scanned by using the inputted search query, is estimated;
constructing a search query for index-type search by replacing, with a truth constant, a term which is regarded as hitting all documents when the estimated total search time takes the minimum value;
performing an index-type search using the search query for index-type search including the truth constant;
performing a scan-type search on a document, which is searched out by the index-type search, by using the inputted search query;
and
outputting a document that is searched out by the scan-type search.

8 more elements

a processor;
the document DB storing documents to be searched;
and an index DB storing an index term included in the documents to be searched, the number of documents including the index term, and a document list of documents including the index term,
the method comprising causing the document search apparatus to execute the steps of:
constructing a search query for index-type search, by replacing each keyword included in the inputted search query with conjunctions of index terms constituting the keyword;
sorting terms in the search query for index-type search in ascending order of the number of hits with reference to the index DB;
estimating the number of documents to be searched out by the index-type search using the search query for index-type search, by obtaining any one of:
a smaller number of the numbers of hits of respective terms when the terms are jointed with AND in a partial search query of the search query for index-type search;
a sum of the numbers of hits of respective terms when the terms are jointed with OR;
and the number of all documents when the sum exceeds the number of all documents in the latter case;
estimating a required time for performing a scan-type search in which the estimated number of documents are scanned by using the inputted search query;
calculating a maximum number of elements in a document list in the index DB, the elements being readable within a time obtained by subtracting the required time for the scan-type search from a given target time of searching;
calculating a cumulative sum of the numbers of hits of terms in the sorted terms from the top up to the cumulative sum reaches to the maximum number of elements, and constructing a search query for index-type search by replacing a term with a truth constant, the term having the number of hits that is not added to the cumulative sum since the cumulative sum exceeds the maximum number of elements;
performing an index-type search using the search query for index-type search including the truth constant;
performing a scan-type search in which a document searched out by the index-type search is scanned by using the inputted search query;
and
outputting a document searched out by the scan-type search.

14 more elements

a processor;
the document DB storing documents to be searched;
and an index DB storing a character 2-gram used as an index term included in the documents to be searched, the number of documents including the index term, and a document list of documents including the index term,
the method comprising causing the document search apparatus to execute the steps of:
constructing a search query for index-type search, by replacing each keyword included in the inputted search query with conjunctions of the index terms constituting the keyword;
calculating a sum of a required time for an index-type search and a required time for a scan-type search, as an estimated value of a total search time, in a way that the required time for the index-type search and the number of documents to be searched out are estimated for each term in the search query for index-type search, by regarding as hitting all the documents in reference to the document index DB, other terms each having a larger number of hits than the each term and not originating from a one-character or two-character keyword, and that the required time for the scan-type search, in which the estimated number of documents are scanned by using the inputted search query, is estimated;
constructing a search query for index-type search, by replacing, with a truth constant, a term which is regarded as hitting all documents when the estimated total search time takes the minimum value;
performing the index-type search using the search query for index-type search including the truth constant;
performing a scan-type search using a search query every time a document is searched out by the index-type search, the search query having a one-character or two-character keyword in the inputted search query replaced with truth or false to reflect a search result of a character 2-gram originating from the one-character or two-character keyword;
and
outputting a document that is searched out by the scan-type search.

8 more elements

a processor;
the document DB storing documents to be searched;
and an index DB storing a character 2-gram used as an index term included in the documents to be searched, the number of documents including the index term, and a document list of documents including the index term,
the method comprising causing the document search apparatus to execute the steps of:
constructing a search query for index-type search, by replacing each keyword included in the inputted search query with conjunctions of the index terms constituting the keyword;
sorting terms in the search query for index-type search in ascending order of the number of hits with reference to the index DB;
estimating the number of documents to be searched out by the index-type search using the search query for index-type search, by obtaining any one of:
a smaller number of the numbers of hits of respective terms when the terms are jointed with AND in a partial search query of the search query for index-type search;
a sum of the numbers of hits of respective terms when the terms are jointed with OR;
and the number of all documents when the sum exceeds the number of all documents in the latter case;
estimating a required time for performing a scan-type search in which the estimated number of documents are scanned by using the inputted search query;
calculating the number of elements in a document list in the index DB, the elements being readable within a time obtained by subtracting the required time for the scan-type search from a given target time of searching, and determining a maximum number of elements by subtracting the calculated number of elements by the number of hits of a character 2-gram originating from a one-character or two-character keyword;
calculating a cumulative sum of the numbers of hits of terms in the sorted terms from the top term up to the cumulative sum reaches to the maximum number of elements, and constructing a search query for index-type search by replacing a term with a truth constant, the term having the number of hits that is not added to the cumulative sum since the cumulative sum exceeds the maximum number of elements;
performing the index-type search using the search query for index-type search including the truth constant;
performing a scan-type search using a search query every time a document is searched out by the index-type search, the search query having a one-character or two-character keyword in the inputted search query replaced with truth or false to reflect a search result of a character 2-gram originating from the one-character or two-character keyword;
and
outputting a document that is searched out by the scan-type search.

14 more elements

Dependencies are inferred from the claim text.