(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 coecccescceseseeeeseeeee 709/219
`
`wee 707/5
`3/2000 Wical...
`2/2001 Fish oo... cesses FOT/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 ofthis
`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
`
`MnO scicccumsnemmanes GORI
`
`Field of Search .........::scsecsseeeeeeereensee 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
`..
`. 77/5
`5,442,778 A *
`8/1995 Pedersen et al.
`
`we TOTS
`5,488,725 A *
`1/1996 Turtle etal.
`...
`
`. 128/732
`5,722,418 A *
`3/1998 Brow...
`
`7/1998 Tukeyetal. ......cccce. 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.
`...
`awe. TCHS
`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.
`........:22:+ 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
`
`1
`
`EX1005
`EX1005
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 1 of 17
`
`US 6,366,910 B1
`
`ANERRATERS,
`
`Our new.shoppingshovemakesnt easyto find andcompareproducts from a munter.ofmerchants oh af ones.When
`. you's found whet you'rlnoling for, we take you ta the marchanit's sRe to meke pour purchase We'veohly Ra.
`“begante buitdShopthe Seu. If s produstisontine, wewant to Help you Bnd,‘Woeneedyourfiectls
`Ad snake this .
`hepsen.
`
`‘Blothingond
`
`2
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 2 of 17
`
`US 6,366,910 B1
`
`aur Search ANPraviucts Results
`forkeyword{ey dnrts> 114
`
`The following:departments, categotinsaddsubcategories
`coutaned matches foryour keyword(s} ‘shirts’. Chek onany
`fuck below tu get aket ofpedsiucts that match yourkeyword.
`
`i
`Women'stressshirtsandblouses
`
`BheCs.
`
`omen's Fulo
`rsoshing
`Man'sTans
`
`bepleysfirbs
`
`and
`
`am
`
`3
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 3 of 17
`
`US 6,366,910 B1
`
`LO?
`
`C07
`
`
`
`auisuqyorreasSqD
`
`$dD
`
`xopu]
`
`JoplingXepulSdO
`
`10c
`
`yonpoig
`
`ad
`
`
`
`807
`
`yNsoyArong)
`
`[eotyoJeOSd
`
`Jokeldsiq
`
`AejdsiqAang)
`
`CSL]
`
`voc
`
`[e1sods
`
`
`
`SULIOIL,
`
`
`
`sol]SsMO01g
`
`Jo}diosoq
`
`AWWIOUg
`
`Joduoseq
`
`SOc
`
`£0C
`
`4
`
`
`
`
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 4 of 17
`
`US 6,366,910 B1
`
`Loe
`
`uondussaq
`JIPIAOIg
`
`TJ
`
`—N
`
`Heme
`
`[PARI]
`
`yorqing
`
`oinjudA,
`
`yorqing
`
`oinjudA,
`
`
`
`
`“"ysapsu|UonRUNssgouIeNy
`
`
` INO|ameesRiyeysnyuelyeysny
`aTeVaSpuryea7MAN|puryeazMaN
`
`apesmneyTEMP]
` mol
`
`
`
`VE‘SLT
`
`uoowAau0}]
`
`osayeoqng
`082}e-)dl
`
`3[qe|,[OAPI],
`
`Lec
`
`OC
`
`OVC
`
`LE
`
`Te
`
`LE
`
`5
`
`
`

