Evaluation system for determining analogy and symmetric comparison among objects in model-based computation systems

• US 4,905,162 A
• Filed: 03/30/1987
• Issued: 02/27/1990
• Est. Priority Date: 03/30/1987
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Holly, Laura E., Hartzband, David J.
• Primary Examiner(s): RUGGIERO, JOSEPH F
• Application Number:
  US07/032,161
• Time in Patent Office: 1,065 Days
• Field of Search: 364/513, 364/300, 364/200 MS File, 364/900 MS File, 382/14, 382/15, 382/30, 382/33, 382/34, 382/36, 382/50
• US Class Current: 706/52
• CPC Class Codes: G06V 30/1985 Syntactic analysis, e.g. using a grammatical approach syntactic image representation G06V30/18171

Abstract

A mechanism for determining analogy and symmetric comparison among objects based on characteristics and weighting values provided by an operator or calling program. The characteristics of each object are defined in a reference table. A similarity table is constructed in which comparisons and differences between objects are detailed based on whether they possess similar characteristics. The weights are used to provide a quantitative measure of similarity and difference.

Claims

1. A system for determining a selected relationship among a plurality of objects each having a plurality of characteristics having diverse values, said system comprising:

A. Association means for establishing associations among characteristics of said objects;

B. comparison means for performing a selected similarity operation in connection with each of the values of associated ones of said objects'"'"' characteristics to determine a characteristic similarity value associated with said characteristics; and

C. similarity determination means for performing a composite operation in response to the characteristic similarity values for determining a composite similarity value representing a degree of similarity among objects.

2. A system as defined in claim 1 wherein said association means includes similarity table establishment means for establishing a similarity table including a plurality of records each having a plurality of characteristic fields for receiving values of associated characteristics.

3. A system as defined in claim 2 in which each object has an associated reference table having a plurality of entries each storing a characteristic value, said similarity table establishment means using the objects'"'"' reference tables in establishing a similarity table.

4. A system as defined in claim 2 wherein said characteristics include type characteristics and value characteristics, each value characteristic being ancillary to a type characteristic, said similarity table establishment means establishing in said similarity table (i) records having characteristic fields for receiving values of associated type characteristic and (ii) other records having characteristic fields for receiving values of value characteristics ancillary to associated type characteristics.

5. A method for determining a selected relationship among a plurality of objects each having a plurality of characteristics having diverse values, said method comprising the steps of:

A. establishing associations among characteristics of said objects;

B. performing a selected similarity operation in connection with each of the values of associated ones of said objects'"'"' characteristics to determine a characteristic similarity value associated with said characteristics; and

C. performing a composite operation in response to the characteristics similarity values for determining a composite similarity value representing a degree of similarity among objects.

6. A method as defined in claim 5 wherein said association step includes a step of establishing a similarity table including a plurality of records each having a plurality of characteristic fields for receiving values of associated characteristics.

7. A method as defined in claim 6 in which each object has an associated reference table having a plurality of entries each storing a characteristic value, the objects'"'"' reference tables being used in said similarity table establishment step in establishing a similarity table.

8. A method as defined in claim 6 wherein said characteristics include type characteristics and value characteristics, each value characteristic being ancillary to a type characteristic, said similarity table establishment step including steps of establishing in said similarity table (i) records having characteristic fields for receiving values of associated type characteristic and (ii) other records having characteristic fields for receiving values of value characteristics ancillary to associated type characteristics.

9. A system for determining a selected relationship between a plurality of objects each having characteristics, including type characteristics and value characteristics, each said value characteristic representing a value associated with a type characteristic, said characteristics being defined by entries in a reference table, said system comprising:

A. similarity table establishment means for establishing a similarity table in response to the contents of the reference tables of said objects, said similarity table including a plurality of records, with each record having a plurality of characteristic fields for receiving associated type characteristics and value characteristics represented by the contents of corresponding entries in said reference tables of said objects;

B. comparison means for performing a similarity function in connection with the contents of the characteristic fields in each record in said similarity table to determine the degree of similarity between type characteristics and value characteristics defined by the contents of the respective fields; and

C. similarity determination means responsive to the comparison determined by said comparison means for determining the degree of similarity between the respective objects.

10. A system as defined in claim 9 in which the reference table associated with each object has a type characteristic comprising at least one attribute identification and a value characteristic comprising an attribute value associated with each attribute identified by an attribute identification, said similarity table including a record comprising attribute identification fields for each different attribute identification for each object and a record associated with each attribute identification comprising fields for attribute values for the various objects, said comparison means operating in response to contents of said records to determine selected relationships between attribute identifications and attribute values associated with each of the respective attribute identifications.

