Applying formal concept analysis to validate expanded concept types

According to one embodiment, attributes associated with a concept type of a query conceptual graph are received. A potentially conceptually similar term is received from an onomasticon. The potentially conceptually similar term is validated according to the attributes. According to another embodiment, attributes associated with a concept type of a document conceptual graph are received. A potentially conceptually similar term is received from an onomasticon. The potentially conceptually similar term is validated according to the attributes.

TECHNICAL FIELD

This invention relates generally to the field of information management and more specifically to applying formal concept analysis to validate expanded concept types.

BACKGROUND

A corpus of data may hold a large amount of information, yet finding relevant information may be difficult. Key word searching is the primary technique for finding information. In certain situations, however, known techniques for keyword searching are not effective in locating relevant information.

SUMMARY OF THE DISCLOSURE

In accordance with the present invention, disadvantages and problems associated with previous techniques for conceptual graph searching documents may be reduced or eliminated.

According to one embodiment, attributes associated with a concept type of a query conceptual graph are received. A potentially conceptually similar term is received from an onomasticon. The potentially conceptually similar term is validated according to the attributes. According to another embodiment, attributes associated with a concept type of a document conceptual graph are received. A potentially conceptually similar term is received from an onomasticon. The potentially conceptually similar term is validated according to the attributes.

Certain embodiments of the invention may provide one or more technical advantages. A technical advantage of one embodiment may be that a query conceptual graph generated for a search query may include terms that represent concept types in the graph. A set of terms conceptually similar to the graph terms may be identified and used to perform the search. The conceptually similar terms may be validated before use.

Another technical advantage of one embodiment may be that a document conceptual graph may be generated for a document. The document conceptual graph may include terms that represent concept types in the graph. A set of terms conceptually similar to the graph terms may be identified and used to represent the document. The conceptually similar terms may be validated before use.

Another technical advantage of one embodiment may be that valid conceptually similar terms of a document conceptual graph may be compared with valid conceptually similar terms of a search conceptual graph. The document may be selected as a result of the search if the valid conceptually similar terms of the query conceptual graph match the valid conceptually similar terms of the document conceptual graph.

DETAILED DESCRIPTION OF THE DRAWINGS

Embodiments of the present invention and its advantages are best understood by referring toFIGS. 1 through 5of the drawings, like numerals being used for like and corresponding parts of the various drawings.

FIG. 1illustrates one embodiment of a system10configured to validate potential conceptually similar terms representing concept types in conceptual graphs. In certain embodiments, system10validates potential conceptually similar terms representing concept types in an existing query conceptual graph that may represent a search query. The existing query conceptual graph may include previously generated conceptual graph terms stored in onomasticon52that potentially represent a concept type. A set of validated terms conceptually similar to concept types in query conceptual graphs may be identified and used to perform a search.

In certain embodiments, system10validates potential conceptually similar terms representing concept types contained in an existing document conceptual graph that may represent a document. The existing document conceptual graph may include previously generated conceptual graph terms stored in onomasticon52that potentially represent a concept type. A set of validated terms conceptually similar to concept types in document conceptual graphs may be identified and used to represent the document.

In certain embodiments, the validated conceptually similar terms representing concept types found in document conceptual graphs may be compared with validated conceptually similar terms representing concept types found in query conceptual graphs of a search. The document may be selected as a result of the search if the validated terms found in concept types in document conceptual graphs match validated terms found in query concept graphs.

In the illustrated embodiment, system10includes a client20, a server24, and a memory50, one or more of which may be embodied as one or more apparatuses. Server24includes an attribute logic engine30, an onomasticon manager45, and a graph matcher46. Memory50includes an onomasticon52, documents53, and an attribute knowledge base54.

In particular embodiments, client20may send input to system10and/or receive output from system10. In particular examples, a system may use client20to send input to system10and/or receive output from system10. In particular examples, a user may use client20to send input to system10and/or receive output from system10. In particular embodiments, client20may provide output, for example, display, print, or vocalize output, reported by server24, such as by graph matcher46.

In particular embodiments, client20may send an input message to server24to initiate validation of potential conceptually similar terms representing concept types contained in either an existing query conceptual graph or an existing document conceptual graph. A term may comprise any suitable sequence of characters, for example, one or more letters, one or more numbers, and/or one or more other characters. An example of a term is a word.

Server24stores system logic (for example, software and/or hardware) that may be used to perform the operations of system10. In the illustrated example, server24includes attribute logic engine30, onomasticon manager45, and graph matcher46.

