75 Inventors: Patrick J. Ferrel, Seattle; Randy Kerr,
`Redmond; Krishna Nareddy, Bellevue;
`Krishna Uppala, Redmond, all of
`Wash.
`73 Assignee: Microsoft Corporation, Redmond,
`Wash.
`This patent issued on a continued pros-
`ecution application filed under 37 CFR
`1.53(d), and is subject to the twenty year
`pass" provisions of 35 U.S.C.
`
`*
`
`Notice:
`
`Z.
`
`United States Patent (19)
`Ferrel et al.
`
`USOO5907837A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,907,837
`*May 25, 1999
`
`54 INFORMATION RETRIEVAL SYSTEM IN AN
`ON-LINE NETWORK INCLUDING
`SEPARATE CONTENT AND LAYOUT OF
`
`5,491,820 2/1996 Belove et al. .......................... 395/600
`5,493.728 2/1996 Solton et al. ........................... 395/250
`5,513,126 4/1996 Harkins et al. .
`. 364/514 A
`
`PUBLISHED TITLES
`
`5,546.577 8/1996 Marlin et al. - - - - - - - - - - - - - - - - - - - - - - - - - - - 395/600
`
`FOREIGN PATENT DOCUMENTS
`
`O 622 743 A2 11/1994 European Pat. Off.
`0 749 081 A1 12/1996 European Pat. Off..
`OTHER PUBLICATIONS
`European Search Report dated Oct. 13, 1998, corresonding
`to EPO Application No. 96118399.3–2201.
`(List continued on next page.)
`Primary Examiner Paul V. Kulik
`Assistant Examiner Jean M. Corrielus
`Attorney, Agent, or Firm-Banner & Witcoff, Ltd.
`57
`ABSTRACT
`A information retrieval System wherein design and content
`are Separated. Within a Section of a title, a designer can
`layout pages with controls that define areas for content to be
`inserted into the pages. Two commonly used controls in the
`System are a Static Story control, wherein a preselected Story
`is Statically placed on a page in the area defined by the
`control, and a dynamic Story control, wherein the designer
`defines Search objects to retrieve Stories. An information
`retrieval (IR) server indexes and Searches Stories in titles.
`Indexing takes place when a title is released to the network
`by a publisher workstation. The IR server interrelates title,
`Section and Story objects by their globally unique identifiers
`and creates a routing table which is used to locate objects
`acroSS multiple database partitions. The IR Search Service is
`requested in tWO different ways at customer runtime. The
`first way is the resolution of the search objects to retrieve
`matching Stories. The retrieved Stories are concatenated and
`3,670,310 6/1972 Bharwani et al. ................... 340/172.5
`d into th
`defined by the d
`trol wh
`4.255.796 3/1981 Gabbe et al. .....
`... 364/900
`4,642,762 2/1987 Fisanick ...
`so poured into Ine area delined by the dynamic control Wnen
`4,754,326
`6/1988 Kram et al.
`... 364/900
`the title is viewed. In the second way, the IR search service
`4,775,956 10/1988 Kaji et al. ..
`... 364/900
`is requested when a Search is initiated by a customer using
`4,845,659
`7/1989 Gifford al.".
`... 395/563
`a “find” dialog to Search acroSS all Stories in one or more
`4,939,689 7/1990 Davis et al. ..
`... 364/900
`5,197,005 3/1993 Shwartz et al. ...
`E, titles, both dynamic and static.
`5,251,316 10/1993 Anicket al. ......
`... 395/600
`5,491,818 2/1996 Malatesta et al. ...................... 395/600
`65 Claims, 24 Drawing Sheets
`
`21 Appl. No.: 08/560,281
`22 Filed:
`Nov. 17, 1995
`
`Related U.S. Application Data
`
`63 Continuation of application No. 08/503,343, Jul. 17, 1995.
`(51) Int. Cl. ................................................ G06F 17/30
`52 U.S. Cl. .............................. 707/3; 707/103; 707/104;
`707/500; 707/517; 707/525; 707/522; 707/526
`58 Field of Search ..................................... 395/600, 614,
`395/615, 610; 707/522, 104,103, 3,500,
`517, 525,526; 358/403
`
`56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`as
`
`
`
`
`
`
`
`i
`
`692
`k FINDw dAlog
`
`CUSTOMER QUERY 22
`TTLE A /2 PublicArlo
`T
`Stora
`GE
`
`Mao
`
`LAYOUS
`
`PUBLISHER
`
`o
`
`CoNEN
`
`
`
`story
`
`sa
`
`a22
`
`QUERY
`
`92
`
`NFoRMATON
`RTRWA
`
`
`
`RESSPAN
`696
`
`RESUS 594
`
`398
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 1 of 51
`
`

