System and method of structuring data for search using latent semantic analysis techniques

• US 9,183,288 B2
• Filed: 01/27/2011
• Issued: 11/10/2015
• Est. Priority Date: 01/27/2010
• Status: Active Grant

• Current Assignee: KinetX, Inc.
• Original Assignee: KinetX, Inc.
• Inventors: Murray, Jonathan
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): RAHMAN, MOHAMMAD N
• Application Number:
  US13/015,372
• Publication Number:
  US 20110225159A1
• Time in Patent Office: 1,748 Days
• Field of Search: 707/739
• US Class Current: 1/1
• CPC Class Codes: G06F 16/358 Browsing; Visualisation therefor

Abstract

The disclosed embodiments provide a system and method for using modified Latent Semantic Analysis techniques to structure data for efficient search and display. The present invention creates a hierarchy of clustered documents, representing the topics of a domain corpus, through a process of optimal agglomerative clustering. The output from a search query is displayed in a fisheye view corresponding to the hierarchy of clustered documents. The fisheye view may link to a two-dimensional self-organizing map that represents semantic relationships between documents.

Claims

1. A computer-based method of organizing data for search, the method comprising the steps of:

accessing a domain corpus;

parsing the domain corpus into a plurality of documents;

parsing each document into at least one term that corresponds to the document;

generating a term-to-document matrix that correlates each document with the at least one term that corresponds to the document, the at least one term defining a document node for the document;

performing a singular value decomposition and a dimension reduction on the term-to-document matrix to form a reformed term-to-document matrix having document nodes with fewer dimensions than the document nodes of the term-to-document matrix;

comparing at least one document node of the reformed term-to-document matrix against another document node of the reformed term-to-document matrix; and

combining at least one document node of the term-to-document matrix with another document node of the term-to-document matrix, based on the comparison of the at least one document node of the reformed tem-to-document matrix against the another document node of the reformed term-to-document matrix, to form a combined document node representing the combination of the at least one document node of the term-to-document matrix with the another document node of the term-to-document matrix, thereby clustering at least two document nodes of the term-to-document matrix.

2. The computer-based method of claim 1, wherein the step of comparing the at least one document node of the reformed term-to-document matrix against the another document node of the reformed term-to-document matrix, includes determining the cosine similarity between the at least one document node of the reformed term-to-document matrix and the another document node of the reformed tem-to-document matrix,

3. The computer-based method of claim 1, wherein the step of combining the at least one document node of the tem-to-document matrix with the another document node of the term-to-document matrix to form a combined document node representing the combination of the at least one document node of the term-to-document matrix with the another document node of the term-to-document matrix, includes summing the at least one document node of the term-to-document matrix with the another document node of the term-to-document matrix,

4. The computer-based method of claim 1, wherein:

the at least one document node of the term-to-document matrix that is combined with the another document node of the term-to-docuinent matrix, represents a document parsed from the domain corpus, that is represented by the at least one document node of the reformed term-to-document matrix that is compared against the another document node of the reformed term-to-document matrix, and

the another document node of the term-to-document matrix, represents a document parsed from the domain corpus, that is represented by the another document node of the reformed term-to-document matrix.

5. The computer-based method of claim 1, wherein the step of comparing the at least one document node of the reformed term-to-document matrix against the another document node of the reformed term-to-document matrix, includes determining if a similarity measure between the at least one document node of the reformed term-to-document matrix and the another document node of the reformed term-to-document matrix exceeds a threshold value.

6. The computer-based method of claim 5, wherein the step of combining the at least one document node of the term-to-document matrix with the another document node of the term-to-document matrix, includes combining the at least one document node of the term-to-document matrix with the another document node of the term-to-document matrix, based on whether the similarity measure between the at least one document node of the reformed term-to-document matrix and the another document node of the reformed term-to-document matrix exceeds the threshold value.

7. The computer-based method of claim 1, wherein the steps of

comparing at least one document node of the reformed term-to-document matrix against another document node of the reformed term-to-document matrix;

and

combining at least one document node of the term-to-document matrix with another document node of the term-to-document matrix, based on the comparison of the at least one document node of the reformed term-to-document matrix against the another document node of the reformed term-to-document matrix, to form a combined document node representing the combination of the at least one document node of the term-to-document matrix with the another document node of the term-to-document matrix, thereby clustering at least two document nodes of the term-to-document matrix,

are performed iteratively until each document node of the term-to-document matrix is combined with at least one other document node of the term-to-document matrix, thereby forming a combined term-to-document matrix.

8. The computer-based method of claim 7, further comprising querying the document nodes of the reformed term-to-document matrix to produce a retrieved document, and displaying on a graphical user interface, both an indicator of the retrieved document and an indicator of at least one other document that corresponds to a document node that is combined with a document node that corresponds to the retrieved document.

9. The computer-based method of claim 7, further comprising querying the document nodes of the reformed term-to-document matrix to produce a retrieved document, and displaying on a self-organizing map, both an indicator of the retrieved document and an indicator of at least one other document that corresponds to a document node that is combined with a document node that corresponds to the retrieved document.

10. The computer-based method of claim 1, wherein the step of parsing each document into the at least one term that corresponds to the document, includes tagging the at least one term with a part-of-speech.

11. The computer-based method of claim 1, wherein the domain corpus is selected from a group consisting of:

textual material, symbols, machine-readable data, and combinations thereof.

12. The computer-based method of claim 1, wherein the at least one document node of the term-to-document matrix is combined with the another document node of the term-to-document matrix based on a steepest descent algorithm applied to the at least one document node of the reformed term-to-document matrix and the another document node of the reformed term-to-document matrix.

