Associative memory

• US 7,908,430 B2
• Filed: 08/14/2008
• Issued: 03/15/2011
• Est. Priority Date: 08/18/2000
• Status: Expired due to Fees

• Current Assignee: Hyland Switzerland, Sarl (HSI Holdings II Incorporated)
• Original Assignee: BDGB Enterprise Software SARL (Ninestar Corporation)
• Inventors: Lapir, Gannady, Urbshat, Harry
• Primary Examiner(s): Farrokh; Hashem
• Application Number:
  US12/191,774
• Publication Number:
  US 20090193022A1
• Time in Patent Office: 943 Days
• Field of Search: 711/108, 707/999.003
• US Class Current: 711/108
• 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 documents 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 obtained similarity measure; and or storing a representation of a document through its feature vector into the above matrix.

Claims

1. A computer-implemented method of simulating an associative memory capable of retrieving a document similar to an inputted query document from a set of stored documents, the method comprising:

coding all documents of the set through a plurality of feature vectors, each feature vector belonging to a particular document or part of the particular document of the set and comprising a series of vector elements which relate to certain features present or absent in the particular document or part of the particular document, the feature vectors each comprising a series of bits as vector elements, wherein each feature of the certain features is associated to one particular bit of the series of bits, the particular bit being set to a logical one if the associated feature is present in a respective document or part of the respective document, so that the series of bits codes for the presence or absence of certain features in the respective document or part of the respective document of the set;

arranging the feature vectors in a matrix, so that the rows of the matrix each are associated to the particular document or part of the particular document of the set and corresponds to a respective feature vector of the plurality of feature vectors, the matrix being stored column-wise to provide that respective bits of each respective matrix column, which respectively are set or not set to a logical one, are simultaneously processed in one processor operation by a processor used for obtaining the result column;

generating a query feature vector based on the query document and according to the rules used for generating the feature vectors corresponding to the set of stored documents such that the query vector corresponds in its length to the length of a row of the matrix, the query feature vector consisting of the series of bits as vector elements, wherein each feature of the certain features is associated to one particular bit of the series of bits, the particular bit being set to a logical one if the associated feature is present in the query document, so that the series of bits codes for the presence or absence of certain features in the query document;

obtaining, on basis of the matrix and the query feature vector, a result column coding for a similarity measure to indicate a similarity between the query document and all documents or parts of documents represented in the matrix, wherein in order to obtain the result column a logical operation is performed on those columns of the matrix for which the respective bit of the query vector is set to a logical one, so a result vector is obtained which codes the similarity measure between the query document and the documents or parts of the documents of the set, the logical operations comprising a logical operation performed bitwise between the bits of those columns of the matrix;

retrieving one or more stored documents based on the obtained similarity measure;

wherein the method is characterized by;

treating the documents of the set as hierarchically structured sets of units, with the respective document of the set consisting of several units, in such a way that the feature vectors, which are arranged in the matrix, are unit feature vectors, which are obtained by coding a respective unit of the respective document of the set each through a corresponding unit feature vector comprising a series of bits which respectively are set to a logical one if the respective associated feature of the certain features is present in the respective unit to code for the presence or absence of the certain features in the respective unit, so that the rows of the matrix each are associated to the respective unit of the respective document of the set and correspond to the respective unit feature vector coded therefor;

obtaining scores from the result vector which represent as a similarity measure a frequency of occurrence of logical ones in the rows of the matrix at the positions indicated by the positions of logical ones in the query feature vector;

adding for the documents of the set the scores which are obtained for the different units of the respective document to obtain a document score of each document of the set; and

selecting for retrieval and retrieving a best document which has the highest document score and/or for which the document score fulfills a score threshold condition.