Methods and apparatus for similarity text search based on conceptual indexing

• US 6,542,889 B1
• Filed: 01/28/2000
• Issued: 04/01/2003
• Est. Priority Date: 01/28/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip Shi-Lung
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): TRUONG, CAM Y T
• Application Number:
  US09/493,811
• Time in Patent Office: 1,159 Days
• Field of Search: 707/1-5, 707/10, 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

In one aspect of the invention, a method of performing a conceptual similarity search comprises the steps of: generating one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search; building a conceptual index of documents with the one or more word-chains; and evaluating a similarity query using the conceptual index. The evaluating step preferably returns one or more of the closest documents resulting from the search; one or more matching word-chains in the one or more documents; and one or more matching topical words of the one or more documents.

Claims

1. A method of performing a conceptual similarity search, the method comprising the steps of:

generating one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search, wherein at least one of the one or more word-chains comprises a meta-document formed by applying a damping function to a set of the one or more documents, concatenating the document set after application of the damping function, and removing from the meta-document one or more least-weighted words;

building a conceptual index of documents with the one or more word-chains; and

evaluating a similarity query using the conceptual index.

2. The method of claim 1, wherein the index building step comprises the steps of:

for each word-chain, finding the one or more documents with conceptual similarity to the word-chain; and

retaining a list of identities of the one or more documents which have conceptual similarity not less than a predefined threshold value.

3. The method of claim 2, wherein a document identity comprises a unique integer value.

4. The method of claim 1, wherein the evaluating step comprises returning one or more of the closest documents resulting from the search.

5. The method of claim 1, wherein the evaluating step comprises returning one or more matching word-chains in the one or more documents.

6. The method of claim 1, wherein the evaluating step comprises returning one or more matching topical words of the one or more documents.

7. The method of claim 1, wherein the evaluating step comprises the step of generating a conceptual representation of a target document associated with the similarity query.

8. The method of claim 7, wherein the evaluating step comprises the step of finding a substantially close match to a target document among a plurality of indexed documents using the conceptual representation of the target document.

9. A method of performing a conceptual similarity search, the method comprising the steps of:

generating one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search;

building a conceptual index of documents with the one or more word-chains; and

evaluating a similarity query using the conceptual index;

wherein the word-chain generating step comprises the steps of;

initializing one or more word-chains to one or more sets of randomly selected documents;

assigning one or more other documents to the one or more sets of randomly selected documents;

concatenating the one or more documents in each set and removing less frequently occurring words from each word-chain; and

merging the word-chains.

10. The method of claim 9, wherein the initializing, assigning, concatenating and merging steps are iteratively repeated.

11. A method of performing a conceptual similarity search, the method comprising the steps of:

generating one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search;

building a conceptual index of documents with the one or more word-chains; and

evaluating a similarity query using the conceptual index;

wherein the evaluating step comprises the step of generating a conceptual representation of a target document associated with the similarity query, and wherein the target document conceptual representation generating step comprises the steps of;

calculating a similarity measure between the target document and each conceptual word-chain;

determining whether each similarity measure is not less than a predetermined threshold value; and

generating conceptual strength measures by respectively setting a conceptual strength measure to a similarity measure minus the predetermined threshold value, when the similarity measure is not less than a predetermined threshold value.

12. A method of performing a conceptual similarity search, the method comprising the steps of:

generating one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search;

building a conceptual index of documents with the one or more word-chains; and

evaluating a similarity query using the conceptual index;

wherein the evaluating step comprises the step of generating a conceptual representation of a target document associated with the similarity query and finding a substantially close match to a target document among a plurality of indexed documents using the conceptual representation of the target document, and wherein the finding step comprises the steps of;

finding one or more concepts in the target document;

evaluating an inverted list associated with the indexed documents to find the one or more documents which have at least one concept in common with the target document;

calculating a conceptual cosine of the one or more common concept documents to the target document;

finding the closest document to the target document based on the conceptual cosine; and

reporting an output statistic between the closest matching document and the target document.

