(12) United States Patent
`Rajaraman et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,366,910 B1
`Apr. 2, 2002
`
`US006366910B1
`
`(54) METHOD AND SYSTEM FOR GENERATION
`()1? HIERARCHICAL SEARCH RESULTS
`
`(75) Inventors: Anand Rajaraman, Seattle; Nigel
`Green, Bellevue, both of WA (US)
`
`(73) Assignee: Amazon.com, Inc., Seattle, WA (US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U-S~C~ 154(k)) by 0 days-
`
`(21) Appl. No.: 09/206,774
`_
`Dec‘ 7’ 1998
`(22) Flled:
`(51) Int. c1.7 .............................................. .. G06F 17/30
`(52) US. Cl. ......................................................... .. 707/5
`(58) Field of Search ............................................ .. 707/5
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5 O62 074 A * 10/1991 Kleinberger ~~~~~~~~~~~~~~~~~ n 7075
`5:251:131 A * 10/1993 Massand et a1‘ “
`704/9
`5,442,778 A * 8/1995 Pedersen et aL __
`707/5
`5,488,725 A * 1/1996 Turtle et a1_ ____ __
`707/5
`5,722,418 A * 3/1998 Bro ,,,,,,,,,,,, ,,
`128/732
`5,787,422 A * 7/1998 Tukey et al. .... ..
`707/5
`705/1
`5,802,493 A * 9/1998 Sher?ott et al- -
`57835905 A * 11/1998 Pirolli “4 a1~ ~~~~ ~~
`707/3
`2 i 142‘;
`707/3
`5:920:2354 A * 7/1999 Kirsch et a1. ..
`.... .. 707/6
`5,987,460 A * 11/1999 NiWa et al.
`6,011,862 A * 1/2000 Doi et a1. ................. .. 382/132
`
`6,029,195 A * 2/2000 HerZ ........................ .. 709/219
`6,038,560 A * 3/2000 Wical .......................... .. 707/5
`6,195,652 B1 * 2/2001 Fish ............................ .. 707/2
`_
`_
`cued by exammer
`
`*
`
`_
`P '' ima" y Examiner—wayne Amsbury
`(74) Attorney, Agent, or Firm—Perk1ns Core LLP
`(57)
`ABSTRACT
`
`A method and system for querying hierarchically classi?ed
`data. The system ?rst receives a query request and then
`identi?es classi?cations of the data that may satisfy the
`received query request. The system then displays the iden
`ti?ed classi?cations. In response to selection of a displayed
`Classi?cation, the system displays sub-Classi?cations When
`the Selected class_i?_cation has §ub'c_lassi?cations and dis
`plays the data Wlthm the Classl?canon When the Selected
`classi?cation has no sub-classi?cations. In another aspect,
`the system generates search results for items that are hier
`archically classi?ed. For classi?cations Within the hierarchy
`of classi?cations, the system generates a search entry con
`taining terms describing the items Within that classi?cation.
`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 classi?cations. This adjustment may include
`removing sub-classi?cations of a classi?cation that is in the
`initial search results or adding a parent classi?cation to
`replace multiple child classi?cations in the initial search
`results‘
`
`59 Claims, 17 Drawing Sheets
`
`202
`
`207
`
`201
`
`Product
`DB
`
`GPS Index Builder
`
`11
`
`I)
`
`A
`
`206
`
`GPS
`Index
`
`203
`
`205
`
`Priority
`Descriptor
`
`Browse Tree
`Descriptor
`
`204
`
`Special
`
`Terms
`
`GPS Search Engine
`
`ll
`
`Query
`
`Result
`208
`
`v
`
`_
`_
`_
`7 GPS Hlerarchlcal
`Displayer
`
`Query T i Display
`
`IPR2017-01039
`Unified EX1005 Page 1
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 1 0f 17
`
`US 6,366,910 B1
`
`Fig, 1A
`
`IPR2017-01039
`Unified EX1005 Page 2
`
`

`