11. A system as defined in claim 10 in which records in said similarity table further include weight value fields, said comparison means further operating in response to said weight value fields.

12. A system as defined in claim 10 in which the reference table associated with each object further has a type characteristic comprising at least one relationship identification and a value characteristic comprising a relationship object associated with each relationship identified by an relationship identification, said similarity table including a record comprising relationship identification fields for each different relationship identification for each object and a record associated with each relationship identification comprising fields for relationship objects associated with each object, said comparison means operating in response to contents of said records to determine selected relationships between relationship identifications and relationship objects associated with each of the respective relationship identifications.

13. A system as defined in claim 12 in which records in said similarity table further include weight value fields, said comparison means further operating in response to said weight value fields.

14. A system as defined in claim 12 in which the reference table associated with each object further has type characteristics comprising at least one set identification, said similarity table including a record comprising relationship identification fields for each different set identification associated with each object, said comparison means further operating in response to contents of said records to determine selected relationships between set identifications.

15. A system as defined in claim 14 in which records in said similarity table further include weight value fields, said comparison means further operating in response to said weight value fields.

16. A system as defined in claim 9 in which each record in said similarity table has an associated similarity value, said similarity determination means includes similarity value generating means for generating a similarity value comprising a similarity score in response to a comparison generated by said comparison means in connection with fields in each record and a maximum value generating means for generating a maximum similarity score in response to the similarity scores associated with all of said records.

17. A system as defined in claim 16 further comprising normalization means for generating a normalized similarity score in response to the similarity score generated by said similarity value generating means and the maximum similarity score generated by said maximum value generating means.

18. A system as defined in claim 17 further comprising iterative enabling means for iteratively enabling said similarity table means, said comparison means, said similarity determination means to iteratively operate in connection with a predetermined object and other objects, said similarity value generating means generating a similarity value in connection with each iteration, and similarity list means for establishing a similarity list for receiving, following each iteration, the identification of said other object if the similarity value has a predetermined relationship with a preselected value.

19. A system as defined in claim 9 in which each record further includes a similarity value identification field, said system further including similarity value identification field establishment means for establishing a similarity value in said similarity field in each record in response to the values in said characteristic fields and in response to the comparison operation by said comparison means.

20. A system as defined in claim 19 in which said similarity value identification field establishment means established the similarity value in each record as a function of the values in said characteristic fields.

21. A system as defined in claim 9 in which each of said objects is assigned to one of a plurality of groups, said system further comprising joint reference table establishing means for establishing a joint reference table associated with each of the groups, said similarity table means establishing a similarity table in response to the contents of the joint reference tables, said comparison means and said similarity determination means operating in response to the similarity table established by said similarity table means.

22. A system as defined in claim 21 in which

A. said joint reference table establishing means includes:

i. joint reference table means for establishing a joint reference table in response to the contents of the reference tables of said objects in a group, said joint reference table including a plurality of records, with each record having a plurality of characteristic fields for receiving associated type characteristics and value characteristics represented by the contents of corresponding entries in said reference tables of said objects, each record further including a joint reference field;

ii. joint comparison means for performing a comparison operation in connection with the contents of the characteristic fields in each record in said joint reference table to determine the degree of similarity between type characteristics and value characteristics defined by the contents of the respective fields; and

iii. joint reference table similarity determination means for establishing the contents of said joint reference field in response to the contents of the characteristic fields and to the comparison determined by said comparison means;

B. said similarity table means thereafter establishing said similarity table in response to the contents of the joint reference fields of the respective joint reference tables associated with each of said groups.

23. A system as defined in claim 22 in which the reference table associated with each object has a type characteristic comprising at least one attribute identification and a value characteristic comprising an attribute value associated with each attribute identified by an attribute identification, said joint reference table means establishing each joint reference table to include a record comprising attribute identification fields for each different attribute identification for each object and a record associated with each attribute identification comprising fields for attribute values for the various objects, said joint comparison means operating in response to contents of said records to determine selected relationships between attribute identifications and attribute values associated with each of the respective attribute identifications.

