A I ct eoSs Me THI aLTac
`
`PATENT
`Docket No.: 4428-4001
`
`particular implementation of the invention, one or more of the aspects maybeused togetherin
`
`various permutations and/or combinations, with the understandingthat different permutations
`
`and/or combinations maybebetter suited for particular applications or have moreorless benefits
`
`or advantages than others.
`
`The underlying scenario commonto all these basic examplesis that there is a hierarchical
`
`arrangementto the possible choices that can beillustrated in a form of“tree”structure.
`
`FIG. ]
`
`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 represents a specific choice or option in the
`
`hierarchy. For purposes described in more detail below, each nodeis arbitrarily uniquely
`
`identified in some manner.
`
`In the example of FIG. 1, the individual nodes 102 - 120 are
`
`numbered | 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 wordsthat
`
`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 —
`
`“reservation” deemed important, so all of the other wordsin 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
`
`internationalflight?” In this description, the terms “domestic” and “international” are “key”
`
`words. Similarly, the word “flight” could be a “key” word, for example, for a system that
`
`728851 vi
`
`214
`214
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`particular implementation of the invention, one or more of the aspects maybeused togetherin
`
`various permutations and/or combinations, with the understandingthat different permutations
`
`and/or combinations maybebetter suited for particular applications or have moreorless benefits
`
`or advantages than others.
`
`The underlying scenario commonto all these basic examplesis that there is a hierarchical
`
`arrangementto the possible choices that can beillustrated in a form of“tree”structure.
`
`FIG. ]
`
`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 represents a specific choice or option in the
`
`hierarchy. For purposes described in more detail below, each nodeis arbitrarily uniquely
`
`identified in some manner.
`
`In the example of FIG. 1, the individual nodes 102 - 120 are
`
`numbered | 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 wordsthat
`
`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 —
`
`“reservation” deemed important, so all of the other wordsin 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
`
`internationalflight?” In this description, the terms “domestic” and “international” are “key”
`
`words. Similarly, the word “flight” could be a “key” word, for example, for a system that
`
`728851 vi
`
`214
`214
`
`
`
`THiesee
`
`PATENT
`Docket No.: 4428-4001
`
`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 becauseit has minimal meaning in that context.
`
`Again, the other words can be ignored as well.
`
`The unique identification of each node allowsthe creation ofa list of all the key words
`
`and their associated nodesso that, if a key word is duplicated in two or more nodes,it need only
`
`be listed once. For example, a hierarchicaltree related to “pens” might have nodesfor 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 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 inventionwill be used.
`
`In addition, each
`
`particular node where the keyword appears is associated with the keyword. Thus, with respect to
`
`the pen application above, the keyword “point” might appear in nodes 2, 3, 6, 7, 13 and 15.
`
`Similarly, the keyword “erasable” might appear in nodes 3, 4, 5, 6 and 22. An index, as
`
`described morefully 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 ofthese associations the “‘tree’’ can be negotiated by allowing presentation
`
`of relevant verbal descriptions for the nodes associated with a term, irrespective of where in the
`
`728851 vi
`
`215
`215
`
`
`
`
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`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 bepresentedto illustrate certain concepts related to the
`
`invention.
`
`It should be understood 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 files in a
`
`computer system, pattern analysis or image processing, etc. the term “transaction” as used herein
`
`relating to traversal througha hierarchy to a goal, not mathematical calculationperse.
`
`Moreover, the specific formats used and presented in these examples are purely for
`
`illustration purposes.
`
`It should be understood that that other techniques for interrelating data,
`
`such as hashtables, 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 thelist. A similar approach could be used for the
`
`thesaurus, the important aspect relative to the invention being the relationship amongcertain
`
`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
`
`wherebythat information is kept or maintained.
`
`Example 1
`
`Example | 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 more
`
`728851 v1
`
`216
`216
`
`
`
`TAL ACaes gt ASS SG Me SOL SHLD Stet
`
`PATENT
`Docket No.: 4428-4001
`
`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 occur. At the
`
`pointin 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 wouldbe created that includes an
`
`association of “Fruit” with the top node 202, “Apple” with the bottom left node 204, and
`
`“Orange” with the bottomright node 206. As shown above, that association can be created using
`
`nodeidentifiers, in this example, the node identifiers 1A01, 1A0Q2 and 1A03 arearbitrarily
`
`assigned and used. Thus, the information can be stored in a file, 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 keywordsare 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
`
`728851 vi
`
`10
`
`217
`217
`
`
`
`SLCey ay wSaat
`
`PATENT
`Docket No.: 4428-4001
`
`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 accordingto the invention.
`
`Example 2
`
`Havingillustrated 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, 1AO1
`Apple, 1A02, 2F09
`Orange, 1A03
`
`As aresult, there are two nodesrelevant to the keyword “apple” one being the node 204
`
`in the portion of the graph shownin FIG. 2 and one in the node uniquely identified as 2F09
`
`located somewhereelse in the hierarchy (not shown).
`
`In this example, a user response containing the keyword “apple” would identify nodes
`
`with identifiers |AOQ2 and 2FO9.
`
`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 becauseit
`
`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 jumpto the portion of the graph nearer to node 2F09 sinceit is closer to the user’s goal
`
`thereby speeding up the process and avoiding potentially confusing or frustrating the user.
`
`728851 vl
`
`11
`
`218
`218
`
`
`
`GE
`
`
`
`at a SIL AL ak etl
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`Example3
`
`While the verbal descriptions associated with various nodes will generally be chosen to
`
`accurately represent the node, in accordance withcertain variants of the invention, it is possible
`
`to create a situation where a user response takes them awayfrom 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 notrigidly trace
`
`throughthe hierarchy. This is accomplished by virtue of the “grouping” aspect inherent in some
`
`implementations of the invention.
`
`This exampleillustrates the “grouping” aspect using a simplified graph 300 representing
`
`a portion of an airline reservation system as shownin FIG. 3.
`
`In particular, the graph of FIG.3 can be thoughtofas part of a very simple interactive
`
`voice response (“IVR”) system.
`
`Asdescribed above, each nodeis uniquely identified, for example, by the numbers 1
`
`through 7 and the identified terms “Reservation”, “Domestic”, “International”, “Business Class”,
`
`“Economy Class” are deemed the relevant keywords. Note, there is no requirementfor 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 specific data
`
`pattern.
`
`Again, an inverted index is created as described above associating those keywords with
`
`the nodes, in this case:
`
`|
`
`Reservation,
`Domestic, 2
`International, 3
`
`728851 vl
`
`12
`
`219
`219
`
`
`
`a act
`
`PATENT
`Docket No.: 4428-4001
`
`Business Class, 4, 6
`Economy Class, 5, 7
`
`Assumingthat the top nodeis 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 cach associated with
`
`two nodes, 4 and 6 inthe first case, and S$ 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 commonparent) can be explained.
`
`Presume that the response to a verbal description presented as an initial query of “What
`
`do you want to do?” was “Makea business class reservation.” In this case there are two
`
`keywordspresent, “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 1s the case here, a set of rules can be established, for example, such thatif
`
`an identified node is a sub-node of another identified node, only the verbal description 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
`
`728851 v1
`
`13
`
`220
`220
`
`
`
`LT aeb al Oe
`
`ow LAL oH eee aes
`
`PATENT
`Docket No.: 4428-4001
`
`system, in presenting the verbal descriptions from each, in effect, alters the tree structure and
`
`groups these nodesin the result. Thus, the combination of result nodes presented depends upon
`
`the user query or response, not that predetermined by the graph structureitself.
`
`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 whetherthey are
`
`combinedor provided sequentially or by other nodes.
`
`Example 4
`
`A persistent and further drawback presentin the priorart is the inability to operate if any
`
`term other than the specific allowed terms are provided. Thus, in an IVR ofthe priorart,
`
`providing anything other than the recognized term(s) will likely result in meaningless repeat of
`
`the same inquiry by the IVR oran error.
`
`Advantageously, the teachings of the present invention allow for construction of a more
`
`flexible system than available 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
`
`synonymof a keyword may also be used by the system to jump to the desired nodesin 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 choice by time slot, genre, favorite actor or actress, etc.
`
`728851 vi
`
`14
`
`221
`221
`
`
`
` TLSe
`
`PATENT
`Docket No.: 4428-4001
`
`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 stringof six characters, the portion of
`
`which corresponding to FIG. 4 is shownasfollows.
`
`Programs; acgyct
`Sitcoms; ifgnxh
`Films; vnymos
`
`Since a common synonymfor“Films”is “Movies” a thesaurus can be created associating
`
`the two. Depending uponthe particular implementation, thesaurus terms to be equated to the
`
`keywords can be taken from a standard thesaurus or can be customcreated for the particular
`
`application.
`
`In addition, the equating of terms can be done in any of a myriad ofdifferent ways,
`
`the exact implementation details of which howeverre irrelevant to the invention, but a few
`
`representative examples of which howeverare contained herein for purposes of illustration.
`
`In one example case, the equating can be done on a purely wordbasis. For example, a
`
`file can be constructed such that one or more single word synonymsare directly associated with
`
`an index word, for example as follows:
`
`Movies, Flicks—Films
`
`Alternatively, the synonyms can be equated with the node identifier(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.
`
`728851 vl
`
`15
`
`222
`222
`
`
`
`
`ATE eeTha SA Ap ac
`
`PATENT
`Docket No.: 4428-4001
`
`In the system of Example 4, a user whoprovides the input “Movies” would cause the
`
`processing to occuras follows.
`
`The system would search the inverted index of keywords and fail to locate “Movies” as a
`
`keyword. Asa result, it would search the thesaurus and find that the word “Movies”is a
`
`synonym that can be correlated with a keyword. At this point, depending uponthe particular
`
`thesaurus, it would either return to the inverted index and search using the synonym keyword
`
`“Films” and return the result as the node 406 identified by “vnymos”, or go directly to the node
`
`406 identified by “vnymos” based upon the thesaurus entry.
`
`Of course, it is possible (and likely) that in actual usage a synonymwill be associated
`
`with more than one keyword. For example, ““Comedies” may be associated with both the
`
`keywords“Sitcoms” and “Films”, resulting in, for example, the following entry in a thesaurus:
`
`Comedies—Sitcoms, Films
`
`In this case, a search for “Comedies” would result in the system identifying that the
`
`synonym wasassociated with nodes 404, 406 for both “Sitcoms” and “Films”, and it would
`
`return both terms or node identifiers corresponding to the two keywordsasthe result.
`
`Example 5
`
`Advantageously, the thesaurus concept can be extended further so that an initially
`
`unknown word (i.e. a word that is neither a keyword nor a thesaurus word) can be learned by the
`
`system and added to a thesaurus for future use.
`
`This example is described with reference to FIG. 5 whichis a portion 500 of a larger
`
`system graphaspart of a very simple “geographic information system” found in some
`
`automobiles, kiosks and elsewhere today. Such a system enables a user to, among other things,
`
`728851 vl
`
`16
`
`223
`223
`
`
`
`vole HT art Ot a
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`identify and get information about different locations in an environment. For example,
`
`information about particular types of restaurants in an area.
`
`In this example, the inverted index for the portion 500 shownin FIG. 5 could look as
`
`follows:
`
`Restaurants, |
`Pizza, 2
`Burgers, 3
`Chinese, 4
`
`A userissues the following query to the system “fast food”in order to find a quick meal.
`
`The system’s search of both the index and thesaurus would result in the “term’’, in this
`
`case a phrase, not being found in either.
`
`In this case, it is an unknownphrase, and the system has
`
`to learn the “meaning” ofthe term.
`
`To dothis, the systemfirst offers the verbal description from the top level node(s) 502 to
`
`the user — in this example, just “Restaurants”. The user presumably providesa posilive response.
`
`(Of course, in areal system, it is possible and likely there are more top level nodes thanjust one.
`
`In that case, the user would be offered two or more of these nodes, and would haveto select
`
`“Restaurants” to match his intended request.)
`
`Continuing on, once the user has responded affirmatively, the system moves downthe
`
`tree and offers the verbal description from each of the child nodes: “Pizza” (504), “Burgers”
`
`(506), and “Chinese” (508). Presuming that the user picks “‘Pizza’’, the transaction interaction
`
`would look somethinglike this:
`
`User: Fast food
`
`System: Restaurants?
`
`728851 v1
`
`17
`
`224
`224
`
`
`
`HA aeeh ye Mea IL2
`
`PATENT
`Docket No.: 4428-4001
`
`User: Yes
`
`System: Pizza, Burgers, or Chinese?
`
`User: Pizza
`
`At this point, the system has “learned”for the time being that it can equate “‘fast food”
`
`with “pizza” and can add “fast food” as a synonym to “pizza”in the thesaurus.
`
`This user, who first used the unknownterm “fast food”, had to trace a path downthetree.
`
`However, now the systemis able to associate “pizza” with “fast food” and create or add a
`
`thesaurus entry to reflect this association, for example as follows:
`
`Fast food — Pizza
`
`Thus, the system has learned a meaning of the initially unknownterm“fast food” and has
`
`addedit to the thesaurus for future use.
`
`As aresult, a subsequent uses of the same term“fast food”will enable the system to jump
`
`directly to the “pizza” node 504.
`
`Example 6
`
`This example illustrates how additional meanings for an existing thesaurus termor phrase
`
`can be learned by the system for future use, whether the existing thesaurus term or phrase was an
`
`original thesaurus term or one previously learned with continuing reference to FIG. 5.
`
`At this point, the inverted index is unchangedas:
`
`Restaurants, |
`Pizza, 2
`Burgers, 3
`Chinese, 4
`
`Additionally, presume the following entry now exists in the thesaurus.
`
`728851 v1
`
`18
`
`225
`225
`
`
`
`oy SAL SOke
`ra elt
`
`PATENT
`Docket No.: 4428-4001
`
`Fast food — Pizza
`
`Suppose a newuser now issues the query “fast food” as above, but with “Burgers”rather
`
`than “Pizza” in mind.
`
`Based uponthe thesaurus, the system would godirectly to the “Pizza” node. However,
`
`the user will reject “Pizza”, having “burgers” in mind. By rejecting the “Pizza” node 504
`
`description, the user indicates that the “Pizza” node 504 is not of interest. The systemis
`
`therefore configured with a further set of rules, in this case one in which the system goes up in
`
`the hierarchy to a higher node, the top node 502 in this portion of the example, and provides the
`
`verbal descriptions for the other nodes 502, 504, 506, 508 so as to cause a tracing downthetree.
`
`This canbeillustrated by the following “dialog”:
`
`User: Fast food
`
`System: Pizza?
`
`User: No
`
`System: Restaurants?
`
`User: Yes
`
`System: Pizza, Burgers, or Chinese?
`
`User: Burgers
`
`This time, althoughthis user has had to trace throughatleast a portion of the path from a
`
`higher-level node 502 of the tree 500, the system has learned yet another meaning for“fast
`
`food’.
`
`It now adds this meaning to the earlier entry in the thesaurus, for example as:
`
`Fast food — Pizza, Burgers
`
`728851 vi
`
`19
`
`226
`226
`
`
`
`
`
` Cae sh eT Paw I A est
`
`PATENT
`Docket No.: 4428-4001
`
`It has now learned two meaningsfor future use. [f a user were now to issue the query
`
`“Fast food”, the system would respond with the verbal descriptions from the nodes 504, 506
`
`correspondingto both Pizza and Burgers.
`
`Thus, the system can keep learning new meaningsof terms based on the intended
`
`meanings of users “deduced”from the interactions between users and the system.
`
`Of course, the nature and extent to which the system will incorporate synonyms and/or
`
`keywords in a continual learning process will not only depend uponits construction and rules,
`
`but also on the quality of the original thesaurus and the quality of the initial inverted index.
`
`In
`
`addition, where in the tree the system jumpsif the user rejects the initial meaning(s) offered by
`
`the system can be handled different ways in different implementations.
`
`For example, the system can always jumpto fixed ancestor(s) (either the top node or a
`
`parent or some ancestor(s) at an intermediate point) or a fixed level (e.g. halfway from the top).
`
`This approachhas the advantage of being simple to implement, but it has the problem of
`
`inflexibility because it may be relatively efficient for certain graphs and associated verbal
`
`descriptions, but not for all. For example, if two or more nodes’ verbal descriptions are offered
`
`and rejected, the relevant node selected would have to be commonancestor(s) of the offered
`
`nodes.
`
`In other words, with reference to Example 6 which is part of a larger tree, going up to the
`
`“Restaurants” node 502 would meangoingto the parentof the “Pizza” node 504 ratherthanall
`
`the way to the top in the larger tree containing the portion 500 shown.
`
`A moreflexible alternative uses the information recorded in the thesaurus to find every
`
`synonym for “pizza” in the thesaurus and collect all the other keywords associated with those
`
`synonyms. Then the system would search the inverted index to identify all the nodes associated
`
`728851 vl
`
`20
`
`227
`227
`
`
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`with these other associated keywordsandidentify the most commonancestorof all of those
`
`nodes and goto it. By using the information in the thesaurus in this way the system makes use
`
`of knownproperties of the one meaning of “fast food”, whichis “Pizza”, to construct an
`
`intelligent hypothesis about where the other meanings of “fast food” mightlie in the graph. This
`
`allows the user to reach another meaning withthe least effort and allows the system thereby to
`
`learn what the new meaning of “fast food” is more efficiently.
`
`Example 7
`
`Ofcourse, just as it may be desirable to create implementations to add meanings to the
`
`thesaurus, it may be equally or more desirable to cause an existing meaning for a thesaurus word
`
`to be dropped, for example, due to relative lack of use. This process is described with continuing
`
`reference to FIG. 5 and the associated inverted index, particularly with respect to the thesaurus
`
`entry resulting from the most recent example.
`
`Fast food — Pizza, Burgers
`
`In this example, presumethat there have been several uses of the query “fast food” and
`
`that the user(s) issuing these queries have almost always selected “Burgers” and almost never
`
`“Pizza,
`
`In accordance with another implementation of the invention, the system is constructed to
`
`track the frequency of use of a particular term in the thesaurus. Depending upontheparticular
`
`implementation, the tracking can be doneforall entries in the thesaurus, for only those added as
`
`part of the “learning” process, or for some specified combination thereof.
`
`In addition, some specified criterion is used to determine when, and whichterms,if any,
`
`should be removed from the thesaurus. Depending upon the particular implementation the
`
`728851 vi
`
`zl
`
`228
`228
`
`
`
`HAD ct Sa ek
`
`|
`
`
`
`PATENT
`Docket No.: 4428-4001
`
`criterion can be based uponusagerelative to time, usage of a particular term relative to some
`
`otherterm(s),term usagerelative to overall thesaurus usage, or simply elimination of all added
`
`terms not used since the last purge.
`
`Thus, presuming that the system has kept track of the frequencyof use of different
`
`meanings of “fast food”, and that “Pizza” does not meet the criterion for a sufficiently high
`
`frequency, the meaning “Pizza” can be dropped as a synonym for“Fast food” and the entry (after
`
`purging) would look as follows:
`
`Fast food — Burgers
`
`Thus, a further enhanced implementation can be constructed so the system is dynamically
`updating the thesaurus, either adding meanings or dropping meanings for existing and/orinitially
`
`unknown words.
`
`Example 8
`
`A further advantage to the invention is that, in some implementations,it can be
`
`configured so that, when there are multiple relevant nodes to be presented, an associated ranking
`
`can be used to determine the type, method or order of presentation. For example, the ranking can
`
`be based upon the frequency of use of particular nodes, which is tracked in these
`
`implementations, so that the most frequently selected or used nodes are presented first, more
`
`prominently, or in a particular manner.
`
`For example, this can be illustrated by continuing from Example 7, where the thesaurus
`
`entry wasas follows:
`
`Fast food — Pizza, Burgers
`
`728851 v1
`
`22
`
`229
`229
`
`
`
` CYi wwaL,
`
`PATENT
`Docket No.: 4428-4001
`
`Underthe assumption that the system has been tracking the frequency of usage of the “Pizza”
`
`_ node and the “Burgers” node and each has been accessed an identical number of times. When a
`
`user enters the query “Fast food”, as above, the system presents the user with both the “Pizza”
`
`node 504 and the “Burgers” node 506, but becauseit tracks usage and the usageis the same,it
`
`presents them in the order theyarelisted, i.e. “Pizza” and then “Burgers”. However,at this
`
`point, the user’s selection will cause one entry to have a greater frequency ofusagerelative to the
`
`other entry, for example a selection of “Burgers” will make it have a higher frequency of usage
`
`and, accordingly, a higher ranking for the next instance ofuse.
`
`Thus, the next time the system will be presenting both the “Pizza” and “Burgers” nodes
`
`to a user, the “Burgers” node 506 will have the higher frequency of usage and, accordingly, will
`
`be presented first, or more prominently, or in some other specified manner becauseof its
`
`ranking. If the frequency reverses with use so that the “Pizza” node 504 outranks “Burgers”
`
`node 506, then the “Pizza” node 504 will supplant the “Burgers” node 506.
`
`Example 9
`
`A further variant of Example 8 allows the node rankings to be used to prune the nodes
`
`themselves.
`
`In this variant, a criterion can be specified, typically zero usage over a long
`
`specified period of time, that is used to remove an entire node. This is advantageously made
`
`possible because of the system’sability to “jump” among nodes. Thus, it may occur that a node
`
`within the tree is never accessed, but a child node of that node is.
`
`In some variants therefore,
`
`whenthis state exists for a sufficiently long period of time, the system is constructed to delete
`
`that node.
`
`It should be understoodthat, if handled properly, this process will not even affect the
`
`>
`p
`“learning” process because, even if no user action ever directly causes the node to be presented,
`
`728851 vl
`
`23
`
`230
`230
`
`
`
`acesre
`
`PATENT
`Docket No.: 4428-4001
`
`if the learning process causes the nodeto be presented the node’s access frequency will be non-
`
`zero and it will not be “pruned”.
`
`In addition, by tracking access frequency on a nodebasis, a qualitative evaluation of the
`
`hierarchical system can be made and visualized. This makesit possible to review the overall
`
`hierarchy after someperiod oftime and periodically optimize it based upon the result instead of
`
`relying purely upon the dynamic optimization that inherently and naturally flows from use ofthe
`
`teachings of the invention.
`
`Having now described various component aspects of different variants implementing the
`
`invention, by way of the above examples, it should be understood that the “jumps” can occur
`
`from any nodeto any node,i.e. vertically and/or laterally and to another node that is higher,
`
`lower or on the same“level” as the node from which the jump is made. All mannerof vertical
`
`and lateral jumps from multiple nodes to multiple nodes are possible.
`
`In addition, it should be understood that in some applications (like documentretrieval
`
`systems) the verbal description from the identified node may be the one issued whereas, in others
`
`(like an IVR system), the verbal descriptions for the children of the identified nodes may be what
`
`is presented. Nevertheless, in both cases, the process as described above by way of examplewill
`
`be the sameor directly analogous.
`
`Having described the various aspects individually a more commercially suitable example,
`
`employing a combination of the above examples, can now be presented with reference to FIG. 6
`
`whichillustrates a simplified example of an “interactive voice response unit” (IVR) hierarchy
`
`600 that might be used in theairline industry. Of course, a real menu tree used in an IVR may
`
`have any numberof nodes from several, up to a thousand, or more. For example, a tree with 4
`
`728851 vi
`
`24
`
`231
`231
`
`
`
` io CT aS
`
`PATENT
`Docket No.: 4428-4001
`
`branches from each node and which has 5 levels uniformly would have 1365 nodes. As shown
`
`in FIG. 6, the tree 600 is a hierarchical tree and consists of the following nodes and branches:
`
`Initial start (node a0) 602
`
`domestic flight arrival information (node al) 604
`
`domestic reservations (node a2) 606
`
`international flight arrival information (node a3) 608
`
`international reservations (node a4) 610
`
`The node 604 identified by al is a service node with pre-recorded information.
`
`The node 606 has twochild nodea 2, first/business class (node a5) and economy (nodea6).
`
`The node 608 identified by a3 is service node with pre-recorded information.
`
`The node identified as a4 has three child nodes identified as first class (node a7), business class
`
`(node a8), and economy(node a9).
`
`The nodes 612, 614, 616, 618, 620 identified as a5, a6, a7, a8, a9 are all service nodes(i.¢.
`
`terminal nodes) where a respective customerservice representative will interact with the caller.
`
`Of course, a real system may also have a choiceat the top level or at each level for a live
`
`operator and may even have a choice to go back to the previous menu.
`
`Even for such a simple example,in a traditional interactive voice response system, the
`
`caller would haveto listen to several choices and then traverse a path downto a service node.
`
`Someoneinterested in business class reservations on a domestic flight would have to traverse the
`
`path(a0, a2, a5) for example. This involves listening to multiple choicesat cach level of the tree
`
`(e.g. first a prompt at a0, then four prompts offering al, a2, a3, and a4 at the next level, at which
`
`the caller would choose a2, and finally two prompts offering a5 and a6, at which level the caller
`
`728851 vi
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
