Apparatus and method for information retrieval

• US 20020111941A1
• Filed: 12/19/2000
• Published: 08/15/2002
• Est. Priority Date: 12/19/2000
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Roux, Claude, Proux, Denys, Gaussier, Eric
• Granted Patent: US 6,678,677 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An information retrieval apparatus retrieves information from databases comprising internal representations of documents. Syntactic relations between terms of the query are extracted and an internal representation of the query is created based on the terms of the query and the extracted syntactic relations. New terms are appended to a semantic lattice if the query includes terms not included in the semantic lattice. The query is projected onto the documents in the database by comparing the internal representation and terms of the query to the internal representations and terms of the documents using the semantic lattice for comparing the terms and a similarity is computed between the query and each document. The documents are ranked according to their computed similarities and are output as retrieved documents according to the established rank order.

Claims

1. A document retrieval method that retrieves documents from a database, the database comprising internal representations of documents wherein the internal representations include syntactic relations between terms of sentences of the documents and a semantic lattice for the terms of the documents in the database, the semantic lattice specifying the semantic relations between the terms, the method comprising the steps of:

a) receiving a database query,

b) extracting syntactic relations between terms of the query,

c) creating an internal representation of the query based on the terms of the query and the extracted syntactic relations between the terms of the query,

d) appending new terms to the semantic lattice if the query includes terms not included in the semantic lattice in the database,

e) projecting the query onto each of the documents in the database by comparing the internal representation and terms of the query to the internal representation and terms of the documents using the semantic lattice for comparing the terms and computing a similarity between the query and the documents in the database,

f) ranking the documents in the database according to the computed similarities, and

g) outputting documents as retrieved documents according to the rank order.

2. The method of claim 1, wherein the extracting step employs a shallow parser for extracting syntactic relations between terms of a sentence.

3. The method of claim 1, wherein the appending step for appending new terms to the semantic lattice receives a semantic relation for a current term from a thesaurus memory.

4. The method of claim 1, wherein the projecting step takes a semantic distance between a term of a query and a term of a document into account when computing similarity between the query and a document.

5. The method of claim 4, wherein the semantic distance between terms depends on the semantic similarity between both terms and being provided by the thesaurus memory.

6. The method of claim 4, wherein the semantic distance is zero if both terms are identical, the semantic distance takes a large value if both terms are semantically not related to each other, and the semantic distance takes an intermediate value if both terms are not identical but are semantically related to each other.

7. The method of claim 1, wherein the projecting step uses an additional weighting factor for computing the similarity between the query and a document, the weighting factor is large when the current term of the query and a term of the document are semantically and syntactically identical, the weighting factor is zero when both terms are neither semantically related to each other nor syntactically identical, the weighting factor takes an intermediate value when both terms are syntactically identical and are semantically related to each other and the weighting factor takes a smaller intermediate value when both terms are syntactically not identical but semantically related to each other.

8. The method of claim 1, wherein the step of creating an internal representation of the query generates a conceptual graph wherein each node of the graph either represents a term or a syntactic relation.

9. A document retrieval apparatus for retrieving documents from a database, the database comprising internal representations of documents wherein the internal representations include syntactic relations between terms of sentences of the documents and a semantic lattice for the terms of the documents in the database, the semantic lattice specifying semantic relations between the terms, the apparatus comprises:

a) a query input unit for receiving a query,

b) a query processing unit for creating an internal representation of the query based on the terms of the query and syntactic relations between the terms of the query,

c) a semantic lattice management unit for appending new terms to the semantic lattice if the query includes terms not included in the semantic lattice in the database,

d) a matching unit that projects the query onto each of the documents in the database by comparing the internal representation of the query to the internal representation of a document using the semantic lattice for comparing the terms and computing a similarity between the query and the document, and

e) a presentation unit for ranking the documents in the database according to the computed similarities and for outputting documents as retrieved documents according to the rank order.

10. The apparatus of claim 9, wherein said query processing unit comprises a parsing unit for extracting syntactic relations between terms of a sentence.

11. The apparatus of claim 9, wherein said query processing unit comprises a thesaurus memory including semantic relations for a plurality of terms.

12. The apparatus of claim 9, further comprising a document preprocessing unit for creating the internal representation of documents in the database, the document preprocessing unit using the syntactic relations extracted by a parsing unit and creating the semantic lattice for the database using semantic relations between terms of the documents provided by a thesaurus memory.

13. The apparatus of claim 9, further comprising a matching unit for computing a similarity between the query and a document wherein the matching unit takes a semantic distance between a term of the query and a term of a document into account when computing similarity.

14. The apparatus of claim 11, wherein the thesaurus memory further comprises a semantic distance for each stored semantic relation wherein the semantic distance depends on the semantic similarity between two terms.

15. The apparatus of claim 14, wherein the semantic distance is zero if both terms are identical, the semantic distance is large if both terms are semantically not related to each other, and the semantic distance takes an intermediate value if both terms are not identical but semantically related to each other.

16. The apparatus of claim 13, further using a weighting factor for computing the similarity between the query and a document, wherein the weighting factor takes a value of one if both terms are semantically and syntactically identical, wherein the weighting factor takes a value of zero if both terms are neither syntactically identical nor semantically related to each other, wherein the weighting factor takes an intermediate value if both terms are semantically related to each other and are syntactically identical, and wherein the weighting factor takes a smaller intermediate value if both terms are semantically related to each other but are syntactically not identical.

17. The apparatus of claim 9, wherein the internal representations of the documents in the database are in the form of a conceptual graph wherein each node of the graph either represents a term or a syntactic relation between terms.

18. A computer program product for use in a computer system that retrieves documents from a database, the database comprising internal representations of documents wherein the internal representations include syntactic relations between terms of sentences of the documents and a semantic lattice for the terms of the documents in the database, the semantic lattice specifying the semantic relations between the terms, the method comprising the steps of:

a) receiving a database query,

b) extracting syntactic relations between terms of the query,

c) creating an internal representation of the query based on the terms of the query and the extracted syntactic relations between the terms of the query,

d) appending new terms to the semantic lattice if the query includes terms not included in the semantic lattice in the database,

e) projecting the query onto the documents in the database by comparing the internal representation and terms of the query to the internal representation and terms of the documents using the semantic lattice for comparing the terms and computing a similarity between the query and the documents,

f) ranking the documents in the database according to the computed similarities, and

g) outputting documents as retrieved documents according to the rank order.