`
`European Patent Office
`
`Office europ6en des brevets
`
`Publication number: (cid:9)
`
`I I
`0 609 517 A2
`
`EUROPEAN PATENT APPLICATION
`
`0 Application number: 93119514.3
`
`0 Int. CI.5: GO6F 15/403, GO6F 15/40
`
`0 Date of filing: 03.12.93
`
`0 Priority: 02.02.93 US 13888
`
`0 Date of publication of application:
`10.08.94 Bulletin 94/32
`
`0 Designated Contracting States:
`DE FR GB
`
`0 Applicant: International Business Machines
`Corporation
`Old Orchard Road
`Armonk, N.Y. 10504(US)
`
`0 Inventor: Braden-Harder, Lisa Carol
`Butler Hill Road
`Somers, New York 10589(US)
`Inventor: Kim, Michelle Yoonkyung Lee
`23 Pheasant Run
`Scarsdale, New York 10583(US)
`Inventor: Klavans, Judith Lynn
`40 South Drive
`Hastings-on-Hudson, New York 10706(US)
`Inventor: Zodrozny, Wlodek Wlodimier
`1 Winding Court
`Mohegan Lake, New York 10547(US)
`
`0 Representative: Harrison, Robert John
`IBM Deutschland
`Informationssysteme GmbH
`D-70548 Stuttgart (DE)
`
`user into describing the multimedia information with
`a string of words so that they conform to the gram-
`mar.
`To retrieve the information, a user can use a
`query which is parsed according to the rules of
`grammar into a query structure in a way identical to
`or similar to the way the structured index was
`formed. This query structure is used to create a key
`which is used along with a searching algorithm to
`search the database of matched pairs. The search
`may be broadened to include words related to the
`words in the key. A list of matched pairs that match
`the key is returned. The segment of matched pairs
`in the list is used to locate and retrieve the archived
`multimedia information.
`
`0 Indexing multimedia objects.
`
`0 To archive information, a phrase or sentence
`describing the information, typically expressed in a
`natural language and conforming to the rules of a
`grammar (like a natural language grammar) is used
`to create a structured index which also conforms to
`the natural language grammar. The structured index
`has structure because the words in the index have a
`function and a relationship among each other as
`determined by the grammar. The index is combined
`with a location pointer of information to be cataloged,
`preferably multimedia information, to form a
`matched pair, i.e., a structured index and a segment
`(or a pointer to a multimedia object). The matched
`pair is stored in a database for later retrieval. A
`heuristic interface presents the multimedia informa-
`tion along with a template in order to prompt the
`
`EP 0 609 517 A2
`
`Rank Xerox (UK) Business Services
`13.10/3.09/3.3.4)
`
`Page 1 of 16
`
`MINDGEEK EXHIBIT 1004
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`
`
`EP 0 609 517 A2
`
`FIG. 2
`
`USER 1255
`
`,-260
`
`
`HUERISTIC
`INTERFACE
`
`
`
`0 2 5
`di/
`
`MULTIMEDIA
`270"..._IN FORMAT ION
`(SEGMENT)
`
`INPUT
`COMPONENTS _5- 275
`(WORDS)
`
`280
`
`(
`
`282
`
`284
`
`PARSER
`
`MAPPING y 285
`
`ALGORITHM
`
`COMBINE
`
`290
`
`MATCHED PAIR
`(SEGMENT,INDEXI
`
`295
`
`STORE IN STRUCTURED
`INDEX DATABASE
`
`298
`
`2
`
`Page 2 of 16
`
`MINDGEEK EXHIBIT 1004
`
`
`
`1 (cid:9)
`
`EP 0 609 517 A2
`
`2
`
`FIELD OF THE INVENTION
`
`This invention relates to the field of using an
`index to archive and retrieve information on a com-
`puter. The information includes multimedia objects, (cid:9)
`such as video clips and audio segments.
`
`BACKGROUND OF THE INVENTION
`
`There are many methods known in the com- (cid:9)
`puter art which can archive and retrieve textual
`expressions (words and phrases) in natural lan-
`guage. Primarily, these methods use key words as
`indexes to archive and retrieve these textual ex-
`pressions. However, many things, particularly
`things in the area of multimedia (images and
`sounds), are not easily described using key words
`indexes. Often multimedia information like the
`sound of a dog barking, images shown in certain
`pictures, or the steps performed in a dance require (cid:9)
`more descriptive indexes than the prior art key
`words can provide. Key word indexes have failed to
`be descriptive enough because they can not easily
`identify the difference between a thing and an
`action, describe what agent performs a given ac- (cid:9)
`tion, or describe what object is acted upon. These
`key word failures, and others, create ambiguities
`when key words are used to identify and catalog
`information.
`The key word indexes of the prior art lack the (cid:9)
`grammatical structure needed to make them more
`descriptive. Key word phrases have no structure
`because the words in the phrases lack two things:
`1. a function and 2. a relationship. In a natural
`language, (i.e., languages spoken by humans) func- (cid:9)
`tion and relationships of the words are provided by
`the language grammar (grammar rules). For exam-
`ple, in the English natural language phrase "a man
`will fall into the pool", each word has a function
`and a relationship to the other words in the phrase
`dictated by English grammar. Functionally, "man"
`and "pool" are nouns and "fall" is a verb. Relation-
`ships exist because, syntactically, "man" is the
`subject of the sentence, and, semantically, it is the
`themeof an action;
`"fall" is the predicate which describes the action;
`and "pool", according to the English syntax, the
`locational object of the sentence, describes the the
`location of the action. Often, the object of a sen-
`tence is the recipient of the action of an agent; and
`the subject of the sentence is the agent of an
`action; for instance, "the woman pushed the ball".
`The word "agent" is used to describe the typical
`subject; that is, by default subjects are assumed to
`be agents. The explicit distinction between agent-
`subject and theme-subject is not made, since it
`does not affect the logic of the proposal. Similarly,
`we will use the word "object" to cover several
`
`syntactic functions, such as direct object, object of
`a preposition, and indirect object. Notice that this
`slot can have multiple fillers when there is more
`than one object as in "The child dropped the ball
`into the pool", where "the ball" is the direct object
`and "into the pool" the locational object of the
`action. (In all our examples we will use only single
`fillers). Natural languages use different kinds of
`grammatical rules to affect the meaning of the
`words. These include: defining parts of speech,
`ordering words in the phrase, and using word pre-
`fixes or endings, etc. Since key words, even in
`phrases, lack these grammatical rules, they can be
`less descriptive and ambiguous. For example,
`when the phrase "man will fall into the pool" is
`parsed into words, the key word "fall" has no
`function (it could be a verb or a noun) and could be
`ambiguously interpreted as "drop" or a "season of
`the year". Furthermore, splitting the key word
`phrase "cat eats mouse" into "cat", "eats", and
`"mouse", yields a sequence of key words with no
`relationship. Because there is no way to tell which
`word is the subject and which is the object, the
`interpretation becomes ambiguous. The phrase
`could mean: "cat eats mouse", "mouse eats cat",
`or "cat and mouse eats".
`The problem is compounded when synonyms,
`hypernyms (words of a broader genus which in-
`clude the key word) or hyponyms (words within the
`key word genus) of key words are used to expand
`a key word search to retrieve data. This is fre-
`quently required in Information Retrieval systems
`because often users use slightly different words
`that are not found via a direct match. For example,
`a synonym (hypernym) of "fall" like autumn (sea-
`son) would give erroneous results when searching
`a database for a match to the key word "fall" which
`really meant "drop".
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`ao (cid:9)
`
`OBJECTS OF THE INVENTION
`
`45 (cid:9)
`
`An object of this invention is an improved
`method of archiving and retrieving data on a mul-
`tipurpose computer by using structured indexes.
`Another object of this invention is an improved
`method of archiving and retrieving multimedia in-
`formation on a multipurpose computer by using
`structured indexes.
`Also an object of this invention is an improved
`50 (cid:9) method of archiving and retrieving multimedia ob-
`jects on a multipurpose computer by using struc-
`tured indexes related to a lexical database.
`An additional object of this invention is an
`improved method of archiving and retrieving mul-
`timedia objects on a multipurpose computer by
`using structured indexes and natural language que-
`ries.
`
`55 (cid:9)
`
`3
`
`Page 3 of 16
`
`MINDGEEK EXHIBIT 1004
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`
`
`3
`
`EP 0 609 517 A2 (cid:9)
`
`4
`
`point to classes of words that are stored in a lexical
`database. These lexical database words are some-
`how related (synonym, etc.) to the word(s) in the
`key. Words can be chosen from the lexical
`database using criteria defined by the search al-
`gorithm. These words, chosen from the lexical
`database, are also used to search the matched pair
`database for a match. Any matched pair that
`matches one of the chosen lexical database words
`is returned on the matching list as well.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`20 (cid:9)
`
`Fig. 3 (cid:9)
`
`SUMMARY OF THE INVENTION
`
`This invention is an efficient method for assist-
`ing computer users in the creation and use of
`structured indexes for archiving and retrieving in-
`formation using a general purpose computer. The
`index structure is based on a grammar (grammati-
`cal rules) and is particularly descriptive for the
`archiving and retrieving of multimedia objects.
`In a preferred embodiment, a heuristic interface
`is presented to the user. The heuristic interface
`presents information, like a film clip, to the user
`and receives strings of input, like a word phrase,
`from the user. The heuristic interface helps the
`user organize the input string into components
`having a structure according to a set of grammati-
`cal rules. Alternatively, a parser can parse natural
`language descriptions to identify components and
`their structures based on rules.
`To archive information, a matched pair is cre-
`ated using a structured index. Using a mapping
`algorithm, the structured index is made of input
`string components (e.g. words) which now have a
`function and a relationship with one another. This
`structured index is then combined with a pointer to
`the information to be archived to create the
`matched pair. Therefore, the matched pair has two
`parts: 1. the pointer, called a segment number or
`segment, correlated to the storage location of the
`(multimedia) information to be archived and 2. the
`structured index describing the information. The
`matched paired is then archived or stored in the
`computer memory.
`To retrieve the archived information, the sys-
`tem is queried using an input string, such as natu-
`ral language string query. In a preferred embodi-
`ment, a heuristic interface assists the user in pro-
`viding an input string query that conforms to a
`grammar. Alternatively, a parser can parse the que-
`ry string into a structured query which has a struc-
`ture that is identical to or related to that of the
`structured index in the archived matched pairs. A
`search algorithm is selected and used to make a
`key. The key is compared to the index part (or a
`component(s) of the index part) of the matched
`pairs in the database. This comparison generates a
`list of the matching pairs that match the key.
`Therefore, this matching pair list contains the
`matched pairs corresponding to archived informa-
`tion that matches the query within the parameters
`defined by the search algorithm. Finally, the (mul-
`timedia) information segment number, part of each
`matched pair on the matching pair list, is used to
`retrieve the archived (multimedia) information asso-
`ciated with the segment number from the storage
`location pointed to by the segment number.
`The retrieval search can be expanded by
`changing the search algorithm. Parts of the key can
`
`5 (cid:9)
`
`/0 (cid:9)
`
`15 (cid:9)
`
`25 (cid:9)
`
`30 (cid:9)
`
`35 (cid:9)
`
`40 (cid:9)
`
`45 (cid:9)
`
`50 (cid:9)
`
`55 (cid:9)
`
`4
`
`Fig. 1 (cid:9)
`
`Fig. 2 (cid:9)
`
`Fig. 4 (cid:9)
`
`Fig. 5 (cid:9)
`
`shows preferred structured indexes, of
`the present invention, as part of a
`matched pair record.
`is a flow chart of the method of ar-
`chiving information, like multimedia in-
`formation, by using a structured index.
`shows a computer screen display
`which uses a template and a mul-
`timedia display as a heuristic interface
`with a user.
`is a flow chart of the method of re-
`trieving information, like multimedia in-
`formation, by using structured index-
`es.
`shows a computer system using
`structured indexes to archive and re-
`trieve information, particularly multi-
`media information.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`The present invention is capable of running on
`any general purpose computer which has the abil-
`ity to present multimedia information to a user. One
`preferred embodiment, shown in Fig. 5, uses an
`IBM Personal System/2 (PS/2) Model 8595 Micro-
`channel Floor Standing 486 System 500 (described
`in the Quick Reference supplied with the system
`unit). An IBM Personal System/2 (PS/2) Action-
`Media II Display Adapter 510 (described in the
`ActionMedia II Technical Reference) is used for
`audio/video capture 520A and playback 520B. This
`preferred embodiment also uses an IBM Operating
`System/2 ( OS/2) 2.0 (described in the OS/2 2.0
`Quick Reference), an IBM Multimedia Presentation
`Manager/2 (described in the IBM Multimedia Pre-
`sentation Manager/2 ActionMedia(R) II Media Con-
`trol Interface Programming Guide and Reference),
`and a SmalltalkNPM (described in the Small-
`talkNPM Tutorial and Programming Handbook).
`Other multimedia hardware 530 known in the art
`that can be connected to a general purpose com-
`puter can also be used. This hardware 530 may
`include video cassette recording devices, laser disc
`player adapter, audio capture playback adapter,
`
`Page 4 of 16
`
`MINDGEEK EXHIBIT 1004
`
`(cid:9)
`
`
`5 (cid:9)
`
`EP 0 609 517 A2
`
`6
`
`etc. The marks OS/2 and PS/2 are trademarks of
`the IBM Corporation, the mark ActionMedia II is a
`trademark of the Intel Corporation, and the mark
`SmalltalkNPM is a trademark of Digitalk Inc..
`The present invention uses structured indexes
`to archive and retrieve information in a computer
`database. Because structured indexes are much
`more descriptive than prior art key word indexes,
`structured indexes are particularly useful in ar-
`chiving and retrieving information about multimedia
`objects. Generally, multimedia includes information
`having a sensory quality that is presented as an
`input or output of a computer. Multimedia informa-
`tion (objects) 550 includes audio 532 and visual
`534 information like audio and video clips, musical
`recordings, speech, typed text, still pictures, draw-
`ings, animation, choreographed dance steps, etc.
`One reason that a structured index is useful in
`describing multimedia objects is that actions,
`agents performing actions, and recipients of actions
`can be included in the index.
`The structured index has a structure because it
`carries information about 1. the function of compo-
`nents of the index and 2. the relationship among
`the index components. The function and relation-
`ship are defined by rules of a grammar. In the
`preferred embodiment, the components of the in-
`dex are words which describe a multimedia object.
`The rules of grammar used to give function and
`relationship to the words in the index are given in a
`natural language grammar that uses the words.
`However, the invention is not limited to words as
`index components nor to a natural language gram-
`mar. The index can be made of any type of com-
`ponent which might be descriptive of the informa-
`tion to be archived or retrieved and any rules that
`define component functions and relationships can
`be a grammar. For instance, an index could be
`created for a musical clip using a series of tones
`given structure by rules concerning rhythm and
`frequency. An index into textual information like a
`telephone directory could be made from a series of
`tones, representing a phone number, which are
`given structure by rules concerning the frequency
`of the tones (the numeric value of the digits),
`number of tones (digits in the phone number), and
`the order of a tone sequence.
`A structured index of one preferred embodi-
`ment takes the form:
`[relation : component (function or attributes)]
`As an example, this form as applied to a word
`index, for a single word component, becomes:
`[action: word (verb, third person, future tense)]
`The relation (action) and function (verb) of this
`index are defined by the rules of the applicable
`grammar, i.e. English grammar. Attributes of the
`word (component) are represented as the informa-
`tion within the parenthesis of the index. These
`
`5 (cid:9)
`
`io (cid:9)
`
`15 (cid:9)
`
`20 (cid:9)
`
`25 (cid:9)
`
`attributes include the function of the word but may
`include additional information. In this example, the
`attributes include the word function (verb) and addi-
`tional information about the verb, person and tense.
`Attribute information can include grammatical de-
`scriptions about a word (like person, number,
`tense, gender) or other descriptive information (like
`color, size, weight). An index like this, that is de-
`scriptive of just one word (component), is called a
`simple index.
`To create an index that is more descriptive of a
`word (component) phrase than a one word simple
`index, a compound index is used. A compound
`index contains simple indexes for more than one
`word (component) in the phase. For example, in
`the English language phrase "Dad will fall into a
`pool", a compound structured index could take the
`form:
`[[agent: Dad (noun, human)], [action: fall (verb, third
`person, future tense, drop)], [object: into the pool
`(prepositional phrase, object, swimming pool)]].
`In this example, the compound structured in-
`dex generated from the natural language word
`phrase, based on English grammar, defines the
`relationship (agent, action, and object or location)
`of the structured index word components "Dad",
`"fall", and "into the pool" respectively. The func-
`tion of each component is given by the grammar
`(noun, verb, prepositional phrase). In addition,
`along with the function, other attribute information
`is included. Here the attributes give information
`about the component/word useful in associating it
`with other components/words. Attributes include
`synonyms ("drop"), and hyponyms ("swimming
`pool").
`Grammar is the set of rules which gives com-
`ponents in a sequence a function and relationship,
`i.e. a structure. The rules of grammar organize
`and/or identify the components in a sequence in
`such a way to give them specific functions. For
`example, the grammar used in the preferred em-
`bodiment is a natural language grammar of Eng-
`lish, which has subjects (nouns and noun phrases),
`predicates (verbs), and objects (nouns, noun
`phrases, prepositional phrases, etc.) arranged in a
`sequence determined by grammatical rules to cre-
`ate a phrase or sentence. Altering the function and
`relationship of the words according to the gram-
`matical rules can change the meaning of the word
`phrase or sentence. Although a natural language
`grammar and a word sequence (phrase or sen-
`tence) are used in the preferred embodiment, prac-
`tice of the invention is not limited to natural lan-
`guage grammar. The invention can use as a gram-
`55 (cid:9) mar any set of rules used to give structure to a
`sequence of components in order to create a sen-
`sory meaning (auditory or visual). This might in-
`clude the rules of music applied to a sequence of
`
`30 (cid:9)
`
`35 (cid:9)
`
`40 (cid:9)
`
`45 (cid:9)
`
`50 (cid:9)
`
`5
`
`Page 5 of 16
`
`MINDGEEK EXHIBIT 1004
`
`(cid:9)
`
`
`7 (cid:9)
`
`EP 0 609 517 A2
`
`8
`
`frequency tones to create a melody, rules of geom-
`etry applied to a sequence of patterns to create a
`shape, or the rules of speech applied to a se-
`quence of phonemes to create a recognizable
`word. The applied rules of grammar are used to
`create the structured index. The rules can also be
`used in designing a heuristic interface for archiving
`and retrieving information.
`Refer to Fig. 1. The present invention archives
`and retrieves information by using a structured
`index database 125 that stores matched pairs 105.
`A matched pair 105 includes two parts: 1) a seg-
`ment 110 that identifies the location of the informa-
`tion to be archived or retrieved and 2) an asso-
`ciated structured index 100. The segment 110 can
`be the starting location in computer memory (540
`in Fig. 5) which contains the information, a pointer
`to some storage media location which contains the
`information, or other data commonly used to ac-
`cess information. Three preferred matched pair
`memory structures are now described.
`One matched pair embodiment stores matched
`pairs 105 as a "flat" data file 140 where the seg-
`ment number 110 and associated index 100 are
`stored as sequential records 120 in a structured
`index database 125. For example:
`(segment(771), "Dad will fall into the pool")
`(segment(772),"a cat and three mice eat an ear of
`corn") are two consecutive records 120 of matched
`pairs 105. The multimedia information associated
`with "Dad will fall into the pool" is located at the
`multimedia storage location 771 just as the in-
`formation associated with "a cat and three mice eat
`an ear of corn" is located at multimedia storage
`location 772. For example, the multimedia informa-
`tion in these cases could be a digitized photograph
`stored in the memory location. The "index" stored
`(here a word phrase) is not "structured" per se
`because the function and relationships of the words
`are not identified. In this embodiment, the word
`phrase "index" will be structured during the re-
`trieval process. See below.
`A more preferred embodiment 150 also stores
`the segment 110 and structured index 100 match
`pairs 105 as records 120 in the structured index
`database 125. Here the records each have fields
`and the records are delineated from one another
`by delimiters like periods 122. Fields within each
`record can be identified by their position in the
`record, delimiters like parenthesis 126, or by field
`identifiers like names 128 (e.g. action:). Storing
`records in this manner is well known.
`A most preferred embodiment stores the seg-
`ment 110 and structured index 100 match pairs
`105 as sequential records 120 in the structured
`index database 125 where each record has a num-
`ber of predefined fields 130. For example,
`{(segment(770), [[action: drop (pos =verb, per-
`
`5 (cid:9)
`
`io (cid:9)
`
`15 (cid:9)
`
`20 (cid:9)
`
`25 (cid:9)
`
`30
`
`35 (cid:9)
`
`40 (cid:9)
`
`45 (cid:9)
`
`50 (cid:9)
`
`55 (cid:9)
`
`6
`
`boy
`[agent: (cid:9)
`tense = present)], (cid:9)
`son = 3rd, (cid:9)
`(pos =noun, number = sing, human = yes)], [object:
`pond (pos = noun, number = sing, prep = into)]]}
`{segment(771), [[action: fall (pos =verb, per-
`son =3rd, tense =future)], [agent: dad (pos =noun,
`number = sing, (cid:9)
`human = yes)], (cid:9)
`[object: (cid:9)
`pool
`(pos = noun, number =sing)]] },
`shows two stored matched pairs 105 using com-
`pound structured indexes 100 as records 120 in
`the structured index database 125. (Note also, that
`here the attributes have the form "attribute =value",
`e.g., "tense =future"). The records are stored in a
`table like structure 160. One preferred embodiment
`is a relational database. Each record 120 in the
`table 160 has a field for the: segment 110 number
`(770,771); the action 114 (drop, fall), three at-
`tributes of the action (part of speech (pos) 116,
`person 118, and tense 119); the agent 122 (boy,
`dad); three attributes of the agent (part of speech
`124, number 126, and whether or not the agent is
`human 128); the object 132 (pond, pool); and two
`attributes of the object (part of speech 134 and
`number 136). One or more of these record fields
`can be searched during the retrieval process to
`find a matched pair 105 record 120 which matches
`a retrieval query. Note that for technical purposes,
`the function of a word could be identified with its
`part of speech (pos) as specified by the grammar.
`Some of the data might be ignored. For instance,
`the fact that the preposition value is "into"
`(prep = into) might be irrelevant.
`The preferred embodiment allows a search of
`the structured index database 125 to be broadened
`by adding another database of components (in the
`preferred embodiment these are words) arranged
`in a lexical hierarchy. This second database, called
`the lexical database, is constructed in any of the
`ways well known in the art.
`The lexical database arranges words hierarchi-
`cally (or other components) with a relatively narrow
`meaning in classes (hyponyms) under a words with
`a broader meaning (hypernym), for example, "bea-
`ver" and "cat" are hyponyms of "mammal", which
`is a hyponym of "animal." These words in turn are
`included in a class of words under a word with a
`still broader (hypernym) meaning. In this manner,
`the database words are related to one another in a
`hierarchical way.
`Any lexical database known in the art can be
`used as the lexical database in the present inven-
`tion. Lexical databases exist that include words and
`their synonyms, hypernyms and hyponyms. Infor-
`mation in the databases of dictionary entries has
`been parsed to determine the structure of the en-
`tries, and the processed entries have been loaded
`into still other prior art lexical data bases. For
`example, in some lexical databases, pronunciation
`information, parts of speech, and definitions are
`
`Page 6 of 16
`
`MINDGEEK EXHIBIT 1004
`
`(cid:9)
`
`
`9 (cid:9)
`
`EP 0 609 517 A2
`
`10
`
`stored as individual fields accessible by a word.
`Definition texts are used to extract implicit informa-
`tion about words. Synonyms are available explicitly
`in the entries of thesauri. Hyponyms can be in-
`ferred from the definition text (e.g. a car is defined
`as a "vehicle" moving on wheels in Webster's
`7th--Merriam 1963). Once extracted from a variety
`of sources, this information can be loaded into a
`lexical data based for subsequent processing. For
`example, in a lexical database, an entry for the
`word "car" may look like this:
`
`car -
`
`synonyms
`
`auto, automobile, jalopy, machine, motor, mo-
`torcar, vehicle, buffet car, cable car, coach, dining
`car, (railway), sleeping car, van
`
`hypernyms
`
`vehicle, chariot, cage, portion
`
`hyponyms
`
`boxcar, cable car, caboose, chair car, chariot,
`coach, dining car, flatcar, go-devil, gondola, gon-
`dola, hand car, lounge car, mini cab, motorcar,
`parlor car, rattletrap, reefer, stock car, sidecar,
`sleeping car, smoker, telpher, trolley, truck, wagon,
`way car
`where the synonym, hypernym and hyponyms are
`fields in a record of the lexical database that con-
`tain lists of words extracted from previous process-
`ing.
`Refer to Fig. 2 which shows the process of
`archiving information 250 using the preferred em-
`bodiment. A user 255 interacts with a heuristic
`interface 260 that presents the user with multi-
`media information 270 and prompts the user to
`enter a string of components (words) according to
`a given grammar 275. Typically, a parser 280 may
`operate on the entered string to parse it into com-
`ponents. Alternatively, the parser 280 may be omit-
`ted 284.
`A mapping algorithm uses these components
`to produce a structured index 285 of a form similar
`to that described above. The structured index is
`combined 290 with the segment number of the
`information to be cataloged 270 to produce a
`matched pair 295 which is stored in the structured
`index database 125 as shown in box 298.
`Fig. 3 shows a preferred embodiment of a
`video heuristic interface 300. The heuristic interface
`in the preferred embodiment is a video display 300
`that can present multimedia information. The mul-
`timedia information is stored in a multimedia stor-
`
`5 (cid:9)
`
`10 (cid:9)
`
`15 (cid:9)
`
`20 (cid:9)
`
`25 (cid:9)
`
`30 (cid:9)
`
`35 (cid:9)
`
`40 (cid:9)
`
`45 (cid:9)
`
`50 (cid:9)
`
`55 (cid:9)
`
`7
`
`age device or is digitized and stored in computer
`memory. The display includes a template 325
`which prompts the user to enter an English natural
`language description of the multimedia information
`330, an animated picture 330 of a dog running
`slowly to a door. The template 325 is formatted to
`encourage the user to describe the picture with a
`phrase or sentence structured using standard Eng-
`lish grammar. The input sections of the template,
`301 through 305 are designed so that the user
`enters textual information that describes the mul-
`timedia information 330 in terms of English gram-
`mar parts of speech (functions and/or relationships,
`306 through 310). In this example, the user fills the
`input section 301 with an adjective 306 (animated)
`describing the clip or the subject 307 (dog) in input
`section 302. The action relationship is describe by
`the verb 309 (runs) which the user puts in input
`section 304. An adverb 308 relationship (slowly),
`describing the verb 309, is placed in the input
`section 303. An object of the action relationship is
`described by the prepositional phrase 310 placed
`in input section 305. Therefore, by using a heuristic
`interface 300, a user parses a natural language
`description of the multimedia information 330 into
`components which have a function and a relation-
`ship among one another according to a natural
`language grammar. In this preferred embodiment,
`box 280 of Fig. 2 can be by-passed 284 because
`the data (301 through 305) placed in the template
`(box 275 of Fig. 2) can be directly used to create a
`structured index (box 285). Any software environ-
`ment, well known in the art, that is capable of
`creating an input template can be used as this
`heuristic interface 300.
`In an alternative preferred embodiment, the
`heuristic interface can be any natural language
`interface known in the art. For example, the mul-
`timedia information 330 to be archived is presented
`on the screen 300 along with a natural language
`query or a prompt. Then the user responds by
`inputting descriptive information, typically natural
`language text, about the multimedia clip. Inputting
`the text is shown in box 275 of Fig. 2.
`The parser analyzes the natural language de-
`scription 275 according to the rules of some gram-
`mar, typically a natural language grammar like
`English, and returns the sentence or phrase parsed
`into words identified as parts of speech, constitu-
`ents and functions. The parser 280 can be any one
`of a number of embodiments known in the art.
`Parsers are also available to provide additional
`information about the words like tense, number,
`and other attributes. If the parser is unable to parse
`the natural language description 275 because the
`description does not conform to the rules of Eng-
`lish grammar or for any other reason, the natural
`language description is discarded 282. An indica-
`
`Page 7 of 16
`
`MINDGEEK EXHIBIT 1004
`
`(cid:9)
`
`
`11 (cid:9)
`
`EP 0 609 517 A2
`
`12
`
`5 (cid:9)
`
`memory record 120 along with the structured index
`information 100 stored by the mapping algorithm
`285. Therefore, the index 100 and segment 110
`combine 290 in one record 120 to form a matched
`pair 105 (box 295) associated with the information
`to be archived. Preferred embodiments of the
`matched pair 105 in the structured index database
`125 are described above. The structured index
`database 125 comprises a plurality of these
`io (cid:9) matched pair 105 records 120 (box 298) archived
`by this method.
`Fig. 4 is a flow chart of the present process
`that is used in retrieving information. A string of
`components, typically words 410, are entered into
`the computer by a user through a heuristic inter-
`face 415. The heuristic interface 415 prompts the
`user to pose the query with a structure as deter-
`mined by the grammar similar to that used in
`archiving the information. This embodiment can
`use an input template 325 as shown in Figure 3.
`Alternatively, a known natural language interface
`could be used as the heuristic interface 415 prom-
`pting the user to enter a natural language query. In
`another alternative, the user could be another corn-
`puter or input device which is able to structure a
`plurality of queries according to the rules of the
`grammar used.
`If the heuristic interface 415 is designed to
`receive a natural language query, a parser 420 is
`used. However, if the heuristic interface 415 gram-
`matically organizes the query, e.g., by using a
`template 325 like that shown in Fig. 3, the parser
`420 is bypassed 418. A parser parses the query
`and returns the query parsed into a structured
`query. If the parser can not parse the query be-