|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`U5006366910B1
`
`(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,560 A "
`6,195,652 Bl
`*
`
`2.!2000 Hera.
`3,?20011 Wical
`232001 Fish
`
`
`
`T09i219
`WINS
`'ifl'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 * 11,0998 Pirolli et al.
`5,849,409 A * 12!]sz Ahn
`5,39?,638 A *
`4.!1999 lesser et a].
`3,920,854 A "
`"#1999 Kirsch et at.
`1981460 A "
`IUI999 Niwa etat.
`ti,{l]l.8t52 A *
`”2000 Doi ct al.
`
`..
`..
`
`707.35
`704i!)
`..
`. TDWS
`
`707.5
`
`. 128i732
`
`NW5
`705M
`701%
`aorta
`T010022
`TIW3
`rows
`382.3132
`
`
`
`
`
`
`Primary Exmnim’r—Wayne Amsbury
`(74) Attorney, Agent, or Firm—Perkins Coic [JP
`
`(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
`
`ELASTIC - EXHIBIT 1005
`
`ELASTIC - EXHIBIT 1005
`
`

`

`US. Patent
`
`Apr. 2,2002
`
`Sheet 1 of 17
`
`US 6,366,910 Bl
`
`hapsm
`
`.611: new. shaming am; make:i1. eugm find an: camp-mpmafmts From 3 mpg afmschm a... 6% mm.m
`-- 3m”: mammmg$333113 for, we Sake Sm: M- the merchant's m: 35:81“ goutmud-mass We‘w''p'm‘y idst
`'begsmw bulk! Shop tin Web. If a Mathew-n. we yam. to hat; you Em!itWe 9H6 your.:MiL-
`Ila snipe :his'
`
`

`

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

`

`U
`
`t
`
`r._PA
`
`mm2:
`
`m
`
`US 6,366,910 B1
`
`mom
`
`2538%bozo
`
`
`
`ULumflmmaQ.mEEE2o0%wwwa
`3frpm
`
`brain
`
`Bitumen
`
`Smom
`
`mom
`
`maama@030
`
`m.uE
`
`VON
`
`38am
`
`actoh
`
`wmmUm-Pcom
`
`QMnowNon
`
`
`
`2&5”:83mwas5?:523m5?:mmO
`
`5m
`
`8.69m
`
`mn—
`
`
`
`
`

`

`US. Patent
`
`2mfl
`
`nf04whS
`
`US 6,366,910 B1
`
`
`
`a”.23:9»SchM(ls/Ixx0330“imammzmbm=<:«=~bms<ova
`
`
`
`
`
`Hm
`
`6%:coo28m
`
`
`
`{Ls/K:naam238m:32swam:nmmflm
`
`
`
`
`
`(Ix/Kx0330233mPESN302u:m_muNBoZovmMm
`
`BEES55H
`
`
`
`
`5ME
`
`
`
`0wowflufih.flea/GHQ;
`
`
`
`
`
`
`
`con.5me5355fame“..COnoflmnflmofluEaZowufion—zmOHBNUn:
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`mm2,
`
`HM5mS
`
`US 6,366,910 B1
`
`hwva
`
`moan—“:0mmomWtwang..535Aufiwfiopdfl
`
`
`
`I.I.D—Om
`
`
`
`3mm8:2:08a:$8EE
`
`3ME
`
`
`
`
`
`{PK05mg?«03:538fin3
`
`
`
`
`
`
`
`cos.58D3on25.2wqfima;H.:5:onofioasm03wan:
`
`2anEEQAE
`
`
`

