Invention for Search query autocompletion

Invented by Ruben E. Ortega, John W. Avery, Robert Frederick, A9 com Inc

The A9 com Inc invention works as follows

A system to facilitate online searches suggests query autocompletion (terms or phrases) to users when they enter their query, wherein the suggested string is based on the specific attributes of the database access system that’s being searched. A string extractor component that is associated with a database system, like a website of an online retailer, generates periodically a dataset containing the autocompletion phrases for the system. The datasets may be tailored to specific users or groups and are biased in favor of the most popular database items (e.g. best sellers or most frequently viewed). The datasets can be transmitted to the computing devices of users, including handheld devices and wireless devices without a keyboard. The datasets are used by an autocompletion program that runs on computing devices and is associated with a web browser to suggest autocompletion strings when users enter queries directed to the database system.

Background for Search query autocompletion

There are a number of techniques that can be used to reduce the time and effort required by search engine users in order to find desired items among large domains. In a published international patent application (WO 99/45487) assigned to Amazon.com, Inc., one such technique involves ranking search results for display according to the frequency with which system users have selected them. This method allows the most popular items to be displayed at the top of a list of search results, saving the user from having to scroll down long lists.

Another method, which can be used when a query returns a lot of results, is to suggest related terms that should be added to the query. U.S. Pat. No. No. 6,006,225, assigned to Amazon.com, Inc., suggests the terms most commonly used in conjunction with the term(s) submitted in recent, successful queries submissions. If the user searches for a book using the term “thin air”, the search system may suggest adding the word “into” to the list of matching titles. If the user submits a book search?thin air? and receives a list of titles that match, then the system will suggest adding ‘into’ to their query. The search system may suggest adding?into? to the query, based on how often other users have submitted this query in the past. This method is similar to the method of ranking search results described above. It tends to guide the user to items that are most popular at the moment. Metaspy? Metacrawler.com’s Metaspy service implements this technique.

It is also known that the autocompletion feature suggests text completions to the user when they enter text. Microsoft’s Internet Explorer browser, for example, suggests complete URLs when the user enters the URL field. And the TextPlus? TextPlus? applications. These tools are usually based on text that has been previously entered into the PC, Palm Pilot or other computing devices. The tools are generally not useful when the user types in a new phrase or term.

One problem not fully addressed by these and other methods is the reduction of the number of keystrokes or voice commands or other actions required to enter a query when searching a catalog or database such as the product database of an online merchant. This is a problem that users of wireless handheld devices and other computing devices face, as they do not have full keyboards. This problem is addressed by the present invention.

The present invention solves these and other problems, by presenting autocompletion (terms or phrases) during the query-entry process. These suggested strings are based upon specific attributes of the database access system that is being searched. According to the invention, an associated string extraction component, such as the web site of an internet merchant, generates periodically a dataset containing the autocompletion (terms or phrases) for a database access system. The datasets are sent to the users’ computing devices. These devices may include wireless handheld devices and other devices without a keyboard.

An autocompletion program that runs on computing devices and is paired with a web browser, uses the datasets in order to suggest autocompletion string suggestions as users type queries to be sent to the database system. The autocompletion string suggestions are useful for both entering new text and text that has been previously entered. The invention can be used regardless of which text input method is used (stylus/graffiti or keyboard, voice, etc .).

The datasets will be generated to give preference to the items or search terms that are most popular at the moment. 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 hundreds of items in the database could begin with “PO”, In one embodiment, datasets are periodically generated at least in part, by extracting search terms and phrases which have appeared most frequently within successful searches within a specified period of time such as the past X days. In another embodiment the autocompletion string is periodically extracted from the database descriptions of most popular items in the database (e.g. the best-selling or most frequently-accessed items during a specified window of time). Datasets can also be tailored to specific users or groups. In one embodiment, the autocomplete client allows the user to submit an autocompletion query by clicking or tapping 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. In certain embodiments, the suggested strings are based on the browsing habits and item interests of a user population. The preferred methods of generating datasets have another benefit: the suggested search string does not result in a null result.

The present invention is a system that suggests autocompletion string to users when they enter search queries. The autocompletion string is based on one or more attributes of a particular database system that’s being searched. For example, the identifiers of items within the database and the frequency with which users performed certain actions in relation to these items. The suggestions are helpful in the process of entering the query. The invention is especially useful for computers without a keyboard, like handheld computers, cellular phones, automobile computers, and wearable computers. However, it can also be used on PCs and other devices with full keyboards. The invention can be used with a wide range of text entry methods including, but not limited, to voice recognition, handwriting recognition, keyboard entry, and even graffiti.

