(12) United States Patent
`US 6,366,910 B1
`(10) Patent No.:
`Apr. 2, 2002
`(45) Date of Patent:
`Rajaramanet al.
`
`US006366910B1
`
`(54)
`
`(75)
`
`METHOD AND SYSTEM FOR GENERATION
`OF HIERARCHICAL SEARCH RESULTS
`
`6,029,195 A *
`6,038,560 A *
`6,195,652 Bl
`*
`
`22000 Herz woecccesscccsseseeeeeeee 709/219
`
`wee 707/5
`3/2000 Wical...
`2/2001 Fish wo... ceeeceeeeneee FOF/2
`
`Inventors: Anand Rajaraman, Seattle; Nigel
`Green, Bellevue, both of WA (US)
`
`* cited by examiner
`
`(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)
`
`(22)
`
`(51)
`(52)
`(58)
`
`(56)
`
`Appl. No.: 09/206,774
`
`Filed:
`
`Dec. 7, 1998
`
`Wnt Oe scicccumnemmanncens GORI
`
`Field of Search .........:cccccceseeseeeeerenseee 7O7/5
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,062,074 A * 10/1991 Kleinberger .............. 7O7/5
`5,251,131 A * 10/1993 Massand et al.
`............... 7O4/9
`..
`. FO7/5
`5,442,778 A *
`8/1995 Pedersen et al.
`
`we TOFS
`5,488,725 A *
`1/1996 Turtle etal.
`...
`
`. 128/732
`5,722,418 A *
`3/1998 Bro oo.
`
`7/1998 Tukeyetal. 00. ccce. FOT/S
`5,787,422 A *
`5,802,493 A *
`9/1998 Sherflott etal. wo... FOS/L
`5,835,905 A * 11/1998 Pirolli et al.
`...
`ws 707/3
`5,848,409 A * 12/1998 Ahn occ
`vee 07/3
`5,897,638 A *
`4/1999 Lasser et al.
`..
`707/102
`5,920,854 A *
`7/1999 Kirsch et al.
`..
`we TOTS
`5,987,460 A * 11/1999 Niwa et al.
`....
`ws FOT/6
`6,011,862 A *
`1/2000 Doiet al. ........02. 382/132
`
`
`
`Primary Examiner—Wayne Amsbury
`(74) Attorney, Agent, or Firm—Perkins Coie LLP
`
`(57)
`
`ABSTRACT
`
`A method and system for querying hierarchically classified
`data. The system first receives a query request and then
`identifies classifications of the data that may satisfy the
`received query request. The system then displays the iden-
`tified classifications. In response to selection of a displayed
`classification, the system displays sub-classifications when
`the selected classification has sub-classifications and dis-
`plays the data within the classification when the selected
`classification has no sub-classifications. In another aspect,
`the system generates search results for items that are hier-
`archically classified. For classifications within the hierarchy
`ofclassifications, the system generates a search entry con-
`laining terms describing the items within that classification.
`The system then receives a search criteria. The system
`selects as initial search results those search entries whose
`terms most closely match the received search criteria. The
`system then adjusts the initial search results based on the
`hierarchy of classifications. This adjustment may include
`removing sub-classifications of a classification that is in the
`initial search results or adding a parent classification to
`replace multiple child classifications in the initial search
`results,
`
`59 Claims, 17 Drawing Sheets
`
`202
`
`207
`
`GPS Index Builder
`
`GPS Search Engine
`
`
`
`Priority
`Descriptor
`
`Browse Tree
`Descriptor
`
`
`
`
`
`
`GPS Hierarchical
`Displayer
`
`Display
`
`ELASTIC - EXHIBIT 1005
`ELASTIC - EXHIBIT 1005
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 1 of 17
`
`US 6,366,910 B1
`
`hepsen.
`
`Our new.shoppingskramemakesnl easyto find andcompareproducts from a munterofmeschenta of af onesWeen
`. you've found whet you'rlooking fos, we take you to the marchanits site io suske your purchase We'véonly ask
`begus ta buitd Shopthe Wet. If s producti oniine, we want bo felp you find,We needyour feeds
`Ae swale this
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 2 of 17
`
`US 6,366,910 B1
`
`aur Search ANPraucts Results
`forkeyword{ey dinrts> 117
`
`The following:departments, categotinsacdsubcategories
`coutsmed matches foryour keyword(s) ‘shirts’. Chek onany
`luck below tu getsket ofpedsiucts that match yourkeyword
`
`i
`Women'stressshirtsandblouses
`
`BhECs.
`
`omen's Fulo
`nsoehing
`MartsTans
`
`bepleysfirbs
`
`and
`
`am
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 3 of 17
`
`US 6,366,910 BL
`
`LOTTOC
`
`90¢
`
`i.
`
`SdD
`
`
`
`
`
`ourduqyo1eegSdDXxopu]JOplingXepulSdO
`
`10c
`
`yonpoig
`
`ad
`
`
`
`807
`
`yNsayArong)
`
`SOc£0¢
`
`d01]SSMOIGBolyosesa;IaeaAWWIOUg
`
`
`
`JoAedsiq,
`
`
`
`AeydsiqAran?)
`
`C‘SL
`
`voc
`
`[e1sods
`
`SUID],
`
`
`
`
`
`5Jojdiiosoq1ojduss9q
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 4 of 17
`
`US 6,366,910 BL
`
`LOE
`
`uondussaq
`JOPIAOIg
`
`J
`
`—~
`
`HemeHy
`
`[PARI]
`
`yorqing
`
`oinjudA,
`
`youqino
`
`ainjudA,
`
`
`
`
`““4sap8uQ|uonRUnsdqoweno8a}v9qns
`
`
`
`apneegineHeEMe}LEZ ayneageyensny|uelyeqsnyOrZ
`
`aqeog=|pueyeoZMON|purjeazMeN}—OKT
`
`
`VE‘SLT
`
`mo].
`
`uoourkau0}]
`
`mo]
`
`Le
`
`Te
`
`LE
`
`osaje7)dl
`
`3[qe|,[PARI],
`
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 5 of 17
`
`US 6,366,910 BL
`
`
`
`TE“B1]
`
`uTYys-LTeo
`
`ouIsLIOgy
`yorqingO
`
`
`
`SIHPONUO24TH68072L8Z
`
`uonaLosoqd
`
`310}§
`
`QUIBN
`
`puelg
`
`A
`
`UIsIIOGY
`
`O[Od
`
`TRIN
`
`
`
`yorqino9€07
`
`ada],Wid}]
`
`osayeoqns
`=
`
`os9}e7)qd]
`a[qe|,joreddy
`
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 6 of 17
`
`US 6,366,910 BL
`
`SOLIOSSAD0W%Surpoly9
`
`joueddy
`
`SE
`
`S,URUIOA,
`
`joreddy
`
`be
`
`Sua
`
`joreddy
`
`8LZ
`
`JONG,
`
`TEOM
`
`p‘Sl]
`
`PEO
`
`sdoy,
`
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 7 of 17
`
`US 6,366,910 B1
`
`Browse Tree
`
`e|Name DisplayName URLAlias ConfigFile Image TitleImage TableNa
`
`
`
`
`
`
`
`
`
`
`
`
`meStem
`
`FeeneeeeNael a
`Electronics /electronics/electro|/electronics/brow|/img/electron|/img/head_electr|ELECT
`
`
`
`nics.html se_elec.propertie|ics_icon.gif|onics.gif RONICS
`5
`
`L_|Eee
`Computer /computersicompu|/computers/brow|/img/comput|/img/head_comp|COMPUComputer
`
`
`
`
`
`
`Hardware se_computers.pro|er_icon.gifHardware ters.html uter.gif TERS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ye|pf} De
`
`
`Gahala /img/headtravel.|TRAVE
` ‘travel/browsetr|/img/travel_i
`
`avel.properties
`con. gif
`if
`LS
`
`
`
`
`
`eae[et ‘travel/browse_tra|/travel/browse_tr|/img/travel i|/img/hcad_travel
`
`
`Travel
`Travel
`vel.html
`.
`i
`con, gif
`packaged. pif
`
`
`
`
`
`
`
`pack beach.gif
`con. gif
`eL.html
`resorts
`resorts
`
`
`Cruises ‘travel/resultstrav|/travel/resultstra|/img/travel_iCruises
`el.html
`vel.properties
`con. gif
`pack cruise. gif
`31 ‘travel/results_trav|/travel/results_tra|/img/travel_i|/img/head_travelBoating Boating and
`
`
`and
`watersports
`el.himl
`vel.properties
`con. gif
`_pack_boating.gi
`watersports
`f
`
`Cycling Aravel/results_trav|Aravel/results_tra|/img/travel_i|/img/head travelCycling
`el.html
`vel.properties
`con. gif
`_pack_cycling.gi
`f
`
`
`Hiking, Aravel/resultstrav|Aravel/resultstra|/img/travel_i|/img/head_travelHiking,
`
`
`climbing
`climbing and
`el.html
`vel. properties
`con.gif
`_pack_hiking.gif
`
`and
`trekking
`trekking
`CO"_]CO_.
`Toys and ‘toys/browse_toy|/img/toys_ic|/img/headtoysg|TOYSToys and ‘oys/toys.html
`
`
`
`Games
`Games
`§.properties
`on. gif
`ames.gif
`
`Clothing /apparel/apparel.ht|/apparel/browse_|/img/apparel|/img/head_clothi|APPARClothing and
`
`
`
`
`
`
`and apparel.propertic|_icon.gifAccessories ml ng.gif EL
`
`Accessories
`$
`
`Men's Men's Apparel|/apparel/browse_a|/apparel/browse_|/img/apparel|/img/head_clothi
`
`
`
`Apparel apparel_men.pro|icon.gifpparel_men.html ng_men.gif
`perties
`272 /apparel/browse_a|/apparel/browse_|/img/apparel|/img/head_clothi34 Men's Shirts
`
`
`
`
`pparel_men_shirts.|apparel_men_shi|_icon.gif ng_men_shirts.gi
`html
`rts.properties
`f
`272 /apparel/results_ap|/apparel/results_a|/img/apparel|/img/head_clothiTops Men's Tops
`
`
`
`
`
`parel. html pparel.properties|icon.gif ng_men_shirtto
`ps. pif
`272 Men's T-shirts|/apparel/results_ap|/apparel/results_a|/img/apparel|/img/head_clothiTees
`
`
`
`
`parel. html pparel.properties|icon.gif ng_men_shirt_te
`es. gif
`
`
`
`Fig. 5A
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 8 of 17
`
`US 6,366,910 B1
`
`
`
`2036|272|Polo and Men's Polo|/apparel/result|/apparel/results|/img/appare|/img/head_clo
`
`henley shirts|andhenley|s_apparel.htm|_apparel.proper||_icon.gif thing_men_sh
`shirts
`l
`ties
`irt_ polo.gif
`
`
`
`shirts s_apparel.htm|_apparel.proper||icon.gif thing_men_sh
`
`1
`ties
`irt_shirt.gif
`i
`:
`34
`/img/appare
`se_apparel_m|e_
`
`
`
`
`
`
`
` /apparel/brow
`|men||icon.gif
`
`
`ties/apparel/results|/img/appare|/img/head_clo 7
`_apparel.proper|1_icon.gif thing_men_pa
`
`
`
`
` 1
`nt_khakis. gif
`
`
`
`
`
`
`273 /apparel/result|/apparel/results /img/head_clo
`
`s_apparel.htm|_apparel.proper thing_men_pa
`
`
`
`
`ties
`nt_jeans.gif
`
`
`273
`
`
`5 /apparel/results|/img/appare|/img/head_clo
`
`
`
`a _apparel.proper||_icon.gif; thing_menpa
`
`
`
`Sesereshorts.g
`EE
`:
`|
`:
`2
`aee
`pee|Eee| Ses[Or[Sc
`
`fect ae seSaperslw|e_apparel_wo icon.gif wewomen.
`
`
`
`
`peepeeyea /apparel/result|/apparel/results|/img/appare|/img/head_clo
`
`
`shirts s_apparel.htm|_apparel.proper||_icon.gif thing_women
`
`1
`ties
`shirt_tees.gif
`
`
`
`
`2059|279|Polo and /apparel/result|/apparel/results|/img/appare|/img/head_cloWomen's
`
`
`
`henley shirts|Polo and s_apparel.htm|_apparel.proper|l_icon.gif thing_women
`henley
`I
`ties
`_shirt_polo.gi
`
`shirts
`f
`
`
`
`
`2060 /img/appare|/img/head_cloDress shirts Women's /apparel/result
`
`
`
`
`
`and blouses|Dress shirts|s_apparel.htm|_; j Licon.gif thing_women
`
`
`
`
`
`and blouses|| i sit_blouse:
`
`
`
`
`
`
`EeKeenbrow SomaI/brows Hemmesaeaclo
`se_apparel_sh|e_apparel_shoe||icon.nat inshoes.gi
`
`s.properties
`oes.html
`36
`Men's
`Men's
`/img/appare a
`287
`
`
`
` L_icon. gif
`thing_shoe_m
`ens.gif
`
`
`35
`
`Shirts
`
`Women's
`
`omen.html
`
`men.properties
`
`z
`
`2057|279|Tops /apparel/result|/apparel/results|/img/appare|/img/head_cloWomen's
`
`
`
`
`Tops s_apparel.htm|_apparel.proper|1icon.gif thingwomen
`|
`ties
`shirt_tops.gif
`
`
`
`Shoes
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 9 of 17
`
`US 6,366,910 B1
`
`
`
`2085|287|Shoes /apparel/result|/apparel/results|/img/appare|/img/head_cloMen's
`
`
`
`
`Shoes s_apparel.htm|_apparel.proper||_icon.gif thing_shoe_m
`l
`ties
`shoes. gif
`
`
`2086|287|Boots /apparel/result|/apparel/results|/img/appare|/img/head_cloMen's
`
`
`Boots s_apparel.htm|_apparel.proper||_icon.gif thing_shoe_m
`1
`ties
`en_boots.gif
`
`
`2087|287|Athletic /apparel/result|/apparel/results|/img/appare|/img/head_cloMen's
`
`
`Athletic s_apparel.htn|_apparel.proper|1icon.gif thingshoe_m
`1
`ties
`en_athletic.gif
`
`
`2088|287|Sandals /apparel/result|/apparel/results|/Aimg/appare|/Aimg/head_cloMen's
`
`
`Sandals s_apparel.htm|_apparel.proper|1_icon.gif thing_shoe_m
`l
`ties
`en_sandals. gif
`
`
`2089|287|Hiking and /appareV/result|/apparel/results|Amg/appare|/img/head_cloMen's
`
`
`outdoor Hiking and|s_apparel.htm|_apparel.proper||_icon.gif thing_shoe_m
`outdoor
`l
`ties
`en_hiking.gif
`
`288 /apparel/brow|/apparel/brows|/img/appare|/img/head_clo36 Women's Women's
`
`
`
`
`
`Shoes se_apparelsh|eapparelshoe||icon.gif thingshoe_w
`oe_women.ht|_women.proper
`ml
`ties
`
`
`
`288|Shoes Women's fapparel/result i i &
`
`
`Shoes s_apparel.htm|_apparel.proper
`
`1
`ties
`
`
`
`Fig. 5C
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 10 of 17
`
`US 6,366,910 B1
`
`_ Harty Descriptor
`
`
`
`_ brand|name(|store|platform|cpu_type||description|category|brand|name|
`
`2|Serenetype|brand|namelstore description|category|subcategory|
`
`item_typelbrand|name|store
`
`
`
`
`
`
`7eaetee———eeeae
`aSSSaitem_type|brand|namelstore
`
`
`
`pu manufacturer|cp
`
`eed
`
`origdest3|provider
`
`item type|brand|name|store
`
`Fig. 6
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 11 of 17
`
`US 6,366,910 B1
`
`Special Terms
`
`
`[Id|DisplayName|GoodTerms|BadTerms|
`aesSe
`
`
`
`
`
`
`
`aP
`
`S
`
`[3___|ComputerHardwareSidi
`
`
`[28|Desktopcomputers——S—~dSSS
`
`
`
`29|Laptop__——SS—S~dcomputersSCid
`es a[iain
`[4|TravelOTtvvideo
`[31___|PackagedTravel|
`|237|Beachandresorts|
`[238|Cmises
`
` |239|Boatingandwatersports||
`
`[240|Cycling
`Hikingclimbing and trekking a
`
`2es) S
`
`Toys and Games
`
`Apparel
`Men's Apparel
`Men's Shirts
`Men's Tops
`
`Men's T-shirts
`Men's Polo and henley shirts
`Men's Dressshirts
`
`Men's Pants and shorts
`Men's Pants and khakis
`Men's Jeans and denim
`Men's Shorts
`
`Women's Apparel
`Women's Shirts
`Women's Tops
`Women's T-shirts
`shirts
`Women's Polo and henley
`Women's Dressshirts and blouses
`
`34
`272
`2034
`2035
`2036
`2037
`273
`
`2039
`2040
`
`35
`279
`2057
`2058
`2059
`
`
`
`adul
`[Shoes
`|287__|Men'sShoes_TT
`|2085__|Men'sShoes|
`|2086__|Men'sBoots|
`|2087_|Men'sAthletic||
`
`
`
`
`
`
`
`Fig. 7
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 12 of 17
`
`US 6,366,910 B1
`
`
`
`L08
`
`SULIO|,
`
`asnoq
`
`
`
`
`
`SUIYSsuopy/jareddysus]
`
`
`
`
`
`O]0dSuISLIOGY/1eaM\YORGINC
`
`
`
`
`
`“*UBULDATORJO}WIYSO[Og
`
`OSpIAAJ
`
`8‘SL
`
`9[qeLUS|,
`Oud
`UOHROTFISSET)
`
`—_—
`
`0
`
`c
`
`6LC
`
`CLT
`
`9£0C
`
`907
`
` 4:
`
`om)
`
`os
`
`aa[™
`
`
`
`dl
`
`z08xopul
`
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 13 of 17
`
`US 6,366,910 B1
`
`GPS Index
`Builder
`
`Addentries to
`classifications
`
`901
`
`902
`
`Add entries for good
`terms
`
`903
`
`Addentries for bad
`terms
`
`904
`Select next dept table
`
`
`
`all dept
`tables already
`
`
`selected?
`
`
`
`Adddept table to
`term table
`
`Fig. 9
`
`Create term index table
`
`907
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 14 of 17
`
`US 6,366,910 B1
`
`Add Depttable
`to Term Table
`
`
`
`
` Select next item in dept
`
`(dept table)
`
`table 4
`
`all items
`already
`
`
`
`
`selected?
`
`
`
`
`
`
`
`
`
`
`1003
`Collect priority 2 terms
`
`1004
`
`Update priority 2 entry
`
`1005
`Collect priority 3 terms
`
`1006
`Update priority 3 entry
`
`Fig. 10
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 15 of 17
`
`US 6,366,910 B1
`
`
`
`GPS Search
`Engine
`
`
`
`(query, result)
`
`1101
`
`Submit query (result)
`
`
`
`
`
`
`
`
`Prioritize scores
`
`Select next dept
`starting from first
`
`
`
`all dept
`already
`
`
`selected?
`
`1105
`
`Traverse
`(root, false)
`
`Fig. 11
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 16 of 17
`
`US 6,366,910 B1
`
`Traverse
`
`(classification,
`
` Ancestor in
`
`result?
`
`Removefrom result
`
`1202
`
`Classification in
`
`result? Set ancestor in result
`
`
`ancestorin result)
`
`
`
`
`classification
`already
`
`selected?
`
`
` sufficient
`
`
`
`Traverse (selected
`classification
`children in
`
`
`ancestorin result)
`result?
`
`
`
`
`
`
`remove child
`
`classifications from
`result
`
`
`add password
`classification to result
`
`Fig. 12
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 17 of 17
`
`US 6,366,910 B1
`
`
`GPS
`Hierarchical
`
`
`
`
`Displayer
`
`1301
`
`Input Query
`
`
`already
`
`
`selected? 130
`
`
`
`Display dept name
`
`13
`Select next entry for
`selected dept with
`highest score
`
`already
`
` all entries
`
`selected?
`
`

`