`

`5,907,837
`Page 2
`
`OTHER PUBLICATIONS
`“Structured Documents' edited by J. André, R. Furuta & V.
`Quint, Cambridge Series On electronic publishing, 2, First
`published 1989.
`Williams, J.H. “An automatic Indexing On-Line Text
`Retrieval System” U.S. Government/NTIS, Jan. 1969.
`Cove, J.F.; Walsh, B.C.; “ONline text retrieval via brows
`ing” Information Processing & Management, Jan. 1988.
`Macleod, I.A., “A query Language for retrieving informa
`tion from hirachic text structures' IEE/INSPEC, Jan. 1991.
`Andre et al. “Structured Documents”, Cambridge University
`Press, Jan. 1989.
`C Thanos, “Multimedia Office Filing Elsevier Science
`Publishing Company Inc, Jan. 1990.
`Paul Nora “The Times they are a changin'::The Los Ange
`les Times on the Web)(World Wide Web) Searcher, V4, né
`p38(10), Jun. 1996.
`David K, Gifford “Polychannel systems for mass digital
`communication' Communications of the ACM, v33, n2,
`p71-83, Feb. 1992.
`
`Hermann et al. “Retrieval of Document Images. Using Lay
`out Knowledge” IEE/IN SPEC pp. 537-540, Jul. 1993.
`Salton, G “Information Storage and Retrieval” U.S. Gov
`ernment/NTIS, Jan. 1969.
`Lee, Lydia, “Alert New Media news & products-Search
`Engines: Keys to the Web Kingdom,” New Media, Aug.
`1995, p. 22.
`Rupley, Sebastian, “Trends: Trends & Technology Shaping
`the Personal Computer Market-Taming the Text Tiger,” PC
`Magazine, Jun. 13, 1995, p. 29.
`Rupley, Sebastian, “Trends: Folio's On-Line Business
`Library," PC Magazine, May 16, 1995, p. 32.
`Weiss, Aaron, “Hop, Skip, and Jump: Navigating the World
`Wide Web.” Internet World, Apr. 1995, pp. 41-44.
`December, John, “New Spiders Roam the Web,” Compu
`ter-Mediated Communication Magazine, vol. 1, No. 5, Sep.
`1, 1994, 3 pages.
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 2 of 51
`
`

`

`U.S. Patent
`
`May25, 1999
`
`Sheet 1 of 24
`
`5,907,837
`
`cO/
`
`OF
`
`SUL
`
`LbYSHSINENd
`
`
`
`/vO
`
`zYaHSIaNnd
`
`p/
`
`cll
`
`SLNOAVT
`
`ANSLNOOD
`
`NOLLVWINV
`
`GNNOS
`
`OAGIA
`
`SSIMOLS
`
`-LNALNOOD
`
`IOV
`
`WYSHSIdNnd
`
`&//
`
`
`
`INSLNODYAHLO
`
`91
`
`STWUL
`
`SLNOAVI
`
`LANALNOO
`
`INFINOD
`
`NOILVUNSISNOSO1SVE~a”OI4
`
`:ZYaWOLSND
`INOAWI\vel'SLU~*~2Hgauu ¢c%7
`
` :ool, 39vedOLS3INOAv)im“|NOWLWONENd_|Tw|oy/Ow
` JOVYOLS;daw¢4/73/\YAHLO.|9G!°
`
`
`Og/-VSMU.
`
`aunoy
`
`NYSWOLSND
`
`LuaWOLSND
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1019
`Page 3 of 51
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 3 of 51
`
`
`
`
`
`
`

`

`U.S. Patent
`
`May25, 1999
`
`Sheet 2 of 24
`
`5,907,837
`
`|
`
`|#8
`
`99/'|solidsa
`
`
`
`JASHSJULS
`
`A9Vd
`
`
`
`6&/"|woulda
`
`
`
`310|OM.|‘\|iaYoLLLee
`
`I}wOLIdaLE/HOZ02UaMSIA
`weeeeweeeeee||C6/~~1||Yoda“!yolda||LNaWN90dlC6.' Wid3N;||uaHsligndO6/xNSE
`|ty'|GB/G6/
`
` I=I||||||[____NOUVLSHYOMUSHSIIENd
`|Loarao|uvas
`(|LogroudYyOLids
`
`
`SINSNOdWOOWALSASSISVE
`
`WYOMLAN
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1019
`Page 4 of 51
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 4 of 51
`
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 3 of 24
`
`5,907,837
`
`------------------------
`292
`HOST DATA CENTER
`
`“...)
`
`/OO
`PUBLISHER
`O/02 M2 124 vulneola
`t
`PSING
`SY
`g 24 {
`SERVER
`
`a
`PUBLISHER
`2 :
`PUBLISHER
`M /26
`
`
`
`MULTIMEDIA
`Se21.6% I.R.
`SERVICE
`
`27O
`
`272b
`
`I.R.
`SERVER
`N
`
`MULTIMEDIA
`I.R.
`PUBLISHING
`SERVER
`SYSTEM
`SERVER 2442
`
`27%ay 2.62
`DB
`DB
`SERVER
`} SERVER
`N
`ADMIN, SERVERS:
`SERVICE MAP25
`DiSEAichER 267 --------
`242
`262
`256
`
`257
`CUSTOM
`GATEWAY
`-------------
`
`ESA
`PROVIDER
`
`s
`CUSTOMER
`1
`. O
`./1.
`/64-1
`CUSTOMER
`N
`
`|
`
`|
`
`FG.3
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 5 of 51
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 4 of 24
`
`5,907,837
`
`PAGE LAYOUTS + CONTENT OBJECTS = DISPLAYED PAGES
`Front Page Section -330
`
`StoryControl
`338
`
`
`
`
`
`
`
`
`
`St E. 372 Page 2
`AC/
`gated
`Sfoy
`06 t
`I2.
`g
`Sect
`
`
`
`Style Sheet X Style SheetY
`357
`352
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 6 of 51
`
`

`