In particular embodiments, attribute logic engine30determines if existing potential conceptually similar terms stored in onomasticon52representing concept types mapped to existing concept types in an existing query conceptual graph or an existing document conceptual graph are valid for use by the system. In particular embodiments, attribute knowledge base54includes attributes that describe the term that represents a concept type in an existing conceptual graph. An existing conceptual graph may be a graph that includes concept types expressed as terms (for example, specific term representations of concept types) and the relationships among the concept types. Examples of existing conceptual graphs are described with reference toFIGS. 2A and 3A.

A component of system10may include an interface, logic, memory, and/or other suitable element. An interface receives input, sends output, processes the input and/or output, and/or performs other suitable operation. An interface may comprise hardware and/or software.

Logic performs the operations of the component, for example, executes instructions to generate output from input. Logic may include hardware, software, and/or other logic. Logic may be encoded in one or more tangible media and may perform operations when executed by a computer. Certain logic, such as a processor, may manage the operation of a component. Examples of a processor include one or more computers, one or more microprocessors, one or more applications, and/or other logic.

A memory stores information. A memory may comprise one or more tangible, computer-readable, and/or computer-executable storage media. Examples of memory include computer memory (for example, Random Access Memory (RAM) or Read Only Memory (ROM)), mass storage media (for example, a hard disk), removable storage media (for example, a Compact Disk (CD) or a Digital Video Disk (DVD)), database and/or network storage (for example, a server), and/or other computer-readable medium.

Modifications, additions, or omissions may be made to system10without departing from the scope of the invention. The components of system10may be integrated or separated. Moreover, the operations of system10may be performed by more, fewer, or other components. For example, the operations of attribute logic engine30and onomasticon manager45may be performed by one component, or the operations of onomasticon manager45may be performed by more than one component. Additionally, operations of system10may be performed using any suitable logic comprising software, hardware, and/or other logic. As used in this document, “each” refers to each member of a set or each member of a subset of a set.

FIGS. 2A and 2Billustrate examples of a query conceptual graph200, an onomasticon220, an attribute knowledge base230, an onomasticon manager240, and an attribute logic engine250. Conceptual graph200includes concept types, such as concept type [Person]210represented by the term “Person”. Concept types may be expressed as subjects, direct objects, verbs, or any suitable part of language. In particular embodiments, the concepts and the relationships among the concepts of a conceptual graph may be expressed in text. In certain embodiments, square brackets may be used to indicate concept nodes that include concept types.

Onomasticon220may be used to store previously generated terms that potentially represent a concept type in graph200. In particular embodiments, onomasticon220stores conceptually similar English and foreign language terms, such as Arabic terms for the existing concept type [Person]210. In the illustrated example, these terms may include Individual, Human, Anomaly, People, Face, Religious Person, Engineer, Male Person,(Individual)(Religious Person), and(Engineer).

Attribute knowledge base230includes existing attributes for an existing term representing existing concept type210in an existing query conceptual graph200. Attributes may be expressed as subjects, direct objects, verbs, or any suitable part of language. In the illustrated example, attribute knowledge base230includes the attributes conceptualization, causal agent, live, soul, and martyr.

The existing attributes may be mapped to an existing term representing an existing concept type described by the attributes. For example, existing concept type [Person]210is described by attributes conceptualization, causal agent, live, soul, and martyr, so these attributes are mapped to the existing term representing existing concept type [Person]210.

Onomasticon manager240, onomasticon220, and attribute logic engine250may validate a term in onomasticon220by determining whether the term is conceptually similar to an existing term of an existing concept type of an existing conceptual graph. For example, a potentially conceptually similar term may be regarded as conceptually similar to the existing term if the attributes of the existing term describe the potentially conceptually similar term. For example, a potentially conceptually similar term may be regarded as a conceptually similar term if a certain percentage of the existing attributes adequately define and/or can be mapped to the potentially conceptually similar term. Any suitable percentage may be used, for example, 50% to 75%, 75% to 80%, 80% to 90%, or 90% to 100% (all).

In particular embodiments, attribute logic engine250retrieves the existing attributes in attribute knowledge base230for the existing concept type. Onomasticon manager240retrieves from onomasticon220a potentially conceptually similar term for a term in the existing concept type and provides the potentially conceptually similar term to attribute logic engine250. Attribute logic manager250determines if the attributes adequately define and can be mapped to the potentially conceptually similar term. Attribute logic manager250notifies onomasticon manager240if the attributes cannot define or map to the potentially conceptually similar term. In response, onomasticon manager240may delete the potentially conceptually similar term from onomasticon220.

