System and method for generating a relationship network

• US 7,987,191 B2
• Filed: 11/27/2007
• Issued: 07/26/2011
• Est. Priority Date: 06/06/2005
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Myers, Cornelia A., Podowski, Raf M., Franks, Kasian
• Primary Examiner(s): Kim; Paul
• Application Number:
  US11/945,909
• Publication Number:
  US 20080162514A1
• Time in Patent Office: 1,337 Days
• Field of Search: 707/999, 707/737, 707/749, 707/750, 1/1
• US Class Current: 707/750
• CPC Class Codes: G06F 16/3347 using vector based model

Abstract

A computer-implemented system and process for generating a relationship network is disclosed. The system provides a set of data items to be related and generates variable length data vectors to represent the relationships between the terms within each data item. The system can be used to generate a relationship network for documents, images, or any other type of file. This relationship network can then be queried to discover the relationships between terms within the set of data items.

Claims

1. A computer-implemented process for generating a relationship network, comprising:

(a) providing a set of data items to be related, wherein said data items comprise a plurality of terms;

(b) selecting a first data item to be processed;

(c) applying a frame to said first data item, wherein said frame comprises a first set of terms within said data item;

(d) calculating data vectors for the terms within said frame;

(e) moving said frame to comprise a second set of terms within said data item;

(f) creating a relationship network by repeating steps (d)-(e) until data vectors for all of the terms in said data item have been calculated;

(g) storing said relationship network to a storage;

(h) receiving a query term from a user;

(i) generating a query of the stored relationship network based on the received query term; and

(j) displaying query results, wherein the query results provide a visualization of a relationship between the query term and other terms in the set of data items,

wherein generating the query of the stored relationship network comprises retrieving a query object vector for the query term;

configuring a filter for use with the query;

expanding the query object vector into an expanded query object vector;

generating expanded associated object vectors based on the query object vector; and

finding associated terms between the expanded associated object vector and the expanded query object vector,

and wherein expanding the query object vector into an expanded query object vector comprises identifying a group of strongest related terms to the query term;

adding the group of strongest related terms to the query term to the beginning of the expanded query object vector;

retrieving vectors for each of the group of strongest related terms to the query term; and

inserting, for each vector of the group of strongest related terms to the query term, a plurality of the strongest terms for the vector.

2. The method of claim 1, comprising adding weight values to said data vectors for unique terms in said first data item.

3. The method of claim 2, wherein said weight values relate to the frequency of said terms in said first data item.

4. The method of claim 1, wherein said data items comprise documents and said terms comprise words.

5. The method of claim 4, wherein said frame comprises at least three sentences in said data item.

6. The method of claim 1, further comprising removing specific terms from said data items.

7. The method of claim 1, wherein said calculating comprises using a Fibonacci sequence in reverse to obtain a decay factor between terms in said frame.

18. The method of claim 1, wherein generating expanded associated object vectors based on the query object vector comprises:

identifying a group of strong related terms to the query term;

for each term in the group of strong related terms, retrieving vectors for the term and generating first dimension associated object vectors based on the retrieved vectors;

identifying a second group of strong related terms to the terms in the first dimension associated object vector;

for each term in the second group of strong related terms, retrieving vectors for the term and generated second dimension associated object vectors based on the retrieved vectors.

19. The method of claim 1, wherein finding associated terms between the expanded associated object vector and the expanded query object vector comprises passing the expanded query object vector to a comparison function configured to determine the similarity between terms in the expanded query object vector and the expanded associated object vectors.

8. A system for generating relationships between data items, comprising:

a storage comprising a set of data items to be related, wherein each data item comprises a plurality of terms;

a frame generator configured to generate a frame that selects a plurality of terms in said data items to associate;

a vector generator configured to generate data vectors to represent the associations between the data items within said frame;

a network generation engine configured to;

receive a query term from a user;

generate a query of the stored relationship network based on the received query term; and

display query results, wherein the query results provide a visualization of a relationship between the query term and other terms in the set of data items,

wherein the network generator configured to generate the query of the stored relationship network further comprises instructions configured to configure a filter for use with the query;

expand the query object vector into an expanded query object vector;

generate expanded associated object vectors based on the query object vector; and

find associated terms between the expanded associated object vector and the expanded query object vector, and

wherein the instructions configured to expand the query object vector into an expanded query object vector further comprise instructions configured to identify a group of strongest related terms to the query term;

add the group of strongest related terms to the query term to the beginning of the expanded query object vector;

retrieve vectors for each of the group of strongest related terms to the query term; and

insert, for each vector of the group of strongest related terms to the query term, a plurality of the strongest terms for the vector.

9. The system of claim 8, wherein the vector generator comprises instructions for assigning a distance measurement to each of said data items in said frame.

10. The system of claim 9, wherein said instructions use a Fibonacci decay calculation.

11. The system of claim 8, wherein said vector generator comprises instructions for modifying the data vectors based upon the frequency of the term within the frame divided by the frequency of the term in the entire set of documents.

12. The system of claim 8, further comprising instructions for removing stop-listed words from the documents.

13. The system of claim 8, further comprising instructions for treating terms comprising multiple-word phrases as single terms.

14. The system of claim 8, further comprising an input module for accepting a query term from a user and determining relationship vectors associated with said query term.

15. The system of claim 14, further comprising an extractor module comprising instructions for extracting all relationship vectors for said query term.

16. The system of claim 15, further comprising a list generator comprising instructions for generating a list of said relationship vectors according to a uniqueness score.

17. The system of claim 8, wherein said vector generator comprises instructions for calculating the distance between terms.

20. The system of claim 8, wherein the instructions configured to generate expanded associated object vectors based on the query object vector further comprise instructions configured to:

identify a group of strong related terms to the query term;

for each term in the group of strong related terms, retrieve vectors for the term and generating first dimension associated object vectors based on the retrieved vectors;

identify a second group of strong related terms to the terms in the first dimension associated object vector;

for each term in the second group of strong related terms, retrieve vectors for the term and generated second dimension associated object vectors based on the retrieved vectors.

21. The system of claim 8, wherein the instructions configured to find associated terms between the expanded associated object vector and the expanded query object vector further comprise instructions configured to pass the expanded query object vector to a comparison function, wherein the comparison function is configured to determine the similarity between terms in the expanded query object vector and the expanded associated object vectors.