`U.S. Patent
`
`Apr.2, 2002
`
`Sheet 2 of 17
`
`US 6,366,910 B1
`
`ne
`
`ehGH Prariucrs
`
`amazon.comOOK
`
`tik belows te get alst ofpeoshiets thatmatch yourkeyword. Fig. 1B
`
`comsined matches for your keywords) ‘shirts', Chek ouany
`
`IPR2017-01039
`Unified EX1005 Page 3
`
`IPR2017-01039
`Unified EX1005 Page 3
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 3 0f 17
`
`US 6,366,910 B1
`
`wow
`
`
`
`228M @050
`
`EQEEQ
`
`
`
`1838805 mmmv
`
`A
`
`@EEQH H 50:0
`
`N .ME
`
`
`
`poatomo? HoEtQmoQ
`
`wow
`
`38%
`950B
`
`
`
`
`
`on; 339m biota
`
`<
`
`
`
`mow mom
`
`bow
`
`Now
`
`mom
`
`x22: m AU
`
`A|
`
`
`
`
`
`625m 59m mp9
`
`How
`
`636E
`
`m5
`
`IPR2017-01039
`Unified EX1005 Page 4
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`LOe
`
`uondisseq
`JIPIAOI
`
`ny
`
`[OAR
`
`yorqing
`
`dINjUudA,
`
`apes
`
`Sheet 4 of 17
`
`US 6,366,910 B1
`
`a
`yorqing
`ainjuaA,
`
`VE‘SLT
`
`“ysap3uQ|wonRUNsagOUIEN,
`
`[OAPI]
`
`
`—“Tremey]
`
`
`
`
`
`TEMPH
`
`uoouAau0pY]
`
`uelyeysny
`
`INO]
`
`JIQUL
`
`IPR2017-01039
`Unified EX1005 Page 5
`
`IPR2017-01039
`Unified EX1005 Page 5
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 5 of 17
`
`US 6,366,910 B1
`
`SUIsIIOGV
`
`
`
`yoeqing8507
`
`TEOMA
`
`
`
`9f0¢
`
`
`
`Joreddy
`
`~~|
`
`dayeoqns|A1osa3e> s[qe,
`
`OTHPON)
`
`TE“S1]
`
`IPR2017-01039
`Unified EX1005 Page 6
`
`IPR2017-01039
`Unified EX1005 Page 6
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 6 6f 17
`
`US 6,366,910 B1
`
`mm
`
`65%?
`m .5803
`
`vm
`
`M52
`
`689$
`
`wbm
`
`.630
`
`.895
`
`IPR2017-01039
`Unified EX1005 Page 7
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 7 0f 17
`
`US 6,366,910 B1
`
`Browse Tree
`
`Pare
`nt
`
`Name
`
`DisplayName
`
`URLAlias
`
`Con?gFile
`
`Image
`
`TitleImage
`
`TableNa
`meStem
`
`Id
`
`2
`
`3
`
`4
`
`3 1
`
`237
`
`238
`
`239
`
`240
`
`3 1
`
`0
`
`Electronics
`
`Electronics
`
`/electronics/electro
`nics.html
`
`0
`
`0
`
`4
`
`31
`
`3 l
`
`3 1
`
`Computer
`Hardware
`
`Computer
`Hardware
`
`/computers/compu
`ters. html
`
`Travel
`
`Travel
`
`ltravel/traveLhtml
`
`Packaged
`Travel
`Beach and
`resorts
`Cruises
`
`Boating
`and
`watersports
`Cycling
`
`Packaged
`Travel
`Beach and
`resorts
`Cruises
`
`Boating and
`watersports
`
`Cycling
`
`/travel/browse_tra
`vel.html
`/travel/results_trav
`el.html
`ltravel/results_trav
`e1.htrnl
`/travel/results_trav
`eLhtml
`
`/electronics/brow
`se_elec.propertie
`s
`
`/computers/brow
`se_computers.pro
`perties
`
`/travel/browse_tr
`aveLproperties
`/travel/browse_tr
`aveLproperties
`/travel/results_tra
`vel.properties
`/travel/results_tra
`vel.properties
`/travel/results_tra
`vel.properlies
`
`/img/eleetron
`ics_ic0n.gif
`
`/img/head_electr
`onicsgif
`
`ELECT
`RONICS
`
`/img/comput
`er_icon. gif
`
`/imyhead_comp COMPU
`uter. gif
`TERS
`
`/img/travel_i
`congif
`/img/travel?i
`con. gif
`/img/travel‘i
`congjf
`/img/travel_i
`con. gif
`/img/travelvi
`con. gif
`
`/imgtravel_i
`con. gif
`
`/img/head_travel. TRAVE
`gif
`LS
`/img/head_travel
`_packaged. gif
`/img/head_travel
`_pack beach. gif
`/img/headgtravel
`_pack eruisegif
`/img/head_travel
`_pack_boating.gi
`f
`/img/headftravel
`_pack_cycling. gi
`f
`/img/head_trave]
`_pack_hiking.gif
`
`/travel/results_trav
`el.html
`
`/travel/results_tra
`vel.properties
`
`/travel/resu|ts_trav
`eLhtml
`
`/travel/results_tra
`vel.properties
`
`/img/travelj
`con. gif
`
`Hiking,
`climbing
`and
`trekking
`
`Hiking,
`climbing and
`trekking
`
`Toys and
`Games
`
`Toys and
`Games
`
`Itoys/toyshtml
`
`/toys/browse_toy
`spmperties
`
`/img/toys_ic
`on.gif
`
`/img/head_toysg
`amesgif
`
`TOYS
`
`Clothing
`and
`Accessories
`Men's
`Apparel
`
`Clothing and
`Accessories
`
`/apparel/apparel.ht
`ml
`
`Men's Apparel
`
`/apparel/browse_
`apparelpropertie
`s
`/appa.rel/browse_
`apparel_men. pro
`perties
`/apparel/browse_
`apparel_men_shi
`rtspmperties
`/apparel/results_a
`ppareLpropenies
`
`/apparel/br0wse_a
`pparel_men.html
`
`lapparel/browsega
`pparel’men_shirts.
`html
`/apparel/results_ap
`pareLhtml
`
`mug/apparel
`_icon.gif
`
`/img/head_clothi
`ng.gif
`
`APPAR
`EL
`
`/img/apparel
`_icon gif
`
`/img/head_clothi
`ng_men. gif
`
`limg/apparel
`_icon. gif
`
`limglapparel
`_icon. gif
`
`/img/head_clothi
`ng_men_shirts . gi
`f
`/img/head_clothi
`ng_men_shirt_to
`ps.gif
`/img/head_clothi
`ng_men_shirt_te
`es.gif
`
`241
`
`3 1
`
`5
`
`6
`
`34
`
`0
`
`0
`
`6
`
`272
`
`34
`
`Shirts
`
`Men's Shirts
`
`2034
`
`272
`
`Tops
`
`Men's Tops
`
`2035
`
`272
`
`Tees
`
`Men's T-shirts
`
`/apparel/results_ap
`pareLhtml
`
`/apparel/results_a
`pparelproperties
`
`limg/apparel
`_icongif
`
`Fig.
`
`IPR2017-01039
`Unified EX1005 Page 8
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 8 0f 17
`
`US 6,366,910 B1
`
`2036
`
`272
`
`Polo and
`henley shirts
`
`2037
`
`272
`
`Dress shirts
`
`273
`
`34
`
`Pants and
`shorts
`
`2038
`
`273
`
`2039
`
`273
`
`Pants and
`khakis
`
`Jeans and
`denim
`
`2040
`
`273
`
`Shorts
`
`35
`
`6
`
`Women's
`Apparel
`
`279
`
`35
`
`Shirts
`
`2057
`
`279
`
`Tops
`
`2058
`
`279
`
`Tees
`
`2059
`
`279
`
`Polo and
`henley shirts
`
`2060
`
`279
`
`Dress shirts
`and blouses
`
`lapparel/result
`Men's Polo
`s_apparel.htrn
`and henley
`I
`shirts
`Men's Dress lapparel/result
`shirts
`s_apparel.htrn
`l
`Men's Pants lapparel/brow
`and shorts
`se_apparel_m
`en _pants.html
`
`Men's Pants
`and khakis
`
`Men's Jeans
`and denim
`
`Men's
`Shorts
`
`lapparel/result
`s__apparel.htm
`l
`lapparel/result
`s__apparel.htm
`1
`lapparel/result
`s_apparel.htm
`1
`
`Women's
`Apparel
`
`Women's
`Shirts
`
`Women's
`Tops
`
`lapparel/brow
`se_apparel_w
`omenhtrnl
`/apparel/brow
`se_apparel_w
`omen_shirts.h
`tml
`lapparel/result
`s_apparel.htm
`l
`Women's T- /apparel/result
`shirts
`s_apparel.htm
`l
`/apparel/result
`s_apparel.htm
`l
`
`Women's
`Polo and
`henley
`shirts
`Women's
`Dress shirts
`and blouses
`
`limg/appare
`l_icon.gif
`
`lapparel/results
`_apparel.proper
`ties
`limg/appare
`lapparel/results
`_apparel.proper l_icon.gif
`ties
`lapparel/brows
`e_apparel__men
`_pants.properti
`es
`lapparel/results
`_apparel.proper
`ties
`/appa.rel/resu1ts
`_appa.re1.proper
`ties
`lapparel/results
`_apparel.proper
`ties
`
`limg/appare
`l_icon.gif
`
`lirng/appare
`l_icon.gif
`
`limglappare
`1_icon.gif
`
`limg/appare
`l_icon.gif
`
`limg/appare
`l_icon, gif
`
`limg/appare
`l_icon.gif
`
`lapparel/brows
`e_apparel_wo
`menproperties
`/apparel/brows
`e_apparel_wo
`men_shirts.pro
`perties
`/img/appare
`/apparel/results
`_apparel.proper 1_icon.gif
`ties
`/irng/appare
`lapparel/results
`_apparel.proper l_icon.gif
`ties
`lapparel/results
`_apparel.proper
`ties
`
`lirng/appare
`l_icon.gif
`
`/img/head_clo
`thing_rnen_sh
`irt__polo.gif
`/img/head__clo
`thing_men_sh
`irt shirtgif
`/irng/head_clo
`thing_men_pa
`nt_shorts.gif
`
`/img/head_c1o
`thing_men_pa
`nt khakisgif
`/irng/head_clo
`thing_men_pa
`nt_jeans.gif
`/img/head__clo
`thing_men_pa
`nt shortsgif
`
`/irng/head__clo
`thing_women.
`gif
`/img/head_clo
`thing_women
`_shirts.gif
`
`/img/head_clo
`thing_women
`shirt topsgif
`/img/head_clo
`thing_women
`shirt teesgif
`/irng/head_clo
`thing_women
`_shirt_polo.gi
`f
`/img/head_clo
`thing_women
`_shirt_blouse.
`gif
`
`/img/head_clo
`thing_shoes.gi
`f
`/img/head_clo
`thing_shoe_m
`ensgif
`
`lapparel/result
`s_apparel.htm
`l
`
`lapparel/results
`_apparelvproper
`ties
`
`limg/appare
`l_icon.gif
`
`lapparel/brow
`se_appa.rel_sh
`oes.html
`lapparel/brow
`se_apparel_sh
`oe_rnens,html
`
`lapparel/brows
`e_apparel_shoe
`sproperties
`lapparel/brows
`e_apparel_shoe
`_mens.properti
`es
`
`limg/appare
`l_icon.gif
`
`limg/appare
`l__icon.gif
`
`Fig. 5B
`
`36
`
`6
`
`Shoes
`
`Shoes
`
`287
`
`36
`
`Men's
`
`Men's
`Shoes
`
`IPR2017-01039
`Unified EX1005 Page 9
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 9 0f 17
`
`US 6,366,910 B1
`
`2085
`
`287
`
`Shoes
`
`2086
`
`287
`
`Boots
`
`2087
`
`287
`
`Athletic
`
`2088
`
`287
`
`Sandals
`
`2089
`
`287
`
`Hiking and
`outdoor
`
`288
`
`36
`
`Women's
`
`2090
`
`288
`
`Shoes
`
`Men's
`Shoes
`
`Men's
`Boots
`
`Men's
`Athletic
`
`Men's
`Sandals
`
`Men's
`Hiking and
`outdoor
`Women's
`Shoes
`
`Women's
`Shoes
`
`lapparel/result
`s_apparel.htm
`l
`lapparel/result
`s_apparel.htm
`l
`/apparel/resu1t
`s_apparel.htm
`1
`lapparel/result
`s_apparel.htm
`l
`lapparel/result
`s_appa.re1.htm
`l
`lapparel/brow
`se_appare1_sh
`oe_w0men.ht
`ml
`lapparel/result
`s_appare1.htm
`1
`
`Fig. 5C
`
`limg/appare
`lapparel/results
`_apparel.proper 1_icon.gif
`ties
`lapparel/results
`_apparel.proper
`ties
`lapparel/results
`_apparel.proper
`ties
`lapparel/results
`_apparel.pr0per
`ties
`lapparel/results
`_apparel.proper
`ties
`lapparel/brows
`e_apparel_shoe
`_women.proper
`ties
`lapparel/results
`_appareliproper
`ties
`
`limg/appare
`l_icon.gif
`
`limg/appare
`1_icon.gif
`
`/img/appa.re
`1_icon.gif
`
`limg/appare
`1_icon.gif
`
`limg/appare
`1_icon.gif
`
`limg/appare
`l_icon.gif
`
`/img/head_clo
`thing_shoe_m
`en shoesgif
`/img/head__clo
`thing_shoe_m
`en bootsgif
`/img/head_c1o
`thing_shoe_m
`en ath1etic.gif
`/img/head_c1o
`thing_shoe__m
`en sandalsgif
`/img/head_c1o
`thing__shoe__m
`en hikinggif
`/img/head_clo
`thing_shoe_w
`omen_shoes.g
`if
`/img/head_clo
`thing_shoe__w
`0men_shoes.g
`if
`
`IPR2017-01039
`Unified EX1005 Page 10
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 10 0f 17
`
`US 6,366,910 B1
`
`Priority Descriptor
`Priority2
`brand|name|store
`
`brandlnamelstore|platform|cpu_type|
`cpu_manufacturer|cpu_speed
`
`Priority3
`description|categorylsubcatcgory]
`item typelbrandlnamelstore
`descriptionlcategorylbrandlnamel
`store|platform|cpu_typel
`cpu manufacturerlcpu speed
`nameIdestinationlorigdestllorigdestZ description
`|origdest3 |provider
`brandlnamelstore
`
`descriptionlcategorylsubcategory]
`item type|brand|name|store
`descn'ptionlcategory|subcategory|
`item typelbrandlnamelstore
`
`ID Priorityl
`2
`category|subcategory|item_type
`
`3
`
`category
`
`categoryIsubcategory
`
`category]subcateg0ry|item_type
`
`4
`
`5
`
`6
`
`categorylsubcategorylitem_type
`
`brandlnamelstore
`
`Fig. 6
`
`IPR2017-01039
`Unified EX1005 Page 11
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 11 0f 17
`
`US 6,366,910 B1
`
`GoodTerrns BadTerms
`
`tv video
`
`Special Terms
`
`Id
`
`2
`
`3
`28
`29
`
`4
`31
`237
`238
`239
`240
`241
`
`DisplayName
`
`Electronics
`
`Computer Hardware
`Desktop computers
`Laptop computers
`
`Travel
`Packaged Travel
`Beach and resorts
`Cruises
`Boating and watersports
`Cycling
`Hiking climbing and trekking
`
`5
`
`Toys and Games
`
`6
`34
`272
`2034
`2035
`2036
`2037
`273
`2038
`2039
`2040
`
`35
`279
`2057
`2058
`2059
`2060
`
`36
`287
`2085
`2086
`2087
`2088
`2089
`288
`2090
`
`Apparel
`Men's Apparel
`Men's Shirts
`Men's Tops
`Men's T-shirts
`Men's Polo and henley shirts
`Men's Dress shirts
`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
`Women's Polo and henley shirts
`Women's Dress shirts and blouses
`
`Blouse
`
`Shoes
`Men's Shoes
`Men's Shoes
`Men's Boots
`Men's Athletic
`Men's Sandals
`Men's Hiking and outdoor
`Women's Shoes
`Women's Shoes
`
`Fig. 7
`
`IPR2017-01039
`Unified EX1005 Page 12
`
`