24. A system as defined in claim 23 in which the reference table associated with each object further has a type characteristic comprising at least one relationship identification and a value characteristic comprising a relationship object associated with said each relationship identified by an relationship identification, said joint reference table means establishing in said joint reference table a record comprising relationship identification fields for each different relationship identification for each object in a group and a record associated with each relationship identification comprising fields for relationship objects associated with each object in a group, said joint comparison means operating in response to contents of said records to determine selected relationships between relationship identifications and relationship objects associated with each of the respective relationship identifications.

25. A system as defined in claim 24 in which the reference table associated with each object further has type characteristics comprising at least one set identification, said joint reference table means establishing in said joint reference table a record comprising relationship identification fields for each different set identification associated with each object, said comparison means further operating in response to contents of said records to determine selected relationships between set identifications.

26. A system as defined in claim 22 in which each record in said joint reference table further includes a weight value field which contains a weighting value and a joint weight value field, said joint reference table similarity determination means including means for establishing a joint weight value for storage in said joint weight value field in response to the weight value in said weight value field and the degree of similarity as determined by said joint comparison means.

27. A system as defined in claim 22 in which each record in said similarity table has an associated similarity value, said similarity determination means includes similarity value generating means for generating a similarity value comprising a similarity score in response to a comparison generated by said comparison means in connection with fields in each record and a maximum value generating means for generating a maximum similarity score in response to the similarity scores associated with all of said records.

28. A system as defined in claim 9 in which said similarity table means establishes, in each record, a similarity field and a difference field, said similarity determination means including means responsive to said comparison means for establishing values in said similarity field and said difference field in response to the comparison performed by said similarity determination means.

29. A system as defined in claim 28 in which said similarity determination means includes similarity value generating means and difference value generating means for generating, respectively, in response to a comparison generated by said comparison means in connection with said characteristic fields in each record, a similarity value comprising a similarity score for storage in said similarity field and a difference value comprising a difference score for storage in said difference field.

30. A system as defined in claim 29 in which said similarity determination means further includes maximum value generating means for generating a maximum similarity score in response to the similarity scores and difference scores associated with all of said records.

31. A system as defined in claim 30 further comprising normalization means for generating a normalized similarity score and a normalized difference score in response to, respectively, the similarity score generated by said similarity value generating means and the difference score generated by said difference score generating means, and the maximum similarity score generated by said maximum value means.

32. A system as defined in claim 28 in which each of said objects is assigned to one of a plurality of groups, said system further comprising joint reference table establishing means for establishing a joint reference table associated with each of the groups, said similarity table means establishing a similarity table in response to the contents of the joint reference tables, said comparison means and said similarity determination means operating in response to the similarity table established by said similarity table means.

33. A system as defined in claim 32 in which

A. said joint reference table establishing means includes:

i. joint reference table means for establishing a joint reference table in response to the contents of the reference tables of said objects in a group, said joint reference table including a plurality of records, with each record having a plurality of characteristic fields for receiving associated type characteristics and value characteristics represented by the contents of corresponding entries in said reference tables of said objects, each record further including a joint similarity reference field and a joint difference reference field;

ii. joint comparison means for performing a comparison operation in connection with the contents of the characteristic fields in each record in said joint reference table to determine the degree of similarity between type characteristics and value characteristics defined by the contents of the respective fields; and

iii. joint reference table similarity determination means for establishing the contents of said joint similarity reference field and said joint difference reference field in response to the contents of the characteristic fields and to the comparison determined by said comparison means;

B. said similarity table means thereafter establishing said similarity table in response to the contents of the joint similarity reference fields and said joint difference reference fields of the respective joint reference tables associated with each of said groups.

46. A method as defined in claim 33 in which said similarity table includes, in each record, a similarity field and a difference field, said similarity determination step including steps of establishing values in said similarity field and said difference field in response to the results of said similarity degree determination step.

47. A method as defined in claim 46 in which each of said objects is assigned to one of a plurality of groups, said method further comprising the steps of establishing a joint reference table associated with each of the groups, said similarity table being established in response to the contents of the joint reference tables, similarity table so established being used during the similarity function performance step and said similarity degree determination step.

48. A method as defined in claim 47 in which

A. said joint reference table establishing step includes the steps of:

`i. establishing a joint reference table in response to the contents of the reference tables of said objects in a group, said joint reference table including a plurality of records, with each record having a plurality of characteristic fields for receiving associated type characteristics and value characteristics represented by the contents of corresponding entries in said reference tables of said objects, each record further including a joint similarity reference field and a joint difference reference field;

ii. performing a joint comparison operation in connection with the contents of the characteristic fields in each record in said joint reference table to determine the degree of similarity between type characteristics and value characteristics defined by the contents of the respective fields; and

iii. establishing the contents of said joint similarity reference field and said joint difference reference field in response to the contents of the characteristic fields and to the comparison determined by said comparison means;

B. said similarity table thereafter being established in response to the contents of the joint similarity reference fields and said joint difference reference fields of the respective joint reference tables associated with each of said groups.

34. A method of determining a selected relationship between a plurality of objects each having characteristics, including type characteristics and value characteristics, each said value characteristic representing a value associated with a type characteristic, said characteristics being defined by entries in a reference table, said system comprising:

A. establishing a similarity table in response to the contents of the reference tables of said objects, said similarity table including a plurality of records, with each record having a plurality of characteristic fields for receiving associated type characteristics and value characteristics represented by the contents of corresponding entries in said reference tables of said objects;

B. performing a similarity function in connection with the contents of the characteristic fields in each record in said similarity table to determine the degree of similarity between type characteristics and value characteristics defined by the contents of the respective fields; and

C. determining the degree of similarity between the respective objects in response to the determined degree of similarity.

35. A method as defined in claim 34, in which records in said similarity table further include weight value fields, said similarity function being further performed in response to the contents of said weight value fields.

36. A method as defined in claim 34, in which each record in said similarity table have an associated similarity value, said similarity degree determination step including a similarity value generating step for generating a similarity value comprising a similarity score in response to the determined degree of similarity.

37. A method as defined in claim 36 further comprising a maximum value generating step for generating a maximum similarity score in response to the similarity scores associated with all of said records.

38. A method as defined in claim 37 further comprising a normalization step for generating a normalized similarity score in response to the similarity score and the maximum similarity score.

39. A method as defined in claim 37 in which said similarity table establishment step, said similarity function performance step and said similarity degree determination step are performed iteratively in connection with a predetermined object and other objects, said similarity value being generated in connection with each iteration, said method further comprising a similarity list establishment step for establishing a similarity list for including, following each iteration, the identification of said other object if the similarity value has a predetermined relationship with a preselected value.

40. A method as defined in claim 34 further including a similarity value identification field establishment step for establishing a similarity value in a similarity field in each record in response to the values in said characteristic fields and in response to the similarity function performance step.

41. A method as defined in claim 40 in which the similarity value in each record is established as a function of the values in said characteristic fields.

42. A method as defined in claim 34 in which each of said objects is assigned to one of a plurality of groups, said method further including the step of establishing a joint reference table associated with each of the groups, said similarity table thereafter being established in response to the contents of the joint reference tables.

43. A method as defined in claim 42 in which

A. said joint reference table establishment step includes the steps of:

i. establishing a joint reference table in response to the contents of the reference tables of said objects in a group, said joint reference table including a plurality of records, with each record having a plurality of characteristic fields for receiving associated type characteristics and value characteristics represented by the contents of corresponding entries in said reference tables of said objects, each record further including a joint reference field;

ii. performing a comparison operation in connection with the contents of the characteristic fields in each record in said joint reference table to determine the degree of similarity between type characteristics and value characteristics defined by the contents of the respective fields; and

iii. establishing the contents of said joint reference field in response to the contents of the characteristic fields and to the comparison determined by said comparison means;

B. said similarity table thereafter being established in response to the contents of the joint reference fields of the respective joint reference tables associated with each of said groups.

44. A method as defined in claim 43 in which each record in said joint reference table further includes a weight value field which contains a weighting value and a joint weight value field, said joint reference field contents establishment step establishing a joint weight value for storage in said joint weight value field in response to the weight value in said weight value field and the degree of similarity as determined during said joint comparison step.

45. A method as defined in claim 40 in which each record in said similarity table has an associated similarity value, said similarity determination step including the step of generating a similarity score in response to the results of said similarity function in connection with fields in each record and a maximum similarity score in response to the similarity scores associated with all of said records.

49. A system for determining a selected relationship between a plurality of objects each having characteristics defined by entries in a reference table, said system comprising:

A. similarity table establishment means for establishing a similarity table in response to the contents of the reference tables of said objects, said similarity table including a plurality of records, with each record having a plurality of characteristic fields for receiving associated characteristics represented by the contents of corresponding entries in said reference tables of said objects, a similarity field and a difference field;

B. comparison means for performing a similarity function in connection with the contents of the characteristic fields in each record in said similarity table to determine the degree of similarity between characteristics defined by the contents of the respective fields; and

C. similarity determination means responsive to the comparison determined by said comparison means for determining the degree of similarity between the respective objects and for establishing the values in said similarity field and said difference field of each record in response to the comparison performed by said similarity determination means.

50. A system as defined in claim 49 in which said similarity determination means includes similarity value generating means and difference value generating means for generating, respectively, in response to a comparison generated by said comparison means in connection with said characteristic fields in each record, a similarity value comprising a similarity score for storage in said similarity field and a difference value comprising a difference score for storage in said difference field.

51. A system as defined in claim 50 in which said similarity determination means further includes maximum value generating means for generating a maximum similarity score in response to the similarity scores and difference scores associated with all of said records.

52. A system as defined in claim 51 further comprising normalization means for generating a normalized similarity score and a normalized difference score in response to, respectively, the similarity score generated by said similarity value generating means and the difference score generated by said difference score generating means, and the maximum similarity score generated by said maximum value generating means.

53. A system as defined in claim 49 in which each of said objects is assigned to one of a plurality of groups, said system further comprising joint reference table establishing means for establishing a joint reference table associated with each of the groups, said similarity table means establishing a similarity table in response to the contents of the joint reference tables, said comparison means and said similarity determination means operating in response to the similarity table established by said similarity table means.

54. A system as defined in claim 53 in which

A. said joint reference table establishing means includes:

i. joint reference table means for establishing a joint reference table in response to the contents of the reference tables of said objects in a group, said joint reference table including a plurality of records, with each record having a plurality of characteristic fields for receiving associated type characteristics and value characteristics represented by the contents of corresponding entries in said reference tables of said objects, each record further including a joint similarity reference field and a joint difference reference field;

ii. joint comparison means for performing a comparison operation in connection with the contents of the characteristic fields in each record in said joint reference table to determine the degree of similarity between type characteristics and value characteristics defined by the contents of the respective fields; and

iii. joint reference table similarity determination means for establishing the contents of said joint similarity reference field and said joint difference reference field in response to the contents of the characteristic fields and to the comparison determined by said comparison means;

B. said similarity table means thereafter establishing said similarity table in response to the contents of the joint similarity reference fields and said joint difference reference fields of the respective joint reference tables associated with each of said groups.

55. A method of determining a selected relationship between a plurality of object each having characteristics defined by entries in a reference table, said system comprising:

A. establishing a similarity table in response to the contents of the reference tables of said objects, said similarity table including a plurality of records, with each record having a plurality of characteristic fields for receiving associated characteristics represented by the contents of corresponding entries in said reference tables of said objects, a similarity field and a difference field;

B. performing a similarity function in connection with the contents of the characteristic fields in each record in said similarity table to determine the degree of similarity between characteristics defined by the contents of the respective fields; and

C. determining the degree of similarity between the respective objects and for establishing the values in said similarity field and said difference field of each record in response to the degree of similarity determined by said similarity function.

56. A method as defined in claim 55 in which said similarity determination step includes steps of generating, respectively, in response to a comparison generated by said comparison means in connection with said characteristic fields in each record, a similarity value comprising a similarity score for storage in said similarity field and a difference value comprising a difference score for storage in said difference field.

57. A method as defined in claim 56 in which said similarity determination step further includes the step of generating a maximum similarity score in response to the similarity scores and difference scores associated with all of said records.

58. A method as defined in claim 57 further comprising a normalization step for generating a normalized similarity score and a normalized difference score in response to, respectively, the similarity score and the difference score, and the maximum similarity score.

59. A method as defined n claim 55 in which each of said objects is assigned to one of a plurality of groups, said method further comprising a joint reference table establishing step for establishing a joint reference table associated with each of the groups, said similarity table means thereafter establishing a similarity table in response to the contents of the joint reference tables.

60. A method as defined in claim 59 in which

A. said joint reference table establishing step includes steps of:

i. establishing a joint reference table in response to the contents of the reference tables of said objects in a group, said joint reference table including a plurality of records, with each record having a plurality of characteristic fields, a joint similarity reference field and a joint difference reference field;

ii. performing a joint comparison operation in connection with the contents of the characteristic fields in each record in said joint reference table to determine the degree of similarity between type characteristics and value characteristics defined by the contents of the respective fields; and

iii. establishing the contents of said joint similarity reference field and said joint difference reference field in response to the contents of the characteristic fields and to the comparison determined by said comparison means;

B. said similarity table thereafter being established in response to the contents of the joint similarity reference fields and said joint difference reference fields of the respective joint reference tables associated with each of said groups.