Search query autocompletion

Details Search query autocompletion Search query autocompletion

2000-04-18

2003-05-13

Alam, Hosain T. (Department: 2172)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

06564213

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to methods for assisting users in efficiently entering search queries.
BACKGROUND OF THE INVENTION
A variety of techniques have been developed for reducing the amount of time and effort needed for search engine users to locate desired items within large domains of items. One such technique, which is described in published international patent application WO 99/45487 assigned to Amazon.com, Inc., involves ranking the search result items for display based on the frequencies with which users of the system have selected the items. With this method, the most frequently accessed items among a population of users tend to be displayed near the top of the search results list, reducing the need for the searcher to scroll through long lists of search results.
Another technique, which may be invoked when a search query produces a large number of hits, involves suggesting related terms to add to the query. One such method, which is described in U.S. Pat. No. 6,006,225 assigned to Amazon.com, Inc., involves suggesting the terms that have appeared in combination with the submitted term(s) the most frequently in recent, successful query submissions. For example, if the user submits the book search “thin air” and obtains a long list of matching titles, the search system may suggest adding “into” to the query based on the high frequency with which other users have recently submitted the query “into thin air.” As with the search result ranking method described above, this method tends to direct the searcher to the items that are currently the most popular among the population of users. Other known techniques for assisting users in conducting searches include (a) displaying to the user search queries being submitted by other users (implemented by the Metaspy™ service of the Metacrawler.com web site), and (b) providing links for the most popular searches of the day on the site (implemented by the Altavista web site).
It is also known in the art to provide an autocompletion tool that suggests completed text strings to the user as the user enters text. For example, Microsoft's Internet Explorer browser automatically suggests completed URLs as the user enters text in the URL field; and the TextPlus™ for Palm tool suggests autocompletion words and phases (based on frequency of use) as users enter text within Palm Pilot™ applications. These tools generally operate based on text strings that have previously been entered on the particular PC, Palm Pilot, or other computing device. As a result, the tools generally are not helpful when the user enters a new term or phrase.
One problem that is not fully addressed by the above and other known methods is that of reducing the number of keystrokes, voice commands, or other actions needed to enter a search query for searching a particular catalog or database, such as the products database of on online merchant. This problem is particularly important to users of handheld and other wireless computing devices that do not include full keyboards. The present invention seeks to address this problem.
SUMMARY OF THE INVENTION
The present invention overcomes the above and other problems by suggesting autocompletion strings (terms and/or phrases) to users during the query entry process, wherein the suggested strings are based on specific attributes of the particular database access system being searched. In accordance with the invention, a string extraction component associated with a particular database access system, such as a web site of an online merchant, periodically generates a dataset that contains the autocompletion strings (terms and/or phrases) for the system. The datasets are transmitted to users' computing devices, which may include handheld and other wireless devices that lack a full keyboard.
An autocompletion client which runs on the computing devices in association with a browser uses the datasets to suggest autocompletion strings as users enter queries that are directed to the database access system. Because the autocompletion strings are not based solely on strings entered on the particular computing device, they tend to be helpful for entering both new and previously entered text strings. The invention may be used regardless of the particular text input method used (stylus/graffiti, voice, keyboard, etc.).
The datasets are preferably generated so as to favor the items and/or search strings that are currently the most popular. For example, if Pokemon toys are currently the best selling or most-frequently-searched-for items within the database, the term POKEMON may be suggested whenever a user enters the letters “PO,” even though many hundreds of other items in the database may start with “PO.” In one embodiment, the datasets are generated periodically at least in part by extracting the search terms and phrases that have appeared the most frequently within successful search queries within a selected period of time, such as the last X days. In another embodiment, the autocompletion strings are periodically extracted from database descriptions of the most popular items within the database (e.g., the best selling or most frequently accessed items over a selected window of time). The datasets may also be customized to particular users or user groups. In one embodiment of the autocompletion client, the user can submit a suggested autocompletion string as the query with a single action, such as clicking or tapping on the string.
An important benefit of the invention—particularly for users of wireless computing devices—is that it significantly reduces the number of keystrokes, voice commands, or other actions needed to enter a query. Another benefit, in certain embodiments, is that the suggested strings strongly reflect the browsing activities, and thus the item interests, of a population of users. Another benefit, which is inherent in the preferred methods for generating the datasets, is that the suggested search strings do not produce a null query result.


REFERENCES:
patent: 5675819 (1997-10-01), Schuetze
patent: 5826240 (1998-10-01), Brockman et al.
patent: 5845300 (1998-12-01), Comer et al.
patent: 5864805 (1999-01-01), Chen et al.
patent: 5897622 (1999-04-01), Blinn et al.
patent: 5995928 (1999-11-01), Nguyen et al.
patent: 6006225 (1999-12-01), Bowman et al.
patent: 6029141 (2000-02-01), Bezos et al.
patent: 6144958 (2000-11-01), Ortega et al.
patent: 6169986 (2001-01-01), Bowman et al.
patent: 6185558 (2001-02-01), Bowman et al.
patent: 6208339 (2001-03-01), Atlas et al.
patent: 6223059 (2001-04-01), Haestrup
patent: 6230173 (2001-05-01), Ferrel et al.
patent: 6266665 (2001-07-01), Vaidyanathan et al.
patent: 6307549 (2001-10-01), King et al.
patent: 6370527 (2002-04-01), Singhal
patent: 6374241 (2002-04-01), Lamburt et al.
patent: 6377965 (2002-04-01), Hachamovitch et al.
patent: 6392640 (2002-05-01), Will
patent: 6401084 (2002-06-01), Ortega et al.
patent: 6401085 (2002-06-01), Gershman et al.
patent: 6421675 (2002-07-01), Ryan et al.
patent: 6430553 (2002-08-01), Ferret
patent: 6466918 (2002-10-01), Spiegel et al.
patent: 6489968 (2002-12-01), Ortega et al.
patent: WO 99/45487 (1999-09-01), None
User's Guide for TextPlus V3.3 for the Palm OS; printed from Smartcell.com web site on Dec. 17, 1999 (12 pages).
Description of TextPlus for Palm Version 3.3 printed from Palmgear.com web site on Dec. 17, 1999 (3 pages).
Jakobsson, M. “Autocompletion in Full Text Transaction Entry: A Method for Humanized Input,” Conference Proceedings on Human Factors in Computing Systems, pp. 327-332, dated Apr., 1986.
Housel, B. and Lindquist, D. “WebExpress: A System for Optimizing Web Browsing in a Wireless Environment,” Proceedings of the Second Annual Internat. Conf. on Mobile Computing and Networking, pp. 108-116, dated Nov. 1996.
Chang, H., Tait, C. Cohen, N., Shapiro, M., Mastrianni, S., Floyd, R., Housel, B. and Lindquist, D. “Web browsing in a wireless environment: disconnected and asynchronous operation in ARTour Web Express,” Proceedings of the Third Annual ACM/IEEE Internat. Conf. on Mobile Co

Affiliated with

Also associated with

Rating

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

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3009915