`

`666| “*WRU
`
`US 6,366,910 B1
`
`8‘SLT
`
`
`
`O]OdSUIdLIOGY/JeIM\YDEqINC,
`
`
`SHIYssuapy/joreddysua
`
`
`SATIOBJOJWIYSO[Og
`
`
`
`
`
`
`
`Apr. 2, 2002
`
`Sheet 12 of 17
`
`U.S. Patent
`
`L08
`
`
`
`6L
`
`c08
`
`XOpuy
`
`IPR2017-01039
`Unified EX1005 Page 13
`
`IPR2017-01039
`Unified EX1005 Page 13
`
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 13 0f 17
`
`US 6,366,910 B1
`
`GPS Index
`Builder
`
`901
`
`Add entries to
`classi?cations
`
`902
`Add entries for good
`terms
`
`903
`Add entries for bad
`terms
`
`———-—-——>
`
`904
`Select next dept table
`
`all dept
`tables already
`selected?
`
`907
`Create term index table
`
`906
`Add dept table to
`term table
`
`1
`
`Return
`
`}
`
`Fig. 9
`
`IPR2017-01039
`Unified EX1005 Page 14
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 14 0f 17
`
`US 6,366,910 B1
`
`Add D t t bl
`to Terreri) T211:
`
`(dept table)
`
`._.__—’
`
`1001
`Select next item in dept
`table
`
`selected?
`
`Collect priority 2 terms
`
`1004
`Update priority 2 entry
`
`1005
`Collect priority 3 terms
`
`1006
`Update priority 3 entry
`
`Fig. 10
`
`IPR2017-01039
`Unified EX1005 Page 15
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 15 0f 17
`
`US 6,366,910 B1
`
`GPS Search
`Engine
`
`(query, result)
`
`1101
`Submit query (result)
`
`1102
`
`Prioritize scores
`
`—-—>
`
`1103
`Select next dept
`starting from ?rst
`
`all dept
`already
`selected?
`
`Traverse
`(root, false)
`
`Fig. 11
`
`IPR2017-01039
`Unified EX1005 Page 16
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 16 0f 17
`
`US 6,366,910 B1
`
`(
`
`Traverse
`
`l
`
`(classi?cation,
`ancestor in result)
`
`Ancestor in
`result?
`
`1202
`Remove from result
`
`Classi?cation in
`result?
`
`1204
`Set ancestor in result
`
`Select next child
`classi?cation
`
`classi?cation
`already
`selected?
`
`1207
`Traverse (selected
`classi?cation
`ancestor in result)
`—I
`
`sumcient
`children in
`result?
`
`1210
`
`add password
`classi?cation to result
`
`1211
`
`remove child
`classi?catlons from
`result
`
`F 12
`
`<
`
`Return
`
`1
`
`IPR2017-01039
`Unified EX1005 Page 17
`
`

`

