Associative memory

• US 20060212431A1
• Filed: 10/03/2005
• Published: 09/21/2006
• Est. Priority Date: 08/18/2000
• Status: Active Grant

• Current Assignee: Hyland Switzerland, Sarl
• Original Assignee: BDGB Enterprise Software Ltd. Liab., Co.
• Inventors: Lapir, Gannady, Urbschat, Harry
• Granted Patent: US 7,433,997 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/332 Query formulation
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: G11C 15/043 using capacitive charge storage elements
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• 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
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A computer-implemented method of realizing an associative memory capable of storing a set of documents and retrieving one or more stored documents similar to an inputted query document, said method comprising: coding each document or a part of it through a corresponding feature vector consisting of a series of bits which respectively code for the presence or absence of certain features in said document; arranging the feature vectors in a matrix; generating a query feature vector based on the query document and according to the rules used for generating the feature vectors corresponding to the stored document s such that the query vector corresponds in its length to the width of the matrix; storing the matrix column-wise; for those columns of the matrix where the query vector indicates the presence of a feature, bitwise performing one or more of preferably hardware supported logical operations between the columns of the matrix to obtain one or more additional result columns coding for a similarity measure between the query and parts or the whole of the stored documents; and said method further comprising one or a combination of the following: retrieval of one or more stores documents based on the obtain ed similarity measure; and or storing a representation of a document through it s feature vector into the above matrix.

Claims

1. A method of retrieving documents comprising the steps of:

coding a plurality of stored documents as respective document feature vectors representing the presence or absence of certain features in each of said stored documents;

generating a query feature vector based on a query document and according to the rules used for generating the feature vectors corresponding to the stored documents; and

bitwise performing one or more logical operations between the query feature vector and said document feature vectors to obtain respective similarity measures.

2. The method of claim 1, wherein further comprising a step of formulating a similarity score:

for respective one of said stored documents, each similarity score representing how often a certain feature or a set of features defined by the logical 1'"'"'s in the query vector occurs within a corresponding feature vector.

3. The method of claim 1, wherein based an said similarity measure a set of candidate documents is chosen for further inspection, said set of candidate documents being further evaluated with respect to their similarity to the query document, said evaluation resulting in one or more further similarity measures reflecting the similarity between query and candidate under one or more aspects.

4. The method of claim 3, wherein based on said one or more further similarity measures there is obtained a final similarity measure based on which it is decided which documents are finally to be retrieved.

5. The method of claim 3, wherein said further inspection comprises comparing the query elements with the elements of the candidate documents to obtain one or more of the following further similarity measures:

a measure for the similarity between the textual query elements and textual document elements, obtaining for each query element a corresponding textual document element based on said similarity measure;

obtaining measure for the degree of coincidence between the sequential order of the textual query elements and the sequential order of the corresponding textual document elements;

obtaining a measure for the similarity between the distance between elements in the query and the corresponding distance between elements in the document.

6. The method of claim 1, wherein results returned which lie above a certain similarity threshold, and/or wherein a user definable number of documents are retrieved which have the highest similarity.

7. The method of claim 1, wherein a desired degree of similarity can be defined by the user to be:

identity;

an settable degree of similarity or a similarity threshold; and

or identity for certain features and a satiable degree of similarity for the other features.

8. The method of claim 1, wherein features coded by a feature vector for their presence or absence comprise one or more of the following;

unigrams, digrams, multigrams, words, fragments of text, sentences, paragraphs, or a combination of them;

semantic classes reflecting a certain meaning which elements in the text to be represented may have;

concept classes reflecting an abstract concept to which elements in the text to be represented belong;

one or more classification classes classifying the document according to a classification scheme;

one or more attributes which may be assigned to a document.

9. The method of claim 8, wherein the classification classes or the attributes may be attributes of the documents such as Date, author, title, publisher, editor, topic of the text, or classification results form classifications by the user or by an automatic classification engine.

10. The method of claim 8, wherein the query document is assigned automatically an attribute or class based on the attribute or classes of one or more result documents obtained through the query according to one of the preceding claims.

11. The method of claim 1, wherein a matrix formed by the feature vectors representing the documents to be searched is stored column-wise, and wherein said method further comprises:

for those columns of the matrix where the query feature vector bit is set, performing a processor supported bitwise operation between the columns of the matrix to obtain one or more result columns, the values in the result columns representing the similarity between the query and the stored documents.

12. The method of claim 1, wherein there is a plurality of result columns such that the result columns form a matrix, and wherein a row of the thus formed result column matrix represents a degree of similarity between the query and the stored document corresponding to said row.

13. The method of claim 1 further comprising the steps of:

obtaining a set of examples for a certain classification class by carrying out a search for documents belonging to a particular class; and

training a classification engine by said obtained set of examples as the learning input.

14. The method of claim 13, wherein said search for example documents is carried out in a subset of the set of stored documents, said subset being defined through the presence of one or more attributes or classification classes specified by the user in the query, thereby selecting for said query only the documents of said subset.

15. The method of claim 13, said method being applied to realize a self-improving system through the steps of:

retrieving relevant documents from a set of documents through an associative search;

using the retrieved documents for improving a classification engine,

using the classification through a classification engine to improve the retrieval through an associative memory; and

using the improved retrieval to improve the classification engine.

16. An apparatus for realizing an associative memory capable of storing a set of documents and retrieving one or more stored documents similar to an inputted query document, said apparatus comprising:

means for storing a set of documents and retrieving one or more of said stored documents;

means for coding each of said stored document as a corresponding feature vector consisting of a series of bits which respectively code for the presence or absence of certain features in said document;

means for generating a query feature vector based on a query document and according to the rules used for generating the feature vectors corresponding to the stored documents;

means for performing one or more logical operations between each of said feature vectors to obtain a similarity measure between the query and parts of the stored documents.

17. A computer program stored in a computer storage medium enabling a computer to store and retrieve one or more documents similar to an inputted query document, said method comprising the steps of:

coding a plurality of stored documents as respective document feature vectors representing the presence or absence of certain features in each of said stored documents;

generating a query feature vector based on a query document and according to the rules used for generating the feature vectors corresponding to the stored documents; and

bitwise performing one or more logical operations between the query feature vector and said document feature vectors to obtain respective similarity measures.