`U.S. Patent
`
`May25, 1999
`
`Sheet 5 of 24
`
`5,907,837
`
`S1S3NDIYGINd
`
`SOP
`
`ooYSMSIA
`
`HOuvaSR
`
`YAANSS
`
`
`
`W9011S3NO34Y—>H913488/
`IN3OIS3Y—-NONYyOLIgSi1935f°0uUd
`
`
`COP
`
`oa”G94
`
`CLP
`
`Sd
`
`LNINNI00
`
`YOLIGS
`
`IN3LNOD
`
`S193°80
`
`PSL
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1019
`Page 7 of 51
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 7 of 51
`
`
`
`
`

`

`
`
` axXauaHsSMEnd]fO&FFOvVYOLS
`
`fcel
`
`
`
`oolYAIHSIIEGNd
`
`WALSAS4OMJIA110GNVIdV
`OO4IMZIAO°O|4
`
`U.S. Patent
`
`May25, 1999
`
`Sheet 6 of 24
`
`5,907,837
`
`Y3SHSITENd
`
`soo
`
`
`
`yuaNousLoardo
`
`YSHSI1EGNdGNV
`
`JOVAYNSLNI
`
`110391AuaS
`
`LN3IT9UI
`
`SEF
`
`YySHSITENd
`
`s711d
`
`Y3HsITeNnd
`
`STOYLNOD
`
`WOLSND
`
`NOILVAYOAN
`
`TWASIYLAY
`
`ADIAYNAS
`
`
`
`ysaNousLoarao
`
`
`
`YSHSITENdGNV
`
`AJDVAYALNI
`
`BEY
`
`LAN3IT9Ui
`
`
`
`T10SD!IANaS
`
`GE
`
`MaHSIIENd
`
`sia
`
`YSHSIMENnd
`
`STOYLNOD
`
`WOLSND
`
`FEV
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1019
`Page 8 of 51
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 8 of 51
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 7 of 24
`
`S907837
`
`O99
`
`NO
`S
`N5
`
`Q
`S
`
`1 NEWTTOOO
`
`
`
`1XEL OB99)\/]zz ç ~! Sal?,3dOHdGNIH
`
`
`
`
`
`
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 9 of 51
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 8 of 24
`
`5,907,837
`
`
`
`
`
`
`
`
`
`2379O379
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 10 of 51
`
`

`

`U.S. Patent
`
`May25, 1999
`
`Sheet 9 of 24
`
`5,907,837
`
`A
`
`NolLovNo|479
`aasva@SLL
`
`YOsLIVM
`
`
`
`NIALVOIAWNNOLLO3SNOILO3S
`
`NOLLOSSNOLLN10S3u
`
`
`IN3AZUasNn969
`
`
`AV1dSIG269INSINODLGDHOUVAS
`
`
`NI39VdNOLLISINDSV1o3rgo
`Losu1396914
`
`
`ONV0991XGN1XGN
`7JULaSUVd|—2C9,
`
`YALNdWODYSAWOLSNDLVYSMAIA
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1019
`Page 11 of 51
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 11 of 51
`
`
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 10 of 24
`
`5,907,837
`
`(JEHSITEIT,
`||ÅRJOLS|
`
`S1 ThOAVT
`
`09
`
`O//
`
`ET11||1
`
`
`
`
`
`62ÅRHETTO (JEWO 1ST) O
`
`
`
`&6&º68 s?n?nsas
`
`19/
`
`?OTWICI A CINI
`
`6269
`
`ENVd S1 TITISEN
`96.9
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 12 of 51
`
`

`

`U.S. Patent
`
`May25, 1999
`
`Sheet 11 of 24
`
`5,907,837
`
`GEL
`
`OFL
`
`Y3SAY3SOLGNSS
`
`
`
`SLINSIYSAIZOSY
`
`
`
`CkLWNISLINSAYAV1dSIG
`
`SLINSSY
`
`oO
`
`301AuNasNOWL
`
`|GINOWLSSS139J!N90LyGELClh3WILGvot
`
`GELHOUWISNOILOSS
`
`GEL93dSSLINSSYNOLLOaZS
`
`
`9/4ONToyLuvs)jO14OOTVICGNISGNVLOSradOHOYVAS
`O69|soon|COPac
` ANVWd
`
`uouvasOL2NSHM‘dadS1YOS¥NISAHOUVSS
` ATIVINSWSYONI
`
`vidaW3LSASUIOZL
`
`LIDAsIDIdSG68AYANDALV3U94OSLINSIY
`—~saind
`Canoa_)|
`
`‘dlNOLLOZS139JAIOS3Y
`
`OlLOVYasn
`
`ATVLL3SMONd
`
`ASMONE
`
`AYOLDANIG4S3A
`
`LOL
`
`ALVOIAVN
`
`O3dS
`
`G3LYOSSHV
`
`yOJVivd13D
`
`OLNIMOT1S
`
`SINVNAQ
`
`STOYLNOD
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1019
`Page 13 of 51
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 13 of 51
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 12 of 24
`
`5,907,837
`
`
`
`YJEVANJES
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LOBTEJO
`
`SOIT,5)
`
`29/
`
`.22%
`
`/228/
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 14 of 51
`
`

`

