(12) United States Patent
`Ortega et al.
`
`USOO6564213B1
`(10) Patent No.:
`US 6,564,213 B1
`(45) Date of Patent:
`May 13, 2003
`
`(54) SEARCH QUERY AUTOCOMPLETION
`
`(75) Inventors: Ruben E. Ortega, Seattle, WA (US);
`John W. Avery, Seattle, WA (US);
`Robert Frederick, Seattle, WA (US)
`
`6/2002 Gershman et al. ............. 707/4
`6,401,085 B1
`7/2002 Ryan et al. ................. 707/100
`6,421,675 B1
`8/2002 Ferret ............................ 707/3
`6,430,553 B1
`6,466,918 B1 * 10/2002 Spiegel et al. ...
`... 705/27
`6,489,968 B1 * 12/2002 Ortega et al. ............... 345/713
`FOREIGN PATENT DOCUMENTS
`
`WO
`
`WO 99/45487
`
`9/1999
`
`(73) Assignee: Amazon.com, Inc., Seattle, WA (US)
`(*) Notice:
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/551,787
`(22) Filed:
`Apr. 18, 2000
`(51) Int. Cl." ................................................ G06F 17/30
`(52) U.S. Cl. .................................... 707/5: 707/3; 707/4
`(58) Field of Search ............................... 707/1-10, 100,
`707/102, 104
`
`(56)
`
`OTHER PUBLICATIONS
`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).
`(List continued on next page.)
`Primary Examiner-Hosain T. Alam
`Assistant Examiner Anh Ly
`(74) Attorney, Agent, or Firm- Knobbe, Martens, Olson &
`Bear LLP
`ABSTRACT
`(57)
`References Cited
`A System for facilitating online Searches Suggests query
`U.S. PATENT DOCUMENTS
`autocompletion Strings (terms and/or phrases) to users dur
`5,675,819 A 10/1997 Schuetze ..................... 704/10
`ing the query entry process, wherein the Suggested Strings
`5,826,240 A * 10/1998 Brockman et al. ............ 705/11
`are based on Specific attributes of the particular database
`5,845,300 A * 12/1998 Comer et al. .....
`... 707/508
`5,864,805. A
`1/1999 Chen et al.................. 7025 access system being searched. A string extraction compo
`5,897,622 A * 4/1999 Blinn et al. ................... 705/26
`nent associated with a database access System, Such as a web
`5,995,928 A 11/1999 Nguyen et al. ...
`... 704/251
`Site of an online merchant, periodically generates a dataset
`6,006,225 A * 12/1999 Bowman et al. ............... 707/5
`r
`6,029,141. A * 2/2000 Bezos et al. ......
`... 705/27
`that contains the autocompletion Strings for the system. The
`6,144.958 A * 11/2000 Ortega et al. .....
`... 707/5
`datasets are preferably biased to favor the database items
`6,169,986 B1 * 1/2001 Bowman et al. ..
`... 707/5
`that are currently the most popular (e.g., best Selling or most
`6,185.558 B1
`2/2001 Bowman et al. ............... 707/5
`frequently viewed), and may be customized to particular
`6,208,339 B1 * 3/2001 Atlas et al. ....
`... 345/780
`users or user groups. The datasets are transmitted to users
`6,223,059 B1
`4/2001 Haestrup ......
`... 455/566
`computing devices, which may include handheld and other
`6,230,173 B1
`5/2001 Ferrel et al. .......
`... 707/513
`wireleSS devices that lack a full keyboard. An autocomple
`6,266,665 B1*7/2001 Vaidyanathan et al. ....... 707/7
`tion client which runs on the computing devices in associa
`6,307,549 B1 10/2001 King et al. ..........
`... 345/810
`tion with a browser uses the datasets to Suggest the auto
`6,370,527 B1 * 4/2002 Singhal ........
`... 707/6
`6,374,241 B1
`4/2002 Lamburt et al. ............... 707/6
`completion Strings as users enter queries that are directed to
`6377.965 B1 is 4/2002 Hachamovitch et al... 707/534
`the database access system.
`6,392.640 B1
`5/2002 Will ........................... 345/184
`6,401,084 B1 * 6/2002 Ortega et al. .................. 707/2
`56 Claims, 6 Drawing Sheets
`
`
`
`36ZOCO
`- is
`
`Search; SONY
`
`SONY WCR
`SONY TV
`SONY TRINITRON
`SONY HANDY CAM
`
`37
`
`66
`(Go)
`
`Facebook's Exhibit No. 1007
`Page 1
`
`

`

