`
` |*2d
`
`US0072
`
`ay
`a
`1379B2
`
`(12)
`
`United States Patent
`Parikh et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,231,379 B2
`Jun. 12, 2007
`
`NAVIGATION IN A HIERARCHICAL
`STRUCTURED TRANSACTION
`PROCESSING SYSTEM
`
`(75)
`
`Inventors: Prashant Parikh, New York, NY (US);
`Stanley Peters. Menlo Park, C.A (US)
`
`(73)
`
`Assignee: Noema, Ine., New York, NY (US)
`
`6.038560 A BI2000 Witt wi csceussnecsessscneercees 707/S
`6,405,188 Bl
`6/2002 Schwartz et al.
`6,408,290 Bl1*
`6/2002 Thicsson et al. 0.0... 706/42
`6,510,406 BL
`1/2003 Marehisio
`6,654,731 BL”
`11/2003 Mahesh ww. T0645
`6.675.159 Bl
`1/2004 Lin et al.
`6,678,677 B2*
`1/2004 Roux et ab. wcccscceeecnes TO7T/3
`6.859.212 B2
`2/2005 Kumar et al.
`
`* cited by examiner
`Notice:—Subject to any disclaimer, the term ofthis
`Primary Examiner—Yicun Wu
`patent is extended or adjusted under 35
`(74) Attorney, Agent, er Firm-—Morgan & Finnegan L[.P
`U.S.C. 154(b) by 485 days.
`
`(21)
`
`(22)
`
`(65)
`
`(51)
`
`(52)
`(58)
`
`(56)
`
`Appl. No.: 10/299,359
`
`Filed:
`
`Nov, 19, 2002
`
`Prior Publication Data
`
`US 2004/0098381 Al
`
`May 20, 2004
`
`Int. Cl.
`(2006.01)
`GO6F 17/30
`UWS. Ch ceccceccsscecsescccce
`707/22 707/60: 707/3: 707/4
`Field of Classification Seareh ............... 7O7/1,
`707/2, 3, 4, 5,6, 7,8, 9.10, 100, 101, 102,
`707/103, 104.1
`See application file for complete search history.
`References Cited
`
`U.S, PATENT DOCUMENTS
`
`5,812,134 A *
`
`9/1998 Pooser et al... 707/102
`
`(37)
`
`ABSTRACT
`
`A method performed in a system having multiple navigable
`nodes interconnected in a hierarchical arrangement involves
`receiving an inpul containing al least one word identifiable
`with at
`least one keyword, identifving at least one node,
`other than the first node, not directly connected to the first
`node, but associated with the at least one keyword, and
`jumping to the identified node. A transaction processing
`system having a hierarchical arrangement of nodes and is
`configured for user navigation among the nodes. The system
`has an inverted index correlating keywords with at
`least
`some nodes in the arrangement so that when the user
`provides an input in response to a verbal description and the
`response includes a meaningful word correlatable with a
`keyword, the system will
`identify at
`least one node corre-
`lated to the meaningful word by (he inverted index and jump
`to that node without first traversing any other node.
`
`7 Claims, 11 Drawing Sheets
`
`
` eywords
`
`Eliminate stop words from
`ki
`
`
`Eliminate duplicate words
`from thesaurus
`
`
`
`918
`
`PETITIONERS - EXHIBIT 1001
`PETITIONERS- EXHIBIT 1001
`
`IPR2022-00217
`
`IPR2022-00217
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 1 of 11
`
`US 7,231,379 B2
`
`
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 2 of 11
`
`US 7,231,379 B2
`
`FIG. 2
`
`200NX
`204NX
`
`é202
`J206
`
` Business
`
`Class
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet3 of 11
`
`US 7,231,379 B2
`
`a402
`400NY
`
`ug406
`404Se
`
`
`
`Programs
`
`FIG. 4
`
`Restaurants
`
`500Le
`J502
`
`504Ny
`
`ar
`asi
`Fic.
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 4 of 11
`
`US 7,231,379 B2
`
`600
`
`Initial Node
`
`
`
`
`
`Domestic
`International
`International
`Domestic
`Reservations
`Arrivals
`Arrivals Info
`Reservations
`
`
`
`
`a3
`at
`a2
`a4
`
`
`
`
`604.
`
`
`
`go
`il<
`ad
`x
`
`
`
`
`
`Business
`Economy
`Class
`Class
`
`a9
`a8
`
`
`B16— SCS 620—
`
`
`
`
`
`First/Business
`Class
`
`
`
`Economy
`Class
`
`612
`
`
`
`FIG. 6
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 5 of 11
`
`US 7,231,379 B2
`
`Readfile p
`
`
`
`
`
`
`Extract keywords from ‘p'
`
`
`
`Store keywords from 'p'
`
`Readfile f
`
`
`
`
`
`Extract keywords from ‘'f
`
`Store keywords from 'f
`
`FIG. 7A
`
`Readfile w
`
`
`
`
`
`Extract thesaurus words
`from 'w'
`
`Store thesaurus words
`trom 'w'
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet6 of 11
`
`US 7,231,379 B2
`
`902
`
`Load stop words from 's'
`
`FIG. 9
`
`904
`
`
`
`Has
`keywordfile been
`
`YES
`
`
`processed?
`
`
`
`Construct inverted index
`
`
`
`NO
`
`Raail tiles
`
`
`
`Eliminate stop words from
`keywords
`
`Eliminate duplicate words
`
`from keywords
`
`Mark keywordfile as
`processed
`
`
`Have both
`
`
`eyword and thesaurus
`files been
`
`
`
`processed?
`
`920
`
`Eliminate stop words from
`thesaurus
`
`Eliminate duplicate words
`from thesaurus
`
`922
`
`i
`
`@
`
`924
`
`Mark thesaurus file as
`processed
`
`Copyinverted index and
`thesaurusto t.cfg
`
`918
`
`DONE
`
`YES
`
`

`

`U.S. Patent
`
`FIG. 10
`
`Wee
`
`1004
`
`1006
`
`1008
`
`1010
`
`Jun, 12, 2007
`
`Sheet7 of 11
`
`US 7,231,379 B2
`
`Add keywords (p + f) ta
`thesaurus words (w)
`
`Create matrix with thesaurus
`words as ‘row-words' and
`keywords as ‘column-words'
`
`‘row-word'
`
`Count co-occurrenceof 'row-
`words' with 'column-words’ in
`document 'w'tofill matrix cells
`
`Calculate cosine value ofall
`pairs of rows correspondingto
`all 'row-words' and rows
`corresponding to ‘column words’
`
`Take keywords matching top
`‘n’ cosine values for every
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 8 of 11
`
`US 7,231,379 B2
`
`FIG. 11
`
`1102
`
`Readfiles t.cfg, |.cfg, f, x ands
`
`1104
`
`Loadfiles t.cfg, |.cfg, 'f, 's' and 'x’
`
`1106
`
`Provideinitial verbal description
`
`Receive response/input from user
`
`1108
`
`1112
`
`
`
`
`Does
`response contain unknown
`word?
`
`
`=e
`
`NO
`
`YES
`
`
`;
`;
`
`
`Does userwish to continue?
`
`
`NO
`
`END
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 9 of 11
`
`US 7,231,379 B2
`
`1202
`
`Identify Keywords from response/input
`
`1204
`
`4206
`
`
`Identify thesaurus words in t.cfg and |.cfg, if
`any, identified from response/input
`
`
`
`Select node with verbal description(s) that
`
`best match keywords and thesaurus words
`
`
`
`
`
`
`Any
`
`
`nodes
`Select top level node
`
`
`selected?
`
`
`
`Issue verbal
`
`
`
`single leaf node
`description for node
`selected?
`and receive response
`
`
`YES
`
`1208
`
`1210
`
`
`
`|ssue verbal
`
`4242 ES|description for nodeverbal description
`corresponding to
`and (if applicable)
`
`receive response
`
`NO
`
`
`
`
`
`
`
`1222
`
`4244
`
`
`is form for
`
`verbal description
`YES (w)
`
`available?
`
`NO
`
`&
`
`FIG. 12
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 10 of 11
`
`US 7,231,379 B2
`
` 1302
`
`
`
`
`Is it
`
`YES
`
`a response
`form?
`
`
`
`
`
`
`Issue questions based on form
`to user and accept response
`
`Execute corresponding action
`returning another form
`
`1308
`
`Issue response
`to user
`
`FIG. 13
`
`

`

`U.S. Patent
`
`Jun. 12, 2007
`
`Sheet 11 of 11
`
`US 7,231,379 B2
`
` 140
`
`Is word
`
`presentin
`|.cfg?
`
`
`
`
`
`
`
`
`
`
`
`
`Add the wordto thelist of
`learned words with
`keywords from selected
`prompt as synonyms
`
`
`YES
`
`Merge keywords from
`selected promptinto the
`list of synonyms
`associated with the word
`
`1408
`
`Copy changesto I.cfg
`
`FIG. 14
`
`

`

`US 7,231,379 B2
`
`1
`NAVIGATION IN A HIERARCHICAL
`STRUCTURED TRANSACTION
`PROCESSING SYSTEM
`
`FIELD OF THE INVENTION
`
`invention relates to information processing
`The present
`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
`file or records, but otherwise reserves all copyright rights
`whatsoever.
`
`BACKGROUND OF THE INVENTION
`
`2
`the caller or user of the system will have some goal. By
`“goal” we mean a combination oftransactions 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 first vertex to the goal vertices. I! this is not done
`as quickly and efficiently as possible the user may become
`frustrated and give up. Moreover, as the numberofpossible
`choices or nodes in the network becomeslarger, the number
`of possible pathways between the first vertex and the goal
`vertices multiplies rapidly. Therefore, the ability to reach the
`voal vertex can become more diflicult, require navigation of
`an excessive number of choices or nodes, or discourage a
`user before the goal vertex is even reached.
`
`wa
`
`wi
`
`SUMMARYOF THE INVENTION
`
`=
`
`45
`
`45
`
`forth in a
`In everyday life, networks of choices set
`particular order or hierarchy are encountered with increasing
`frequency. Usually, it is desired to traverse the network in 4
`the mostefficient 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 finds
`practical applications in chemistry, computer science, ecu-
`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 pointto 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, (transmits a verbal description or prompt to the caller:
`“Tf 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 descripuon” to mean a set of words relating to the
`subject matter whether presented audibly or in written form.
`The verbal deseriptions may range from a few words to an
`entire document worth of text), A first 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 |, calls are directed along a first 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 bya 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 ts positive, the caller is
`directed along another edge to the selected person’s voice
`mail, which would be represented by another vertex ofthe
`graph.
`In general. whether for a telephone response network or
`for any other application representable by a graph structure.
`
`_
`
`65
`
`invention creates a method for navigating
`The present
`efficiently aud naturally through a series of choices to obtain
`information, performtransactions, or accomplish some simi-
`lar goal. The invention is implemented in a programmed
`computer that has a hierarchically configured decisional
`network that must be navigated as part of the processing and
`is constructed to accept inputs or data and process them in
`a mannerthat facilitates navigation of the network vertices
`more efficiently.
`
`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;
`PG, 2 is an example portion of a graph used to illustrate
`jumping amony, nodes in accordance with one variant of the
`invention:
`
`FIG, 3 is an example portion of a graph in a simple
`interactive voice response (“TVR”) 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. § 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 flowchart
`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 flowchart illus-
`trating an example process in accordance with a further
`variant of the present invention,
`
`DETAILED DESCRIPTION
`
`In graph theory, mathematicians refer to a “path” from
`one vertex ina graph to another specified vertex in the graph
`as consisting of a sequence of edges that connect the vertices
`between the first vertex and the final vertex. If the path
`
`

`

`3
`contains an edge sequence that is “closed”. meaning that it
`loops back on itself,
`the path is called a “circuit” or a
`“evele”. A graph structure is consideredto be “connected” if
`there is at least one path connecting every pair of vertices.
`Our invention js particularly applicable to transactional
`processing as applied to instances where graph theorycan 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 first
`es
`vertex. (ii) every vertex except the first vertex, 1e., every 2
`“option vertex”, is associated with the verbal description (or
`such other means) by which a “menu” presents that option,
`(ii) an edge connects the first vertex to each vertex that the
`first “menu” presents to the user as an option, and (iv) each
`other vertex is similarly connected by edges to every other
`vertex that (he corresponding “menu” presents to the user as
`an opuion. As the number of options increases, so does the
`length of paths from the first 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 poal, 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-
`lions 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
`modifies itself to thereby increase the likelihood that a user
`will efficiently and quickly reach the goal.
`Por purposes of illustration,
`the invention will be
`described by way of example, first 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.
`invention is
`the present
`lt should be understood that
`applicable to a wide range ofdifferent 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 efficient
`“Find” function or file system browser for personal com-
`puler operating systems, 4 navigation systemfor television
`
`s
`
`45
`
`ws
`
`a&
`
`US 7,231,379 B2
`
`4
`programlisting. document managementor 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 ofits 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
`beneficial manner in an implementation of the invention.
`Depending upon the particular implementation ofthe inven-
`lion, one or more ofthe 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 benefits or advantages than others.
`these basic
`The underlying scenario common to all
`examples is that there is a hierarchical arrangement to the
`possible choices that can be illustrated in a form of “tree”
`structure,
`
`wa
`
`2
`
`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 specific choice or option in the hierarchy. Por
`purposes described in more detail below, each node is
`arbitrarily uniquely identified 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,
`Bach “node” is associated with exactly one verbal
`description, for example in the case ofan airline system, a
`verbal description relating to some aspect ofthe reservation
`tuaon
`5 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” word—‘reser-
`vation” deemed important, so all of the other words in the
`description can be ignored.
`A level in the hierarchy belowthat one may be used to
`obtain further narrowing information, for example, using the
`verbal description “Is the reservation for a domestic or
`international flight?” In this description, the terms “domes-
`tie” and “international” are “key” words, Similarly, the word
`“flight” could be a “key” word, for example, lor a system
`that involves not onlyairline 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 identification of each node allows the creation
`ofa list of all the key words and their associated nodes so
`that, ia key word is duplicated in two or more nodes,it need
`only be listed onee. For example, a hierarchical ree related
`to “pens” might have nodes for ball-point pens, fine point
`pens, mediumpoint 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 usiny the unique
`identifier for each node where the term appears.
`In this manner the keywords are oblained 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-
`aled with the keyword. Thus. with respect
`to the pen
`application above,
`the keyword “point” mighi appear in
`
`usan
`
`

`

`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
`ofthings andlikely experiences ofordinary people, the same
`approach can be applied to other forms of transaction
`processing including navigating through hierarchically
`nested data files 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 specific formats used and presented in
`these examples are purelyfor 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
`configured such that the location of the word ina 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 orits
`form or format whereby that information is kept or main-
`tained.
`
`EXAMPLE 1
`
`Example | illustrates, in simplified form, how an index is
`used to jump among nodes with reference to PIG. 2. In this
`example, the hierarchical tree 200 represents a portion of a
`more complex tree specifically involving possible decision
`relating to fruit and a decision between two specific types of
`fruits, an apple and an orange.
`In prior art hierarchical trees, navigation ofthis graph 200
`would necessarily involve going through the “fruit” node
`202 in order to reachthe “apple” 204 or “orange” 206 nodes.
`As a result, assuming this simple tree was part ofa 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 [or 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 bottomleft node 204, and “Orange” with
`the bottom right node 206. As shown above, that association
`can be created using node identifiers, in this example, the
`
`wi
`
`L
`
`hy
`
`io
`
`a
`
`of
`
`6
`node identifiers 1A01. LA02 and 1A03 are arbitrarily
`assigned and used. Thus, the information can be stored in a
`file, for example, as lollows:
`Fruit, LAOL
`Apple, 1A02
`Orange, 1403
`Accordingly, to navigate the system 200, when a response
`to a verbal description is provided by a user, possible
`keywords are identified 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
`ihe node whose verbal description should be presented next,
`thereby avoiding the need to traverse intervening nodes. for
`example, through the “fruit” node (202) 1.A01, al 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 | graph of FIG. 2 applies, but relevant portion of
`the index is as follows:
`Fruit, 1A01
`Apple, LA02, 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 identified as
`5 2F09 located somewhere else in the hierarchy (not shown).
`In this example, a user response containing the keyword
`“apple” would identify nodes with identifiers LA02 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 21°09 might be more
`appropriate because it is part of the “drinks” portion of the
`overall hierarchy.
`Thus. presenting the user with the verbal description [rom
`both nodes would likely result in a jump to the portion of the
`graph nearer to node 2F09 since itis closer to the user's goal
`thereby speeding up the process and avoiding potentially
`confusing or frustrating the user.
`EXAMPLE3
`
`While the verbal descriptions associated with various
`nodes will generally be chosen to accurately represent the
`node, in accordance with certain variants ofthe 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 ofthe present invention, the user can
`ofien 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 ofthe “group-
`ing” aspect inherent in some implementations ofthe inven-
`lion,
`This example illustrates the “grouping” aspect using a
`simplified graph 300 representing a portion of an airline
`reservation system as shown in PIG. 3.
`In particular, the graph of FIG.3 can be thought of as part
`ofa very simple interactive voice response (“IVR") system.
`
`

`

`US 7,231,379 B2
`
`7
`As described above, each node is uniquely identified, for
`example, by the numbers 1
`through 7 and the identified
`terms “Reservation”. “Domestic”, “International”, “Busi-
`ness Class”, “Economy Class’ are deemed the relevant
`keywords. Note, there is no requirement fora 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 specilic 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
`EconomyClass, 5. 7
`Assuming that the top nodeis assigned the number1, its
`two child nedes (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 takenfromleft to nght 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 inthe first case,
`and § and 7 in the second.
`Using the above, the concept of grouping of nodes from
`different parts of the graph (i.c. nodes that are notsiblings or
`nodes that do not have a common parent) can be explained.
`Presume that the response to a verbal description pre-
`sented as aninitial 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
`identified node could be presented together or in sequence.
`Altematively. and as is the case here, a set of rules can be
`established, for example. such that if an identified nodeis a
`sub-node of another identified node, only the verbal deserip-
`tion of the sub-node(s) is provided because of inherent
`redundaney. Thus. since both “business class” nodes 310.
`314 are sub-nodes of the “reservation” oode 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
`ree 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 “International”, 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 specific
`allowed terms are provided. Thus, in an [VR 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.
`
`wn
`
`an
`
`a
`
`8
`the teachings of the present invention
`Advantageously,
`allow for construction of a more flexible system than ayail-
`able in the prior art. Specifically, 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 thal a synonym ol a keyword may
`also be used by the system to jump to the desired nodes in
`the graph, Example 4 is discussed with relerence 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 choice by time slot, genre. favorite actor or
`actress, etc,
`
`This example, as with the other examples above, use an
`inverted index, in this case one where each node 402, 404,
`406 is uniquely identified by a string of six characters, the
`portion of which corresponding to FIG. 4 is shown as
`follows.
`Programs; acgyet
`Sitcoms: ifgnxh
`Films; vaymos
`Since a common synonym for “Films” is “Movies” a
`thesaurus can be created associating the two. Depending
`upon the particular implementation, thesaurus terms to be
`equated to the keywords can be taken from a standard
`thesaurus or can be custom created for the particular appli-
`cation. In addition, the equating of terms can be done in any
`of a myriad of different ways, the exact implementation
`details of Which however re irrelevant to the invention, but
`a fewrepresentative examples of which however are con-
`tained herein for purposes of illustration.
`In one example case, the equating can be done on a purely
`word basis. Por example, afile can be constructed such that
`one or more single word synonyms are directly associated
`with an index word, for example as follows:
`Movies, Flicks —Films
`Alternatively, the synonyms can be equated with the node
`idlentifier(s) corresponding to the index term, for example as
`follows:
`Movies. Flicks —vnymos
`In the former case, the system would still have to search
`the index after the thesaurus has provided the proper index
`term(s). In the latter case, the thesaurus provides a directlink
`to the respective node(s) so that re-searching Is not required.
`In the system of Example 4, a user who provides the input
`“Movies” would cause the processing to occur as lollows,
`The system would search the inverted index of keywords
`and fail
`to locate “Movies” as a keyword, As a result,
`it
`would search the thesaurus and find that the word “Movies
`is a synonymthat can be correlated with a keyword, At this
`point, depending upon the particular thesaurus,
`it would
`either return to the inverted index and search using th