`

`Apr.2, 2002
`
`Sheet 5 of 17
`
`US 6,366,910 B1
`
`
`
`
`
`uonaLosoqd3101SOUuIeNpuelgadA[w93}]OsdovoqnsOo”dav
`hecmyOHHPBI|vOMH6807L8Za
`
`—,uiys-LTRIM:
`
`
`suIsLIOgyyorqing8S0Z6L7ZcE
`
`TE‘81
`
`U.S. Patent
`
`O[0dIRI
`
`g[qe|,joreddy
`
`6
`
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 6 of 17
`
`US 6,366,910 B1
`
`SOLIOSSAD0V%Surpoj>9
`
`joueddy
`
`SE
`
`S,URUIOA,
`
`joreddy
`
`ve
`
`S,Usjy
`
`joreddy
`
`8LT
`
`JONG.
`
`TEOM
`
`a|
`
`PEO
`
`sdoy,
`
`7
`
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 7 of 17
`
`US 6,366,910 B1
`
`Browse Tree
`
`Pare|Name DisplayName|URLAlias ConfigFile Image TitleImage TableNa
`
`
`
`
`nt
`meStem
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a /computersicompu|/computers/brow|/img/comput|/img/head_comp|COMPU
`eeee
`
`
`
`
`
`Hardware se_computers.pro|er_icon.gifnous ters.html uter.gif TERS
`
`
`
`[tatPata—eae travel/browsetr|/img/travel_i
`Eeeeeeeee
` Annpihentrevel.
`
`
`:
`con. gif
`
`
`
`Packaged ‘travel/browse_tra|/travel/browse_trPackaged Amp/weveli fnghheadtravel
`
`
`
`.
`i
`aged.
`Travel
`Travel
`E
`
`
`31
`Beach and
`Beach and
`ftravel/results_trav
`Faagitarel.i
`img/head_nd
`
`
`
`tesorts
`Tesorts
`el.html
`con. gif
`pack beach. gif
`E
`Cruises
`Cruises
`‘travel/results_trav
`‘img/travel_i
`fingfoead_twat
`heavevenusWe
`
`
`31 ee Boatingand ‘travel/resultstrav|/travel/results_tra|/img/travel1 lapeltravel
`
`watersports
`el.himl
`vel.properties
`con.gif
`pakboating.gi
`Cycling Aravel/resultstrav|Aravel/results_tra|/img/travel_i aEtravel
`
`
`el.html
`vel.properties
`con.gif acycling.gi
`
`Aravel/resultstrav|Aravel/results_tra|/imp/travel_i alae
`
`climbing and
`el.html
`vel. properties
`con.gif
`_pack_hiking.gif
`
` =e
`Toys and ‘toys/browse_toy aeic|/img/headtoysg|TOYSAoys/toys.html
`
`
`
`Games _————|——4pif§.properties
`
`
`Clothingand Leenaerrehht|/apparel/browse_|/img/apparelaPEclothi|APPAR
`
`
`
`
`
`
`
`
`Accessories eatpropertie|icon.gif ng.gif EL
`
`
`Men's Apparel|/apparel/browse_a lopaaas fimg/apparel|/img/head_clothi
`
`
`pparel_men.html apparel_men.pro|icon gif ng_men.gif
`perties
`Men's Shirts /apparel/browse_a|/apparel/browse_ seins fimg/head_clothi
`
`Pparel_men_shirts. SAmen_shi
`con.gif
`ng_men_shirts.gi
`
`rts.properties
`Men's Tops aie /apparel/results_a
`/img/apparel iaclothi
`
`
`parel.html pparel.properties|icon.gif oecishirt_to
`
`Men'sT-shirts|/appare—ap|/apparel/results_a ‘img/apparel —clothi
`
`
`parel.ht pparel.properties|icon.gif me_men_shirt_te
`
`
`Electronics lelectronics/clectro|/electronics/brow|/img/electron|/img/head_electr|ELECT
`
`
`
`nics.html se_elec.propertie|ics_icon.gif|onics.gif RONICS
`5
`
`vel. properties
`
`con. gif
`
`ack cruise.gif
`
`
`
`
`
`el.html
`
`8
`
`

`

`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
`apparel.proper
`s_apparel. htm
`L_icon.gif
`thing_men_sh
`henley shirts|and henley
`1
`shirts
`hes
`irt_polo.gif
`/apparel/results
`/img/appare
`/img/head_clo
`Dress shirts|Men's Dress|/apparel/result
`_apparel. proper
`1icon.gif
`thing_men_sh
`shirts
`s_apparel.htm
`ties
`itt shirt.gif
`
`] /
`
`apparel/brow
`se_apparel_m
`
`
`/img/appare
`Licon.gif
`
`/apparel/results
`/img/appare
`_apparel. proper
`Licon.gif
`re
`ties
`/apparel/result
`/apparel/results
`s_apparel.htm
`_apparel. proper
`tes
`/apparel/results
`_apparel.proper
`
`/ime/head_clo
`thing_men_pa
`nt_khakis. gif
`/img/head_clo
`thingmen_pa
`nt_jeans.gif
`/img/head_clo
`thingmen_pa
`sere.shorts.g
`Ls
`
`Singhalaooo]
`rewomen.
`
`/img/appare
`Licon.gif
`
`Licon. gif
`
`Sapa+—___Sapa
`
`se2opensw
`omen.html
`
`€_apparel_wo
`men. properties
`
`ens.gif
`
`ae$s eaeSs
`
`Apparel
`
`Shirts
`
`Apparel
`
`Women's
`Shirts
`
`
`
`
`
`2057 279|Tops Women's /apparel/result /apparel/results /img/appare
`
`
`/img/head_clo
`_apparel.proper
`thingwomen
`Tops
`1icon.gif s_apparel.htm
`hes
`l
`shirt_tops.gif
`279|Tees Women's T-
`
`/img/appare
`/img/head_clo
`/apparel/results
`shirts
`fe
`_apparel.proper
`Licon.gif
`thingwomen
`ties
`shirt_tees.gif
`
`2059|279|Polo and Women's /apparel/result /apparel/results /img/head_clo
`
`
`
`/img/appare
`L_icon.gif
`thingwomen
`
`henley shirts|Polo and s_apparel.htm
`_apparel.proper
`ties
`henley
`I
`_shirt_polo.gi
`shirts
`/apparel/result
`Women's
`Dress shirts
`2060
`/img/appare
`img/head_clo
`and blouses|Dress shirts|s_apparel.htm
`icon.gif
`thing_women
`and blouses||
`_Shirt_blouse.
`
`f /
`
`I
`
`
`
`r=>_
`
`aia
`
`thing_shoe_m
`
`Skeaoel/brow
`
`SapaI/brows
`
`se_apparel_sh
`oes.html
`
`e_apparel_shoe
`5. propel
`ies
`
`287
`
`36
`
`Men's
`
`Men's
`Shoes
`
`/img/appare
`Licon. gif
`
`9
`
`

`

`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
`l
`ties
`en_boots.gif
`
`
`2087|287|Athletic /apparel/result|/apparel/results|/img/appare|/img/head_cloMen's
`
`
`Athletic s_apparel.hun|_apparel.proper|1icon.gif thingshoe_m
`1
`ties
`en_athletic.gif
`
`
`2088|287|Sandals /apparel/result|/apparel/results|/img/appare|/img/head_cloMen's
`
`
`Sandals s_apparel.htm|_apparel.proper|1_icon.gif thing_shoe_m
`l
`ties
`en_sandals.gif
`
`
`2089|287|Hiking and /apparel/result|/apparel/results|/img/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
`
`10
`10
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 10 of 17
`
`US 6,366,910 BI
`
`
`
`pu manufacturerjcp
`
`eed
`
`_ PHO Descriptor
`
`
`
`
`ee brand|name(|store|platform|cpu_type||description|category|brand|name|
`
`2|Savoeeeaneareretype|brand|namelstore description|category|subcategory|
`
`item_typelbrand|name|store
`
`
`
`
`
`
`7eaeeeeitem type|brand|namelstore
`aeSSitem_type|brand|name|store
`
`origdest3|provider
`
`Fig. 6
`
`11
`11
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 11 of 17
`
`US 6,366,910 B1
`
`Special Terms
`
`
`|Id_|DisplayName|GoodTerms|BadTerms|
`pO
`
`
`So
`a
`
`
`
`[3___|ComputerHardwareSid
`
`
`28|Desktopcomputers——S—~dSSS
`
`
`
`29|LaptopcomputersSidCd
`ee =o
`nn
`[4|TravelOTtvvideo|
`[31___|PackagedTravel|
`|237|Beachandresorts|
`[238|Cmises
`
` |239|Boatingandwatersports[|
`
`[240[Cycling
`Hikingclimbing and trekking feft
`
`2os) 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
`
`
`
`
`
`adiL
`[Shoes
`|287__|Men'sShoesTT
`|2085_|Men'sShoes|
`|2086__|Men'sBoots|
`|2087_|Men'sAthletic|
`
`
`
`
`
`Fig. 7
`
`12
`12
`
`

`

`US 6,366,910 B1
`
`Apr.2, 2002
`
`Sheet 12 of 17
`
`U.S. Patent
`
`gjqeLWO],
`
`Z08Xopu]
`
`
`
`13
`13
`
`
`

`

`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
`
`14
`
`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 1
`
`all items
`already
`
`
`
`
`selected?
`
`
`
`
`
`
`
`
`
`
`1003
`Collect priority 2 terms
`
`1004
`
`Updatepriority 2 entry
`
`1005
`Collect priority 3 terms
`
`1006
`Update priority 3 entry
`
`15
`
`

`

`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)
`
`16
`
`

`

`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
`
`17
`17
`
`

`

`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
`
`130
`Select next entry for
`selected dept with
`highest score
`
`already
`
` all entries
`
`selected?
`
`18
`18
`
`

`

`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 of the search criteria
`within the document or the presence of a word of the search
`criteria within the title of the document.
`
`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
`
`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
`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 difficulty a potential purchaser faces is identifying a
`FIG, 2 is a block diagram illustrating components of one
`particular product that satisfies 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 apparel table of the product database.
`in purchasing a television may enter the search criteria of
`a9wn
`FIGS. 5A, 5B, and SC illustrate an example organization
`“tv.” The search tool may identify every TV, but mayalso ,
`of the browse tree descriptor file.
`identify items such as video game players and VCRsthat
`FIG, 6 illustrates the contents of a sample priority descrip-
`happen to use the term “tv” in their description fields in the
`tor file. The priority descriptor file contains an entry for each
`database. Thus, many products that are of no interest to the
`department represented in the product database.
`potential 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 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
`
`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 OF THE
`INVENTION
`
`Embodiments ofthe 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
`
`65
`
`Embodiments of the present invention provide a method
`and system for querying hierarchically classified data. The
`
`19
`19
`
`

`

`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 eachof 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 illustratesthe 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 searchcriteria. 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 ofthose 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 department after 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 descriptorfile 203, the special terms
`of the present invention are particularly well suited for use
`file 204, a browse tree descriptorfile 205, a GPS index file
`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
`
`20
`20
`
`

`

`US 6,366,910 B1
`
`5
`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 remove each 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 include field 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 indicates that
`the item is in category 31 and sub-
`category 237. The entries also contain various other fields to
`describe the item. For example, the travel table contains a
`name field,
`a destination field, a provider field, and a
`description field. Each table also contains an ID field, which
`contains a value that uniquely identifies each 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
`priority descriptorfile, the special terms file, and the browse
`tree descriptor file and generates the GPS index