13. The method of claim 12, wherein the closest document finding step further comprises the steps of:

reporting concepts which are present in the target document and the closest matching document; and

finding a topical vocabulary which is common to the target document and the closest matching document and matching word-chains.

14. Apparatus for performing a conceptual similarity search, the apparatus comprising:

at least one processor operative to;

(i) generate one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search, wherein at least one of the one or more word-chains comprises a meta-document formed by applying a damping function to a set of the one or more documents, concatenating the document set after application of the damping function, and removing from the meta-document one or more least-weighted words;

(ii) build a conceptual index of documents with the one or more word-chains; and

(iii) evaluate a similarity query using the conceptual index; and

memory, coupled to the at least one processor, for storing at least one of the conceptual word-chains and the conceptual index.

15. The apparatus of claim 14, wherein the processor is further operative to perform the index building operation by:

(i) for each word-chain, finding the one or more documents with conceptual similarity to the word-chain; and

(ii) retaining a list of identities of the one or more documents which have conceptual similarity not less than a predefined threshold value.

16. The apparatus of claim 15, wherein a document identity comprises a unique integer value.

17. The apparatus of claim 14, wherein the processor is further operative to perform the evaluating operation by returning one or more of the closest documents resulting from the search.

18. The apparatus of claim 14, wherein the processor is further operative to perform the evaluating operation by returning one or more matching word-chains in the one or more documents.

19. The apparatus of claim 14, wherein the processor is further operative to perform the evaluating operation by returning one or more matching topical words of the one or more documents.

20. The apparatus of claim 14, wherein the processor is further operative to perform the evaluating operation by generating a conceptual representation of a target document associated with the similarity query.

21. The apparatus of claim 20, wherein the processor is further operative to perform the evaluating operation by finding a substantially close match to a target document among a plurality of indexed documents using the conceptual representation of the target document.

22. Apparatus for performing a conceptual similarity search, the apparatus comprising:

at least one processor operative to;

(i) generate one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search;

(ii) build a conceptual index of documents with the one or more word-chains; and

(iii) evaluate a similarity query using the conceptual index; and

memory, coupled to the at least one processor, for storing at least one of the conceptual word-chains and the conceptual index;

wherein the processor is further operative to perform the word-chain generating operation by initializing one or more word-chains to one or more sets of randomly selected documents;

assigning one or more other documents to the one or more sets of randomly selected documents;

concatenating the one or more documents in each set and removing less frequently occurring words from each word-chain; and

merging the word-chains.

23. The apparatus of claim 22, wherein the processor is further operative to iteratively repeat the initializing, assigning, concatenating and merging operations.

24. Apparatus for performing a conceptual similarity search, the apparatus comprising:

at least one processor operative to;

(i) generate one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search;

(ii) build a conceptual index of documents with the one or more word-chains; and

(iii) evaluate a similarity query using the conceptual index; and

memory, coupled to the at least one processor, for storing at least one of the conceptual word-chains and the conceptual index;

wherein the processor is further operative to perform the evaluating operation by generating a conceptual representation of a target document associated with the similarity query, and wherein the processor is further operative to perform the target document conceptual representation generating operation by calculating a similarity measure between the target document and each conceptual word-chain;

determining whether each similarity measure is not less than a predetermined threshold value; and

generating conceptual strength measures by respectively setting a conceptual strength measure to a similarity measure minus the predetermined threshold value, when the similarity measure is not less than a predetermined threshold value.

25. Apparatus for performing a conceptual similarity search, the apparatus comprising:

at least one processor operative to;

(i) generate one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search;

(ii) build a conceptual index of documents with the one or more word-chains; and

(iii) evaluate a similarity query using the conceptual index; and

memory, coupled to the at least one processor, for storing at least one of the conceptual word-chains and the conceptual index;

wherein the processor is further operative to perform the evaluating operation by generating a conceptual representation of a target document associated with the similarity query and finding a substantially close match to a target document among a plurality of indexed documents using the conceptual representation of the target document, and wherein the processor is further operative to perform the finding operation by finding one or more concepts in the target document;