For the purposes of illustration, this invention will primarily be described in relation to web-based systems as well as systems for searching online merchants’ catalogs. The invention will, however, be understood to not be so limited.

FIG. The flow and basic components of an embodiment of the invention are shown in FIG. A database access 20 comprises a database 22, and a query service 24. The database 22 can be any kind of data repository, or a combination of data repositories. It stores records and other representations. Items can be, for instance, products available for purchase, web pages indexed by crawler programs, or businesses. To make things easier, we will use the term “item”. The term?item? will be used interchangeably for the actual items and the database representations thereof.

The query server 24 allows remote users to search for items in the database 22 using textual queries. The database access system may provide other methods of locating items in the database. For example, a browse tree and item recommendation services.

As shown in FIG. Searches can be conducted using different computing devices 40. For example, a PC 40A or a handheld computing device 40B (wireless), which does not include a full keyboard. The handheld computing 40B can be a PDA device such as the Palm Pilot, or a cellular phone with Internet browsing capability. These handheld devices typically provide an interface to enter text using voice recognition or handwriting recognition.

The components that are associated with the query-autocompletion feature include a string extractor component 46, an automatic completion server 48, as well as an autocompletion user 50. The autocompletion server 48 is associated with the browser 54 and provides autocompletion suggestions to users when they enter search queries that correspond (e.g. are entered in a search page for) the database system 20. In one embodiment, autocompletion 50 is implemented as an add-on for a browser that users can download from the database system 20. The autocompletion service may also be integrated into the browser 54. The autocompletion user interface is dependent on the type of computing devices (PC, hand-held, voice-activated etc.). being used.

The string extraction component 46 generates one or more datasets 30, which contain autocomplete strings (terms or phrases) that describe objects within the database 22, on a periodic basis. The autocompletion string is preferably extracted from the log of queries submitted (as shown in FIGS. The autocompletion strings are preferably extracted from a log of query submissions (as shown in FIGS. Other sources of information, such as reviews from customers or databases of manufacturers could also be used. As shown in FIG. As shown in FIG. This data structure may include string scores or weights to give certain strings a preference over others.

If the database 22 has a large number of items (e.g. over one million), it is preferred that the dataset generation task be performed so that the autocomplete strings suggested correspond to items or search stings which are currently most “popular”. If Pokemon products are the most popular items in the database 22, then the term POKEMON could be suggested to a user when they enter the letters “PO”. Even though hundreds of items within the database have names that begin with ‘PO,’ To achieve this goal, one method is to monitor browsing (and, if applicable purchasing) activities to identify the most popular products, and then to parse these items to identify defining terms and/or phrase. FIG. FIG. 6 illustrates this method. A second method is shown in FIG. The following paragraphs describe how to monitor query submissions in order to identify the most commonly used search terms or phrases. The datasets 30 can be customized for specific users or groups of users.

As shown in FIG. The autocompletion service 48 sends datasets 30 created by the string extractor 46 to computing devices 40. These devices then store the data structures for later use (preferably on nonvolatile memory over multiple sessions). The timing of such data transfers can be controlled by a number of different methods. The user can, for example, manually transfer the latest dataset using the autocompletion 50 client, or set parameters to automatically download new datasets in the background. The frequency at which new datasets become available for download may depend on the frequency of database updates. A merchant who adds products frequently to his online catalog might want to create new datasets relatively often (e.g. once a day) by using a sliding-window approach. Instead of sending the entire dataset 30, the autocompletion servers 48 could simply send updates to previously downloaded data.

The computing device 40 may be sent periodic information about the format of and address of relevant search pages. This information can be used by the autocompletion client to identify which web pages or search fields should receive the autocompletion feature. Information about search pages can be “hard-coded” within the autocompletion client 50. The information about the search pages could alternatively be?hard coded?

An alternative method that could be useful with small datasets is to send the dataset along with the web page to the computing device. This approach allows the autocompletion string to be tailored to the search functionality of the web page. For example, on a search page for books, the autocompletion strings correspond to the book titles in the database 22 and for a search page for music, they correspond to the music titles. Another variation is to send the autocomplete client 50 and corresponding search pages in a Java applet.

The autocompletion client may be configured so that it provides autocompletion for several distinct database access systems (e.g. the websites of different online merchants). In these implementations, users can download and store datasets 30 that are associated with the database access systems they wish to browse. The autocompletion 50 client may also be associated with a specific database access system.

The operator(s), of the database system(s), could offload the tasks of generating the autocompletion data sets 30 in whole or in part to a different business entity. A single business entity, for example, could extract strings from multiple online merchants, under contract. The extracted strings of merchants with similar business areas would then be combined into a dataset. The same business entity can provide a service to distribute the datasets.

Click here to view the patent on Google Patents.