`US 6,366,910 B1
`
`1
`METHOD AND SYSTEM FOR GENERATION
`OF HIERARCHICAL SEARCH RESULTS
`
`TECHNICAL FIELD
`
`The present invention relates to generating search results
`and, more particularly,
`to generating search results for
`hierarchically organized data.
`
`BACKGROUND OF THE INVENTION
`
`Many search tools are available to provide searching
`capability for a collection of data. For example, search tools
`are available to search for documents that may contain
`information related to a particular search criteria, Such
`search tools typically create an index of the words within
`each document. When the search criteria is received, the
`search tools scan the index to determine which documents
`contain the words of the search criteria. The search tools
`may also rank these documents based on various factors
`including the frequency of the words ofthe search criteria
`within the document or the presence of a word of the search
`criteria within the title of the document.
`
`In the emerging field of electronic commerce, many
`thousands of products are available to be purchased elec-
`tronically. For example, an online retailer may offer for sale
`electronic devices, major appliances, clothing, and so on.
`The difficulty a potential purchaser faces is identifying a
`particular product that satisfies the purchaser's needs. Some
`online retailers provide a search tool that receives a search
`criteria from a potential purchaser and searches a database ,
`containing information for each of the available products to
`identify those products that most closely match the search
`criteria. For example, a potential purchaser whois interested
`in purchasing a television may enter the search criteria of
`“tv.” The search tool may identify every TV, but mayalso,
`identify items such as video game players and VCRsthat
`happen to use the term “tv” in their description fields in the
`database. Thus, many products that are of no interest to the
`potential purchaser are identified. Many potential
`purchasers, when faced with such a list that includes many
`products that are of no interest will simply shop elsewhere
`rather than wade throughthe list. Other online retailers may
`hierarchically organize the products so that a potential
`purchaser can browse through the hierarchy to identify the
`classification that contains products that are most likely of
`interest. For example, the potential purchaser may select an
`electronics device classification, a home electronics sub-
`classification, and a television sub-sub-classification. The
`hierarchical classification of products has several problems.
`First, many users of computer system do not fully under-
`stand the concept of hierarchical classifications. Thus, it is
`difficult for such users to use such a classification-based
`system. Second, products may notfall conveniently into any
`one classification. For example, a combination VCR and
`television couldbe classified as a VCR or a television. It is .
`unlikely that an online retailer would have a separate clas-
`sification for such a combination. Therefore, a potential
`purchaser may not even be able to locate the products of
`interest using a hierarchical classification system.
`It would be desirable to have a product search technique
`that would combinedthe advantages of the search systems
`and theclassification-based systems and thal minimizes their
`disadvantages.
`SUMMARY OF THE INVENTION
`
`45
`
`;
`
`Embodiments of the present invention provide a method
`and system for querying hierarchically classified data. The
`
`65
`
`2
`system ofthe present inventionfirst receives a query request.
`The system then identifies classifications of the data that
`may satisfy the received query request. The system then
`displays the identified classifications. In response to selec-
`tion of a displayed classification, the system displays sub-
`classifications when the selected classification has sub-
`classifications and displays the data within the classification
`when the selected classification has no sub-classifications,
`
`In another aspect, the present invention provides a system
`that generates search results for items that are hierarchically
`classified. For classifications within the hierarchy of
`classifications, the system generates a search entry contain-
`ing terms describing the items within that classification. The
`system then receives a search criteria. The system selects as
`initial search results those classifications whose search entry
`has terms that most closely match the received search
`criteria. The system then adjusts the initial search results
`based on the hierarchy ofclassifications. This adjustment
`may include removing sub-classifications of a classification
`that
`is in the initial search results or adding a parent
`classification to replace multiple child classifications in the
`initial search results.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIGS, 1A and 1B illustrate an example user interface for
`one embodiment ofthe present invention.
`FIG, 2 is a block diagram illustrating components of one
`embodiment of the GPS system.
`FIGS. 3A and 3B illustrate example contents of a travel
`table and of an apparel table.
`FIG, 4 illustrates a hierarchical organization of the items
`in the apparel table of the product database.
`FIGS. 5A, 5B, and 5C illustrate an example organization
`of the browse tree descriptor file.
`FIG, 6 illustrates the contents of a sample priority descrip-
`tor file. The priority descriptor file contains an entry for each
`department represented in the product database.
`FIG. 7 illustrates example contents of the special terms
`file.
`FIG. 8 illustrates the contents of the GPS index.
`
`FIG. 9 is a flow diagram illustrating an example embodi-
`ment of the GPS index builder.
`
`FIG. 10 is a flow diagram of an example routine to add a
`department table to the term table.
`FIG. 11 is a flow diagram of an example implementation
`of the GPS search engine.
`FIG, 12 is a flow diagram of an example implementation
`of the traverse routine.
`
`FIG, 13 into flow diagram of an example implementation
`of a GPS hierarchical displayer routine.
`DETAILED DESCRIPTION OFTHE
`INVENTION
`
`Embodiments of the present invention provide a method
`and system for general purpose searching (“GPS”). The GPS
`system allows a user to search for items that best match a
`search criteria. To facilitate the searching, the GPS system
`groupsthe itemsinto a classification hierarchy. For example,
`if the items are articles of clothing, then classifications may
`be “shirts,” “pants,” and “shoes,” and sub-classification of
`“shirts” may be “T-shirts,” “casual shirts,” and “dress
`shirts.” The GPS system inputs a search criteria from a user,
`searches for the classifications of items that best match the
`search criteria, and displays those classifications in an order
`
`

`