In the illustrated example, a term in onomasticon220may be validated by determining whether the term is conceptually similar to “Person” of [Person]. Attribute logic engine250retrieves existing attributes mapped to [Person]: conceptualization, causal agent, live, soul, and martyr. Onomasticon manager240retrieves “Anomaly” from onomasticon220as a potentially conceptually similar term for “Person” and provides “Anomaly” to attribute logic engine250.

Attribute logic engine250determines the attributes live, soul, and martyr do not adequately define and/or cannot be mapped to “Anomaly,” and notifies onomasticon manager240that the attributes do not define or map to “Anomaly.” Onomasticon manager240removes “Anomaly” from onomasticon220as a conceptually similar term for “Person.”

In the illustrated example, attribute logic engine250retrieves the existing attributes mapped to [Person]. Onomasticon manager240retrieves from onomasticon220“Human” as a possible conceptually similar term for “Person” and provides “Human” to attribute logic engine250. Attribute logic engine250determines that the attributes, conceptualization, causal agent, live, soul, and martyr adequately define and can be mapped to “Human”. “Human” contained in onomasticon220remains as a conceptually similar term for “Person.”

FIGS. 3A and 3Billustrate examples of a document conceptual graph400, an onomasticon420, an attribute knowledge base430, an onomasticon manager440, and an attribute logic engine450. Conceptual graph400includes concept types, such as concept type [Person]410represented by the term “Person”. Onomasticon420may be used to store previously generated terms that represent a concept type in graph400and may be substantially similar to onomasticon220. Attribute knowledge base430includes existing attributes for an existing term representing existing concept type410in an existing document conceptual graph400and may be substantially similar to attribute knowledge base230. Onomasticon manager440and an attribute logic engine450may be substantially similar to onomasticon manager240and an attribute logic engine250, respectively.

FIG. 4illustrates an example of a method for validating existing expanded terms in an existing onomasticon. In the example, the method is performed for query conceptual graph200, using onomasticon220, attribute knowledge base230, onomasticon manager240, and attribute logic engine250ofFIGS. 2A and 2Bas onomasticon52, attribute knowledge base54, onomasticon manager45, and attribute logic engine30described with reference toFIG. 4.

In the example, attribute logic engine30requests retrieval of the existing attributes for “Person” from attribute knowledge base54at step80. As described with reference toFIGS. 2A and 2B, the existing attributes include conceptualization, causal agent, live, soul, and martyr. Attribute knowledge base54reports the attributes at step90.

Onomasticon manager45retrieves a potentially conceptually similar term for “Person” from onomasticon52at step100. Onomasticon manager45reports the potentially conceptually similar term to attribute logic engine30at step110.

At step120, attribute logic engine30performs a logic function to determine if a certain percentage of the existing attributes adequately define and/or can be mapped to the potentially conceptually similar term. If the certain percentage of existing attributes adequately define and/or can be mapped to the potentially conceptually similar term, the term is considered to be a conceptually similar term for an existing term for “Person,” and the method then proceeds to step125.

If the certain percentage of existing attributes do not adequately define and/or cannot be mapped to the potentially conceptually similar, the term is not considered to be a conceptually similar term for an existing term for “Person,” and the method proceeds to step130. Attribute logic engine30reports that there is no adequate definition or mapping to onomasticon manager45to initiate removal of the term from onomasticon52. Onomasticon manager45removes the term at step135. The method then proceeds to step125.

Another term may be validated at step125. If another term is to be validated, attribute logic engine30requests onomasticon manager45to provide a term contained in onomasticon52that has not been validated, and the method returns to step100. If there is no other term to be validated, the method proceeds to step140.

Onomasticon manager45reports the validated conceptually similar terms to graph matcher46at step140. The validated conceptually similar terms may be used to determine matches between existing query conceptual graphs and existing document conceptual graphs. The method then ends.

FIG. 5illustrates another example of a method for validating existing expanded terms in an existing onomasticon. In the example, the method is performed for document conceptual graph400, using onomasticon420, attribute knowledge base430, onomasticon manager440, and attribute logic engine450ofFIGS. 3A and 3Bas onomasticon52, attribute knowledge base54, onomasticon manager45, and attribute logic engine30. The steps may be substantially similar to those described with reference toFIG. 4.

Modifications, additions, or omissions may be made to the methods described herein without departing from the scope of the invention. The methods may include more, fewer, or other steps. Additionally, steps may be performed in any suitable order.