`May 25, 1999
`
`Sheet 13 of 24
`
`U.S. Patent
`
`5,907,837
`TITLE PUBLISHING FLOW DIAGRAM
`(server side )
`
`
`
`FG.3
`
`500
`
`RECEIVE
`TRANSMITTED COS
`FILE
`(bbObSVC.C)
`
`COPY RECEIVED
`COS FILE TOR
`SERVER
`(bbobSvc.dll)
`
`COS SERVER
`NOTFESR SYSTEM
`OF RECEIVED COS
`FILE
`(NT File System)
`
`R SERVER UPDATES
`INDEX WITH NEW,
`MODIFIED AND
`DELETED OBJECTS
`OF RECEIVED COS
`FILE
`(Rindexing Service)
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 15 of 51
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 14 of 24
`
`5,907,837
`
`9/6
`
`R INDEXING
`
`a/
`
`GET PUBLISHED PACKET
`
`
`
`CHECK iN OBJECT
`NFORMATION TABLE
`
`522
`
`824
`EXISTSN
`OBJECT ABUE 2
`
`
`
`NO
`
`926
`
`GET ROOT
`OBJECT
`
`
`
`
`
`625
`CREATE ENTRY IN
`CONTAINERTABLE;
`CREATE SOURCE IN
`ROUTING TABLE
`
`
`
`33O
`
`632
`
`NO
`
`PROCESS ROOT
`CONTENT FOLDER
`
`YES 934
`
`PROCESS TITLE
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 16 of 51
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 15 of 24
`
`5,907,837
`
`898ON
`
`
`
`HOYVASSYOW
`
`éSLOarao
`
`SS390¥d
`
`LNALNOD
`
`YANIVLNOOWOud
`
`
`
`AVLLOsrgOHOYVAS
`
`AINOQ
`
`SSA
`
`
`
`3LVOdN-GalsIQOW
`
`
`
`LOSrdOHOYVAS
`
`AVaVL
`
`
`
`HOYVASSS3DOV
`
`Loarao
`
`
`
`NIAY.LNSSLV3SYd
`
`
`
`id3fsOHOYVAS
`
`
`
`NIAYLNSSLV3Y9
`
`
`
`A198VLYSNIVLNOD
`
`“S18VL
`
`
`
`NiAYLNS3.13740
`
`
`
`/L93°8OHOYVSASHOYVSSTIL139
`‘-A1aVLLXALNOOOSENISLOSreoO
`
`
`
`
`
`
`AYLNS3.13130NOILO3S
`
`$S3900ud
`
`SLNOLYOHS
`
`
`
`
`ONIX‘S1aVLOSNILOSraoZtE
`.‘378V1USNIVLNODOLSSoCG]5S)|4NIAMLNZ315740YOSLV3audD
`
`SONIYlNIANLNA315730YOS1V3ayu0
`
`ksLeNIAMLNA313730YOSLVaYO
`
`
`318VLOANILXALNOODSNOLLOZSTVL139
`
`
`
`NIAY.LNA3LVSYO
`
`
`
`/LOAaraOHOYVSAS
`
`
`
`‘JTavLLXSALNOO
`
`
`
`
`
`
`
`‘SIGVLOAN!LOArEOS3kNIAYLNS
`3LV3Y9D
`
`HUE
`
`S1LILNI
`
`
`
`NOILOASSSADOV
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1019
`Page 17 of 51
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 17 of 51
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 16 of 24
`
`5,907,837
`
`d568 FIG.I6
`
`R INDEXING
`
`DETERMINE
`EXISTING OBJECTS
`PARTITIONS BASED
`ON ROUTING TABLE
`INFORMATION
`
`956
`
`
`
`INFORMATION FROM
`THOSE PARTITIONS
`
`START
`PR oCESS CONTENN,
`
`ACCESS CONTENT - 662
`OBJECT
`
`
`
`EXIST IN
`OBJECT TABLE 2
`
`DETERMINE
`PARTITIONS BASED
`ON SOURCE AND
`PUBLISH DATE
`
`
`
`TABLE
`
`
`
`
`
`
`
`CREATE OBJECT
`INFORMATION
`TABLE ENTRY
`
`2
`69
`
`694
`
`CREATE INDEX
`ENTRIES IN
`PARTITIONS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`fMORE CONTEN
`OBJECTS 7
`
`NO
`
`5296
`
`RETURN
`
`
`
`YES
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 18 of 51
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 17 of 24
`
`5,907,837
`
`FIG. 7
`RESOLVING SEARCH OBJECTS
`902
`M
`
`
`
`9074
`
`
`
`START RESOLVE
`SEARCH OBJECT
`
`NOT PRESENT
`
`9/2
`OAO SEARCH
`OBJECT FROM
`SEARCH OBJECT
`TABLE
`
`
`
`RESOLVE
`SEARCH
`RECUEST
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CHECK
`N SEARCH
`OBJECT
`CACHE
`
`PRESENT
`
`
`
`
`
`
`
`
`
`
`SEND RESULTS
`FROM CACHE TO
`OUTPUT OUEUE
`
`
`
`
`
`
`
`WRITE RESULTS
`TO OUERY
`CACHE
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 19 of 51
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 18 of 24
`
`5,907,837
`
`FIG.8
`°/r RESOLVING SEARCH OBJECTS
`92O
`
`START RESOLVE
`SEARCH REOUEST
`
`PLACE SEARCH
`REQUEST IN
`REGUEST GUEUE
`
`GET FREE
`SUPERVISOR
`
`
`
`MAKE PARTITION
`SPECIFIC
`SUBORUERIES
`
`
`
`OUEUE THE
`SUBOUERES
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`GET AVAILABLE
`WORKER
`
`932
`
`SEND SUBQUERY
`TODATABASE
`SERVER
`
`
`
`GET RESULS
`FROM DATABASE
`SERVER
`
`ELMINATE
`DUPLICATES
`
`940
`
`939
`
`RETURN
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 20 of 51
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 19 of 24
`
`5,907,837
`
`
`
`AYANDYASNONIATOSAY
`
`
`|096
`
`AYANODENSGNSS
`JTISVUVAV139
`aSvavivdoL
`AYSsnNodENns
`SHLANAND
`6lSl4
`O1S3HOVDWOUS
`anandLNdino
`
`SLinsayanas|ON
`LN3S3udLON
`
`AHIVOAYAND
`SssaLvondnd
`
`0564|LYVIS
`
`isand3ySS390ud
`
`
`
`WaNyOM
`
`IN3S3ud
`
`LN3S3ud
`
`996
`
`
`
`£56-|4031HOWaHOS
`
`3ounos
`
`YSANgaS
`
` Y3SAN3S
`3SvVaevlvdWOUdOLGNVdX3
`SLINSAYLAD
`
`AILVNIWITSs1osgraoHOYVaSsS
`
`
`CVE
`
`886OlONVdX3
`
`S39uNOS
`
`OLALUM
`
`
`
`3DYNOSSHV
`
`saly¥anodsns
`
`AlDAdS
`
`
`
`NOLLILYVdANVW
`
`I1dIDAadS
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1019
`Page 21 of 51
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 21 of 51
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`
`OlaindGNY
`ylavi=:3781
`
`
`
`
`NOILILYVdGCLOGL,41W389
`
`S3X30NI193ra040She
`000!Auand—29
`
`
`
`
`
` YIpantZO|800!RETHSAY3NOIGIAONd
`
`
`
`31N0YS31LY3dOUd|NIANIS3SVEVLVG
`
`
`QNILNOYONILNOYGa)(clefuiNOUS0131MMNOILILYVd
`
`NOILILYWdNOILILYVd
`
`avaiVindS1InS3urC1NOWOaTION
`
`NAeet|YOSIANIaNSNOILILYd|3NNOS
`
`ONYAY¥3Nd),29Z0/naNJHOVO“08S20)a=gecor|e
`so)GLO!
`
`
`
`
`COWogySTIROVESOVIUHLYOSIAYIENS40100d]fouJ1GVLONILNOY
`
`
`S101JOIAYIS“YTAMFDIANIS“YTOLO729l4
`
`ssvoviveftwosinesans_|
`hoceo
`
`
`nanoIndio1SnanoS300
`aNVgaaagd
`
`fy|fy40yOeeeJDIANIS
`
`OV3YHIOV3YHI
`YIOVNYAL,|YO]Yny
`
`
`
`
`
`
`
`
`U.S. Patent
`
`May 25, 1999
`
`Sheet 20 of 24
`
`5,907,837
`
`QV3YNSLINS3IaIN3JAZLINS3a
`
`
`
`G3X30NI31MANaNDANS
`
`UCEL
`
`
`
`ININOLSINOISY
`
`OMOM
`
`Ol
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1019
`Page 22 of 51
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 22 of 51
`
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 21 of 24
`
`5,907,837
`
`IoD
`
`AF
`
`ASVEVLVO
`
`YSAAYNSS
`
`
`
`
` SEL nano||INdLNOHOUVaS)HOUVAS/NOILOAS NOILOSS/SWIL
`LOargo
`NOILVISNVUL
`
`mavi744,meviaitoarao8%say,PEW
` SLINSAY
`ONINOLLILYVd
`
`YAANASHOYVSS
`ALIMONd|HSIIENd|LNSWNDOG
`
`3TaV1W130LNAWND0G
`3Lvdging
`
`AYAND-OLZ
`
`
`£E4L~NOLMIOSSYAYAND
`SEFY3aSNO69
`
`SEO!
`
`YANYOM
`
`QVAaYyHL
`
`AYAND
`
`on
`
`SO
`
`ADIAYAS
`
`on
`
`ul
`
`1N3IN9Ulyasn
`
`
`
` ryYSNSIS3IG|P|[ean
`
`AyanoOe
`
`rTGNIS
`
`76/
`
`AYAND
`
`IGEL9CEL
`
`PEEL
`
`JAsvavivd
`
`SNOIWLILYVd
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1019
`Page 23 of 51
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 23 of 51
`
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 22 of 24
`
`5,907,837
`
`
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 24 of 51
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 23 of 24
`
`5,907,837
`
`
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 25 of 51
`
`

`

`U.S. Patent
`
`May 25, 1999
`
`Sheet 24 of 24
`
`5,907,837
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 26 of 51
`
`

`

`5,907,837
`
`1
`INFORMATION RETRIEVAL SYSTEM IN AN
`ON-LINE NETWORK INCLUDING
`SEPARATE CONTENT AND LAYOUT OF
`PUBLISHED TITLES
`
`This application is a continuation of application Ser. No.
`08/503,340 filed on Jul. 17, 1995.
`
`BACKGROUND OF THE INVENTION
`
`2
`SGML are Standards for tagging text in documents to be
`displayed in an on-line network. Documents that are for
`matted in HTML or SGML can be viewed by several widely
`distributed browsers such as Mosaic and Netscape for the
`Internet. These browser programs read SGML and HTML
`tagged documents and display them with proper formatting.
`However, the formatting information is stored with the
`browser and is not distributed by the publisher.
`Computer users look for information in disk-based com
`puter Systems and in on-line environments. In a personal
`computer environment, most personal computer users are
`used to a browsing model of navigating through content. On
`a personal computer the hard disks have been fairly large,
`but they have been of a manageable size until now. Users
`assembled the content on their disk themselves, So it is a
`finite Structure that users are fairly comfortable Searching
`through. The hard drive content has known context because
`of the way things are located Side-by-Side; it gives good
`organization to the material and it also permits casual
`Searching. Users don’t have to have a specific goal in mind
`but can browse and find things in a Serendipitous manner.
`But the problem with this is that it doesn’t scale well for
`large amounts of information.
`With going on-line, just the sheer Volume of content
`makes it unreasonable to browse in this way. Therefore,
`what is needed is a Searching Strategy that enables people to
`Specify more of a criteria or a specification to Some facility
`or agency that will actually go off and do the matching for
`them. When the search results or hits are received by the
`user, there will be a reasonable size of results that a user can
`actually browse. Some of the problems with this approach
`are that these results are often brought out of context, the
`user does not have any idea about the adjacent material, and
`it requires the user to be very goal directed.
`Some on-line systems, such as Microsoft Network
`(MSN), Prodigy, CompuServe and America Online have a
`type of a department Structure. In this structure there is a top
`level categorization of busineSS and finance or certain Spe
`cial interests, which provides one editorial view of Slicing
`content as a way to organize information for people to
`Search. The problem with this approach is, of course, that
`everyone's conception of where a certain topic resides may
`differ. For example, one person may look in one area for
`things on Scuba diving and Someone else may look under a
`totally different categorization. Because people conceive of
`topics Stored in different places, there is often a mismatch in
`finding things when one browses according to Someone
`else's classification or categorization.
`Another on-line system is the Internet World Wide Web
`(WWW). The WWW provides a rich medium by virtue of
`how links are constructed between related information. By
`utilizing links and citations, many different editors can
`propagate different ways of looking at content. So the
`WWW is not one structure but many structures. A user will
`often identify with a certain directory Service that matches
`the way they conceive of information which makes it easier
`to browse. The problem is, just because of the sheer size of
`the Web, it cannot be browsed exhaustively. A user is always
`left with a sense there's something else out in the Web. A
`user doesn’t have a very good Sense of completion in
`actually Searching.
`Some of the techniques to actually Search the Internet are
`crawler-based full-text indices. This type of indexer actually
`goes around traversing the different Internet Sites, building
`up an indeX as it travels, So that on Some basis of updating,
`people can Search and See what new content appears on the
`
`1. Field of the Invention
`The present invention relates to information retrieval
`Systems and more particularly, to a System and method for
`indexing, querying and retrieving information in an on-line
`network.
`2. Description of the Related Technology
`Microsoft Network, Internet, CompuServe, Prodigy, and
`America Online are examples of on-line networkS. End users
`typically access these networks using a microcomputer
`equipped with a modem. During an on-line Session, a user
`can use a variety of information-related Services and com
`munications Services, including news Services, weather
`Services, bulletin board Services, E-mail, and the like.
`While on-line Services are becoming increasingly
`popular, today's on-line applications are Still in their infancy.
`In fact, Significant problems continue to block independent
`content providers or publishers from deploying the type of
`Sophisticated and compelling Services that are necessary to
`provide a Sustainable on-line business. At the same time,
`providers of existing on-line Services are working to find the
`right technical busineSS model and usability Solutions that
`will promote acceptance beyond just an early-adopter audi
`CCC.
`In any large city, it is impossible for a Single individual to
`keep up with the activities and events unfolding in the
`community. Consequently, people turn to writers, reporters,
`editors, critics, and others, for help in understanding and
`Structuring the information available. In a related trend,
`broadcast media are increasingly unable to Satisfy the needs
`of a diverse populace. Consequently, in most markets,
`narrowcast media (media that have tailored and distributed
`their content to Smaller, well defined audiences) have
`become increasingly popular and profitable. In the on-line
`community this trend will be correspondingly more impor
`tant.
`One problem content providers encounter when creating
`applications for the mass market is the diverse audience. For
`example, Some customers will be interested in games, Some
`in business, Some in computer technology, and Some in
`movies. What information should content providers deliver
`to keep their customers satisfied? What is needed is a system
`that enables a content provider to create applications that
`blend the content provider's editorial voice with individual
`customization. For example, from within a particular
`application, a customer could indicate an interest in the
`computer busineSS and/or classical music, and be able to
`acquire additional information focused on these areas.
`Similarly, an on-line publication might automatically Syn
`thesize and prioritize content based on different consumer
`preferences.
`Current publication Systems include Software for elec
`tronically publishing Stories acroSS on-line networkS Such as
`CompuServe, America On-Line, or the Internet. Most of
`these Systems create and display Stories that are formatted in
`a Standard Generalized Markup Language (SGML) or
`Hypertext Markup Language (HTML). Both the HTML and
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 27 of 51
`
`

