System, apparatus, and method for user tunable and selectable searching of a database using a weigthted quantized feature vector

Abstract

The invention disclosed herein concerns a data processing means for user tunable and selectable searching of a database wherein the data contained therein have associated descriptive properties capable of being expressed in numeric form. A quantized vector representative of the descriptive properties is created for each item in the database. This quantized vector becomes the fingerprint for each data item. The user submits a query item to be matched against the database for similarity. A fingerprint is calculated for the query item. The user may then assign weights to the individual descriptive properties based upon perceived importance. A newly weighted fingerprint for the query item is then compared with the weighted fingerprints for all the data in the database. A list of results sorted in order of decreasing similarity is presented to the user. The user may then change the previously assigned weights and then re-run the similarity search. This may be done as often as necessary to achieve the desired results. The invention describes similarity searching in a generic database. However, this invention is particularly desirable in databases containing chemical compound structure data or biological response screening result data. The process described herein may be run stand alone or as a preliminary screening search in a large database. If used for screening, it can greatly reduce the amount of data required for exactly matching a query item to the data in the database.

We claim:  
     
         1 . A method for searching an electronic database of data, 
 wherein said data has associated with them a set of one or more calculated descriptive properties related to said data; and    wherein said descriptive properties are capable of being expressed in numeric form;    said method comprising: 
 a) accepting a query datum submitted electronically by a user;  
 b) electronically calculating a set of one or more descriptive properties of said query datum wherein the descriptive properties of said query datum are capable of being expressed in numeric form, are of the same number and arrangement, and are calculated in the same manner as said descriptive properties of the data in said database;  
 c) allowing the user to electronically examine the calculated descriptive properties of said query datum;  
 d) electronically setting a weight for every descriptive property to unity, said weight being an importance value for that particular descriptive property;  
 e) allowing the user to change said weights for any or all of the descriptive properties to other numeric values, said other numeric values being set at the user's discretion;  
 f) electronically calculating a similarity value to the query datum for all data in the database according to a method comprising: 
 factoring in the user assigned weights of the descriptive properties to both the query datum and each datum in the database thereby forming a weighted query datum and a weighted database datum;  
 computing a quantized vector distance, or equivalent indicator or coefficient, between said weighted query dataum and said weighted database datum; and,  
 assigning said quantized vector distance, or equivalent indicator or coefficient, to the similarity value;  
 
 g) presenting a list of data from said database to the user wherein said data is sorted in order of their similarity values;  
 h) repeating steps f) and g) of this method at the user's discretion as many times as the user desires.  
   
     
     
         2 . The method according to  claim 1  wherein a user can assign weights to said descriptive properties by manipulating objects on a computer screen.  
     
     
         3 . The method according to  claim 2  wherein said objects are sliders with numeric scales.  
     
     
         4 . The method according to  claim 2  wherein said objects are dials with numeric scales.  
     
     
         5 . The method according to  claim 2  wherein said objects are text boxes allowing numeric entry.  
     
     
         6 . The method according to  claim 1  wherein said similarity value is calculated using a weighted Euclidean Distance between said quantized vectors of the descriptive properties.  
     
     
         7 . The method according to  claim 1  wherein said similarity value is calculated using a weighted Hamming Distance between said quantized vectors of the descriptive properties.  
     
     
         8 . The method according to  claim 1  wherein said similarity value is calculated using a weighted Soergel Distance between said quantized vectors of the descriptive properties.  
     
     
         9 . The method according to  claim 1  wherein said similarity value is calculated using a weighted Tanimoto Coefficient between said quantized vectors of the descriptive properties.  
     
     
         10 . The method according to  claim 1  wherein said similarity value is calculated using a weighted Dice Coefficient between said quantized vectors of the descriptive properties.  
     
     
         11 . The method according to  claim 1  wherein said similarity value is calculated using a weighted Cosine Coefficient between said quantized vectors of the descriptive properties.  
     
     
         12 . The method according to  claim 1  wherein said data in said database is representative of structures of chemical compounds and wherein said query datum is also representative of the structure of a chemical compound.  
     
     
         13 . The method according to  claim 12  wherein said qurey datum is generated by a chemical structure drawing package.  
     
     
         14 . The method according to  claim 12  wherein said descriptive properties of said database data and query datum are characterized by assigned structure fragments.  
     
     
         15 . The method according to  claim 14  wherein the numeric values of said descriptive properties are set to either one or zero, a one representing the presence of the structure fragment associated with a particular descriptive property, and a zero representing the absence of said structure fragment.  
     
     
         16 . The method according to  claim 14  wherein the structure fragments are contained within and referenced in an electronic dictionary.  
     
     
         17 . The method according to  claim 14  wherein the structure fragments are generated by an algorithm.  
     
     
         18 . The method according to  claim 1  wherein said data in said database is representative of biological activity screening results and wherein said query datum is also representative of biological activity screening results.  
     
     
         19 . The method according to  claim 18  further comprising: 
 a) a user entering biological response values for known screening results;  
 b) a user entering the biological response values for a target query item;  
 c) a user entering weights for each of the biological response values;  
 d) a user selectively designating a method to be used to calculate similarity;  
 
     
     
         20 . The method according to  claim 1  further comprising storing the sorted calculated similarity results for further use.