`US 6,564,213 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`Jakobsson, M. “Autocompletion in Full Text Transaction
`Entry: A Method for Humanized Input,” Conference Pro
`ceedings 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 Com
`puting and Networking, pp. 260-269, dated Sep. 1997.
`Gessler, S. and Kotulla, A. “PDAs as mobile WWW brows
`ers,” Computer Networks and ISDN Systems 28, pp. 53-59
`(1995).
`* cited by examiner
`
`Facebook's Exhibit No. 1007
`Page 2
`
`

`

`U.S. Patent
`
`May 13, 2003
`
`Sheet 1 of 6
`
`US 6,564,213 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Facebook's Exhibit No. 1007
`Page 3
`
`

`

`U.S. Patent
`
`May 13, 2003
`
`Sheet 2 of 6
`
`US 6,564,213 B1
`
`
`
`
`
`36ZCO)
`
`--
`
`s
`
`as
`
`66
`
`62
`
`a (g
`
`SONY
`SOFTWARE
`SONGS
`SOCKS
`SONY WCR
`SONGS FROM THE ATTIC
`SO LONG AND THANKS FOR ALL THE FISH
`
`A7C2 24
`
`36ZCO
`
`Search; SONY
`
`SONY WCR
`SONY TV
`SONY TRINITRON
`SONY HANDY CAM
`
`A7C2 2A
`
`6O
`
`66
`(Go)
`
`Facebook's Exhibit No. 1007
`Page 4
`
`

