`
`
`
`910B1O49
`
`US00636
`
`United States Patent
`(12)
`(10) Patent No,:
`US 6,366,910 Bl
`Rajaraman et al.
`(45) Date of Patent:
`Apr. 2, 2002
`
`
`(54) METHOD AND SYSTEM FOR GENERATION
`OF HIERARCHICAL SEARCH RESULTS
`
`(75)
`
`Inventors: Anand Rajaraman, Seattle; Nigel
`Green, Bellevue, both of WA (US)
`
`6.029.195 A ™
`6,038,560 A *
`6,195,652 ‘Bl
`*
`sited Bu
`ecariaan
`Ged
`DY} BXAYDIEE,
`
`a
`
`
`sence TOVZLD
`2/2000 Herz ...,
`+ 7075
`3/2000 Wical
`
`-2f2001 ASH cccccsesnsereessecaseesersasee FOT/2
`
`(73) Assignee: Amazon.com, Inc., Seattle, WA (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the termofthis
`patent is extended or adjusted under 35
`U.S.C, 154(b) by 0 days.
`
`;
`Primary Examiner—Wayne Amsbury
`(74) Atiarney, Agent, or Firm—Perkins Coie LLP
`5
`sT
`“T
`6”)
`ERE
`A method and system for querying hierarchically classified
`data. The system first receives a query request and then
`(21) Appl. No.: 09/206,774
`identifies classifications of the data that may satisfy the
`£
`received query request. The system then displays the iden-
`(22) Viled:
`Dee. 7, 1998
`tified classifications. In response to selection of a displayed
`(SL) Un, C12 covccccecnesssseeccneseecee GO6F 17/30
`classification, the system displays sub-classifications when
`
`vee 707/5
`(S2Y TBO,
`asicorssssicvers
`the selected classification has sub-classifications and dis-
`
`(58) Field of Search........
`“cccttecnnneee WTS
`plays the data within the classification when the selected
`classification has no sub-classifications. In another aspect,
`(56)
`Referendes Cited
`the system generates search results for items that are hier-
`archically classified. For classifications within the hierarchy
`U.S. PATENT DOCUMENTS
`of classifications, the system generates a search entry con-
`5,062,074 A * 10/1991 Kleinberger cevseesccsseer TOTS ee ea ee ihe AE ape rE ee
`5.251.131 A * 10/1993 Massand et al.
`” a04/9
`@ system then receives a search
`criteria.
`The system
`5.442.778 A *
`8/1995 Pedersen elal.
`W075
`sclects as initial search results those search entries whose
`5.488.725 A *
`1/1996 Turtle etal.
`07/5
`terms most closely match the received search criteria, The
`5,722,418 A 3/1998 Bro...
`128/732
`system then adjusts the initial search resulis based on the
`5,787,422 A *
`7/1998 Tukey et al.
`-» TO7/S
`hierarchy of classifications. "This adjustment may include
`5.802403 A“ 9/1998" Sherflott et al.
`» T0S/L
`removing sub-classifications of a classification that is in the
`DgteSAUS A. ALi vee KirgHy eal.
`TONS
`initial search resulis or adding a parent classification to
`S848A09 A
`12/1998 ARM serssvseen
`ve 07/3
`replace multiple child classifications in the initial search
`5,897,638 A *
`4/1990 Lasser el al.
`7O7/LO2
`rasitltis
`5,920,854 A * F900 Kirsch et ale jcjccueuee TOTS
`1
`
`egies MOPS
`5,987460 A * 111999 Niwa eb al.
`.
`
`6011862 A *
`1/2000 Doietal ...
`. 382/132
`
`59 Claims, 17 Drawing Sheets
`
`202
`
`GPS Index Builder
`
`GPS Search Engine
`
`
`207
`
`Result
`
`208
`
`
`
`
`
`
`
`
`
`Priority
`Descriptor
`
`Browse Tree
`Descriptor
`
`
`GPS Hierarchical
`
`Displayer
`
`Display
`
`PETITIONERS - EXHIBIT 1005
`PETITIONERS- EXHIBIT 1005
`
`IPR2022-00217
`
`IPR2022-00217
`
`