23. The computer based method of claim 1, further comprising:

combining a plurality of the document nodes of the term-to-document matrix to form a plurality of combined document nodes, each combined document node representing a combination of at least one document node of the term-to-document matrix with another document node of the term-to-document matrix and being formed based on a comparison of the at least one document node of the combined document node with the another document node of the combined document node, the plurality of combined document nodes forming a combined term-to-document matrix; and

performing a singular value decomposition and a dimension reduction on the combined term-to-document matrix to form a reformed combined term-to-document matrix having document nodes with fewer dimensions than the document nodes of the combined term-to-document matrix.

13. A non-transitory computer readable medium storing instructions that when executed by a processor, cause the processor to:

access a domain corpus;

parse the domain corpus into a plurality of documents;

parse each document into at least one term that corresponds to the document;

generate a term-to-document matrix that correlates each document with the at least one term that corresponds to the document, the at least one term defining a document node for the document;

perform singular value decomposition and a dimension reduction on the term-to-document matrix to form a reformed term-to-document matrix having document nodes with fewer dimensions than the document nodes of the term-to-document matrix;

compare at least one document node of the reformed term-to-document matrix against another document node of the reformed term-to-document matrix; and

combine at least one document node of the term-to-document matrix with another document node of the term-to-document matrix, based on the comparison of the at least one document node of the reformed term-to-document matrix against the another document node of the reformed term-to-document matrix, to form a combined document node representing the combination of the at least one document node of the term-to-document matrix with the another document node of the term-to-document matrix, thereby clustering at least two document nodes of the term-to-document matrix.

14. The computer readable medium of claim 13, wherein the instruction of combine the at least one document node of the term-to-document matrix with the another document node of the term-to-document matrix to form a combined document node representing the combination of the at least one document node of the term-to-document matrix with the another document node of the term-to-document matrix, includes summing the at least one document node of the term-to-document matrix with the another document node of the term-to-document matrix.

15. The computer readable medium of claim 13, wherein:

the at least one document node of the term-to-document matrix that is combined with the another document node of the term-to-document matrix, represents a document parsed from the domain corpus, that is represented by the at least one document node of the reformed term-to document matrix that is compared against the another document node of the reformed term-to-document matrix, and

the another document node of the tem-to-document matrix, represents a document parsed from the domain corpus, that is represented by the another document node of the reformed term-to-document matrix.

16. The computer readable medium of claim 13, wherein the instruction of compare the at least one document node of the reformed term-to-document matrix against the another document node of the reformed term-to-document matrix, includes determining if a similarity measure between the at least one document node of the reformed term-to-document matrix and the another document node of the reformed term-to-document matrix exceeds a threshold value.

17. A computer-based method of ascertaining semantic relationships between documents, the method comprising the steps of:

accessing a domain corpus;

parsing the domain corpus into a plurality of documents;

parsing each document into at least one term that corresponds to the document;

generating a term-to-document matrix that correlates each document with the at least one term that corresponds to the document, the at least one term defining a document node for the document;

performing a singular value decomposition and a dimension reduction on the term-to-document matrix to from a reformed term-to-document matrix having document nodes with fewer dimensions than the document nodes of the term-to-document matrix;

selecting a document node of the reformed term-to-document matrix;

filtering terms of at least one document node of the reformed term-to/-document matrix that is not the selected document node, based on which at least one term defines a document node in the term-to-docuinent matrix that corresponds to the document node that has been selected, to form at least one filtered document node that has not been selected; and

displaying an output of a similarity between the document node that has been selected, and the at least one filtered document node that has not been selected, thereby displaying a semantic relationship between the document node that has been selected and the at least one filtered document node that has not been selected.

18. The computer-based method of claim 17, wherein the step of filtering terms of at least one document node of the reformed term-to-document matrix that is not the selected document node, includes excluding terms from the at least one document node of the reformed term-to-document matrix that is not the selected document node, that do not correspond to the at least one term that defines the document node in the term-to-document matrix that corresponds to the document node that has been selected.

19. The computer-based method of claim 17, wherein the output is displayed on a two-dimensional map.

20. The computer-based method of claim 19, wherein the two-dimensional map is a self-organizing map.

21. A non-transitory computer readable medium storing instructions that when executed by a processor, cause the processor to:

access a domain corpus;

parse the domain corpus into a plurality of documents;

parse each document into at least one term that corresponds to the document;

generate a term-to-document matrix that correlates each document with the at least one term that corresponds to the document, the at least one term defining a document node for the document;

perform a singular value decomposition and a dimension reduction on the term-to-document matrix to form a reformed term-to-document matrix having document nodes with fewer dimensions than the document nodes of the term-to-document matrix;

select a document node of the reformed term-to-document matrix;

filter terms of at least one document node of the reformed term-to-document matrix that is not the selected document node, based on which at least one term defines a document node in the term-to-document matrix that corresponds to the document node that has been selected, to form at least one filtered document node that has not been selected; and

display an output of a similarity between the document node that has been selected, and the at least one filtered document node that has not been selected, thereby displaying a semantic relationship between the document node that has been selected and the at least one filtered document node that has not been selected.

22. The non-transitory computer readable medium of claim 21, wherein the instruction of filter terms of at least one document node of the reformed term-to-document matrix that is not the selected document node, includes excluding terms from the at least one document node of the reformed term-to-document matrix that is not the selected document node, that do not correspond to the at least one term that defines the document node in the term-to-document matrix that corresponds to the document node that has been selected.