evaluating an inverted list associated with the indexed documents to find the one or more documents which have at least one concept in common with the target document;

calculating a conceptual cosine of the one or more common concept documents to the target document;

finding the closest document to the target document based on the conceptual cosine; and

reporting an output statistic between the closest matching document and the target document.

26. The apparatus of claim 25, wherein the processor is further operative to perform the closest document finding operation by:

(i) reporting concepts which are present in the target document and the closest matching document; and

(ii) finding a topical vocabulary which is common to the target document and the closest matching document and matching word-chains.

27. An article of manufacture for performing a conceptual similarity search, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

generating one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search, wherein at least one of the one or more word-chains comprises a meta-document formed by applying a damping function to a set of the one or more documents, concatenating the document set after application of the damping function, and removing from the meta-document one or more least-weighted words;

building a conceptual index of documents with the one or more word-chains; and

evaluating a similarity query using the conceptual index.

28. The article of claim 27, wherein the index building step comprises the steps of:

for each word-chain, finding the one or more documents with conceptual similarity to the word-chain; and

retaining a list of identities of the one or more documents which have conceptual similarity not less than a predefined threshold value.

29. The article of claim 28, wherein a document identity comprises a unique integer value.

30. The article of claim 27, wherein the evaluating step comprises returning one or more of the closest documents resulting from the search.

31. The article of claim 27, wherein the evaluating step comprises returning one or more matching word-chains in the one or more documents.

32. The article of claim 27, wherein the evaluating step comprises returning one or more matching topical words of the one or more documents.

33. The article of claim 27, wherein the evaluating step comprises the step of generating a conceptual representation of a target document associated with the similarity query.

34. The article of claim 33, wherein the evaluating step comprises the step of finding a substantially close match to a target document among a plurality of indexed documents using the conceptual representation of the target document.

35. An article of manufacture for performing a conceptual similarity search, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

generating one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search;

building a conceptual index of documents with the one or more word-chains; and

evaluating a similarity query using the conceptual index;

wherein the word-chain generating step comprises the steps of;

initializing one or more word-chains to one or more sets of randomly selected documents;

assigning one or more other documents to the one or more sets of randomly selected documents;

concatenating the one or more documents in each set and removing less frequently occurring words from each word-chain; and

merging the word-chains.

36. The article of claim 35, wherein the initializing, assigning, concatenating and merging steps are iteratively repeated.

37. An article of manufacture for performing a conceptual similarity search, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

generating one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search;

building a conceptual index of documents with the one or more word-chains; and

evaluating a similarity query using the conceptual index;

wherein the evaluating step comprises the step of generating a conceptual representation of a target document associated with the similarity query, and wherein the target document conceptual representation generating step comprises the steps of;

calculating a similarity measure between the target document and each conceptual word-chain;

determining whether each similarity measure is not less than a predetermined threshold value; and

generating conceptual strength measures by respectively setting a conceptual strength measure to a similarity measure minus the predetermined threshold value, when the similarity measure is not less than a predetermined threshold value.

38. An article of manufacture for performing a conceptual similarity search, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

generating one or more conceptual word-chains from one or more documents to be used in the conceptual similarity search;

building a conceptual index of documents with the one or more word-chains; and

evaluating a similarity query using the conceptual index;

wherein the evaluating step comprises the step of generating a conceptual representation of a target document associated with the similarity query and finding a substantially close match to a target document among a plurality of indexed documents using the conceptual representation of the target document, and wherein the finding step comprises the steps of;

finding one or more concepts in the target document;

evaluating an inverted list associated with the indexed documents to find the one or more documents which have at least one concept in common with the target document;

calculating a conceptual cosine of the one or more common concept documents to the target document;

finding the closest document to the target document based on the conceptual cosine; and

reporting an output statistic between the closest matching document and the target document.

39. The article of claim 38, wherein the closest document finding step further comprises the steps of:

reporting concepts which are present in the target document and the closest matching document; and

finding a topical vocabulary which is common to the target document and the closest matching document and matching word-chains.