Dynamic query expansion

Details Dynamic query expansion Dynamic query expansion

1998-11-30

2002-06-25

Mizrahi, Diane D. (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06411950

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method and apparatus for searching records stored in an electronic database. More specifically, but not by way of limitation, the present invention relates to a method and apparatus for dynamic search result refinement by refining a vague text-search query into a more specific text-search query.
2. Description of the Related Art
In recent years, the amount of text-based data electronically stored has grown tremendously. This text-based information includes everything from E-mail messages to patient records to world wide web (Web) pages. Specifically, much of the growth in stored text-based data is a direct result of the explosion in the number of Web pages. As anyone who has attempted to search the Web or any large database knows, however, Web pages and database records are practically useless unless they can be searched rapidly, accurately and efficiently. To aid in such searching, a number of search engines using a variety of techniques are available.
A common and accurate searching technique is full-text searching—shown in FIG.
1
. In a full-text search, the entire text that is to be searched, e.g., a database record, is scanned to find a match with a particular received query. Steps
100
and
110
. When a match between that which is scanned and the search query is located, the location of the match is returned as a search result—called a hit. Step
120
. This location corresponds to a particular database record or in terms of the Web, the location or the URL of a particular Web page.
Although full-text searching is very accurate, this accuracy sometimes presents major drawbacks. For a very specific query, the full-text search is accurate and efficient in that it returns only a few locations. Thus, a user can quickly scan through the records corresponding to these returned locations. In essence, full-text searching is most useful and most powerful when it is searching for a needle in a haystack. If, however, a user is not searching for such a needle, i.e., does not have a very specific query, the full-text search is cumbersome and inefficient. For example, if the user attempts to search the Web for the phrase “New York,” a full-text search could return millions of hits. obviously, it would be virtually impossible for the user to wade through millions of records to find specific records of interest. Even if the particular site for which the user is searching is included in the hits, the user could easily overlook this site because it is buried among the other records.
One way to reduce the number of hits from a full-text search is to narrow the search term. For instance, the phrase “New York” could be narrowed to “New York transit.” Although it may seem elementary to modify the query by, for example, adding another term, many times it is not clear as to which term to add or how to otherwise modify the query. If a user is looking for commuter buses leaving New York City, it is not clear whether the proper query would include “buses”, “commuter”, “transit”, or any combination thereof. Very possibly, the proper query might involve terms that elude a user, i.e., “port authority,”—because many commuter buses leave from the New York Port Authority.
Some current search engines provide a user with possible or suggested terms to be added to their search. For example, a search engine might suggest that for the query“law” one of the following terms be added: “legal,” “intellectual,” “court” or “appeals.” Thus, the new search could be, e.g., “law appeals” or “law legal.” Thus, the suggested query is not a coherent phrase but rather a jumble of related words. The flaw with these current search engines is that the suggested terms do not necessarily focus a user's search. An additional flaw with these current search engines is that their list of suggested terms is not dynamically updated to reflect the most popular or most requested records.
Accordingly, an invention is needed that provides the user the ability to focus a general search query so that a user can readily refine a general search query until the search results contain a usable amount of record locations. Further, an invention is needed that dynamically generates lists of more specific queries for a given query, thereby giving a user the most up-to-date and most popular choices for query refinement.
SUMMARY OF THE INVENTION
The present invention overcomes the above identified problems as well as other deficiencies of existing technologies by providing, in one aspect, a method for generating an index useable to refine a vague query into more specific queries for searching stored records. The method includes the step of generating a phrase list. This phrase list can be constructed by receiving a number of queries from various users and then extracting phrases from those queries. These extracted phrases may be quoted phrases, i.e., user's search phrases that were placed in quotation marks. Further, the phrase list could include only those phrases that are determined to be statistically significant. The statistical significance of the search phrase may be determined by the number of times a particular phrase appears in the received user queries. This number is the query frequency.
Another step of the method of this invention includes computing the index frequency of the phrases in the phrase list. The index frequency indicates to what degree a phrase is general or specific, and it can be calculated a number of ways. For example, the index frequency for a particular phrase can be the number of times that the particular phrase appears in all the html pages associated with a particular search engine database.
It is contemplated that in one embodiment of the present invention, a step is included that determines whether the frequency for a particular phrase is lower than that of another particular phrase. Good results have been achieved by utilizing either of the index frequency or the query frequency. In using the index frequency, if the index frequency for one particular phrase is lower than that of another particular phrase, the present invention stores the two phrases in an index, the two phrases being associated with each other in the index. In one embodiment, the two phrases are stored in an index only if the index frequency for one phrase is many times larger, e.g. 10 times larger, than that of another particular phrase. Regardless of what difference is required in the index frequencies, for the two phrases to be stored in the index, the two phrases should be at least partial syntactic matches. In other words, the two phrases should share at least one common term before the two phrases can be stored in the index. It is contemplated to be within the scope of this invention that the two phrase can be stored in the index if the common terms are similar but not an exact match.
In an additional embodiment, the method of the invention includes the step of receiving a query from a user. If an entry similar to this query is stored in an index, index entries associated with the that entry are transmitted to the user. The user then can use the transmitted index entries to either search the database or to further refine the original query.


REFERENCES:
patent: 5819260 (1998-10-01), Lu et al.
patent: 5963965 (1999-10-01), Vogel
patent: 5974455 (1999-10-01), Monier
patent: 5987446 (1999-11-01), Corey et al.
patent: 6006223 (1999-12-01), Agrawal et al.
patent: 6070158 (2000-05-01), Kirsch et al.
patent: 6101491 (2000-08-01), Woods
patent: 6101515 (2000-08-01), Wical et al.
patent: 6112203 (2000-08-01), Bharat et al.
patent: 6144958 (2000-11-01), Ortega et al.
Mining term association rules for automatic global query expansion:methodology and preliminary results by Wei et , National University of Singapore, pp. 366-373, Jan. 2000 (IEEE publication).

Affiliated with

Also associated with

Rating

Dynamic query expansion does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic query expansion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic query expansion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2943382