Method and system of ranking and clustering for document indexing and retrieval

• US 7,496,561 B2
• Filed: 12/01/2003
• Issued: 02/24/2009
• Est. Priority Date: 01/18/2001
• Status: Expired due to Fees

• Current Assignee: Leidos, Inc. (Leidos Holdings, Inc.)
• Original Assignee: Science Applications International Corporation
• Inventors: Wang, Lei, Tseng, Jason Chun-Ming, Caudill, Maureen
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): MYINT, DENNIS Y
• Application Number:
  US10/724,170
• Publication Number:
  US 20040111408A1
• Time in Patent Office: 1,912 Days
• Field of Search: 707/3, 707/100, 704/1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A relevancy ranking and clustering method and system that determines the relevance of a document relative to a user'"'"'s query using a similarity comparison process. Input queries are parsed into one or more query predicate structures using an ontological parser. The ontological parser parses a set of known documents to generate one or more document predicate structures. A comparison of each query predicate structure with each document predicate structure is performed to determine a matching degree, represented by a real number. A multilevel modifier strategy is implemented to assign different relevance values to the different parts of each predicate structure match to calculate the predicate structure'"'"'s matching degree. The relevance of a document to a user'"'"'s query is determined by calculating a similarity coefficient, based on the structures of each pair of query predicates and document predicates. Documents are autonomously clustered using a self-organizing neural network that provides a coordinate system that makes judgments in a non-subjective fashion.

Claims

1. One or more computer readable media storing computer executable instructions to perform a method for vectorizing a set of document predicate structures, the method comprising:

identifying at least one predicate and argument in said set of document predicate structures by a predicate key that is an integer representation;

estimating conceptual nearness of two of said document predicate structures in said set of document predicate structures by subtracting corresponding ones of said predicate keys; and

outputting at least one document based upon the estimated conceptual nearness.

2. The computer readable media of claim 1, the method further comprising constructing multi-dimensional vectors using said integer representation.

3. The computer readable media of claim 2, the method further comprising normalizing said multi-dimensional vectors.

4. The computer readable media of claim 3, the method further comprising identifying at least one query predicate structure by a second predicate key that is a second integer representation, and constructing second multi-dimensional vectors, for said at least one query predicate structure, using said second integer representation.

5. The computer readable media of claim 1, the method further comprising identifying at least one query predicate structure by a second predicate key that is a second integer representation, and constructing second multi-dimensional vectors, for said at least one query predicate structure, using said second integer representation.

6. The computer readable media of claim 1, wherein said set of document predicate structures are representations of logical relationships between words in a sentence.

7. The computer readable media of claim 1, wherein each of said document predicate structures in said set includes a predicate and a set of arguments, wherein the predicate is one of a verb and a preposition.

8. One or more computer readable media storing computer executable instructions to perform a method for vectorizing a set of document predicate structures, the method comprising:

identifying at least one predicate in said set of document predicate structures by a predicate key that is an integer representation;

estimating conceptual nearness of two of said document predicate structures in said set of document predicate structures by subtracting corresponding ones of said predicate keys; and

outputting at least one document based upon the estimated conceptual nearness.

9. The computer readable media of claim 8, the method further comprising constructing multi-dimensional vectors using said integer representation.

10. The computer readable media of claim 9, the method further comprising normalizing said multi-dimensional vectors.

11. The computer readable media of claim 10, the method further comprising identifying at least one query predicate structure by a second predicate key that is a second integer representation, and constructing second multi-dimensional vectors, for said at least one query predicate structure, using said second integer representation.

12. The computer readable media of claim 8, the method further comprising identifying at least one query predicate structure by a second predicate key that is a second integer representation, and constructing second multi-dimensional vectors, for said at least one query predicate structure, using said second integer representation.

13. The computer readable media of claim 8, wherein said set of document predicate structures are representations of logical relationships between words in a sentence.

14. One or more computer readable media storing computer executable instructions to perform a method for constructing multi-dimensional vector representations for each document of a set of documents, the method comprising:

determining each predicate structure of one or more predicate structures M in each document of the set of documents, said M predicate structures including a predicate and at least one argument;

identifying the predicate and the at least one argument in each of said M predicate structures by a predicate key that is an integer representation;

determining a fixed number of arguments q for vector construction;

constructing an N-dimensional vector representation of each document based upon the predicate and q arguments; and

outputting at least one document of the set of documents based upon the constructed N-dimensional vector representation of the at least one document,

wherein any predicate structure of said M predicate structures that includes less than q arguments fills unfilled argument positions with a numerical zero.

15. The computer readable media of claim 14, wherein any predicate structure of said M predicate structures that includes more than q arguments omits remaining arguments after q argument positions are filled.

16. The computer readable media of claim 15, wherein conceptual nearness of two of said N-dimensional vector representations is estimated by subtracting corresponding ones of said predicate keys.

17. The computer readable media of claim 15, the method further comprising normalizing said N-dimensional vector representations.

18. The computer readable media of claim 14, wherein conceptual nearness of two of said N-dimensional vector representations is estimated by subtracting corresponding ones of said predicate keys.

19. The computer readable media of claim 14, the method further comprising normalizing said N-dimensional vector representations.