`US 6,366,910 B1
`
`3
`based on how well they match the search criteria. In one
`embodiment, the GPS system displays only the best match-
`ing classifications of items, rather than displaying informa-
`tion about any individual items. The user can then select a
`displayed classification to view the sub-classifications
`within that classification or, if that classification has no
`sub-classification, the items within that classification.
`When the GPS system inputs a search criteria, it scores
`each classification in the classification hierarchy to indicate
`the degree to which the classification contains items that
`match the search criteria. For example,
`the GPS system
`would generate a score for each ofthe “shirts,” “pants,” and
`“shoes” classifications and for each of the “T-shirts,” “casual
`shirts,” and “dress shirts” sub-classifications. The GPS sys-
`tem then selects those classifications or sub-classifications
`with the highest scores and displays them in order based on
`their score. Because users often find it difficult to interface
`with hierarchically presented information, the GPS system
`in one embodiment displays the names of the selected
`classifications with no indication of where the classifications
`are within the hierarchy. For example, if the classifications
`of “dress shirts” and “shoes” have the highest scores, then
`the GPS system may simply list the classification names as
`follows:
`dress shirts
`shoes
`
`15
`
`20
`
`25
`
`4
`the clothing and
`referred to as item type. For example,
`accessories department has four item categories: men’s
`apparel, women’s apparel, shoes, and accessories. The user
`enters the searchcriteria or query into search query box 106.
`In this example, the user has entered the word “shirts” as the
`search criteria. Display 110 of FIG. 1B illustrates the display
`of the search results. Rather than displaying the particular
`items that best match the search criteria, the GPS system
`displays the classifications of items that best match the
`search criteria. The GPS system orders the classifications
`based on the likelihood that they contain itemsof interest. In
`this example, the GPS system determines that the clothing
`and accessories department contains items that best match
`the search criteria. As a result, the GPS system displays an
`indication of the clothing and accessories departmentfirst.
`The GPS system also displays the various categories and
`sub-categories of the clothing and accessories department
`that best match the search criteria. The GPS system displays
`these categories and sub-categories in order based on the
`likelihood that the categories contain itemsthat satisfies the
`search criteria. In this example, the GPS system haslisted 10
`classifications of the clothing and accessories department.
`The GPS system highlights the first eight classifications
`because the word “shirts” was found in the sub-category
`name. For example, the category “Polo and henley shirts”
`contain the word “shirts” in its name. However, the last two
`classifications do not contain the word “shirts” in their
`sub-category names. Rather,
`the word “shirts” may have
`been contained in a description field for an item within those
`classifications. For example, the sub-category “Men’s Ties”
`may have had an item that contained the word “shirts” in its
`description field. The placing of the word“shirts” in paren-
`thesis indicates that the word was not found in the name of
`the sub-category.
`In general,
`the GPS system highlights
`(e.g., bolds) the names of those classifications in which
`every item should satisfy the search criteria. For example,
`the first eight displayed classifications of the clothing and
`accessories department are highlighted. The GPS system
`determinedthat the department “travel” is the second most
`relevant department for the search criteria. The GPS system
`displays the information for the travel departmentafter the
`information for the clothing and accessories department
`because the score for the classifications within the travel
`
`If the user then selects “shoes,” the GPS system displays the
`sub-classifications of “shoes.” If the user, however, selects
`“dress shirts,” then the GPS system may display a descrip-
`tion of each dress shirt.
`Since the GPS system scores eachclassification within the
`hierarchy, various parent and child classifications and more
`generally various ancestor and descendent classifications
`may have high scores. For example, both the “shirts”
`classification and the “dress shirts” sub-classification may
`have high scores. In one embodiment, the GPS system does
`not display any descendent classifications of a displayed
`classification. For example, if the GPS system selects to
`display the classification “shirts,” then it does not displayits
`sub-classification of “dress shirts,” regardless ofthe score of
`the sub-classification. The user can always select the dis-
`played ancestor classification to view the descendent clas-
`department were lower than the score for the classifications
`sifications. In some situations, a parent classification may
`have a relatively low score, but many ofits child classifi-
`in the clothing and accessories department.
`45
`
`cations may have a high score. In suchasituation, the GPS Once the GPS system displays the search results, as
`system may display the parent classification rather than
`shown in FIG. 1B, a user may select one ofthe classifica-
`tions to view detailed information about the classification.
`displaying each child classification. For example, if the
`“shirts” classification has a relatively low score, but
`the
`For example, if the user is interested in purchasing a T-shirt
`“T-shirts” and “dress shirts” sub-classifications have high
`for a man, then the user may select the category “Men’s
`scores,
`the GPS system may decide to display only the
`T-shirts.” Upon selecting this classification, the GPS system
`“shirts” classification, The GPS system may set the score of
`displays information describing the items within that clas-
`sification.
`If
`the selected classification has sub-
`the “shirts” classification to that of its highest sub-
`classification so that
`the displayed classification will be
`classifications,
`then the GPS system instead displays the
`ordered based on the score of its sub-classifications.
`sub-classifications.
`FIGS. 1A and 1B illustrate an example user interface for
`FIG, 2 is a block diagram illustrating components of one
`one embodiment of the present
`invention,
`In this
`embodiment of the GPS system. The GPS search system
`embodiment,
`the GPS system provides capabilities for
`comprises a product (or item) database 201, a GPS index
`searching for items that may be purchased. The techniques
`builder 202, a priority descriptor file 203, the special terms
`of the present invention are particularly well suited for use
`file 204, a browse tree descriptorfile 205, a GPS indexfile
`in a Web-based shopping environment. The display 100 of
`206, a GPS search engine 207, and a GPS hierarchical
`FIG. 1A illustrates a Web page for searching for items that
`displayer 208. These components can be implemented as
`may be purchased via an online store, This Web page
`part of a general purpose computer system. The GPS system
`illustrates that
`the available item are grouped into five
`may be implemented as a server in a client/server environ-
`departments: clothing and accessories LOI, electronics 102,
`ment such as the World Wide Web or may be implemented
`computer hardware 103, toys and games 104,and travel 105.
`on a computer, such as a mainframe.
`The GPS index builder creates the GPS index, which
`The item in each of these departments are classified into
`categories, sub-categories, and possibly a sub-sub-category
`contains an entry for cach classification, based on the names
`
`30
`
`35
`
`40
`
`$0
`
`55
`
`60
`
`65
`
`

`

