IP Library Granted Patent US 9,183,288
Granted Patent B2
US 9,183,288 · App. 13/015,372 · Granted Nov 10, 2015

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

Inventor: Jonathan Murray (Berthoud, CO)
Assignee: Kinetx, Inc.
G06F17/30713
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 9,183,288
App. No.
13/015,372
Granted
Nov 10, 2015
Kind
B2
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 (62)

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.

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.

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.

Assignments (3)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 25, 2023
From: SYNTORG, INC.
To: KINETX, INC.
Reel/Frame 063767/0491 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 8, 2019
From: KINETX, INC.
To: SYNTORG, INC.
Reel/Frame 050001/0142 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Feb 4, 2011
From: MURRAY, JONATHAN
To: KINETX, INC.
Reel/Frame 025745/0052 →
Continuity (2)
Provisional Application 61298684 · Jan 27, 2010
Related Publication 20110225159A1 · Sep 15, 2011