`

`U
`
`tnet
`
`2mfl
`
`h
`
`U
`
`US 6,366,910 B1
`
`amutOmwuuBfiPa.3520
`
`
`
`CMm.~23me
`
`SI
`
`(0ENmo
`
`fEu?0330
`
`O
`
`
`
`7”.0393m.$5503Amm
`
`flum
`
`952
`
`33%?
`
`V.uR
`
`
`

`

`US. Patent
`
`Apr. 2, 2002
`
`Sheet 7 0f 17
`
`US 6,366,910 B1
`
`Browse Tree
`
`Pare
`TableNa
`
`n1
`meStem
`
`_-——————
`2
`Electronics
`.I'clectronicsa'elcctro
`lelaolronicsfbmw
`Iimgl'electron
`fimg’hesd_eleotr
`EUICT
`
`nicshtml
`semelec.propertie
`ics_il:on. gif
`onicsgil‘
`RONICS
`3
`
`DisplayNeme
`
`Name
`
`
`
`URLAlias
`
`
`
`Confi gFiie
`
`Image
`
`Tillelmage
`
`
`
`
`
`_ _—_—
`Computer
`Computer
`foomputersfcompu
`fmmpuicm’bmw
`fimg’compul
`fimg/headwcomp
`COMPU
`Hardware
`Hardware
`tershlrnl
`se_ccmpulers.pro
`er_ioorL gif
`utengif‘
`TERS
`
`
`
`
`
`Boating
`and
`waters n u-
`Cycling
`
`5
`
`limiting and
`i?E
`
`Cycling
`
`
`
`
`
`’1 k cruiseff
`Iimgfhcsdjravel
`_pack _hoaimg 31
`1‘
`Ifingfhead_mvel
`_peck_cycl|ng gl
`1'
`
`fimgfhesdj‘avel
`_pack_hiking.gif
`
`
`
`
`
`
`
`237
`
`
`
`
`
`
`
`
`
`
`“-- mvearmvclmm
`fimg’hcaijrsveI.
`TRAVE
`a'traveb'browsej
`Iimgl'trsvelj
`_. l'
`LS
`avel.
`. mics
`conuf
`
`
`
`
`Packaged
`Packaged
`flrwclflrowsgfla
`Jimgfllcadjravcl
`mavel’browse_tr
`Iimga'trsvel 1i
`
`
`
`
`Travel
`Travel
`wl.html
`-
`we]. . enies
`can 91'
`.m-if
`,.
`
`Beach and
`Beach and
`ftravwresultsjav
`fimgfhced_tmvcl
`Jimgitravelj
`
`
`resorts
`resorts
`el.hlmi
`con-Lu?
`sck beach-T
`rt:avel’results_tra
`JimgltreveLi
`a‘trweh’resullLtraV
`Cruises
`Cruises
`
`vel. .. o -ertie5
`eon. -'f
`el.hlml
`
`
`{traveL'resulterav
`{travelr'resultera
`fimgr’tmvcl _i
`
`
`c|.hlrnl
`vehproperlies
`Don. gif
`
`flravelfresults_trav
`hmvelu’results_tra
`JhngI'u'aVeLi
`cl.hlml
`velpropenies
`con. gif
`
`
`
`
`
`
`
`
`
` Hiking.
`
`Hiking.
`climbing and
`trekking
`
`firsveb'resultsjav Maveb‘resnltst
`el.h1rn[
`vehpmperties
`
`climbing
`and
`mkkin
`——_——
`Toysand
`'l‘oys and
`fioys’ioyshlml
`MysfbrowaeJoy
`Ihngl'toysje
`Jimgfhesdjuysg
`TOYS
`Games
`Games
`5. -r » . erLies
`on. if
`smcs. : if
`
`Clothing
`and
`Accessories
`Men's
`
`I Apparel
`
`272
`
`34
`
`Clothing and
`Accessories
`
`fapparellapparelhl
`ml
`
`Men's Apparel
`
`Men's Shirts
`
`fapparelfbrowsc}
`
`pparel_men.hl.m]
`
`fapparelfbruwsej
`ppsrci_men_shirts.
`111ml
`
`fappare]fbmwse_
`sppareLpropc-rtic
`3
`lapparclr’brflwse_
`- flies
`lapparelfbrowse_
`apparel_men_si1i
`I13. -r- nerties
`
`apparcl_mn.pro
`
`_ioongif‘
`
`nggif
`
`APPAR
`EL
`
`Fmg/apparel
`
`__ioon.gif
`
`fm1gfsppare]
`_ioorLg'if
`
`Jimgfhead_clotl|i
`
`ng_men.gjf
`
`Iimghead_clothi
`ng_men_shi.fls.gi
`f
`
`
`
`
`ng_meu_shi.rl_to
`s. : 'f
`
`limg/headflclothi
`ng_men_shir1_le
`_ioon.gif
`pparelpropcrtics
`parel.html
`fl
`es. 'f‘
`
`
`27“.!
`
`Tees
`
`Men's T—shirls
`
`fapparelfresullsgp
`
`rapparclfresullx_s
`
`fimgfapparel
`
`pml.html
`
`pparclproperties
`
`_ioon.gif
`
`Fig. 5A
`
`

`

`US. 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
`shirts
`
`{apparela’result
`J'apparelfresults
`Igappamlhtm _appml.propei'
`ties
`s_apparel. htm _appa.rel.proper
`ties
`
`iimgfappm‘e
`i_icon.gif
`
`l__icon.gif
`
`fimgfhead_clo
`thing_men_5h
`ifl. u_10.if
`filing_men_sh
`in shirtif
`limgfhead_c10
`fimgr‘appare
`fapparelfbrow
`thing_men_pa
`l_imn.gif
`_
`_
`se_appa.rel_m
`' nt_shorts.gif
`
`
`
`ens gif
`
`'
`lapparelfresults
`.
`_'
`_apparel.proper
`
`tics
`fappmellrcsults
`_apparel.proper
`‘
`fapparelfrcsults
`fiapparelproper
`
`'
`
`'
`
`.
`
`'
`_'
`
`Jungiappare
`1_icon.gif
`
`
`
`Women'5
`Apparel
`
`Women's
`Apparel
`
`fapparela’brow
`se_apparel_w
`omenhtml
`
`iappareli'brows
`evappamen
`men. n o . flies
`
`
`
`2957
`
`279
`
`Taps
`
`2058
`
`279
`
`Tees
`
`Women's
`Tops
`
`Women's T-
`shins
`
`2059
`
`279
`
`Polo and
`henley shirts
`
`Polo and
`
`.
`
`.
`
`u
`
`_
`
`{apparellresults
`_appa.rel.proper
`lies
`lapparellreaulis
`"apparelpmper
`ties
`Iappamla’msults
`{apparel/result
`s_apparel.htm _apparel_pmpa
`ties
`
`'
`l_iconigif
`
`fimga‘appare
`]_icon.gif
`
`'
`_'
`
`.
`
`'
`
`Iimgfhead_cln
`thing_men_pa
`nt khalds.,if
`fimgfhlldjiu
`thing_men_pa
`nt ’wns-_'f
`IimgfhmcLclo
`Lhing_men_pa
`
`{imgfhcad_clo
`flifiiqumen
`_shj11$. gif
`
`Iimgfheaiclo
`thing_women
`shirt to s.-if
`Iimgr'head_clo
`diing_womcn
`shit! icesif
`fimgfheachlo
`Ihmg_\m}men
`mshifl_polo.gi
`
`2060
`
`Dress shirts Womens
`and blouses
`
`__
`
`.
`
`IappamL’tesults
`"apparelproper
`
`fimglapparc
`l_icon.gif
`
`fimg/hmd_cio
`thing_mmen
`
`287
`
`36
`
`Men's
`
`Men's
`Shoes
`
`{apparelfbrow
`se_appa.rel_sh
`oeshtml
`
`iappamlfbrows
`e_appa.re_i_shoc
`5mm .. es
`
`limyapparc
`l_icon. gif
`
`__
`
`_
`
`cw
`_
`
`_
`
`.
`
`'
`
`_
`
`l_icon.gif
`
`thing_shocsgi
`
`limgfheadjlo
`'
`_shoe_m
`
`

`

`US. Patent
`
`Apr. 2, 2002
`
`Sheet 9 of 17
`
`US 6,366,910 B1
`
`
`
`2085
`
`287
`
`Shoes
`
`Men's
`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
`
`ties
`
`Jimga‘apparc
`l_icon.gif
`
`fimgz‘apparc
`l_icon.gif
`
`fimgfappare
`1_icon.gif
`
`limgm‘fldflo
`thingwshogm
`shoes.if
`limgfllcadjlo
`thing_shoc_rn
`on boo-13.1"
`Iimgfheadjlo
`thing‘shogrn
`on athletic.if
`
`ffinglappare
`1_icon.gif
`
`{immeadjlo
`thing_Shoe_m
`on sandals.if
`fimgmeadflclo
`thing_shoc_m
`en '.' c._if
`limgfapparc Ximgflteadjlo
`1_ioon‘gif
`thing_shoe_w
`
`fimglappare
`1_icon.gif
`
`lappaxelfrcsults
`lapparcllrcsult
`sqappamlhtm _appare1.proper
`1
`lies
`lapparcllrcsull
`lapparclfrcsults
`s_apparel.htm _appa.re1.proper
`l
`ties
`{apparellresult
`{apparclr’rcsuits
`s_appawl.htm _appamliproper
`1
`time
`
`lapparellresults
`fapparelfresult
`s_apparel.htm _apparel.proper
`l
`lies
`iappm’ellresult
`lapparellresults
`s_appaml.htm _apparcl.propcr
`l
`ties
`{appamllbrow
`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
`
`Fig. 5C
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 10 01‘17
`
`US 6,366,910 B1
`
`Priority Descriptor
`
`
`
`descfipfionlcaiegoryjsubcategoryi
`
`
`11cmmelbrandfnamelstore
`descriptionlcategorylbrandtnamel
`storclplatfonnlcpu"typcl
`
`
`
`
`
`
`_W“m
`
`
`I—_—'
`
`uri: (1:513 . ovider
`
`I__lull-ilern 1: brand name store
`I__I.Illl-
`item pebrand name store
`
`epumanufacturer|Cpu_speed
`
`Fig. 6
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 11 0f 17
`
`US 6,366,910 B1
`
`Special Terms
`
`
`
`
`
`[IE-__—
`
`
`_———
`-——_
`————
`
`
`__—
`——-—_—
`"__—
`————
`_—
`—_—_
`-—__
`-———
`_-E—__
`—I:om—--
`_—
`-—__
`-_——
`-—-_
`__—_
`“__—
`-——-
`-_—-
`-——_
`_—_—_
`_——_
`-——_
`__—
`-——_
`-——_
`-_——
`__1_-—
`-—m—
`-——_-
`_——_
`_——_
`-_——
`__——
`__—_
`-—__
`-—__
`_—__
`-———
`-—__
`__—__
`_——_
`
`
`-_—_
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Apr. 2, 2002
`
`Sheet 12 of 17
`
`US 6,366,910 BI
`
`
`
`Pom
`
`ESP—L
`
`om=£m
`
`
`
`mtEm9:02:93..<$32
`
`
`
`2amcamtoaiaoa40330
`
`
`
`“:9:963..Sm5%2am
`
`83>B
`
`H
`
`o
`
`N
`
`M
`
`Coflm
`
`a3m
`
`“WEE.SSH
`soumofim30
` INDH
`
`ohm
`
`mum
`
`wmom
`
`omom
`
`m
`
`e.
`
`C\
`h
`
`New
`
`5?:
`
`$63
`
`hB I2“aN35%
`
`BE..<
`
`
`
`
`

`

`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
`
`90?
`
`Create term index table
`
`

`

`US. Patent
`
`Apr. 2, 2002
`
`Sheet 14 0f 17
`
`US 6,366,910 B1
`
`Add Dept table
`to Term Table
`
`(dept table)
`
`
`
`Select next item in dept
`table
`
`1001
`
`1003
`
`Collect priority 2 terms
`
`
`
`1005
`
`Collect priority 3 terms
`
`1006
`
`Update priority 3 entry
`
`Fig. 10
`
`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
`
`

`

`
`
`
`
` 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
`clasmfication
`children in
`
`result?
`ancestor :11 result)
`
`
`
`
`
` 1209
`
`add password
`classification to result
`
`
`
`
`remove child
`classifications from
`
`result
`
` Fig. 12
`
`

`

`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
`
`
`
`all dept
`already
`selected?
`
`
`
`
` Select next entry for
`highest score
`
`selected dept with
`
`
`all entries
`already
`
`selected?
`
`
`Display entry name
`
`1308
`
`Fig. 13
`
`

`

`US 6,366,910 B]
`
`1
`METHOD AND SYSTEM FOR GENERATION
`OF HIERARCHICAI. SEARCH RESULTS
`
`TECHNICAL FIEI .D
`
`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.
`
`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
`“1v.” 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 onIine 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
`
`Embodiments of the present invention provide a method
`and system for querying hierarchically classified data. The
`
`ID
`
`15
`
`25
`
`3f]
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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.
`
`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.
`
`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 5(? illustrate an example organization
`of the browse tree descriptor file.
`FIG. 6 illustrates the contents of a sample priority descrip-
`tor file. The priority descriptor file contains an entry for each
`department represented in the product database.
`FIG. 7 illustrates example contents of the special terms
`file.
`FIG. 8 illustrates the contents of the GPS index.
`
`FIG. 9 is a flow diagram illustrating an example embodi-
`ment of the GPS index builder.
`
`FIG. 10 is a flow diagram of an example routine to add a
`department table to the term table.
`FIG. 11 is a [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 dillicult 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 "shirLs," 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, 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 be 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 be 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-sub-category
`
`IO
`
`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 ofinterest. 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 GPS 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. 113, 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 Gl’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 GPS 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 clienti‘scrver 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
`
`

`

`US 6,366,910 B1
`
`5
`of the classifications and the content of 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.,
`lowestvlevel)
`classifications, however, may also contain additional entries
`in the UPS index. One additional entry may contain all the
`words from all 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 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 (c.g., 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 differences 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-
`
`10
`
`15
`
`25
`
`3f]
`
`35
`
`40
`
`45
`
`50
`
`55
`
`an
`
`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
`databas