`

`3
`Web. But here again, users are often left with the sense of not
`knowing how complete a Search is. Different indices may
`have access to Some sites that others may not. There is no
`real clear way of finding all the desired content. WAIS
`provides an Internet Server that indexes and retrieves text
`Strings over multiple databases. This server is based on the
`evolving 239.50 search protocol used with WAIS and
`Gopher Sites.
`An example of a WWW crawler-based indexer is the Web
`Crawler. Another WWW indexing engine is known as
`Lycos. The LycoS engine makes a weighted random choice
`of which links to follow in a document, biased towards
`documents with multiple links pointing at them (implying
`popularity) and links with shorter path names (URLS), on the
`theory that short path names tend to imply shallower Web
`links and, therefore, more breadth. LycoS tries to make a
`Summary of a document to preserve its content while
`alleviating the inefficiency of cataloging it in its entirety. The
`LycoS Search language does not Support Boolean queries
`(AND, OR, and so forth) or adjacency searches.
`Another WWW indexer under development is the Harvest
`project. Harvest provides a means of gathering and distrib
`uting indexing information; Supports the construction of
`different types of indexes for each information collection;
`and provides caching and replication Support.
`Another problem of the current indexerS is that it takes a
`lot of time to try to traverse the servers on the Web. When
`new content is added to a server that has just been accessed
`by a current indexer, it may be a long time period before the
`indexer returns to index the Server again. Alternately, con
`tent may be removed from a Server, but the indexer has no
`way to know this event until the server is revisited. These
`indexers are also vulnerable to “robot exclusion” that pre
`vent a Web server from being indexed. A “No Robots'
`Standard is applied to Some Web Servers, which prevents any
`of the content on the Server from being included in the index.
`What is desired is an indexing and Search component of an
`information retrieval Service that is always up-to-date and
`can indeX all the content on the System or on-line Service.
`Getting content to an on-line Service will not be a major
`problem, but once all this content SWells to an enormous
`size, the problem is going to be the user's ability to Wade
`through all of the content to find the Specific things they
`want. The on-line industry needs the ability of content
`providers to tag their information and target their customers
`to make this connection from both Sides to make the content
`delivery a success. So to depict this problem with the
`traditional on-line Services, an administrator may go with
`the approach of providing a new Service that will be put
`on-line and will locate it in a couple of Spots. The problem
`that frequently occurs is that a user may think the Service
`resides Somewhere else and therefore, a connection is not
`made. What is needed therefore is a way of full-text based
`Searching across an entire on-line Service. This Searching
`should allow Searches over text like the properties (e.g., for
`images, stories, Sound clips) and titles of different available
`Services, as well as Searching within the titles, e.g., within an
`article or Story. Thus, for example, a user would have the
`ability to Search over Services by a description of properties.
`A publisher could define a Search object to retrieve
`content matching desired criteria. The publisher could also
`Specify where to Search. Thus, a System and method for
`indexing Structured titles and Search objects would be an
`advance in the industry.
`The above disadvantages are overcome by the present
`invention.
`
`1O
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,907,837
`
`4
`SUMMARY OF THE INVENTION
`An information retrieval (IR) server indexes and Searches
`Stories and other content objects, Such as images and Sound
`clips, in titles in an on-line network. Indexing takes place
`when a title is released to the network by a publisher
`workstation. If a content object is deleted from the network
`server, the IR server is notified. Thus, the IR server has a
`current index of all the content on the network as Soon as the
`content is published or deleted.
`The IR server interrelates title, section and story objects
`by their globally unique identifiers and creates a routing
`table which is used to locate objects acroSS multiple database
`partitions. A partition is Source and date range specific. An
`IR search service is requested in two different ways by the
`title viewer at the customer WorkStation. First, a Search is
`requested for each dynamic control or display region in a
`title. A dynamic control is associated with Stories retrieved
`on the basis of a Search query defined by the publisher.
`Second, a Search can be initiated by a customer who uses a
`“Find” dialog to search across all stories in a title, both
`dynamic and static. The IR function is made possible by the
`decomposition of a title into content and design objects and
`it satisfies the need for fast and efficient Search over a
`low-bandwidth communication path, e.g., 9600 baud.
`One aspect of the present invention is a method of
`computerized Searching, comprising the Steps of Storing a
`plurality of content in a publication Storage; publishing a
`title to the publication Storage, wherein the title comprises
`Separate content and layout, wherein the layout includes a
`Search query associated with a control, and wherein the
`control defines a region for displaying results of the Search
`query; retrieving content Satisfying the query from the
`publication Storage; and displaying the retrieved content in
`the control.
`Another aspect of the present invention is a computerized
`information retrieval System, comprising: a publication
`Storage, comprising: a content Storage, an indexer for index
`ing the content, and a Searcher for Satisfying queries on the
`indexes, a designer providing a title with one or more Search
`objects, wherein each Search object defines a query; and a
`Viewer accessing the title and causing the Search objects to
`retrieve content to be displayed.
`Yet another aspect of the present invention is, in a
`computer network, an indexing System of a title having a
`title layout and content, wherein Said title layout includes
`Search objects, each of Said title layout, content and Search
`objects having an associated object identifier, and Said
`content having Search properties, the System comprising: an
`indeX Server receiving the title; a catalog database contain
`ing tables associating object identifiers with other informa
`tion including Search properties, an indeX Service executing
`on the indeX Server and accessing the catalog database; and
`a database Server Storing indeX associations between the
`Search properties and object identifiers provided by the
`indeX Service.
`Still another aspect of the present invention is a computer
`implemented method of Searching a title, comprising the
`Steps of: Storing content in a publication Storage; publishing
`a title comprising Separate content and layout to the publi
`cation Storage; and retrieving content from the publication
`Storage Satisfying a user query.
`Another aspect of the present invention is a method of
`computerized Searching, comprising the Steps of publishing
`a title to a publication Storage containing content, wherein
`the title comprises Separate content and layout, and wherein
`the layout includes a Search query; retrieving content Satis
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1019
`Page 28 of 51
`
`

`

`25
`
`S
`fying the Search query from the publication Storage; and
`displaying the retrieved content.
`Still yet another aspect of the present invention is a
`computerized method of electronic publication, comprising
`the Steps of: creating a title containing a Search query;
`Storing the title in a publication Storage; displaying the title,
`wherein the Search query retrieves content from the publi
`cation Storage.
`In a computer network, a Search System, comprising: a
`Search object Server for Storing the location of Search objects
`in a title and Search queries associated with the Search
`objects, a Search Server for decomposing the Search queries
`into a plurality of Subqueries, and a database Server for
`receiving Subqueries from the Search Server and providing
`object identifiers responsive to each Subquery.
`Another aspect of the present invention is a computer
`implemented method of Searching a title using a Search
`query, comprising the Steps of: Storing content in a publi
`cation Storage; checkin