`US 6,366,910 B1
`
`§
`of the classifications and the content ofthe fields in the
`product database. The product database contains an entry for
`eachitem. The entries of the GPS index contain a collection
`of the words that appear in the entries of the product
`database for the items within that classification or the words
`in the names of the classification. After the GPS index is
`created, the GPS search engine receives a query andreturns
`those entries whose collection of words most closely match
`the query. In one embodiment, the GPS index may contain
`multiple entries for some classifications that indicate differ-
`ent priorities assigned (or weights) based on the fields of the
`product database in which the terms appear. For example,
`each classification may contain one entry that contains the
`words from the name ofthe classification and from the name
`of its parent classification. The leaf (i.c.,
`lowest-level)
`classifications, however, may also contain additional entries
`in the GPS index. One additional entry may contain all the
`words fromall the description fields of all the items within
`the classification. Such entries are said to have a lower
`
`priority than entries that contain only the words in the name
`of the classifications because words in the name of a
`classification are assumed to be more descriptive of the
`entire classification than a word in a description field of
`some item within that classification. Each entry also con-
`tains an indication ofits priority.
`The GPS search engine may use a conventional database
`search engine to locate the entries of the GPS index that
`contain words that best match the search criteria. The
`conventional search engines return as the results of the
`search the entries that best match along with a score that
`indicates how well each matches. The GPS search engine
`then adjusts the scoresof the entries in the result to factor in
`their priorities. For example, the GPS system may not adjust
`the score of an entry that has a high priority, but may reduce
`the score of an entry that has low priority. Once the scores
`are adjusted, the GPS search engine may removeall but the
`entry with the highest score for each classification from the
`result. The GPS search engine then removesall entries for
`sub-classifications when an entry for an ancestor classifica-
`tion in the result. That is, the GPS search engine ensures that
`if an entry for the root of a classification sub-tree is in the
`result, then the result contains no entry for any descendent
`classifications. The GPS search engine sets the score of the
`root classification of a sub-tree to the highest score of the
`entries for that sub-tree, The result may also contain an entry
`for each child classification but not an entry for the parent
`classification. In such a situation, the GPS search engine
`may removeeach of the entries for the child classifications
`and adds a new entry for the parent classification. The GPS
`search engine may set the score of the new entry to the
`highest score of the child classifications.
`The GPShierarchical displayer receives the results of the
`GPS search engine andfirst determines which highest level
`classification (¢.g., department) has the highest score. The
`GPShierarchical displayer selects those classifications with
`that highest level classification with the highest score and
`displays the name ofthe highest-level classification along
`with the names of the selected classification. The GPS
`hierarchical displayer can select a predefined number of
`such classifications or select a variable number depending
`on the differences in the scores ofthe classifications. The
`GPS hierarchical displayer then repeats this process for the
`highest level classification with the next highest score and so
`on.
`
`the product database contains a
`In one embodiment,
`department table for each department in the online store. The
`department may be considered to be the highest classifica-
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`$0
`
`55
`
`60
`
`65
`
`6
`tion. Each department table contains one entry for each item
`that is available to be purchased through the department.
`FIGS. 3A and 3Billustrate example contents of a travel table
`and of an apparel table. The tables includefield that specify
`the classification of each item within the classification
`hierarchy. For example,
`the travel
`table 301 contains a
`category and a sub-category field. The first entry in the travel
`table in