`
`USUUG366910Bl
`
`(12)
`
`United States Patent
`
`US 6,366,910 B1
`(10) Patent N0.:
`
`(45) Date of Patent: Apr. 2, 2002
`Raj araman et al.
`
`(54)
`
`(75)
`
`MlC’l‘HOI) AND SYSTEM FOR GENERATION
`OF HIERARCHICAL SEARCH RESULTS
`
`6,029,195 A *
`(1,038,500 A "
`6,195,652 Bl
`*
`
`2.!2000 Hera.
`3,?2000 Wical
`232001 Fish
`
`
`
`?D9I219
`HHS
`'i'fl't'i’l
`
`Inventors: Anand Rajaraman, Seattle; Nigel
`Green, Bellevue, both of WA (US)
`
`‘ cited by examiner
`
`(73)
`
`Assignm: Amazoncum, Inc, Seattle, WA (US)
`
`( *J
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`USC. 154(b) by 0 days.
`
`(21)
`
`(22
`
`(51)
`(52)
`(58)
`
`(56)
`
`App}. No: 09i206,774
`
`Filed:
`
`Dec. 7, 1998
`
`Int. CL?
`
`Field of Search
`
`(1MP 1730
`
`70725
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,062,074 A * 10f1991 Kleinherger
`5,251,131 A * 102’1993 Massand et al.
`5,442,778 A *
`Silt-J95 Pcdetscn et at.
`5,483,725 A *
`111996 Turtle etal.
`$322,418 A *
`3,0998 Bro
`5,?8?,422 A "
`?f1998 ‘l‘ukeyclal.
`5,802,493 A *
`9,0998 Sherfinttetal.
`5,835,905 A * ӣ1998 Pirolli et al.
`5,849,409 A * 121sz Mm
`5,39?,638 A *
`4.!1999 lesser et a].
`5,920,854 A "
`"#1999 Kirsch et at.
`5981460 A "
`IUI999 Niwa etat.
`ti,{l]l.8t52 A *
`”2000 Doi ct al.
`
`..
`..
`
`707.35
`704i!)
`..
`. TONS
`
`707.5
`
`. 128f732
`
`ӣ0795
`705M
`701%
`aorta
`T010022
`TUNE}
`1"”?th
`382.3132
`
`
`
`
`
`
`Primary Exmnim’r—Wayne Amsbury
`(74) Attorney, Agent, or Finn—Perkins Coic [.1 .P
`
`(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. l-‘or classifications within the hierarchy
`of classifications, the system generates a search entry con-
`taining 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 subclassifications ofa 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
`
`20?
`
`GPS Index Builder
`GPS Search Engine
`
`
`
`
`
`
`Priority
`Descriptor
`
`Browse Tree
`tieseriptor
`
`GPS Hierarchical
`IJisplayer
`
`1
`
`EX1005
`EX1005
`
`
`
`US. Patent
`
`Apr. 2,2002
`
`Sheet 1 of 17
`
`US 6,366,910 B1
`
`hapsm
`
`.611: new. magma sham. make:i1. sugar find an: copy-mpmdmts firm. a mtg afmschm 63‘. 6% Wm.M
`you‘ve msmymng1.9333113 for, we take vou M- the merchant's m: 3mg“ goutmud-mass We‘vfi'p'm‘y 3.51.
`'beghmhbuiififihopmfifihb. Ehmdumsmnkm. we yam. tnfictfymfinditWe ӣ136 yamfixi
`Ildmfifis'
`
`--
`
`2
`
`
`
`U.S. Patent
`
`Apr. 2,2002
`
`Sheet 2 of 17
`
`US 6,366,910 B1
`
`$213301}.me
`
`-
`
`.
`”M
`
`
`
`{Er kewdié) shitsw 1 1 1
`
`
`
`" m mam-mmm, mgo'rimasid's'ubcmm
`mflsfineé matches forqu Wwdfii fiiiirt's‘; Cfick «Ming
`Idol»: balmy w gat-a'is‘f'sfgetéésiots Mmmhym'gkwoifi
`
`I fimr fiaamh Mi ymaum was: its;
`
`
`
` fireman?
`tha-,1:
`Efflfii’gflfl-
`
`
`
`3
`
`
`
`U
`
`t
`
`LD.A
`
`2;
`
`mfl
`
`m
`
`US 6,366,910 B1
`
`maEmMQ@030
`
`m.32
`
`VON
`
`38%
`
`actoh
`
`wmmUm-Pnew
`
`GM3mNon
`
`
`
`2&5.fiaomED2?:223m23who
`
`5m
`
`8.69m
`
`mn—
`
`mom
`
`2538%bozo
`
`
`
`ULumflmmaQ22%03%3Hm
`
`brain
`
`Bitumen
`
`Smom
`
`mom
`
`4
`
`
`
`
`
`
`US. Patent
`
`2002
`
`nf04whS
`
`US 6,366,910 B1
`
`
`
`0rowflufih.flea/GHQ;
`
`
`
`
`
`con.5me5355fame“..EO:oflmnflmofl25Zowufion—zm0896n:
`
`
`
`
`
`
`
`
`
`{C#0330053mBEENEzgfiwEz2a:
`BEES55H
`
`
`
`5ME
`
`
`
`a”.83:9»SchM(Ix/Kx0330033wmzmbm=<:22“mequova
`
`
`
`
`
`6%:coo28m
`
`
`
`
`
`{Ls/K523$233m332swam:K.mmflm
`
`Hm
`
`5
`
`
`
`
`US. Patent
`
`mm2,
`
`n.m5m%
`
`SU
`
`3,6w
`
`1B
`
`xix/Knimcoeq.
`
`
`#0350omow
`
`20m
`
`So?
`
`:9:.woman8on0:52Uqfim
`
`9‘H.Eu:
`
`
`
`a.-ofioasm
`
`
`
`o..030
`
`H
`oEwHEEQAE
`
`m3.MQ
`
`
`
`6.,{fix3E2:2:08m:
`
`
`
`awom
`
`nmm
`
`
`
`
`w:EméA{BK“ways?
`
`#03930wmomohmmm
`:33_
`
`6
`
`
`
`
`U
`
`tnet
`
`2mfl
`
`h
`
`U
`
`US 6,366,910 B1
`
`amutOmwuuBfiPa.3520
`
`
`
`CMm.~23me
`
`SI
`
`(0ENmo
`
`fEu?0330
`
`O
`
`
`
`7”Bumnnzxm.M5503Amm
`
`flum
`
`£52
`
`33%?
`
`V.uE
`
`7
`
`
`
`
`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 7 0f 17
`
`US 6,366,910 B1
`
`Browse Tree
`
`Pare
`n1
`
`Name
`
`DisplayName
`
`URLAlias
`
`Electronics
`
`feleetronicsr'elcctro
`nieshtml
`
`
`
`
`
`Confi gFiie
`
`Image
`
`Tillelmage
`
`—
`leladronicsfbmw
`Iimgl'electron
`nucleapropertie
`ics_il:on. gif
`8
`
`fimg’llead_electr
`onicsgil‘
`
`
`
`
`
`TableNa
`meStem
`
`EUICT
`RONICS
`
`
`
`
`
`
`
`
`
`
`
`
`
`237
`
`
`
`
`-_————
`Computer
`Computer
`{computer-groom
`foompuicm’brow
`fimgicompui
`firng/headwcomp
`COMPU
`Hardware
`Hardware
`tershlrnl
`se_ccmpulers.pro
`er_ioorL gif
`utengif
`TERS
`
`
`
`
`
`“-- mverrmvclmmr
`Iimg’hcadjmvel.
`Iimgl'trevelj
`TRAVE
`mavevbmwsey
`_. f
`cor-Luf
`LS
`avel,.
`. mies
`
`
`
`Packaged
`Packaged
`.I‘travdr'irowse_tra
`Jimga'llcadJraVCI
`Iimg’travel 1i
`mavel’browse_tr
`Travel
`Travel
`w1.htm]
`can -'f
`-
`'
`we]. . miss
`.
`._
`I -|
`.. ad, : |f
`
`
`Beach and
`Beach and
`Maveb‘resultsjav
`JimgruaveU
`fimgfhcedJrach
`
`resorts
`resorts
`el.h!mi
`can. u‘f
`ack beach. -'f
`a‘travetl'resullLtrav
`.I‘lmvelfresuhs_tra
`JimgltreveLi
`Cruises
`Cruises
`fimgflteadntmvel
`
`el.hlml
`velwo- flies
`eon-T
`r: k cruiseff
`
`
`{traveL'resulterav
`.I’Lraveh'results_tra
`fimgr’tmvcl _i
`Iimgi'hcadjrave}
`
`
`cl.hlrnl
`vehpropenies
`magi!"
`Jack _hoahng 31
`1‘
`
`flravelfresults_trav
`r‘traveUresulls_tra
`Ikngl’b'avelj
`Iimgfhead_ travel
`cl.hlml
`velpropenies
`congif
`_pe.ck_cycl|ng gr
`f
`
`
`
`31
`
`3 1
`
`Boating
`and
`waters - u-
`Cycling
`
`s
`
`limiting and
`water-spews
`
`Cycling
`
`‘_'
`'
`a‘lravelfresulteraV Maveb‘resultst
`Hiking.
`Hiking.
`
`climbing
`climbing and
`el.h1rn[
`whpmperties
`‘
`and
`trekking
`trekkin-
`
`fimgfheadj‘avel
`_pack_hiking.gif
`
`Toysand
`Games
`
`Clothing
`and
`Accessories
`Men's
`
`
`
`I Apparel
`
`
`
`
`272
`
`27“.!
`
`Tees
`
`
`
`——_—
`'l‘oys and
`fioyflioyehlml
`Mys’browaeJoy
`Iimgl'toysje
`Jimgfheadjuysg
`TOYS
`Games
`5. ur- . erLies
`_.-‘
`smcs. : if
`on If
`————
`Clothing and
`fapparelr'apparelhl
`fapparelfbrowse_
`Imyappnrel
`Ihngfhead_clothj
`APPAR
`Accessories
`ml
`apparelpropcrtic
`_ioon.gif‘
`nggif
`EL
`3
`fapparclr’brflwse_
`- flies
`lapparelfbrowse_
`apparel_men_sl1i
`rts. -r- nerfies
`
`Men's Apparel
`
`Men's Shirts
`
`fapparelfbrowsc}
`
`pparel_men.hl.m]
`
`fapparelfbruwseg
`pparci_men_shirts.
`111ml
`
`apparclfimnpro
`
`Fmg/apparel
`
`__ioon.gif
`
`fm1gfapparel
`_ioorLgif
`
`Jimgfheadjlotlli
`
`ng_men.gjf
`
`Iii-rifledjlothi
`ng_men_shirls.gi
`f
`
`Men's 'l'—shirls
`
`mehtml
`
`pparclpeoperties
`
`_ioon.gif
`
`ng_meu_shifl_to
`s. : 'f
`rims/I1 eadflclothi
`fimgx’apparel
`fapparclfresullga
`fapparelfresulttap
`E
`ng_men_shi,r1_te
`jean. gif
`ppmlpropcrtics
`{.html
`es. :T
`
`
`Fig. 5A
`
`8
`
`
`
`
`
`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 8 0f 17
`
`US 6,366,910 B1
`
`2036
`
`272
`
`Polo and
`henley shirts
`
`Men's Polo
`and herdey
`shirts
`
`{apparela’result
`fapparelfresults
`iimgfappm‘e
`fimgfhead_clo
`Igappamlhtm _appml.propa'
`l_icon.gif
`Lhing_men_5h
`ties
`i110!_10.if
`W“ W“ I
`
`s_appa.ret. htm _appa.rel.proper
`ties
`
`l__icon.gif
`
`filing_men_sh
`in shirtif
`limgfheadjlo
`fimgr‘appare
`fapparelfbrow
`ming_men_pa
`l_imn.gif
`se_appa.rel_m
`nt_shorts.gif
`
`shirts
`
`ens gif
`
`lapparelfresults
`Apparel-prom:
`
`tics
`l
`iapparellremm fappmclhtsmflts
`s_apparei,htm _appa.rel.proper
`ties
`fapparelfrcsults
`_apparcl.propcr
`ties
`
`Jungiappare
`l_icon_gif
`
`Iimge'headjln
`thing_mcn_pa
`nt khalds :if
`fimgfhnd_cio
`mmcmpa
`nt wnL f
`:‘imgfhmcLclo
`Lhing_men_pa
`nt 3110115.;
`
`-
`
`Women'5
`Apparel
`
`279
`
`35
`
`Shirts
`
`2957
`
`279
`
`Taps
`
`2058
`
`279
`
`Tees
`
`Women's
`Apparel
`
`Women'5
`Shirts
`
`Women's
`TOPS
`
`Woman's T-
`5111213
`
`2059
`
`279
`
`P010 and.
`henley shirts
`
`Polo and
`
`2060
`
`Dress shirts Womens
`and blouses
`
`.I--
`
`287
`
`36
`
`Men's
`
`Men's
`Shoes
`
`fappareb’brow
`se_appa.rel_w
`omenhtml
`
`iappareli'brows
`evappamewo
`men. 010 0 flies
`
`
`
`{imgfhcad_clo
`tl1ing_wumen
`_shj113.gif
`
`:‘appamllresults
`fimgfappare
`Iimgfhead clo
`I
`31:98:61me
`l_icon.gif
`flung women
`_I ..
`Lies
`shut to 3
`If
`lapparellmults
`fimga‘appare
`Iimgr'head_clo
`.apparelpromr
`]_icon.gif
`dling_womcn
`fies
`Shir! icesif
`fimg)head_clo
`Ihing_\wmen
`"shinylogi
`
`{apparellremflts
`{apparel/result
`s_apparel.hzm _apparel_pmpa
`ties
`
`IappamL’tesults
`"apparelproper
`ties
`
`fimglapparc
`l_icon.gif
`
`fimg/hmd_cio
`thing_mmen
`
`{appamvbmw
`se_appa.rel_sh
`DEShtIl‘ll
`
`iappamL’brows
`c_appa.rei_shoc
`5.0:000:
`'03
`
`limyapparc
`1_icon. gif
`
`fimglhead_do
`thing_shocs. gi
`
`l_icon.gif
`
`limgfhaadjlo
`'
`_shoe_m
`
`9
`
`
`
`US. Patent
`
`Apr. 2, 2002
`
`Sheet 9 of 17
`
`US 6,366,910 B1
`
`
`
`Men's
`Shoes
`
`lappaxelfrcsults
`lapparcllrcsult
`sqappawlhtm _appare1.proper
`1
`lies
`
`Jimgfapparc
`l_icon.gif
`
`limgfhcad_510
`thing_,shoc_m
`shoes.if
`
`fimgz‘apparc
`l_icon.gif
`
`fimgfappare
`1_ioon.gif
`
`limgflicadjlo
`thing_shoc_m
`on boots. '1"
`Iimgfheadjlo
`thing‘shoejn
`on athletic.if
`
`ffinglappare
`1_icon.gif
`
`limgfheadjlo
`thing_5hoe_m
`on sandals.if
`fimgmoadflclo
`thing_shoc_m
`en '.' c._if
`limgfapparc Ximgflleadjlo
`1_ioon,gif
`th‘mg_shoe_w
`
`(ting/aware
`1_icon.gif
`
`
`
`2085
`
`287
`
`Shoes
`
`2086
`
`28?
`
`Boots
`
`2087
`
`287
`
`Athletic
`
`2088
`
`237
`
`Sandals
`
`2089
`
`287
`
`Hiking and
`outdoor
`
`288
`
`36
`
`Women's
`
`Men‘s
`Boots
`
`Men's
`Athletic
`
`Men's
`Sandals
`
`Men's
`Hiking and
`outdoor
`Womm's
`Shoes
`
`lapparclfrcsulls
`lapparcllrcsull
`s_appa.rel.htm _appa.re1.proper
`l
`ties
`{apparellresult
`{apparcllrcsuits
`s_apparel.htm _appaml,proper
`1
`time
`
`lapparellresuits
`fapparelfresult
`s_apparel.htm _apparel.proper
`l
`lies
`iappm’ellresult
`lapparellresults
`s_appaml.htm _apparcl.propcr
`l
`ties
`{appamlr’brow
`lapparcb'brows
`se_apparel_sh
`e_apparel_shc—e
`oc_women.ht
`_womcn.proper
`ml
`ties
`
`Iapparel/restflts
`Iappareljrewlt
`s_apparel.htm _appa.rel.proper
`I
`ties
`
`Fig. 5C
`
`10
`10
`
`
`
`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 10 01‘17
`
`US 6,366,910 B1
`
`Priority Descriptor
`
`
`
`descripfionlcaiegory]subcategory!
`
`
`11cmJEperrandfnameistore
`descriptionlcategorylbrandtnamel
`storclplatfonnlcputypcl
`
`
`
`
`
`
`_W“’8‘
`
`
`fl—_—-ri: (1:513 . ovider
`
`
`__mHam 1: brand name store
`I__I.Illl-
`item pebrand name store
`
`epumanufacturer|Cpu_speed
`
`Fig. 6
`
`11
`11
`
`
`
`US. Patent
`
`Apr. 2, 2002
`
`Sheet 11 0f 17
`
`US 6,366,910 B1
`
`Special Terms
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[IE-___
`
`___—
`___—
`___—
`
`___——
`___——
`”___
`___—
`_—
`___—
`___—
`___—
`—-r—_—
`—I:om—--
`_—
`___—
`___—
`___-
`___—
`___——
`___-
`___—-
`___—
`___——
`___—
`___—
`__—
`___—
`___—
`___—
`__1_-—
`-—m—
`___—-
`___—
`___—
`___—
`___—
`___—
`___—
`___—
`___—
`___—
`___—
`___——
`___—
`
`___—
`
`
`
`
`
`
`
`
`
`
`
`12
`12
`
`
`
`US. Patent
`
`200223
`
`7.lf02ItcehS
`
`US 6,366,910 B1
`
`WDmfioAINowN33:
`Sm035.HEM;
`
`
`
`
`
`
`13
`13
`
`
`
`US. Patent
`
`Apr. 2, 2002
`
`Sheet 13 0f 17
`
`US 6,366,910 B1
`
`GPS Index
`
`Builder
`
`Add entries 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?
`
`
`
`Add dept table to
`term table
`
`Fig. 9
`
`14
`14
`
`90?
`
`Create term index table
`
`
`
`US. Patent
`
`Apr. 2, 2002
`
`Shect14 0f17
`
`US 6,366,910 B1
`
`Add Dept table
`to Term Table
`
`(dept table)
`
`
`
`1001
`
`Select next item in dept
`table
`
`1003
`
`Collect priority 2 terms
`
`
`
`1005
`
`Collect priority 3 terms
`
`1006
`
`Update priority 3 entry
`
`Fig. 10
`
`15
`15
`
`1004
`
`Update priority 2 entry
`
`
`
`
`
`
`
`
`
`US. Patent
`
`Apr. 2, 2002
`
`Sheet 15 0f17
`
`US 6,366,910 B1
`
`
`
`GPS Search
`Engine
`
`
`
`
`
`(query, result)
`
`1101
`
`Submit query (result)
`
`
`
`
`
`
`
`
`
`
`
`
`
`1102
`
`Prioritize scores
`
`
`
`1103
`
`Select next dept
`starting from first
`
`all dept
`already
`selected?
`
`1105
`
`Traverse
`(root, false)
`
`Fig. 11
`
`16
`16
`
`
`
`
`
`
`
` Ancestor in
`
`result?
`
`1202
`Remove from result
`
`US. Patent
`
`Apr. 2, 2002
`
`Sheet 16 01'17
`
`US 6,366,910 B1
`
`Traverse
`
`(classification,
`ancestor in result)
`
`
`
`
` Classification in
`
`
`result?
`
`Set ancestor in result
`
`
`
`
`
`classification
`already
`
`selected?
`
`
`
`
`
` sufiicient
`Traverse (selected
`children in
`clasmfication
`
`result?
`ancestor :11 result)
`
`
`
`
`
` 1209
`
`add password
`classification to result
`
`
`
`
`remove child
`classifications from
`
`result
`
` Fig. 12
`
`17
`17
`
`
`
`US. Patent
`
`Apr. 2, 2002
`
`Sheet 1? 01'17
`
`US 6,366,910 B1
`
`GPS
`
`Hierarchical
`
`
`Displayer
`
`Input Query
`
`1 301
`
`1302
`
`Invoke GPS search
`
`engine
`
`1303
`
`
`
`
`
`
`Select next dept with
`highest score
`
`
`
` Select next entry for
`highest score
`
`already
`selected?
`
`selected dept with
`
`
`all entries
`
`already
`selected?
`
`
`Display entry name
`
`1308
`
`Fig. 13
`
`18
`18
`
`
`
`US 6,366,910 B]
`
`1
`METHOD AND SYSTEM FOR GENERATION
`OF HIERARCHICAI. 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 deten'nine 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 ofthe search
`criteria within the title of the document.
`
`2
`system of the present invention first 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.
`
`ID
`
`15
`
`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 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.
`
`25
`
`3f]
`
`40
`
`In the emerging field of electronic commerce, many
`thousands of products are available to be purchased elec-
`tronically. For example, an online retailer may ofier 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 who is interested
`in purchasing a television may enter the search criteria of
`“tv.” The search tool may identify every TV, but may also ‘
`identify items such as video game players and VCRs that
`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 through the 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 01. 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 not fall conveniently into any
`one classification. For example, a combination VCR and
`television could be 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 combined the advantages of the search systems
`and the classification-based systems and that minimizes their
`disadvantages.
`SUMMARY OF THE INVENTION
`
`50
`
`55
`
`60
`
`65
`
`Embodiments of the present invention provide a method
`and system for querying hierarchically classified data. The
`
`19
`19
`
`BRIEF DESCRIPTION OF THE. DRAWINGS
`
`FIGS. 1A and 1B illustrate an example user interface for
`one embodiment of the present invention.
`FIG. 2 is a block diagram illustrating components of one
`embodiment of the GPS system.
`FIGS. 3A and 3]? 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, SB, 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 oonta ins 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 [low 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 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 subclassificat ion 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 ofwhere 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
`
`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 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, the Gl’S system does
`not display any descendent classifications of a displayed
`classification. For example, if the GI’S 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 descendenl clas-
`sifications.
`in some situations, a parent classification may
`have a relatively low score, but many of its child classifi-
`cations 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, but
`the
`"'l"-shirts" and "dress shirts" sub-classifications have high
`scores,
`the GPS system may decide to display only the
`“shirts” classification. The GPS system may set the score of
`the “shirts" classification to that of its highest sub-
`classification so that
`the displayed classification will be
`ordered based on the score of its sub—classifications.
`FIGS. 1A and 1B illustrate an example user interface for
`one embodiment of the present
`invention.
`In this
`embodiment,
`the GPS system provides capabilities for
`searching for items that may he purchased. The techniques
`of the present invention are particularly well suited for use
`in a Web—based shopping environment. The display 100 of
`FIG. 1A illustrates a Web page for searching for items that
`may he purchased via an online store. This Web page
`illustrates that
`the available item are grouped into five
`departments: clothing and accessories 10], electronic. 102,
`computer hardware 103, toys and games 104, and travel 105.
`The item in each of these departments are classified into
`categories, sub-categories, and possibly a sub-suh-catcgory
`
`It)
`
`15
`
`25
`
`3f]
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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 search criteria 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. IB illustrates the display
`of the search results. Rather than displaying the particular
`items that best match the search criteria, the (3138 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 items of 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 department first.
`The GPS system also displays the various categories and
`sub-categories of the clothing and accessories department
`that best match the search criteria. The UPS system displays
`these categories and sub-categories in order based on the
`likelihood that the categories contain items that 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 wort "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 sutwategory.
`In general,
`the UPS system highlights
`(e.g., holds) 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 OPS system
`determined that 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
`
`department were lower than the score for the classifications
`in the clothing and accessories department.
`Once the GPS system displays the search results, as
`shown in FIG. 18, a user may select one of the classifica-
`tions to view detailed information about the classification.
`For example, if the user is interested in purchasing a T-shirt
`for a man, then the user may select the category “Men’s
`T—shirts.” 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 instead displays the
`sub-classifications.
`FIG. 2 is a block diagram illustrating components of one
`embodiment of the GI’S 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 GI’S search engine 207, and a GPS hierarchical
`displayer 208. These components can be implemented as
`part of a general purpose computer system. The (3133 system
`may be implemented as a server in a clientlscrver environ—
`ment such as the World Wide Web or may be implemented
`on a computer, such as a mainframe.
`The (BPS index builder creates the GPS index, which
`contains an entry for each classification, based on the names
`
`20
`20
`
`
`
`US 6,366,910 B1
`
`5
`of the classifications and the content 01. the fields in the
`product database. The product database contains an entry for
`each item. 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 UPS 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 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 of the classification and from the name
`of its parent classification. The leaf (i.e.,
`lowestvlevcl)
`classifications, however, may also contain additional entries
`in the UPS index. One additional entry may contain all the
`words front all the description fields of all the items within
`the classilication. 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 oonv
`tains an indication of its priority.
`The UPS 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 scores of 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 remove all but the
`entry with the highest score for each classification from the
`result. The GPS search engine then removes all 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 [or 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 GPS hierarchical displayer receives the results of the
`GPS search engine and first determines which highest level
`classification (cg, department) has the highest score. The
`GPS hierarchical displayer selects those classifications with
`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
`hierarchical displayer can select a predefined number of
`such classifications or select a variable number depending
`on the difi‘ercnccs in the scores of the classifications. The
`Gl’S 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-
`
`it)
`
`15
`
`25
`
`3f]
`
`35
`
`40
`
`45
`
`50
`
`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 3B illustrate 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 descriptor file, the special terms file, and the browse
`tree descriptor file and generates the GPS index file. The
`browse tree descriptor
`file contains a definition of the
`hierarchical organization of the items in the product data-
`base. Although the product tables inherently contain the
`classification hierarchy (cg, classification 237 is a sub—
`category of classification 31), it is not in a form that is easy
`to use. Moreover, the product database in this embodiment
`contains no information that describes the names of the
`various classifications. FIG. 4 illustrates a hierarchical orga-
`nization of the items in the apparel
`table of the product
`database. As shown,
`the items in the apparel
`table are
`clas