`

`U.S, Patent
`
`Apr,2, 2002
`
`Sheet 1 of 17
`
`US 6,366,910 B1
`
`
`
`| Gurney shopping sirnsemikesi oxsyto find ant compara products from snmaier ofmeschants af at uiie. Beet
`gore Mund whet youremolangfor we jakeyou te the merchauit's site tomske pour muchas We
`began to bultd Shop the Wet, Its peoductsy onkine, oe met te Kelp yeuBadd,Os seed groue facts
`hiepgen.
`
` Higthing aad
`
`
`
`
` Found aproduct you
`
`
`(ardon't}? wine
`Mie
`wie get
`é
`
`Ergun
`er
`:
`
`ADEeaanees,
`
`
`
`‘dgnigutesHardware
`
`Hathus baile this a
`sevice. Gata
`Nx
`auggestion? tellust
`
`™
`
`
`
`
`
`au 9082
`
`
`
`

`

`U.S, Patent
`
`Apr,2, 2002
`
`Sheet 2 of 17
`
`US 6,366,910 B1
`
` ote
`
`Search Ail Products
` aur Search ail Pravhacts Resuite
`for keyword(s) sire7 947
`
`
` The Blowin depacramts, categories andsubeatepones
`contaned sratches for your keyword(s} ‘shirts’. Cack ot any
`ink belote get ohetofpeoducts that matchpourkeyword
`
`
`
` Glothing and Accessoriag~—"~ 112
`Ment:Patyoralheresslits
`Men'sDressshcs
`
`
`HEB
`
`Learn more about
`the Morcivant
`RRR.
`
`
`
`
`need
`
`
`
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 3 of 17
`
`US 6,366,910 B1
`
`AvjdsiqKeres
`
`vised
`
`suuay,
`
`C“Shy
`
`807
`
`ynsoy
`
`LOEOE
`
`
`
`
`
`ouIsUTYyaireasSqDJoplingxepulSd
`
`10é
`
`pnpoig
`
`ad
`
`BOYISHSdD
`
`Jodeidsigg
`
`
`
`
`
`dai]asmoigAWIOU
`
`
`
`Jo\dii9saqJodasaq
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 4 of 17
`
`US 6,366,910 Bl
`
`—L?A
`
`=~
`
`LOE
`
`uoydussaq
`IIPiAolg
`
`EME}
`
`[OARLL
`
`yorqing
`
`aunjua,
`
`
`
`
`“"ySsepGLC)WOQBUNSod
`gyveag=|pueyeazMan|puejeazMon
`
`
`apeasBleyqsnyuelyejsny
`
`ayyeasmeyy©afasboes
`
`
`yorqino
`
`ainjua,
`
`mol]
`
`OVE
`
`VE‘S1q
`
`INO],
`
`quo}
`
`osaeoqns
`
`LET
`
`OFC
`
`age|,[AAPL],
`
`Le
`
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 5 of 17
`
`US 6,366,910 B1
`
`
`
`
`
`uondiosaq3101$auIeNypueigadA]wis}]osa}Boqnsosa}e7Z
`<>3IHeBIN|YOMH6807L87Z2a|
`
`
`
`etouIsLIOgYyyoeqino8502
`
`
`IE“81]
`
`10d
`
`uIYs-1.TRIM
`
`o[qe|,joreddy
`
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 6 of 17
`
`US 6,366,910 B1
`
`saliossaqoy7Sunol9
`
`joreddy
`
`S,U2]A]
`
`jaureddy
`
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 7 of 17
`
`US 6,366,910 B1
`
`Browse Tree
`
`/electronics/electro
`‘electronics/brow|/img/electron|/img/head_electr|ELECT
`nics.html
`
`se_elec.propertie|ics_icon.gif onics.gif RONICS
`
`
`oe
`
`hes
`
`TableNa
`meStem
`
`
`
`
`
`
`
`
`
`LAlias erSes
`
`
`e
`/computers/compu
`/computers/brow|/img/comput|/img/head_comp
`ters.html
`
`s¢_computers.pro|er_icon.gif uter.gif TERS
`
`perties
`
`
`‘TRAVE
`Travel
`
`fimg/head travel.
`
`‘travel/browsetr|/im2/travel_i
`
`
`
`avel.propertics
`gif
`gif
`
`
`/img/head_travel
`/travel/browse_tr
`firmg/trave! |
`/travel/browse_tra
`
`&
`packaged. pif
`ftravel/results_tra
`/ime/head_travel
`(travel/results_tray
`resorts
`resorts
`el. html
`vel.properti
`pack beach. gif
`‘travel/results_tra
`/img/head_tavel
`/travel/resulis_trav
`
`peesiPtne|
`pack cruise. gif
`eL html
`vel.properties
`con. gif
`/ravel/results_tra
`fimp/travel i
`Timp/head_wravel
`Boating
`Boating and
`/travel/results_trav
`and
`el.html
`watersports
`vel.properties
`con.gif
`_pack_beating.gi
`watersports
`f
`fimg/head travel
`Cycling
`_pack_cycling. gi
`
`A
`8p
`
`
`
`8
`
`
`
`
`
`
`
`Men's Apparel|/apparel/browse_aPee
`PP= [eehuni
`(ealel
`rete|
`
`31
`
`Hiking.
`climbing
`and
`trekking
`
`Hiking,
`chmbing and
`trekking
`
`/travel/results_trav
`
`/travel/results.tra
`
`vel.properties
`
`bef
`Toys and
`Aoys/toys.html
`ftoys/browse_toy|/img/toysic|/img/headtoysg|TOYS
`Games
`Games
`s.properties
`on.pit
`ames.pif
`
`Po
`
`
`
`Clothing /apparel/browse_|/img/apparel|/img/head_clothi|APPARClothing and /apparel/apparel.nt
`ml
`Accessories
`and
`
`apparelpropertice|icon.gif ng.gif EL
`
`Accessories
`apparel/browse_|/img/apparel|/img/head_clothi
`Men's
`perties
`apparel_men.pro
`_icon. gif
`ng_men.gif
`4
`/apparel/browse_a
`Men's Shirts
`3
`272
`/apparel/brawse|/img/apparel|/img/head_clothi
`
`apparel_men_shi|_icomgif ng_men_shirts.gi
`rs.properties
`f
`‘apparel/results_a|/img/appare]|/img/head_clothi
`parel html
`
`pparel.properties|_icongif ng_men_shirt_to
`ps. pif
`
`Men's T-shirts|/apparel/results_ap
`
`/appareLresultsa|/i ppurel|/img/head_clothi
`parel. html
`
`pparel.properties|icon.gif ng_men_shirt_te
`es.pit
`
`
`8 J
`
`
`
`
`
`Fig.
`
`5A
`
`Packaged
`‘Travel
`
`Packaged
`Travel
`
`Cycling
`
`/travel/resulis_trav
`el].html
`
`
`
`Aravel/results_tra
`vel.properties
`
`fimg/travel_i
`con.pif
`
`
`
`
`

`

`U.S, Patent
`
`Apr.2, 2002
`
`Sheet 8 of 17
`
`US 6,366,910 Bl
`
`Shorts
`
`oooh
`Shirts
`
`nen
`Women's
`Shirts
`
`279
`
`35
`
`OMen.,html
`
`famg/headclo
`ine /mg/appare
`+Sseshorts, gif
`Licon.gif
`tgoe
`Hieabpae
`_icon, gif
`
`seapparelwifeeewo
`
`men proper
`
`
`
`2036|272|Polo and Men's Polo|/apparel/result|/apparel/results|/Aimg/appare|/imeg/head_clo
`
`
`
`henley shirts|andhenley|s_apparel.htm|_apparel.proper|icon.gif thing_men_sh
`shirts
`1
`tes
`irt_polo.pif
`2037|272|Dress shirts|Men's Dress|/apparel/result|/apparel/results|/img/appare|/img/head_clo
`
`
`shirts s_apparel.htm|_apparel.proper|1icon.gif thing_men_sh
`
`
`1
`ties
`int shirt.gi
`
`
`
`s fapparel/brows|/img/appare|/img/head_clo
`
`
`shorts
`
`
`
`e_apparel_men||icon.gif thing_men_pa
`
`
`nt_shorts, gif
`
`
`
`ie, /apparel/result|/apparel/results|/img/appare gesclofees
`
`
`
`
`
`
`ieaaae /apparel/results|/img/appare|/img/head_clo
`
`
`
`_apparel.proper|l_icon.gif thing_men_pa
`
`
`
`
`tes
`nt_khakisgif
`
`
`s_apparelLhtm|_apparel.proper _icon.pif thingmenL_pa
`
`ties
`nt_jeans.gif
`PoPier[tea[Seas[Sere=e
`
`
`
`
`omen_shirts.h seslatspro
`
`
`2057|279|Tops pparel/result Sari /imp/appare|/img/head_cloWomen's
`
`
`Tops capa _apparel.proper|1_icon,gif thingwomen
`1
`ties
`shirt_tops.gif
`gree|e|e |
`
`
`
`oT Poloand fappareV/result|/appareV/results|/Amg/appare:
`henley shirts|Polo and _apparel.proper||_icon.gifa :
`
`ties
`i
`f
`
`
`
`2060 /appareV/result|/apparel/results|/img/appare|/img/head_cloDress shirts Women's
`
`
`
`
`and blouses _apparel.proper||_icon.gifBs ; thing_women
`
`ties
`=pect
`PeLSJoa=—a
`
`seensh|€earpashoe |_icon.gif tgsos
`
`
`
`ae
`
`thingshoe_m
` |_icon.gif
`ens.pif
`
`
`
`
`
`shirts s_apparel.htm|_apparel.proper||_icon.gif thing_women
`
`1
`ties
`shirt tees. gif
`
`
`
`
`
`oes html
`
`$.propel
`
`Shoes
`
`

`

`U.S, Patent
`
`Apr, 2, 2002
`
`Sheet 9 of 17
`
`US 6,366,910 B1
`
`
`
`1
`
`/img/appare
`Licon.gif
`
`g a
`
`/apparel/results
`_apparelproper
`ties
`Men's /apparel/result|/apparel/results|/img/appare|/img/head_clo
`
`
`
`Boots s_appareLhtm|apparel-proper||_icon.gif thingshoe_m
`1
`ties
`en_boots.gif
`/apparel/resuli|/apparel/results|/img/appare|/img/head_clo
`
`sapparel.htm|_apparel.proper||icon.gif thingshoem
`1
`ties
`en_athiletic.gif
`/apparel/result|/apparel/results|/img/appare|/img/head_clo
`
`s_apparel.htm|_apparel.proper|1_icon.gif thing_shoe_m
`1
`ties
`en_sandals.gif
`
`/appareV/result|/apparel/results /img/appare
`s_apparel.htm|_apparelproper
`Licon.gif
`I
`ies
`/apparcl/braws
`€ apparelshoe
`__women.proper
`ties
`
`ties /imp/head_clo
`
`/img/head_clo
`thing_shoe_w
`|icon.gif
`omen_shoes.g
`if
`/imp/appare
`/apparel/result
`s_apparel. hun
`_apparel.proper||_icon.gif thingshoe_w
`
`omen_shoes.g
`if
`
`

`

`U.S, Patent
`
`Apr. 2, 2002
`
`Sheet 10 of 17
`
`US 6,366,910 B1
`
`Priority Descriptor
`
`Priority3
`
`calegory|subcategory|item_type|brand|name|store description|category|subcategory|
`item_type/brand|name|store
`
`3|category brand|name(store|platform|cpu_type||deseription|category|brand|name|
`cpu_manufacturer|cpu_speed.
`store|platform|cpu_type|
`pu_manufacturer|cpu_speed
`
`
`
`———ljorigdest3|provider
`[ayee—item type brand e|store
`
`
`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
`Ye |rl
`
`a:eae
`
`—f.
`
`
`[3|ComputerHardwareSidSSSSSCidSS
`
`
`
`28|Desktopcomputers|++
`
`29]Laptopcomputers|_|
`a?asl
`
`
`fameSddt
`
`
`
`[31___|PackagedTravel’——SCSC~dSCSSCSCSC~dSC(CS~S~*™
`
`[237|Beachandresots|
`page>Cris
`|239|Boatingandwatersports||
`poetsseit
`
`
`[241|Hikingclimbingandtrekking||
`FSte
`}5|ToysandGames|
`eeee
`aCea
`
`[34|Men'sApparel=|
`[272|Men'sShitsTT
`|2034|Men'sTops
`
`12035_|Men'sT-shirts|
`|2036_|Men'sPoloandhenleyshirts||
`|2037_[Men'sDressshirts||
`
`[273|Men’sPantsandshorts||
`[2038|Men'sPantsandkhakis|]
`[2039|Men'sJeansanddenim||
`[2040|Men'sShorts
`peeees]
`
`[35|Women'sApparel|
`
`1279|Women'sShirts|BlouseTO
`|2057_|Women'sTops|CT
`|2058|Women'sT-shirts|
`
`|2059|Women'sPoloandhenleyshins|TO
`
`|2060__|Women’sDressshirtsandblouses[|
`Dea
`[36|Shoes
`[287__|Men'sShoes
`
`[2085__|Men'sShoesCT
`|2086|Men'sBoots|
`[2087_|Men'sAthletic|
`|2088_|Men'sSandalsTT
`
`|2089|Men'sHikingandoutdoor[TO
`|288|Women'sShoesTT
`|2090__|Women'sShoes|CT
`
`
`
`
`
`
`
`Fig. 7
`
`

`

`asno|q
`
`
`
`OSPIAAq
`
`
`
`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 12 of 17
`
`US 6,366,910 Bl
`
`
`
`LO8
`
`age,Way,
`
`c08
`
`LE9TT
`
`
`
`
`

`

`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
`
`Add entries for bad
`terms
`
`904
`Select next dept table
`
`
` all dept
`
`tables already
`
`selected?
`
`
`
`Create term index table
`
`907
`
`906
`
`Return
`
`Adddepttable to
`term table
`
`Fig. 9
`
`

`

`to Term Table all items
`
`already
`selected?
`
`
`
`
`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 14 of 17
`
`US 6,366,910 B1
`
` (dept table)
`
`Add Depttable
`
`
`
`
`
`
`
`
`
`
`
`
`1003
`Collect priority 2 terms
`
`1004
`
`Update priority 2 entry
`
`1005
`Collect priority 3 terms
`
`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)
`
`
`
`
`
`
`
`
`Select next dept
`starting from first
`
`
`
`Prioritize scores
`
`1102
`
`1103
`
`
`
`
`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
`
`(classification,
`ancestorin result)
`
`Remove from result
`
`1202
`
`
`
`
`
`
`
`1201
`
`Ancestor in
`result?
`
`
`
`
`
`
` Classification in
`
`result?
`
`Set ancestorin result
`
`
`
`classification
`already
`
`
`selected?
`
`
`
`
`
`
`
`
`sufficient
`Traverse (selected
`classification
`children in
`
`
`ancestor in result)
`result?
`
`
`
`
`
`
`add password
`classification to result
`
` Fig. 12
`
`
`remove child
`classifications from
`result
`
`

`

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

`

`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 sean 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 of the search criteria
`within the documentor the presence of a word of the search
`criteria wilhin the litle of the document,
`
`20
`
`2
`system of the present invention lirst receives a query request.
`The system then identifies classifications of the data that
`may salisfy 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 bas 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 maich 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 imitial search results or adding a parent
`classification to replace multiple child classifications in the
`initial search results.
`
`BRIEF DESCRIPTION OP THE DRAWINGS
`
`In the emerging field of electronic commerce, many
`thousands of products are available to be purchased elec-
`= wr
`ironically. Por example, an online retailer may offer forsale 5
`FIGS, 1A and 1B illustrate an example user interface for
`electronic devices, major appliances, clothing, and so on.
`one embodiment of the present invention.
`The difheulty a potential purchaser faces is identifying a
`FIG, 2 is a block diagram illustrating components ofone
`particular product that salislies the purchaser's needs. Some
`embodiment of the GPS system.
`online retailers provide a search tool that receives a search
`criteria from a potential purchaser and searches a database ,
`FIGS. 3A and 3B illustrate example contents of a travel
`containing information for each of the available products to
`table and of an apparel table.
`identify those products that most closely match the search
`FIG. 4 illustrates a hierarchical organization of the items
`criteria. For example, a potential purchaser whois interested
`in the appare] table of the product database.
`in purchasing a television may enter the search criteria of
`FIGS. 5A, 5B, and 5C illustrate an example organization
`“tv.” The search tool may identify every TV, but may also ,
`of the browse iree descriptor file.
`identify items such as video game players and VCRs that
`FIG, 6 illustrates the contents of a sample priority descrip-
`happen to use the term “iv” in their description fields in the
`tor file. The priority descriptor file contains an entry lor each
`database, Thus, many products that are of no interest to the
`department represented in the product database.
`polential purchaser are identified. Many potential
`
`purchasers, when faced with suchalist that includes many FIG. 7 illustrates example contents of the special terms
`file.
`products that are of no interest will simply shop elsewhere
`FIG. 8 illustrates the contents of the GPS index.
`rather than wade through the list. Other online retailers may
`hierarchically organize the products so thal
`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 oot fall conveniently into any
`one classification. for example, a combination VCR and
`(elevision couldbe classified as a VCR or a television, Itis
`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 produet search technique
`that would combined the advantages of the search systems
`and the classification-based systems and thal minimizes their
`disadvantages.
`SUMMARY OF TILE INVENTION
`
`45
`
`FIG, 9 is a flow diagramillustrating an example embodi-
`ment of the GPS index builder.
`
`FIG. 10 is & 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 OF THE
`INVENTION
`
`6c
`
`65
`
`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
`groups the items into 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 systeminputs a search criteria from a user,
`searches for the classifications of items that best match the
`search crileria, and displays those classifications in an order
`
`Embodiments of the present invention provide a method
`and system for querying hierarchically classified data. The
`
`

`

`US 6,366,910 B1
`
`a
`
`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-
`lion 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-classilication, 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 of the “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 classilications 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
`lollows:
`dress shirts
`shoes
`[f the user then seleets “shoes,” the GPS system displays the
`sub-classifications of “shoes,” If the user, however, selects
`“dress shirts,” then the GPS system may display a deserip-
`tion of each dress shirt.
`Since the GPS system scores each classification 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, he 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 display its
`sub-classification of “dress shirts,” regardless of the score of
`the sub-classification. The user can always select the dis-
`played ancestor classification to view the descendent clas-
`sifications. In some situations, a parent classification may
`have a relatively low score, bu! many of its child classifi-
`calions may have a high score. In such a situation, the GPS
`system may display the parent classification rather than
`displaying each child classification. For example, if the
`“shirts” classification has a relatively low score, bul
`the
`“T-shirts” and “dress shirts” sub-classificalions have high
`a
`scores,
`the GPS system may decide to display only the 5
`“shirts” classification. The GPS system may set the score of
`the “shirts” classification to that of its highest sub-
`classification so thal
`the displayed classification will be
`ordered based on the score of ils sub-classilications.
`PIGS. 1A and LB illustrate an example user mterface for 5
`one embodiment of the present
`invention.
`In this
`embodiment,
`the GPS system provides capabilities for
`scarching for items that may be purchased, The techniques
`of the present invention are particularly well suited for use
`in a Web-based shopping environment. The display LOO of
`FIG. LA itlustrates a Web page for searching for items that
`may be purchased via an online store. This Web page
`illustrates that
`the available item are grouped into five
`departments: clothing and accessories 101, electronics 102,
`computer hardware 103, toys and games 104, and travel LOS.
`The item in each of these departments are classilied into
`calegories, sub-calegories, and possibly a sub-sub-category
`
`4
`the clothing and
`referred to as item type. For example,
`aecessories department has four item categories: men’s
`apparel, women’s apparel, shoes, and accessories. The user
`centers 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 searchcriteria, The GPS system displays
`these calegories and sub-categories in order based on the
`likelihood that the categories contain items thal satisfies the
`search criteria. In this example, the GPS system has listed 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,
`ihe word “shirts” may have
`been contained in a deseription field for an item within those
`classifications. For example, the sub-category “Men’s Tics”
`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 [ound 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
`determined that the department “travel”is the second mast
`relevant department for the search criteria.The GPS system
`displays the information for the travel department after the
`information for the clothing and accessories department
`because the score for the classifications within the travel
`department were lower than the score for the classifications
`in the clothing and accessones department.
`Once the GPS system displays the search results, as
`shown in FIG, 1B, a user may select one of the classifica-
`tions to view detailed information about the classification.
`Por example, if the user is interested in purchasing a T-shirt
`for a man,
`then the user may select the category “Men’s
`‘Fshirls.” Upon selecting this classification, the GPS system
`displays information describing the items within that clas-
`sification.
`If
`the selected classification has sub-
`classifications,
`then the GPS system insiead displays the
`sub-classilications.
`PIG, 2 is a block diagram illustrating components of one
`embodiment of the GPS system. The GPS search system
`comprises a product (or item) database 201, a GPS index
`builder 202, a priority descriptor file 203, the special terms
`file 204, a browse tree descriptor file 205, a GPS index file
`206, a GPS search engine 207, and a GPS hierarchical
`displayer 208. These components can be implemented as
`part of a general purpose computer system. The GPS system
`may be implemented as a server in a client/server environ-
`ment such as the World Wide Web or may be implemented
`on a computer, such as a mainframe.
`The GPS index builder creates the GPS index, which
`contains an entry for each classification, based on the names
`
`as
`
`40
`
`45
`
`6c
`
`6S
`
`

`

`US 6,366,910 Bl
`
`a
`
`oT
`
`AC
`
`45
`
`5
`of the classifications and the content of the fields in the
`product database. The product database contains an entry for
`each item. Theentries of the GPS index contain a collection
`of ihe words that appear in the entries of the product
`database for the items within that classification or the words
`in ibe names of the classification. After the GPS index is
`created, the GPS search engine receives a query and returns
`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 thefields of the
`product database in which the terms appear. Vor example,
`eachclassification may contain one entry that contains the
`words from the name of the 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 from all the description fields ofall 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
`enlire classification than a word in a descriplion field of
`some item within that classification. Each entry also con-
`lains 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 ihat best match the search criteria. The
`conventional search engines return as the resulis 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 scores of the entries in the resull to factor in
`their priorities. For example, ihe 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 remove all but the
`entry with the highest score for each classification from the
`result. The GPS search engine ihen 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-iree 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 remove eachof 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 GPS bierarchical displayer receives the results of the
`GPS search engine and first determines which highest level
`classification (¢.g., department) bas the highest score. The
`GPS hierarchical displayer selects those classifications with 5
`that highest level classification with the highest score and
`displays the name of the highest-level classification along
`with the names of the selected classification. The GPS
`hierarehieal displayer can select a predefined number of
`such classifications or select a variable number depending
`on the differences in the scores of the 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 cach depariment in the online store. The
`department may he considered to be the highest classifica-
`
`(
`
`wm
`
`=or
`
`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 ofa travel table
`and of an apparel table. The tables include field that specify
`the classification of each item within the classification
`hierarchy. Por example,
`the travel
`table 301 contains a
`category anda sub-calegory field. Thefirst entry in the travel
`table indicates that
`the item is in category 31 and sub-
`category 237. The entries also contain various other fields to
`describe the ilem. For example, the travel table contains a
`name field, a destination field, a provider field, and a
`description field. Each table also contains an 1D held, which
`contains a value that uniquely identifies cach entry within
`that table. The apparel table of FIG, 3B contains the items
`for the clothing and accessories department.
`The GPS index builder inputs the product database, the
`pnority descriptorfile, the special termsfile, and the browse
`tree descriptor file and generates the GPS index file. The
`browse tree descriptor file contains a d