`

`U.S. Patent
`
`May 13, 2003
`
`Sheet 3 of 6
`
`US 6,564,213 B1
`
`
`
`
`
`(G) OIVA ANOS
`
`
`
`(978) AL ANOS
`
`
`
`(6): Nos || • • •[(s) SÐNOS
`
`
`
`(S) WVO WONVH \NOS
`
`
`
`
`
`Facebook's Exhibit No. 1007
`Page 5
`
`

`

`on
`
`<a
`
`SLONdONd
`
`(S)aSVavVLvd
`
`ALISDIMLNVHOYNSAN
`
`SSAN5SGAM
`
` Po
`
`U.S. Patent
`
`May13, 2003
`
`Sheet 4 of 6
`
`US 6,564,213 Bl
`
`YSWOLSNO
`
`Jsvavivd
`
`JNOSOLNV
`
`ASVaVLlVd
`
`vivd
`
`NOILOVYLXI
`
`(S‘O14)
`
`AMANO
`
`YAAYAS
`
`dWOSOLNV&F
`
`Or—eS
`
`dDWOOSOLNV
`
`LASVLVG|LN3IT9
`
`Facebook's Exhi
`
`it No. 1007
`Page 6
`
`Facebook's Exhibit No. 1007
`Page 6
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`May 13, 2003
`
`Sheet 5 of 6
`
`US 6,564,213 B1
`
`GENERATE DATASET
`FROM QUERY LOG
`
`GET OUERY LOG
`DATA FOR LAST
`M DAYS
`
`52
`
`52
`
`FILTER OUT OUERIES THAT
`PRODUCED NULL QUERY
`RESULT OR REQUIRED
`SPELL CORRECTION
`
`547
`
`OPTIONALLY PARTITION OUERY
`DATA ACCORDING TO USER
`GROUPS, AND PERFORM
`REMAINING STEPS FOR
`EACH USER GROUP
`
`
`
`56
`
`ss
`
`IDENTIFY AND ASSIGN SCORES
`TO MOST FREQUENTLY
`USED SEARCH TERMS
`AND PHRASES
`
`
`
`STORE RESULTS IN TRE
`OR OTHER DATA STRUCTURE
`
`LAST
`GROUP
`
`YES
`
`END
`
`AC2 15
`
`Facebook's Exhibit No. 1007
`Page 7
`
`

`

`U.S. Patent
`
`May 13, 2003
`
`Sheet 6 of 6
`
`US 6,564,213 B1
`
`
`
`GENERATE DATASET
`FROM ITEM DESCRIPTIONS/
`
`GET USER PURCHASE
`HISTORES FOR LAST
`X DAYS
`
`
`
`
`
`
`
`
`
`
`OPTIONALLY PARTITION PURCHASE
`HISTORY DATA ACCORDING TO
`USER GROUPS, AND PERFORM
`REMAINING STEPS FOR EACH
`SUCH GROUP
`
`
`
`
`
`
`
`IDENTIFY Y BEST
`SELLING TEMS
`
`FOR EACH BEST SELLING
`|TEM EXTRACT CHARACTERIZING
`TERMS AND/OR PHRASES AND
`ASSIGN SCORES
`
`STORE RESULTS IN TRE
`OR OTHER DATA STRUCTURE
`
`LAST
`GROUP
`2
`
`
`
`
`
`A72 6
`
`Facebook's Exhibit No. 1007
`Page 8
`
`

`

`1
`SEARCH QUERY AUTOCOMPLETION
`
`US 6,564,213 B1
`
`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 interna
`tional 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 TM service of the Metacrawl
`er.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 TextPlusTM for Palm tool
`Suggests autocompletion words and phases (based on fre
`quency of use) as users enter text within Palm Pilot"M
`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 mer
`chant. 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/
`
`5
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`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 accor
`dance 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 auto
`completion 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 que
`ries 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 autocomple
`tion 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.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 illustrates the basic components and process flow
`of a System that embodies the invention.
`FIGS. 2(a) and 2(b) illustrate an example user interface
`that may be used to Suggest autocompletion Strings.
`FIG.3 illustrates the general form of a trie search tree that
`may be used to rapidly look up autocompletion Strings.
`FIG. 4 illustrates one embodiment of the system shown in
`FIG. 1.
`FIG. 5 illustrates a method for extracting autocompletion
`Strings from a query log.
`FIG. 6 illustrates a method for extracting autocompletion
`Strings from item descriptions according to item sales his
`tories.
`Throughout the drawings, like reference numbers are used
`to reference items that are identical or functionally similar.
`
`Facebook's Exhibit No. 1007
`Page 9
`
`

`

`3
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`The present invention provides a System and associated
`methods for Suggesting autocompletion Strings to users
`during entry of Search queries. The autocompletion Strings
`are based one or more attributes of the particular database
`System being Searched, Such as the identities of the items
`contained within the database, frequencies with which users
`have performed particular actions with respect to Such items,
`and/or queries Submitted by users to Search the database. AS
`a result, the Suggestions tend to be helpful to the query entry
`process. The invention is particularly useful with computers
`that lack a full keyboard, Such as handheld computing
`devices, cellular telephones, automobile computers and
`wearable computers, but may also be used with PCs and
`other computing devices that have full keyboards. The
`invention may be used with any of a variety of text entry
`methods, including but not limited to handwriting recogni
`tion (e.g., graffiti), Voice recognition, and keyboard entry.
`For purposes of illustration, the invention will be
`described primarily in the context of web-based Systems and
`Systems for Searching catalogs of online merchants. It will
`be recognized, however, that the invention is not So limited.
`FIG. 1 illustrates the basic components and process flow
`of a preferred embodiment of the invention. A database
`access System 20 includes a database 22 and a query Server
`24. The database 22, which may be any type of data
`repository or combination of data repositories, Stores records
`or other representations of items. The items may, for
`example, be products that are available for Sale, web pages
`that have been indexed by a crawler program, or businesses.
`For convenience, the term “item' will be used to refer
`interchangeably to the items themselves and to the database
`representations of Such items.
`The query server 24 provides functionality for remote
`users to Search the database 22 for desired items using
`textual queries. The database access System 20 may also
`provide alternative methods for locating items within the
`database, Such as a browse tree or an item recommendation
`Service.
`AS depicted in FIG. 1, Searches may be performed using
`a variety of different types of computing devices 40, Such as
`a conventional PC 40A, or a handheld (wireless) computing
`device 40B that lacks a full keyboard (e.g., does not have
`fixed keys for the characters A-Z). The handheld computing
`device 40B may be a PDA (personal digital assistant) such
`as a Palm Pilot device, or may be a cellular telephone that
`includes Internet browsing capabilities. Typically, Such
`handheld devices provide an interface for entering text using
`handwriting recognition and/or voice recognition
`The components associated with the query autocomple
`tion function include a String extraction component 46, an
`autocompletion server 48, and an autocompletion client 50.
`The autocompletion client 50 runs in association with a
`browser 54, and is responsible for Suggesting autocomple
`tion Strings to users during entry of Search queries that
`correspond to (e.g., are entered into a search page of) the
`database acceSS System 20. In one embodiment, the auto
`completion client 50 is implemented as a browser plug-in
`that can be downloaded from the database access system 20
`to assist users in the Searching process. Alternatively, the
`autocompletion client may be provided as an integral com
`ponent of the browser 54. The user interface provided by the
`autocompletion client is preferably dependent upon the type
`of computing device (PC, handheld, Voice-activated, etc.)
`being used.
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,564,213 B1
`
`15
`
`25
`
`4
`The String extraction component 46 is responsible for
`periodically generating one or more datasets 30 that contain
`autocompletion Strings (terms and/or phrases) that describe
`items within the database 22. The autocompletion Strings are
`preferably extracted from a log of query Submissions (as
`illustrated in FIGS. 4 and 5) and/or from the item descrip
`tions within the database 22 (as illustrated in FIG. 6),
`although other Sources of information could be used Such as
`customer reviews or manufacturers’ databases. AS illustrated
`in FIG.3 and described below, each dataset 30 is preferably
`in the form of a data Structure, Such as a trie, that is adapted
`to be rapidly searched by the autocompletion client 50.
`String Scores or weights may be included in this data
`Structure to favor certain Strings over others.
`If the database 22 is large (e.g., over one million items),
`the dataset generation task is preferably performed Such that
`the autocompletion Strings Suggested generally correspond
`to the items and/or the Search Stings that are currently the
`most "popular.” For example, if Pokemon products are
`currently the best Selling items within the database 22, the
`term POKEMON may be suggested whenever a user enters
`the letters “PO,” even though many hundreds of other items
`in the database may have names that start with “PO.” One
`method for achieving this goal is to monitor the browsing
`(and if applicable, purchasing) activities of users to identify
`the most popular items, and to then parse Such items to
`identify characterizing terms and/or phrases. FIG. 6 provides
`one example of this method. Another method, which is
`illustrated in FIGS. 4 and 5 and described below, involves
`monitoring query Submissions over time to identify the most
`frequently used Search terms and/or phrases. AS discussed
`below, the datasets 30 may optionally be customized to
`particular users and/or groups of users.
`As depicted in FIG. 1, the autocompletion server 48
`dispatches the datasets 30 generated by the String extraction
`component 46 to the computing devices 40, which in-turn
`Store the data structures (preferably in nonvolatile storage
`over multiple Sessions) for Subsequent use. Any of a variety
`of methods may be used for controlling the timing for Such
`data transferS. For example, using the autocompletion client
`50, the user may be able to manually initiate a transfer of the
`latest dataset, or to Set up parameters for the automatic
`background downloading of new datasets. The frequency
`with which new datasets are made available for download
`ing may be dependent upon the frequency with which
`updates are made to database 22. For example, an online
`merchant that frequently adds new products to its online
`catalog may wish to generate new datasets on a relatively
`frequent basis (e.g., once per day) using a sliding window
`approach. Rather than Sending the entire dataset 30 each
`time, the autocompletion Server 48 could simply dispatch
`updates to previously downloaded datasets.
`Information about the format and addresses of the rel
`evant Search pages may also be periodically Sent to the
`computing devices 40. The autocompletion client 50 may
`then use this information to identify the web pages and
`asSociated Search fields to which the autocompletion func
`tion should be applied. The information about the search
`pages could alternatively be “hard coded” within the auto
`completion client 50.
`An alternative approach that may be desirable with rela
`tively small datasets 30 is to transmit the dataset to the
`computing device 40 with the corresponding web page. With
`this approach, the autocompletion Strings may be custom
`ized to the particular Search functionality provided on the
`web page. For example, for a book Search page, the Strings
`would correspond to book titles within the database 22, and
`
`Facebook's Exhibit No. 1007
`Page 10
`
`

`

`S
`for a music Search page, the Strings would correspond to
`music titles. A further variation is to transmit the auto
`completion client 50 with corresponding Search pages as a
`Java applet.
`The autocompletion client 50 may be configured to pro
`vide autocompletion functionality for multiple, distinct data
`base access Systems 20 (e.g., the webs sites of Several
`different online merchants). In Such implementations, the
`user may download and store the datasets 30 associated with
`each Such database acceSS System the user wishes to browse.
`Alternatively, the autocompletion client 50 may be uniquely
`asSociated with a particular database access System.
`The tasks of generating and disseminating the auto
`completion datasets 30 could be offloaded in-whole or
`in-part by the operator(s) of the database access System(s) to
`a separate business entity. For example, a single busineSS
`entity could perform the String extraction task for multiple
`online merchants under contract, in which case the extracted
`Strings for merchants in Similar busineSS areas could option
`ally be combined within a single dataset. The same busineSS
`entity could provide a Service for disseminating the datasets
`to uSerS.
`FIGS. 2(a) and 20b) illustrate the general form of a user
`interface that may be used by the autocompletion client 50
`for both PCs and handheld computing devices. In this
`example, as the user enters a Search query into a Search field
`60 of the Amazon.com web site (by voice, stylus, etc.), the
`autocompletion client displayS Suggested autocompletion
`terms and phrases in a drop-down box 62. AS illustrated in
`FIG. 2(a), terms are displayed in an upper pane of the box
`and phrases are displayed in a lower pane of the box. In other
`implementations, the autocompletion client may only Sug
`gest one type of string (terms or phrases) without the other.
`As illustrated in FIG. 2(b), once the user has completed a
`term, the autocompletion client may only display Suggested
`phrases.
`The user interface may implement one or more methods
`for the user to perform the dual action of Selecting and
`Submitting a displayed autocompletion String with a single
`Selection action, Such as a single (or double) mouse click, a
`Single (or double) tap on the String with a stylus, or a voice
`command. In one embodiment, for example, if the user taps
`or clicks once on a Suggested String (term or phrase), the
`string is automatically added to the search field 60; and if the
`user taps or clickS twice on a String, the String is automati
`cally Submitted as the Search query. In another embodiment,
`tapping or clicking once on a String causes the String to be
`Submitted as the Search query. In either case, the user can
`advantageously initiate the Search without moving the Stylus
`or mouse cursor away from the Selected String. In embodi
`ments that Support Voice recognition, each Suggested String
`may be displayed in conjunction with a number (1, 2, 3, . .
`..) that can be used as a voice command to perform the dual
`action of Selecting the String and initiating the Search.
`Many Search engines allow the user to Specify a particular
`context for performing the Search. The context may, for
`example, be a particular item category (e.g., books, music,
`or electronics), a particular record field (e.g., title, artist, or
`Subject), or a combination thereof. In Such cases, the auto
`completion Strings Suggested to the user may depend upon
`the particular context designated by the user. For example,
`when the user conducts a title Search for books, the auto
`completion Strings may be limited to terms and phrases that
`appear within book titles, or that have appeared in book title
`Searches conducted by other users.
`FIG. 3 illustrates the general form and content of a trie
`data Structure 30 that may be used for the Storage and lookup
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,564,213 B1
`
`6
`of autocompletion Strings. The leaf nodes of the trie repre
`Sent autocompletion phrases, and are preferably Stored
`together with respective scores (shown in parenthesis).
`Autocompletion terms may be represented within the trie
`either as leaf nodes or as intermediate nodes, and are
`likewise preferably Stored with respective Scores. Although
`only alphabetical characters are shown, the trie may also
`include numeric and/or other types of characters that com
`monly occur within Search queries for the particular System.
`In operation, each time the user enters a character of the
`search query, the autocompletion client 50 effectively moves
`down the trie by one level to a node that matches the entered
`characters, and then Searches the nodes falling below that
`node for the X terms having the highest Scores and Yphrases
`having the highest Scores, where X and Y are the maximum
`numbers of terms and phrases, respectively, to be displayed
`at a time. The located terms and phrases, if any, are then
`displayed to the user as in FIG. 2.
`In embodiments in which the Suggested Strings depend
`upon the Search context, the terms and phrases may be
`tagged within the trie to indicate the contexts to which they
`correspond. For example, nodes containing the term SONY
`may be tagged to indicate that they correspond to the item
`category “electronics.” The autocompletion client 50 uses
`these tags to effectively filter out nodes that do not corre
`spond to the context of the user's Search.
`Each score within the trie reflects an estimated probability
`or prediction that the user is entering the corresponding
`String. The Scores are preferably based on at least one of the
`following: (a) the frequency with which the String has
`appeared within Search queries of users over a Selected
`period of time, optionally giving more weight to Searches
`that are deemed “Successful.” (b) the sales ranks or other
`popularity ranks of the item(s) to which the String
`corresponds, and (c) the frequency of occurrence of the
`String within the database 22.
`Prior to transmitting the trie to a given user, the Scores
`may optionally be adjusted based on information known
`about the particular user. For example, if the user has shown
`a strong affinity for electronics products over other types of
`products within the database 22, all of the Scores associated
`with Strings corresponding to the electronicS items may be
`multiplied by an appropriate Scaling factor. The String con
`tent of the trie may similarly be customized to the user, Such
`as by deleting nodes that correspond only to item categories
`for which the user has shown no interest. AS discussed
`below, another customization method that may be used
`involves generating community-Specific datasets 30 that
`correspond to the activities (e.g., query Submissions) or
`interests (e.g., purchases) of particular communities or user
`groupS.
`Another type of data Structure that could be used for
`autocompletion is a related terms table of the type described
`in above-referenced U.S. Pat. No. 6,006,225. Each entry in
`the related terms table includes two components: (1) a
`keyword, and (2) a “related terms” list, which is preferably
`a ranked list of the X terms that have occurred the most
`frequently in multi-term Search queries that included the
`keyword. For example, the related terms list for the keyword
`COSMOS might start with the terms SAGAN and SPACE,
`indicating that SAGAN has occurred the most frequently,
`and SPACE has occurred the second most frequently, in
`searches that included the term COSMOS. With this type of
`data Structure, once the user has entered a term that appears
`as a keyword within the table, the autocompletion client 50
`could simply Suggest adding the most highly ranked terms in
`the corresponding related terms list. If the user begins
`
`Facebook's Exhibit No. 1007
`Page 11
`
`

`

`US 6,564,213 B1
`
`15
`
`35
`
`45
`
`25
`
`7
`entering characters of the Second term of the query, the client
`could then filter out from the list the terms that no longer
`apply, and display any remaining terms in their ranked order.
`FIGS. 4 and 5 illustrate an embodiment of the FIG. 1
`System in which the autocompletion datasets 30 are gener
`ated using information Stored within a query log 76 of an
`online merchant, Such as Amazon.com. The information
`contained within the query log that may be used in the
`dataset generation process preferably includes the follow
`ing: (a) the query and Search context of each Search, (b) an
`identifier of the user who performed the search, (c) the
`number of hits (items found) by the search, (d) whether any
`of the query terms were modified by a query Spell checker
`component, and (e) the time the Search was performed. The
`query log 76 also preferably includes information that may
`be used to determine whether the user viewed, purchased, or
`added to a shopping cart a Search result item. Techniques for
`processing query logs to extract Such information are
`described, for example, in published international patent
`application WO 99/45487, assigned to Amazon.com, Inc.,
`the disclosure of which is hereby incorporated by reference.
`FIG. 5 illustrates the basic method used by the string
`extraction component 46 (“process”) to generate one or
`more autocompletion datasets 30 from the query log 76. In
`State 80, the proceSS obtains the query log data for the most
`recent M days (e.g. one week). Limiting the query log data
`in this manner has the desirable effect of producing a dataset
`that Strongly reflects the current item interests of users. In
`State 82, the process filters out all query Submissions that
`produced a null query result or required use of a query spell
`checker. Other types of searches that may be filtered out
`include Searches that produced very large numbers of hits,
`and searches for which the user did not view any of the
`Search results. To preserve Search context information, each
`remaining query may be appended with a code that identifies
`the context of the Search.
`In State 84, the process optionally partitions the remaining
`query log data according to predefined user groups. This
`may be accomplished, for example, using information Stored
`40
`in the customer database 78 (FIG. 4) to identify the com
`munity or communities to which each user belongs.
`Alternatively, each user's community membership may be
`recorded within a cookie on the user's device 40, and
`inserted into the query log 76 when a Search is performed.
`The partitions may, for example, be based on the domiciles
`of the users, as reflected in user Shipping addresses. With this
`approach, a user living in Southern California that types in
`HOLLYWOOD may see autocompletion phrases related to
`Hollywood California, while a user living in South Florida
`who enters the same characters may See autocompletion
`phrases related to Hollywo