`U.S. Patent
`
`Apr. 2, 2002
`
`Sheet 17 6f 17
`
`US 6,366,910 B1
`
`GPS
`Hierarchical
`Displayer
`
`1301
`
`Input Query
`
`1302
`Invoke GPS search
`engine
`
`4
`1303
`Select next dept with
`highest score
`
`already
`selected?
`
`1305
`Display dept name
`
`1306
`Select next entry for
`selected dept with
`highest score
`
`all entries
`already
`selected?
`
`1308
`Display entry name
`
`Fig. 13
`
`IPR2017-01039
`Unified EX1005 Page 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.
`In the emerging ?eld of electronic commerce, many
`thousands of products are available to be purchased elec
`tronically. For example, an online retailer may offer for sale
`electronic devices, major appliances, clothing, and so on.
`The dif?culty a potential purchaser faces is identifying a
`particular product that satis?es 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 ?elds in the
`database. Thus, many products that are of no interest to the
`potential purchaser are identi?ed. 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
`classi?cation that contains products that are most likely of
`interest. For example, the potential purchaser may select an
`electronics device classi?cation, a home electronics sub
`classi?cation, and a television sub-sub-classi?cation. The
`hierarchical classi?cation of products has several problems.
`First, many users of computer system do not fully under
`stand the concept of hierarchical classi?cations. Thus, it is
`dif?cult for such users to use such a classi?cation-based
`system. Second, products may not fall conveniently into any
`one classi?cation. For example, a combination VCR and
`television could be classi?ed as a VCR or a television. It is
`unlikely that an online retailer Would have a separate clas
`si?cation for such a combination. Therefore, a potential
`purchaser may not even be able to locate the products of
`interest using a hierarchical classi?cation system.
`It Would be desirable to have a product search technique
`that Would combined the advantages of the search systems
`and the classi?cation-based systems and that minimiZes their
`disadvantages.
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`SUMMARY OF THE INVENTION
`Embodiments of the present invention provide a method
`and system for querying hierarchically classi?ed data. The
`
`65
`
`2
`system of the present invention ?rst receives a query request.
`The system then identi?es classi?cations of the data that
`may satisfy the received query request. The system then
`displays the identi?ed classi?cations. In response to selec
`tion of a displayed classi?cation, the system displays sub
`classi?cations When the selected classi?cation has sub
`classi?cations and displays the data Within the classi?cation
`When the selected classi?cation has no sub-classi?cations.
`In another aspect, the present invention provides a system
`that generates search results for items that are hierarchically
`classi?ed. For classi?cations Within the hierarchy of
`classi?cations, the system generates a search entry contain
`ing terms describing the items Within that classi?cation. The
`system then receives a search criteria. The system selects as
`initial search results those classi?cations 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 classi?cations. This adjustment
`may include removing sub-classi?cations of a classi?cation
`that is in the initial search results or adding a parent
`classi?cation to replace multiple child classi?cations 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 3B illustrate example contents of a travel
`table and of an apparel table.
`FIG. 4 illustrates a hierarchical organiZation of the items
`in the apparel table of the product database.
`FIGS. 5A, 5B, and 5C illustrate an example organiZation
`of the broWse tree descriptor ?le.
`FIG. 6 illustrates the contents of a sample priority descrip
`tor ?le. The priority descriptor ?le contains an entry for each
`department represented in the product database.
`FIG. 7 illustrates example contents of the special terms
`?le.
`FIG. 8 illustrates the contents of the GPS index.
`FIG. 9 is a How diagram illustrating an example embodi
`ment of the GPS index builder.
`FIG. 10 is a How diagram of an example routine to add a
`department table to the term table.
`FIG. 11 is a How diagram of an example implementation
`of the GPS search engine.
`FIG. 12 is a How diagram of an example implementation
`of the traverse routine.
`FIG. 13 into ?oW 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 classi?cation hierarchy. For example,
`if the items are articles of clothing, then classi?cations may
`be “shirts,” “pants,” and “shoes,” and sub-classi?cation of
`“shirts” may be “T-shirts,” “casual shirts,” and “dress
`shirts.” The GPS system inputs a search criteria from a user,
`searches for the classi?cations of items that best match the
`search criteria, and displays those classi?cations in an order
`
`IPR2017-01039
`Unified EX1005 Page 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 classi?cations of items, rather than displaying informa
`tion about any individual items. The user can then select a
`displayed classi?cation to vieW the sub-classi?cations
`Within that classi?cation or, if that classi?cation has no
`sub-classi?cation, the items Within that classi?cation.
`When the GPS system inputs a search criteria, it scores
`each classi?cation in the classi?cation hierarchy to indicate
`the degree to Which the classi?cation contains items that
`match the search criteria. For example, the GPS system
`Would generate a score for each of the “shirts,” “pants,” and
`“shoes” classi?cations and for each of the “T-shirts,” “casual
`shirts,” and “dress shirts” sub-classi?cations. The GPS sys
`tem then selects those classi?cations or sub-classi?cations
`With the highest scores and displays them in order based on
`their score. Because users often ?nd it dif?cult to interface
`With hierarchically presented information, the GPS system
`in one embodiment displays the names of the selected
`classi?cations With no indication of Where the classi?cations
`are Within the hierarchy. For example, if the classi?cations
`of “dress shirts” and “shoes” have the highest scores, then
`the GPS system may simply list the classi?cation names as
`folloWs:
`dress shirts
`shoes
`If the user then selects “shoes,” the GPS system displays the
`sub-classi?cations 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 classi?cation Within the
`hierarchy, various parent and child classi?cations and more
`generally various ancestor and descendent classi?cations
`may have high scores. For example, both the “shirts”
`classi?cation and the “dress shirts” sub-classi?cation may
`have high scores. In one embodiment, the GPS system does
`not display any descendent classi?cations of a displayed
`classi?cation. For example, if the GPS system selects to
`display the classi?cation “shirts,” then it does not display its
`sub-classi?cation of “dress shirts,” regardless of the score of
`the sub-classi?cation. The user can alWays select the dis
`played ancestor classi?cation to vieW the descendent clas
`si?cations. In some situations, a parent classi?cation may
`have a relatively loW score, but many of its child classi?
`cations may have a high score. In such a situation, the GPS
`system may display the parent classi?cation rather than
`displaying each child classi?cation. For example, if the
`“shirts” classi?cation has a relatively loW score, but the
`“T-shirts” and “dress shirts” sub-classi?cations have high
`scores, the GPS system may decide to display only the
`“shirts” classi?cation. The GPS system may set the score of
`the “shirts” classi?cation to that of its highest sub
`classi?cation so that the displayed classi?cation Will be
`ordered based on the score of its sub-classi?cations.
`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 ?ve
`departments: clothing and accessories 101, electronics 102,
`computer hardWare 103, toys and games 104, and travel 105.
`The item in each of these departments are classi?ed into
`categories, sub-categories, and possibly a sub-sub-category
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`4
`referred to as item type. For example, the clothing and
`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. 1B illustrates the display
`of the search results. Rather than displaying the particular
`items that best match the search criteria, the GPS system
`displays the classi?cations of items that best match the
`search criteria. The GPS system orders the classi?cations
`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 ?rst.
`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 items that satis?es the
`search criteria. In this example, the GPS system has listed 10
`classi?cations of the clothing and accessories department.
`The GPS system highlights the ?rst eight classi?cations
`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
`classi?cations do not contain the Word “shirts” in their
`sub-category names. Rather, the Word “shirts” may have
`been contained in a description ?eld for an item Within those
`classi?cations. For example, the sub-category “Men’s Ties”
`may have had an item that contained the Word “shirts” in its
`description ?eld. The placing of the Word “shirts” in paren
`thesis indicates that the Word Was not found in the name of
`the sub-category. In general, the GPS system highlights
`(e.g., bolds) the names of those classi?cations in Which
`every item should satisfy the search criteria. For example,
`the ?rst eight displayed classi?cations 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 classi?cations Within the travel
`department Were loWer than the score for the classi?cations
`in the clothing and accessories department.
`Once the GPS system displays the search results, as
`shoWn in FIG. 1B, a user may select one of the classi?ca
`tions to vieW detailed information about the classi?cation.
`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 classi?cation, the GPS system
`displays information describing the items Within that clas
`si?cation. If the selected classi?cation has sub
`classi?cations, then the GPS system instead displays the
`sub-classi?cations.
`FIG. 2 is a block diagram illustrating components of one
`embodiment of the GPS system. The GPS search system
`comprises a product (or item) database 201, a GPS index
`builder 202, a priority descriptor ?le 203, the special terms
`?le 204, a broWse tree descriptor ?le 205, a GPS index ?le
`206, a GPS search engine 207, and a GPS hierarchical
`displayer 208. These components can be implemented as
`part of a general purpose computer system. The GPS system
`may be implemented as a server in a client/server environ
`ment such as the World Wide Web or may be implemented
`on a computer, such as a mainframe.
`The GPS index builder creates the GPS index, Which
`contains an entry for each classi?cation, based on the names
`
`IPR2017-01039
`Unified EX1005 Page 20
`
`

`

`US 6,366,910 B1
`
`6
`tion. Each departmenttable contains one entry for each item
`that is available to be purchased through the department.
`FIGS. 3A and 3Billustrate example contents of a travel table
`and of an apparel table. The tables includefield that specify
`the classification of each item within the classification
`
`table 301 contains a
`the travel
`hierarchy. For example,
`category and a sub-categoryfield. Thefirst entry in the travel
`table indicates that the item is in category 31 and sub-
`category 237. The entries also contain variousotherfields 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 termsfile, 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 (e.g., classification 237 is a sub-
`category ofclassification 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
`variousclassifications. 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
`classified into three levels: c