US007231379B2
`
`(12)
`
`United States Patent
`Parikh et a].
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,231,379 B2
`Jun. 12, 2007
`
`(54) NAVIGATION INAHIERARCHICAL
`STRUCTURED TRANSACTION
`PROCESSING SYSTEM
`
`(75) Inventors: Prashant Parikh, New York, NY (US);
`Stanley Peters’ Menlo Park’ CA (Us)
`
`(73) Assignee: Noema, Inc., New York, NY (US)
`
`( * ) Not1ce:
`
`Subject' to any d1scla1mer,~the term of this
`$12318 11S siéggngsdé‘sog gig/listed under 35
`
`(21) Appl. N0.: 10/299,359
`
`(22) Filed:
`
`Nov. 19, 2002
`
`(65)
`
`Prior Publication Data
`Us 2004/0098381 A1
`May 20’ 2004
`
`(51) Int CL
`(200601)
`G06F 17/30
`(52) us. Cl. ...................... .. 707/2; 707/6; 707/3; 707/4
`(58) Field of Classi?cation Search .................. .. 707/1
`7070 3 4 5 6 7 8 9 10 100 101 102’
`’
`’
`’
`’
`’
`’
`’
`’
`’707 f1 03 1041’
`See application ?le for Complete Search histol’y
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`3/2000 Wical .......................... .. 707/5
`6,038,560 A *
`6/2002 Schwartz et a1.
`6,405,188 B1
`6,408,290 B1* 6/2002 Thiesson et a1. ............ .. 706/52
`6,510,406 B1
`1/2003 Marchisio
`*
`$21125; """"""""""" " 706/45
`6:678:677 B2 *
`1/2004 Roux et a1. .................. .. 707/3
`
`2/2005 Kumar et a1’
`
`6359212 B2
`* cited by examiner
`Primary ExamineriYicun Wu
`(74) Attorney, Agent, or F irmiMorgan & Finnegan LLP
`
`ABSTRACT
`(57)
`A method performed in a system having multiple navigable
`nodes interconnected in a hierarchical arrangement involves
`receiving an input containing at least one Word identi?able
`With at least one keyword, identifying at least one node,
`other than the ?rst node, not directly connected to the ?rst
`node, but associated With the at least one keyWord, and
`jumping to the identi?ed node. A transaction processing
`system having a hierarchical arrangement of nodes and is
`Con?gured for user navigation among the nodes- The System
`has an invented index Correlating keywords with a‘ least
`some nodes‘ 1n the arrangement so that When the user
`provides an mput 1n response to a verbal descr1pt1on and the
`response mcludes a meanmgful Word correlatable W1th a
`keyword, the system Will identify at least one node corre
`lated to the meaningful Word by the inverted index and jump
`to that node Without ?rst traversing any other node.
`
`5,812,134 A *
`
`9/1998 Pooser et a1. ............. .. 707/102
`
`7 Claims, 11 Drawing Sheets
`
`902
`
`Load stop words from 's'
`
`Has
`keyword ?le been
`processed?
`
`YES
`
`906 I
`
`Read ?le x
`
`l
`
`920 1
`thesaurus _l
`Eliminate stop words from
`
`I
`
`908 Eliminate stop words from
`keywords
`
`Eliminate duplicate words
`from thesaurus
`
`910 Eliminate duplicate words
`from keywords
`
`922
`
`912
`
`Construct inverted index
`
`914 I
`
`Mark keyword ?le as
`processed
`
`924
`Mark thesaurus ?le as
`processed
`
`YES Copy inverted index and
`thesaurus to Lofg
`
`PETITIONERS
`EXHIBIT 1001, Page 1
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 12, 2007
`Jun. 12, 2007
`
`Sheet 1 0f 11
`Sheet 1 of 11
`
`US 7,231,379 B2
`US 7,231,379 B2
`
`100
`
`102
`1 /
`
`4
`
`5
`
`6
`
`7
`
`8
`
`
`
`108
`
`110
`118/
`
`9
`
`10
`
`114
`\120
`
`116
`
`FIG. 1
`
`PETITIONERS
`
`EXHIBIT 1001, Page 2
`
`PETITIONERS
`EXHIBIT 1001, Page 2
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 2 0f 11
`
`US 7,231,379 B2
`
`FIG. 2
`
`200 \
`
`Fruit /02
`204\ Hi / 206
`
`Apple
`
`Orange
`
`300 \
`
`302 \
`
`304 \
`
`Reservations
`
`/ 306
`
`Domestic
`
`International
`
`I
`
`/31O
`
`Business
`Class
`
`Economy
`Class
`
`Economy
`Class
`
`I—J—l
`314/
`
`Business
`Class
`
`\ 308
`
`312/
`FIG. 3
`
`PETITIONERS
`EXHIBIT 1001, Page 3
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 3 0f 11
`
`US 7,231,379 B2
`
`400
`
`\
`
`404 \
`
`Programs
`
`/ 402
`
`/ 406
`
`Sitcoms
`
`Films
`
`FIG. 4
`
`500
`
`\
`
`/ 502
`
`Restaurants
`
`504 \\
`
`Pizza
`
`Burgers
`
`Chinese
`
`506/
`FIG. 5
`
`508/
`
`PETITIONERS
`EXHIBIT 1001, Page 4
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 4 0f 11
`
`US 7,231,379 B2
`
`/ 602
`
`Initial Node
`a0
`
`/ 600
`
`/ 610
`
`International
`Reservations
`a4
`
`Domestic
`Domestic
`International
`Arrivals Info
`Reservations
`Arrivals
`a1
`a2
`a3
`604 / I—|—|\ 606 \ 608
`First/Business
`Economy
`Class
`Class
`a5
`a6
`612 /
`I
`I
`I
`First
`Business
`Economy
`Class
`Class
`Class
`a7
`a8
`a9
`616 / 618 / 620 /
`
`614
`
`FIG. 6
`
`PETITIONERS
`EXHIBIT 1001, Page 5
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 5 0f 11
`
`US 7,231,379 B2
`
`@
`
`Read file p
`
`Read file 1‘
`
`Extract keywords from 'p'
`
`Extract keywords from 'f'
`
`Store keywords from 'p'
`
`Store keywords from 'f'
`
`e
`
`FIG. 7A
`
`a
`
`FIG. 75
`
`FIG. 8
`
`Read file w
`
`t
`Extract thesaurus words
`from 'w'
`t
`Store thesaurus words
`from 'w'
`
`PETITIONERS
`EXHIBIT 1001, Page 6
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 6 0f 11
`
`US 7,231,379 B2
`
`FIG. 9
`
`902
`
`Load stop words from 's'
`
`904
`
`Has
`keyword file been
`processed?
`
`YES
`
`906
`
`.
`Read me X
`
`Eliminate stop words from
`thesaurus
`
`908 Eliminate stop words from
`keywords
`+
`910 Eliminate duplicate words
`from keywords
`
`912
`
`Construct inverted index
`
`914
`
`t
`Mark keyword file as
`processed
`
`Eliminate duplicate words
`from thesaurus
`922
`
`924
`Mark thesaurus file as
`processed
`
`916
`
`Have both
`eyword and thesaurus
`files been
`processed?
`
`YES Copy inverted index and
`thesaurus to t.cfg
`
`918
`
`PETITIONERS
`EXHIBIT 1001, Page 7
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 7 0f 11
`
`US 7,231,379 B2
`
`FIG. 10
`
`1002
`
`Add keywords (p + f) to
`thesaurus words (w)
`
`l
`
`1004
`
`Create matrix with thesaurus
`words as ‘row-words‘ and
`keywords as ‘column-words‘
`
`l
`
`1006
`
`Count co-occurrence of ‘row
`words' with ‘column-words‘ in
`document 'w' to fill matrix cells
`
`1
`
`Calculate cosine value of all
`pairs of rows corresponding to
`all ‘row-words’ and rows
`corresponding to ‘column words’
`
`1008
`
`1
`
`1010
`
`Take keywords matching top
`'n' cosine values for every
`‘row-word‘
`
`PETITIONERS
`EXHIBIT 1001, Page 8
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 8 0f 11
`
`US 7,231,379 B2
`
`FIG. 11
`
`1102
`
`Read files t.cfg, |.cfg, f, x and s
`
`i
`
`1104
`
`Load files t.cfg, |.cfg, 'f', 's' and 'x'
`
`i
`
`1106
`
`Provide initial verbal description
`
`—> Receive response/input from user
`
`1108
`
`1112
`
`Does
`response contain unknown
`word?
`
`YES
`
`Does user wish to continue?
`
`PETITIONERS
`EXHIBIT 1001, Page 9
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 9 0f 11
`
`US 7,231,379 B2
`
`1202
`
`Identify keywords from response/input <——-———
`
`1204
`
`1206
`
`Identify thesaurus words in t.cfg and l.cfg, if
`any, identified from response/input
`lr
`Select node with verbal description(s) that
`best match keywords and thesaurus words
`
`1208
`
`Any
`nodes
`selected?
`
`1210
`
`single leaf node
`selected?
`
`1212
`
`verbal description
`corresponding to
`
`.
`
`1214
`
`is form for
`verbal description
`available?
`
`1216
`
`Error handling
`
`1218
`
`Select top level node
`
`1220
`
`Issue verbal
`description for node
`and receive response
`
`Issue verbal
`description for node
`and (if applicable)
`receive response
`
`1222
`
`FIG. 12
`
`PETITIONERS
`EXHIBIT 1001, Page 10
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 10 0f 11
`
`US 7,231,379 B2
`
`1302
`
`Is it
`a response
`form’?
`
`YES
`
`1304
`Issue questions based on form
`to user and accept response
`
`1306
`
`l
`
`Execute corresponding action
`returning another form
`
`1308
`
`Issue response
`to user
`
`FIG. 13
`
`PETITIONERS
`EXHIBIT 1001, Page 11
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 11 0f 11
`
`US 7,231,379 B2
`
`140
`
`ls word
`present in
`Lofg?
`
`YES
`
`1404
`
`Add the word to the list of
`learned words with
`keywords from selected
`prompt as synonyms
`
`1406
`
`Merge keywords from
`selected prompt into the
`list of synonyms
`associated with the word
`
`1408
`
`—> Copychangestolcfg <—
`
`FIG. 14
`
`PETITIONERS
`EXHIBIT 1001, Page 12
`
`

`

`US 7,231,379 B2
`
`1
`NAVIGATION IN A HIERARCHICAL
`STRUCTURED TRANSACTION
`PROCESSING SYSTEM
`
`FIELD OF THE INVENTION
`
`The present invention relates to information processing
`and, more particularly, computer based transaction process
`ing.
`
`NOTICE OF COPYRIGHT RIGHTS
`
`A portion of the disclosure of this patent document,
`particularly the Appendix, contains material that is protected
`by copyright. The copyright oWner has no objection to the
`facsimile reproduction of the patent document or the patent
`disclosure as it appears in the Patent and Trademark Office
`?le or records, but otherWise reserves all copyright rights
`Whatsoever.
`
`BACKGROUND OF THE INVENTION
`
`In everyday life, netWorks of choices set forth in a
`particular order or hierarchy are encountered With increasing
`frequency. Usually, it is desired to traverse the netWork in
`the most ef?cient manner possible to accomplish a particular
`goal.
`In modern mathematics, graph theory is used to study
`netWorks of hierarchical choices. The hierarchical netWorks
`can be represented as a graph structure. Graph theory ?nds
`practical applications in chemistry, computer science, eco
`nomics, electronics and linguistics.
`A graph structure is a collection of points, called “verti
`ces”, and a collection of lines, called “edges”. Each edge
`joins a pair of vertices or a single point to itself.
`A simple example of a netWork represented by a graph
`structure is a road map. The vertices represent toWns or
`cities. The edges represent the roads that connect the toWns
`and cities.
`Another type of netWork familiar to anyone Who has a
`telephone is an automated telephone voice response system,
`such as commonly utiliZed by many large companies, to
`direct incoming calls to particular individuals or depart
`ments or to assist the caller in performing a transaction, such
`as making a purchase.
`That type of telephone netWork can also be represented as
`a graph structure. When the system ansWers an incoming
`call, it transmits a verbal description or prompt to the caller:
`“If you Would like to speak to Harry, press 1; if you Would
`like to speak to Fred, press 2”. (In general, We Will use
`“verbal description” to mean a set of Words relating to the
`subject matter Whether presented audibly or in Written form.
`The verbal descriptions may range from a feW Words to an
`entire document Worth of text). A ?rst vertex on the graph
`represents the initial prompt, Which a caller hears upon
`reaching the telephone response system. If the user’s
`response is pressing 1, calls are directed along a ?rst edge to
`Harry, represented by a second vertex. If the response is
`pressing 2, the call is directed along a second edge to Fred,
`represented by a third vertex. Then, if the chosen person is
`not available, the caller is asked Whether the caller Wishes to
`leave a message. If the response is positive, the caller is
`directed along another edge to the selected person’s voice
`mail, Which Would be represented by another vertex of the
`graph.
`In general, Whether for a telephone response netWork or
`for any other application representable by a graph structure,
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`the caller or user of the system Will have some goal. By
`“goal” We mean a combination of transactions and informa
`tion accesses Which the user seeks to accomplish. By “trans
`action” We mean an operation performed electronically With
`a user. In general, there Will also be a combination of
`vertices or nodes in the graph that best represent or are
`closest to the goal the user is trying to accomplish. We call
`these vertices the “goal vertices”.
`For the user, the object in navigating the graph is to get
`from the ?rst vertex to the goal vertices. If this is not done
`as quickly and e?iciently as possible the user may become
`frustrated and give up. Moreover, as the number of possible
`choices or nodes in the netWork becomes larger, the number
`of possible pathWays betWeen the ?rst vertex and the goal
`vertices multiplies rapidly. Therefore, the ability to reach the
`goal vertex can become more dif?cult, require navigation of
`an excessive number of choices or nodes, or discourage a
`user before the goal vertex is even reached.
`
`SUMMARY OF THE INVENTION
`
`The present invention creates a method for navigating
`ef?ciently and naturally through a series of choices to obtain
`information, perform transactions, or accomplish some simi
`lar goal. The invention is implemented in a programmed
`computer that has a hierarchically con?gured decisional
`netWork that must be navigated as part of the processing and
`is constructed to accept inputs or data and process them in
`a manner that facilitates navigation of the netWork vertices
`more ef?ciently.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is an example graph representing a simple, generic
`hierarchically arranged transaction processing or decisional
`system suitable for use With the invention;
`FIG. 2 is an example portion of a graph used to illustrate
`jumping among nodes in accordance With one variant of the
`invention;
`FIG. 3 is an example portion of a graph in a simple
`interactive voice response (“IVR”) system used to illustrate
`grouping in accordance With one variant of the invention;
`FIG. 4 is an example portion of a graph in a simple
`interactive television program listing used to illustrate
`another variant of the invention;
`FIG. 5 is an example portion of a graph in a simple
`geographic information system used to illustrate a further
`variant of the invention;
`FIG. 6 is an example portion of a graph for a simple
`automated voice response system used to illustrate a more
`complex variant of the invention;
`FIGS. 7A, 7B, and 8-10 are collectively a ?owchart
`illustrating an example setup process for use in accordance
`With an example implementation of one variant of the
`present invention; and
`FIGS. 11-14 are collectively an overall ?owchart illus
`trating an example process in accordance With a further
`variant of the present invention.
`
`DETAILED DESCRIPTION
`
`In graph theory, mathematicians refer to a “pat ” from
`one vertex in a graph to another speci?ed vertex in the graph
`as consisting of a sequence of edges that connect the vertices
`betWeen the ?rst vertex and the ?nal vertex. If the path
`
`PETITIONERS
`EXHIBIT 1001, Page 13
`
`

`

`US 7,231,379 B2
`
`3
`contains an edge sequence that is “closed”, meaning that it
`loops back on itself, the path is called a “circuit” or a
`“cycle”. A graph structure is considered to be “connected” if
`there is at least one path connecting every pair of vertices.
`Our invention is particularly applicable to transactional
`processing as applied to instances Where graph theory can be
`used to represent the transactions as a set of options and
`When the options are structured according to a connected
`graph that contains no circuits. We call such a graph a “tree”.
`We use the term “menu tree” for a netWork that provides a
`“menu” of options, typically presented as verbal descrip
`tions, to assist a user in making a series of choices through
`Which he or she is able to accomplish one or more of his or
`her information access or transaction goals. Informally, a
`“menu tree” can be regarded as a series of vertices in a
`hierarchy or ordered pattern, arranged in roWs of increasing
`numbers of vertices. More precisely, a “menu tree” can be
`represented as a “tree” in Which (i) the vertices are all the
`options provided anyWhere in the “menu tree”, plus a ?rst
`vertex, (ii) every vertex except the ?rst vertex, i.e., every
`“option vertex”, is associated With the verbal description (or
`such other means) by Which a “menu” presents that option,
`(iii) an edge connects the ?rst vertex to each vertex that the
`?rst “menu” presents to the user as an option, and (iv) each
`other vertex is similarly connected by edges to every other
`vertex that the corresponding “menu” presents to the user as
`an option. As the number of options increases, so does the
`length of paths from the ?rst vertex to goal vertices.
`In overvieW, in accordance With the teachings of our
`invention, the user can navigate the graph or tree in a Way
`that alloWs them to skip from one vertex to another vertex
`that may be many roWs doWn the graph or tree and/ or Where
`the vertices may not be connected together by an edge. This
`eliminates the necessity for making many choices.
`Particular implementations make it possible to jump lat
`erally from one vertex to another if the navigation enters a
`Wrong branch of the tree or if the user changes his goal. The
`approach is accomplished through associating each vertex
`With a verbal description (or prompt), and matching Words
`in users’ requests and responses With these verbal descrip
`tions to enable the selection of vertices that may not be
`directly connected to the user’s current location in the graph
`or tree by an edge.
`In some variants, We create a system With the unique
`ability to learn by incorporating previously unknoWn Words,
`keyWord or synonyms of keyWords so that the system
`modi?es itself to thereby increase the likelihood that a user
`Will e?iciently and quickly reach the goal.
`For purposes of illustration, the invention Will be
`described by Way of example, ?rst using a series of simple
`examples folloWed by a more complex example of a more
`detailed and commercially suitable example variant, in the
`context of a menu-type automated telephone voice response
`system for a publication, a hierarchical netWork of the type
`that is frequently encountered and easily understood that
`implements a combination of some of the features of the
`simple examples in order to illustrate hoW those features can
`be combined or overlayed.
`It should be understood that the present invention is
`applicable to a Wide range of different netWorks, Which can
`be mathematically represented by graph structures consist
`ing of vertices and edges and should not be considered to be
`limited to the particular application described. Representa
`tive examples of suitable applications for the invention
`include implementing an enhanced and more ef?cient
`“Find” function or ?le system broWser for personal com
`puter operating systems, a navigation system for television
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`program listing, document management or retrieval systems,
`a “geographic information system” in an automobile that
`alloWs location of addresses or business(es) meeting certain
`criteria, or other devices that incorporate some hierarchical
`navigation aspect as part of its operation.
`In order to more fully understand the invention, various
`independent aspects are noW presented beloW by Way of
`simple illustrative examples. In this manner the teachings of
`the invention can be understood in a Way that makes it
`possible to use, overlay and/or combine those aspects in a
`bene?cial manner in an implementation of the invention.
`Depending upon the particular implementation of the inven
`tion, one or more of the aspects may be used together in
`various permutations and/or combinations, With the under
`standing that different permutations and/or combinations
`may be better suited for particular applications or have more
`or less bene?ts or advantages than others.
`The underlying scenario common to all these basic
`examples is that there is a hierarchical arrangement to the
`possible choices that can be illustrated in a form of “tree”
`structure.
`FIG. 1 is an example graph 100 representing a possible
`hierarchically arranged transaction processing or decisional
`system suitable for use With the invention. The individual
`boxes 102-120 are referred to as “nodes” and each repre
`sents a speci?c choice or option in the hierarchy. For
`purposes described in more detail beloW, each node is
`arbitrarily uniquely identi?ed in some manner. In the
`example of FIG. 1, the individual nodes 102-120 are num
`bered 1 through 10 starting from the top node 102 in the
`hierarchy.
`Each “node” is associated With exactly one verbal
`description, for example in the case of an airline system, a
`verbal description relating to some aspect of the reservation
`process. Each such description contains “key” Words that are
`deemed to be of importance and other Words that can be
`disregarded. For example, one node may have the associated
`verbal description “Would you like to make a reservation?”
`In this description, there is only one “key” Wordi“reser
`vation” deemed important, so all of the other Words in the
`description can be ignored.
`A level in the hierarchy beloW that one may be used to
`obtain further narroWing information, for example, using the
`verbal description “Is the reservation for a domestic or
`international ?ight?” In this description, the terms “domes
`tic” and “international” are “key” Words. Similarly, the Word
`“?ight” could be a “key” Word, for example, for a system
`that involves not only airline travel but also rail and/or cruise
`travel or it could be an “ignored” or stop Word for a purely
`airline related system because it has minimal meaning in that
`context. Again, the other Words can be ignored as Well.
`The unique identi?cation of each node alloWs the creation
`of a list of all the key Words and their associated nodes so
`that, if a key Word is duplicated in tWo or more nodes, it need
`only be listed once. For example, a hierarchical tree related
`to “pens” might have nodes for ball-point pens, ?ne point
`pens, medium point pens, fountain pens, felt-tip pens, quill
`pens, erasable pens, etc. By using this approach, one could
`list the keyWord “point” once, but associate it With each of
`the nodes Where that keyWord appears by using the unique
`identi?er for each node Where the term appears.
`In this manner the keyWords are obtained from the
`collection of available descriptions found in the particular
`application in Which the invention Will be used. In addition,
`each particular node Where the keyWord appears is associ
`ated With the keyWord. Thus, With respect to the pen
`application above, the keyWord “point” might appear in
`
`PETITIONERS
`EXHIBIT 1001, Page 14
`
`

`

`US 7,231,379 B2
`
`5
`nodes 2, 3, 6, 7, 13 and 15. Similarly, the keyword “eras
`able” might appear in nodes 3, 4, 5, 6 and 22. An index, as
`described more fully below, associating these keywords with
`the nodes containing them is then created, for example:
`point: 2, 3, 6, 7, 13, 15
`erasable: 3, 4, 5, 22
`By making use of these associations the “tree” can be
`negotiated by allowing presentation of relevant verbal
`descriptions for the nodes associated with a term, irrespec
`tive of where in the hierarchy they are, thereby causing a
`“jump” to a particular node without necessarily traversing
`the tree in the rigid hierarchical manner.
`Various examples will now be presented to illustrate
`certain concepts related to the invention. It should be under
`stood that while these examples are presented in the context
`of things and likely experiences of ordinary people, the same
`approach can be applied to other forms of transaction
`processing including navigating through hierarchically
`nested data ?les in a computer system, pattern analysis or
`image processing, etc. the term “transaction” as used herein
`relating to traversal through a hierarchy to a goal, not
`mathematical calculation per se.
`Moreover, the speci?c formats used and presented in
`these examples are purely for illustration purposes. It should
`be understood that other techniques for interrelating data,
`such as hash tables, direct or indirect indexing, etc. can be
`substituted in a straightforward manner. Thus, for example,
`the relationship between the word and a node could be
`con?gured such that the location of the word in a list as the
`“n-th” item could be used as an index into another list
`containing the nodes correlated to the list. A similar
`approach could be used for the thesaurus, the important
`aspect relative to the invention being the relationship among
`certain words and the node(s) in which they occur and,
`where applicable, the relationship between certain words
`and “synonyms” for those words, not the data structure or its
`form or format whereby that information is kept or main
`tained.
`
`EXAMPLE 1
`
`Example 1 illustrates, in simpli?ed form, how an index is
`used to jump among nodes with reference to FIG. 2. In this
`example, the hierarchical tree 200 represents a portion of a
`more complex tree speci?cally involving possible decision
`relating to fruit and a decision between two speci?c types of
`fruits, an apple and an orange.
`In prior art hierarchical trees, navigation of this graph 200
`would necessarily involve going through the “fruit” node
`202 in order to reach the “apple” 204 or “orange” 206 nodes.
`As a result, assuming this simple tree was part of a larger
`tree for an on-line supermarket that prompted the user for
`what they wanted to purchase, the exchange would be both
`rigid and time consuming. For example, in response to a
`prompt “What do you want to purchase?” if the response
`was anything other than “fruit” traversal to the “fruit” node
`202 could not occur. At the point in the tree that would lead
`to the “fruit” node 202, neither apple nor orange would be
`an acceptable response.
`In accordance with the invention, assuming the only
`relevant keywords for that portion of the tree were “fruit”,
`“apple” and “orange”, an inverted index would be created
`that includes an association of “Fruit” with the top node 202,
`“Apple” with the bottom left node 204, and “Orange” with
`the bottom right node 206. As shown above, that association
`can be created using node identi?ers, in this example, the
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`node identi?ers 1A01, 1A02 and 1A03 are arbitrarily
`assigned and used. Thus, the information can be stored in a
`?le, for example, as follows:
`Fruit, 1A01
`Apple, 1A02
`Orange, 1A03
`Accordingly, to navigate the system 200, when a response
`to a verbal description is provided by a user, possible
`keywords are identi?ed in the response and used to search
`the index and identify any node to which the response may
`be directed, irrespective of the hierarchy. Thus, a user
`response of “an orange” to a verbal description located
`above the “fruit” node 202 in the hierarchy, for example,
`“What would you like to buy today?” would cause the
`system to identify “orange” as a key word from the response,
`search the index, and directly identify node 1A03 (206) as
`the node whose verbal description should be presented next,
`thereby avoiding the need to traverse intervening nodes, for
`example, through the “fruit” node (202) 1A01, at all. This
`illustrates an example of a simple jump according to the
`invention.
`
`EXAMPLE 2
`
`Having illustrated a simple “node jump” a more complex
`(and likely) scenario can be shown. In this example, the
`Example 1 graph of FIG. 2 applies, but relevant portion of
`the index is as follows:
`Fruit, 1A01
`Apple, 1A02, 2F09
`Orange, 1A03
`As a result, there are two nodes relevant to the keyword
`“apple” one being the node 204 in the portion of the graph
`shown in FIG. 2 and one in the node uniquely identi?ed as
`2F09 located somewhere else in the hierarchy (not shown).
`In this example, a user response containing the keyword
`“apple” would identify nodes with identi?ers 1A02 and
`2F09. In this case, and unlike the prior art, the verbal
`descriptions from both nodes would be presented to the user,
`likely in alternative fashion. Thus, if the user did not want
`an apple, they wanted apple cider, node 2F09 might be more
`appropriate because it is part of the “drinks” portion of the
`overall hierarchy.
`Thus, presenting the user with the verbal description from
`both nodes would likely result in a jump to the portion of the
`graph nearer to node 2F09 since it is closer to the user’s goal
`thereby speeding up the process and avoiding potentially
`confusing or frustrating the user.
`
`EXAMPLE 3
`
`While the verbal descriptions associated with various
`nodes will generally be chosen to accurately represent the
`node, in accordance with certain variants of the invention, it
`is possible to create a situation where a user response takes
`them away from their ultimate desired goal. Nevertheless,
`by using the teachings of the present invention, the user can
`often still be brought to their goal quicker than possible with
`the prior art because the user need not rigidly trace through
`the hierarchy. This is accomplished by virtue of the “group
`ing” aspect inherent in some implementations of the inven
`tion.
`This example illustrates the “grouping” aspect using a
`simpli?ed graph 300 representing a portion of an airline
`reservation system as shown in FIG. 3.
`In particular, the graph of FIG. 3 can be thought of as part
`of a very simple interactive voice response (“IVR”) system.
`
`PETITIONERS
`EXHIBIT 1001, Page 15
`
`

`

`US 7,231,379 B2
`
`7
`As described above, each node is uniquely identi?ed, for
`example, by the numbers 1 through 7 and the identi?ed
`terms “Reservation”, “Domestic”, “Intemational”, “Busi
`ness Class”, “Economy Class” are deemed the relevant
`keyWords. Note, there is no requirement for a the “keyword”
`to be a single Word, in some implementations, keyWords
`could be single Words, phrases of tWo or more Words, or
`even some other form of information like a speci?c data
`pattern.
`Again, an inverted index is created as described above
`associating those keyWords With the nodes, in this case:
`Reservation, 1
`Domestic, 2
`International, 3
`Business Class, 4, 6
`Economy Class, 5, 7
`Assuming that the top node is assigned the number 1, its
`tWo child nodes (Domestic and International) are assigned
`the numbers 2 and 3, and the grandchild nodes (i.e. at the
`loWest level in the hierarchy) have been assigned numbers 4,
`5, 6, and 7 taken from left to right each node can be uniquely
`located. Note that the last tWo entries in the inverted index
`are each associated With tWo nodes, 4 and 6 in the ?rst case,
`and 5 and 7 in the second.
`Using the above, the concept of grouping of nodes from
`different parts of the graph (i.e. nodes that are not siblings or
`nodes that do not have a common parent) can be explained.
`Presume that the response to a verbal description pre
`sented as an initial query of “What do you Want to do?” Was
`“Make a business class reservation.” In this case there are
`tWo keyWords present, “reservation” and “business class”.
`Depending upon the particular implementation, as noted
`previously, the verbal descriptions associated With each
`identi?ed node could be presented together or in sequence.
`Alternatively, and as is the case here, a set of rules can be
`established, for example, such that if an identi?ed node is a
`sub-node of another identi?ed node, only the verbal descrip
`tion of the sub-node(s) is provided because of inherent
`redundancy. Thus, since both “business class” nodes 310,
`314 are sub-nodes of the “reservation” node 302, the verbal
`description associated With the “reservations” node can be
`suppressed if it can be determined that business class
`necessarily implies reservations.
`In this example, a search of the inverted index Would
`identify nodes 4 and 6 (310, 314) from different parts of the
`tree are associated With the keyWords in the query, and thus
`the system, in presenting the verbal descriptions from each,
`in effect, alters the tree structure and groups these nodes in
`the result. Thus, the combination of result nodes presented
`depends upon the user query or response, not that predeter
`mined by the graph structure itself.
`Of course, the goal Would still not be reached because of
`the ambiguity caused by “Business Class” being under both
`“Domestic” and “Intemational”. HoWever, that ambiguity
`can be handled by suitable Wording of the folloWing verbal
`descriptions and Whether they are combined or provided
`sequentially or by other nodes.
`
`EXAMPLE 4
`
`A persistent and further draWback present in the prior art
`is the inability to operate if any term other than the speci?c
`alloWed terms are provided. Thus, in an IVR of the prior art,
`providing anything other than the recogniZed term(s) Will
`likely result in meaningless repeat of the same inquiry by the
`IVR or an error.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`Advantageously, the teachings of the present invention
`alloW for construction of a more ?exible system than avail
`able in the prior art. Speci?cally, We can incorporate a
`thesaurus to accommodate synonyms for the keyWords.
`Example 4 illustrates the addition of a simple thesaurus as
`an aspect of a system so that a synonym of a keyWord may
`also be used by the system to jump to the desired nodes in
`the graph. Example 4 is discussed With reference to a portion
`400 of an interactive television program listing system as
`shoWn in FIG. 4.
`Such a system implementing the invention Will alloW a
`user to speak to or interact With a device to look for
`programs of his choi