|||||||||||||||||||||||||||||||||l|||
`
`
`
`||
`
`
`
`
`
`|||l||||||||||||||||||||||||||||
`
`USOU7231379B2
`
`(12}
`
`United States Patent
`Parikh et a].
`
`(10) Patent No.:
`
`(45} Date of Patent:
`
`US 7,231,379 32
`Jun. 12, 2007
`
`(54)
`
`(75}
`
`NAVIGATION [N A HIERARCHICAL
`ST RUCTURED TRANSACTION
`PROCESSING SYSTEM
`
`Inventors: Prashant Parikh. New York. NY (US):
`Stanley Peters. Menlo Park. CA (US)
`
`(73)
`
`Assignee: Noema, Inc.. New York. NY (US)
`
`(*1
`
`Notice:
`
`Subject to any disclaimer. the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(1)) by 485 days.
`
`(21)
`
`Appl. No.: 10099359
`
`(22)
`
`Filed:
`
`Nov. 19, 2002
`
`(65)
`
`(51)
`
`(52)
`(58)
`
`(56)
`
`Prior Publication Data
`
`US 200410098381 Al
`
`May 20. 2004
`
`Int. Cl.
`(2006.01)
`G06F J 7/30
`70772; 70776; 70773; 70714
`U.S. Cl.
`Field of Classification Search
`70771.
`70712. 3. 4. 5. 6. 7. 8. 9. 10. 100. 101. 102.
`707.1103. 104.1
`See application file for complete search history.
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5.033.560 A "‘
`6.405.188 Bl
`(1.408.290 131“‘
`6.510.400 Bl
`6.654.731 Bl *
`6.67211 59 El
`6.678.677 112 "‘
`6.859.212 132
`
`312000 Wicai
`6.12002 Schwartz et' al.
`052002 'l'l'licssotl ct al.
`132003 Marchisio
`11.52003 Mahesh
`152004
`1.in ct al.
`19200-4 Roux et al.
`2.12005 Kumar et a1.
`
`70755
`
`700552
`
`706-"45
`
`70733
`
`* cited by examiner
`
`Prfrtiafit' Examiner Y'tcun Wu
`(74) Attorney. Agent. or Firm Morgan & Finnegan I.I..lJ
`
`[57}
`
`ABSTRACT
`
`A method performed in a system having multiple navigable
`nodes interconnected in a hierarchical arrangement involves
`receiving an input containing at least one word identifiable
`with at
`least one keyword. identifying 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 illvenod 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 identity at least one node corre-
`lated to the meaningful word by the inverted index and jump
`to that node without first traversing any other node.
`
`5.812.134 A ‘1‘
`
`971998 Pooscrct a].
`
`707-"102
`
`7 Claims, 11 Drawing Sheets
`
`902
`
`
`
`Load stop words [mm ‘s’
`
`EX1001
`EX1001
`
`Has
`
`YES
`
`keyword file been
`
`
`processed?
`
`
`
`Eliminate stop
`
`kBywords
`
`Ellmlnata du pllcale mes
`swords
`[rent I:
`
` 1
`
`1
`
`

`

`US. Patent
`
`Jun. 12, 2007
`
`Sheet 1 of 11
`
`US 7,231,379 32
`
`
`
`2
`
`

`

`US. Patent
`
`Jun. 12, 2007
`
`Sheet 2 of 11
`
`US 7,231,379 32
`
`FIG. 2
`
`200
`
`\
`/202
`/ 206
`
`/ 306
`
`International
`
`Economy
`Class
`
`Business
`Class
`
`308
`
`3
`
`
`
`
`
`\ 312 / 314/
`
`Economy
`Class
`
`Business
`Class
`
`

`

`US. Patent
`
`Jun. 12, 2007
`
`Sheet 3 of 11
`
`US 7,231,379 32
`
`400
`
`\
`/402
`/406
`404 \
`
`Programs
`
`FIG. 4
`
`500
`
`/502
`\
`
`504 \
`
`505/
`508/
`FIG. 5
`
`
`
`4
`
`

`

`US. Patent
`
`Jun. 12, 2007
`
`Sheet 4 of 11
`
`US 7,231,379 32
`
`/602
`
`Initial Node
`a0
`
`600
`
`/
`
`/610
`
`Domestic
`Arrivals Info
`
`Domestic
`Reservations
`
`Intern ational
`Arrivals
`
`International
`Reservations
`
`604 /
`
`\\ 505 \\ 608
`
`FirstlElusiness
`Class
`a5
`
`Economy
`Class
`a6
`
`
`
`514
`
`512/
`
`First
`Class
`
`Business
`Class
`
`Economy
`Class
`
`616/ 618/
`
`620/
`
`5
`
`

`

`US. Patent
`
`Jun. 12, 2007
`
`Sheet 5 of 11
`
`US 7,231,379 32
`
`Read file p
`
`
`
`
`
`Extract keywords from 'p‘
`
`
`
`Store keywords from 'p'
`
`Read file f
`
`
`
`
`
`
`Extract keywords from 'f'
`
`Store keywords from 'f‘
`
`
`
`6
`
`

`

`US. Patent
`
`Jun. 12, 2007
`
`Sheet 6 of 11
`
`US 7,231,379 32
`
`902
`
`Load stop words from 's'
`
`FIG. 9
`
`904
`
`
`
`Has
`
`
`keyword file been
`
`processed?
`
`
`
`
`N0
`
`Read file x
`
`Eliminate stop words from
`keywords
`
`Eliminate duplicate words
`
`from keywords
`
`Construct inverted index
`
`YES
`
`920
`
`Eliminate stop words from
`thesaurus
`
`Eliminate duplicate words
`from thesaurus
`
`922
`
`924
`
`9
`
`0
`
`Mark thesaurus file as
`processed
`
`Mark keyword file as
`processed
`
`
`
`Have both
`
`
`
`
`
`eyword and thesaurus
`files been
`
`
`
`YES
`
`
`
`processed?
`
` 918
`
`7
`
`Copy inverted index and
`thesaurus to mfg
`
`DONE
`
`

`

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

`

`US. Patent
`
`Jun. 12, 2007
`
`Sheet 8 of 11
`
`US 7,231,379 32
`
`FIG. 11
`
`1102
`
`Read fiies t.cfg, Lofg, f, x and 5
`
`1104
`
`Load files t.cfg, Lofg, 'f‘,
`
`'s' and 'x'
`
`1 106
`
`Provide initial verbal description
`
`Receive responsefinput from user
`
`1108
`
`
`1112
`
`
`Does
`response contain unknown
`word?
`
`YES 0
`
`
`NO
`
`YES
`
`.
`.
`Does user Wish to continue?
`
`
`
`
`
`
`NO
`
`END
`
`9
`
`

`

`US. Patent
`
`Jun. 12, 2007
`
`Sheet 9 of 11
`
`US 7,231,379 32
`
`1202
`
`1204
`
`1206
`
`identity keywords from response/input
`
`identify thesaurus words in t.cfg and l.cfg, if
`any. identified from responsefinput
`
`
`
`
`
`
`Select node with verbal description(s) that
`best match keywords and thesaurus words
`
`
`
`
`1218
`
`1208
`
`1210
`
`1212
`
`1214
`
`Any
`nodes
`
`selected?
`
`Select top level node
`
`Issue verbal
`
`
`
`
`
`
`
`
`
`ls
`
`description for node
`single leaf node
`
`
`selected?
`and receive reSponse
`
`
`YES
`
`
` Issue verbal
`
`
`
`
`ES
`
`description for node
`and (if applicable)
`receive response
`
`1222
`
`verbal description
`corresponding to
`
`
`
`NO
`
` ls form for
`verbal description
`available?
`
`
`YES» 0
`
`
`NO
`
`FIG. 12
`
`10
`10
`
`

`

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

`

`US. Patent
`
`Jun. 12, 2007
`
`Sheet 11 of 11
`
`US 7,231,379 32
`
` 140
`
`
`
`ls word
`YES
`
`present in
`|.cfg?
`
`Add the word to the list of
`
`learned words with
`
`
`
`
`Merge keywords from
`selected prompt into the
`
`
`
`list of synonyms
`
`
`
`associated with the word
`prompt as Synonyms
`
`
`
`
`keywords from selected
`
`
`
`Copy changes to |.cfg
`
`1408
`
`FIG. 14
`
`12
`12
`
`

`

`US 1231.379 B2
`
`1
`NAVIGATION IN A HIERARCHICAL
`STRUCTURE!) TRANSACTION
`PROCESSING SYSTEM
`
`171F511) OF 'I‘HF. INV’lziN'l‘ION
`
`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
`file or records. bttt otherwise reserves all copyright rights
`whatsoever.
`
`BACKGROUND OF THE INVENTION
`
`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
`the most efficient manner possible to accomplish a particular
`goal.
`In modern nuttherrmtics. graph theory is used to study
`networks ofhjerarchical choices. The hierarchical networks
`can be represented as a graph structure. Graph theory finds
`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 ruap. The venices 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 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 1, 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 1" red.
`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.
`[11 general. whether for a telephone response network or
`for any other application representable by a graph structure.
`
`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 “traits-
`action“ we mean an operation performed electronically with
`a user.
`In general.
`there will also he 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. If this is not done
`as quickly and eflicient'ly 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 first vertex and the goal
`vertices multiplies rapidly. Therefore. the ability to reach the
`goal 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.
`
`SUMMARY 01: Till". INVl'iN'I‘ION
`
`invention creates a method for navigating
`The present
`efliciently and naturally through a series ofchoices to obtain
`information. perform transactions. 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 manner that 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;
`[-‘IG. 2 is an example ponion 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 {“lVR") 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.
`‘i'A, TB. and 8-10 are collectively a flowchart
`illustrating an example sentp process for use in accordance
`with an example implementation of one variant of the
`present invention; and
`FIGS. 11-14 are (xtllectively an overall flowchart illus-
`trating an example process in accordance with a further
`variant of the present invention.
`
`DE'I'AILEI) DESCRIPTION
`
`10
`
`3t]
`
`4t]
`
`45
`
`50
`
`55
`
`60
`
`65
`
`In graph theory. mathematicians refer to a “path" from
`one vertex in a graph to another specified vertex in the graph
`as consisting ofa sequence ofedgcs that connect the venices
`between the first vertex and the final vertex. If the path
`13
`13
`
`

`

`3
`
`4
`
`US 123 1,379 B2
`
`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 “cormected” 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 lhwry 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 “mentl 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
`vert'x. (ii) every vertex except the first 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 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 the corresponding “menu“ presents to the user as
`an option. 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 andfor 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
`modifies itself to thereby increase the likelihood that a user
`will efficiently and quickly reach the goal.
`For 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
`It should be understood that
`applicable to a wide range of dilferent 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. Represent‘ ~
`tive examples of suitable applications for the invention
`include implementing an enhanced and more efficient
`“Find" function or file system browser for personal com-
`puter operating systems, a navigation system for television
`
`10
`
`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 sortie hierarchical
`navigation aspect as part of its operation.
`In order to more fully tutdcrstand the invention. various
`independent aspects are now presented below by way of
`simple illustrative examples. In this mamier the teachings of
`the invention can be understood in a way that makes it
`possible to use. overlay andtor combine those aspects in a
`beneficial maturer 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 andt‘or combinations. with the under—
`standing that different permutations andfor combinations
`may be better stlitod for particular applications or have more
`or less benefits or advantages than others.
`these basic
`The underlying scenario corrunon to all
`examples is that there is a hierarchical arrangement to the
`possible choices that can be illustrated in a form of “tree”
`structure.
`
`3t]
`
`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. For
`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 nutri—
`bered I
`thmugh 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" word—“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 flight?” 111 this description, the terms “domes-
`tic" and “international" are “key" words. Similarly. the word
`“flight” could be a “key“ word, for example. for a system
`that involves not only airline travel but also rail andtor cruise
`travel or it could be an “ignored" or stop word for a purely
`airline related system because it has minitnal meaning in that
`context. Again, the other words can be ignored as well.
`The unique identification of each node allows the creation
`of a list of all the key words and their associated nodes so
`that. ifa 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. fine 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
`identifier 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
`14
`14
`
`4t]
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`5
`
`6
`
`US 2,231,379 B2
`
`node identifiers lAOl. 1A02 and 1A03 are arbitrarily
`assigned and used. Thus, the information can be stored in a
`file. for example, as follows:
`Fruit. lAtll
`Appie. 1AM
`Orange. 1AM
`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
`the node whose verbal description should be presented next.
`thereby avoiding the need to traverse intervening nodes. for
`example. through the “fruit“ node (202) LAM. 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
`l'ixampie l graph of HG. 2 applies, but relevant portion of
`the index is as follows:
`Fruit. 1A8]
`Apple. IAUZ. 21:09
`Orange. 1.403
`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
`2F09 located somewhere else in the hierarchy (not shown).
`In this example. a user response containing the keyword
`“apple" would identify nodes with identifiers lAUZ and
`21409.
`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-709 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
`
`10
`
`3t]
`
`4t]
`
`45
`
`50
`
`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. IS
`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 marmcr.
`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 and likely 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 trsed 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 purely for illustration purposes. it should
`be understood that other techniques for int‘errelating 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 in a list as the
`“ti-th" item could be used as an index into another list
`
`containing the nodes correlated to the list. A similar
`approach could be ttsed 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 simplified 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
`tnore 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 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 ocettr. 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 leli node 204, and “Orange“ with
`the bottom right node 206. As shown above, that association
`can be created ttsing node identifiers. in this example. the
`
`55
`
`60
`
`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
`simplified graph 300 representing a portion of an airline
`reservation system as shown in FIG. 3.
`ln particular. the graph of FIG. 3 can be thought of as part
`of a very simple interactive voice response (“NR") system.
`15
`15
`
`65
`
`

`

`7
`
`8
`
`US 123 1,379 B2
`
`Advantageously, the teachings of the present invention
`allow for construction of a more flexible system than avail-
`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 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.
`
`10
`
`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: acgyct
`Sitcoms: ifgnxh
`Films: vnymos
`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 difi'erent ways. the exact implementation
`details of which however re irrelevant to the invention. but
`a few representative 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. For example. a file 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
`identitierfs} 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
`ternt(s). In the latter case. the thesaurus provides a direct link
`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 lbllows.
`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”
`
`3o
`
`40
`
`45
`
`50
`
`As described above, each node is uniquely identified, for
`example. by the numbers 1
`through it and the identified
`terms “Reservation”, “Domestic", “International". “Busi-
`ness Class". “Economy Class" are deemed the relevant
`keywords. Note. there is no requirement for a the “keyword”
`to he a single word.
`in some implementations, keywords
`could be single words, phrases of two or more words. or
`even some other toml of information like a specific data
`pattern.
`Again. rm 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 first case,
`and 5 and 7 in the second.
`
`Using the above. the concept of grouping of nodes from
`diflerent parts ofthe 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
`identified 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 identified node is a
`sub-node of another identified 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 ot'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 efiect. 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 C lass" being under both
`“Domestic" and “Intentational”. 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. This, in an IVR of the prior art,
`providing anything other than the recognized