Method and apparatus, using attribute set harmonization and default attribute values, for matching entities and predicting an attribute of an entity

• US 6,353,813 B1
• Filed: 01/22/1998
• Issued: 03/05/2002
• Est. Priority Date: 01/22/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kadie, Carl M., Breese, John S.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/010,818
• Time in Patent Office: 1,503 Days
• Field of Search: 706/12, 395/759, 364/468, 707/3, 707/5, 707/6, 707/104
• US Class Current: 706/12
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• 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/99945 Object-oriented database structure processing

Abstract

Matching (e.g., via correlation or similarity process) entities having attributes, some of which have associated values. The values of the attributes may be adjusted based on number of entities that have values for a particular attribute so that the values decrease as the number increases. The attributes of the entities may be harmonized and provided with default values so that entities being matched have common attributes defined by the union of the attributes of the entities being matched. The attributes of the entities may be expanded and provided with default values so that the entities being matched have attributes that neither had originally. Match values may be normalized to provide a weight value which may be used to predict an attribute value of a new entity based on known attribute values of known entities. The weight values may be tuned such that relatively high weights are amplified and relatively low weights are suppressed.

Claims

1. A method for use in computer-implemented apparatus for providing an indication that specifies a degree to which (i) a first entity having a first set of attributes and (ii) a second entity having a second set of attributes match each other, each of said first and second entities having at least one corresponding computer user, each of said sets of attributes reflecting predefined characteristics of an associated one of the entities, wherein the apparatus has a processor, a storage device, connected to the processor and storing both computer executable instructions and a data structure therein, the data structure storing both a corresponding parameter defining each of said entities and a set of attribute parameters for a corresponding set of the attributes associated with said each entity, wherein the method, performed by the processor in response to execution of the instructions implements a collaborative filter match engine, comprises the steps of:

a) receiving, on a signal bearing medium, data, for use by the collaborative filter match engine, which includes the parameters defining the first and second entities and the set of attribute parameters for each of the first and second sets of attributes;

b) storing the data in the data structure;

c) manipulating, through interaction with the storage device, at least a portion of the data structure stored within the storage device to form a harmonized set of common attributes by extending at least one of (i) the first set of attributes to form a first extended set of attributes which includes all attributes of the second set of attributes, and (ii) the second set of attributes to form a second extended set of attributes which includes all attributes of the first set of attributes;

d) determining, in response to attribute parameters associated with the first and second entities in the harmonized set of attributes stored within the data structure, a degree to which the first and second entities, at least one of which having a corresponding extended set of attributes, match; and

e) generating the indication, as output, that specifies the degree of match.

2. The method of claim 1 wherein both (i) the first set of attributes is extended to form the first extended set of attributes which includes all attributes of the second set of attributes, and (ii) the second set of attributes is extended to form the second extended set of attributes which includes all attributes of the first set of attributes.

3. The method of claim 2 wherein the first and second extended sets of attributes are defined as a union of the first set of attributes and the second set of attributes.

4. The method of claim 3 wherein at least some of the attribute parameters associated with the first set of attributes have associated values and at least some of the attribute parameters associated with the second set of attributes have associated values.

5. The method of claim 4 further comprising a step of:

assigning, with the machine, a default value to any of said attribute parameters not having an associated value, wherein the step of assigning a default value is performed before the step of determining the degree to which the first and second entities match.

6. The method of claim 2 wherein at least some of the attribute parameters associated with the first set of attributes have associated values and at least some of the attribute parameters associated with the second set of attributes have associated values.

7. The method of claim 6 further comprising a step of:

assigning, with the machine, a default value to any of said attribute parameters not having an associated value, wherein the step of assigning a default value is performed before the step of determining the degree to which the first and second entities match.

8. The method of claim 1 wherein at least some of the attribute parameters associated with the first set of attributes have associated values and at least some of the attribute parameters associated with the second set of attributes have associated values.

9. The method of claim 8 further comprising a step of:

assigning, with the machine, a default value to any of said attribute parameters not having an associated value, wherein the step of assigning a default value is performed before the step of determining the degree to which the first and second entities match.

10. The method of claim 1 wherein the step of determining a degree to which the first and second entities match is performed by correlating the attribute parameters associated with the first and second entities and contained in the harmonized set.

11. The method of claim 1 wherein the step of determining a degree to which the first and second entities match is performed by determining a similarity between the attribute parameters associated with the first and second entities and contained in the harmonized set.

12. The method of claim 1 further comprising a step of:

determining, with the machine, a weight based on the degree to which the first and second entities match.

13. The method of claim 12 wherein the weight determined is a normalized value of the degree to which the first and second entities match.

14. A computer-readable medium having computer executable instructions stored therein, said instructions being executed by a computer for performing the steps of claim 1.

15. A method for use in computer-implemented apparatus for predicting a value of an attribute of an entity, having a first set of attributes, based on values of attributes associated with a group of entities, each of the entities of the group being at least one corresponding computer user and having has a corresponding set of said attributes which reflect predefined characteristics thereof, the apparatus having a processor, and a storage device, connected to the processor and storing both computer executable instructions and a data structure therein, the data structure storing, for each one of said entities, both a corresponding parameter defining said each one entity and attribute values associated with said each one entity, wherein the method comprises the steps, performed by the processor in response to execution of the instructions, of:

a) receiving, on a signal bearing medium, data which includes the parameter defining each one of the entities and the attribute values for said each one entity;

b) storing the data in the data structure;

c) manipulating, through interaction with the storage device, at least a portion of the data structure stored within the storage device to form a harmonized set of common attributes by extending the first set of attributes to include all attributes associated with at least one other entity in the group of entities;

d) determining, for each one of the entities in the group other than the first entity and in response to values of the attributes, in the harmonized set, associated with the first entity and said each one of the other entities, a degree to which the first entity matches said each one of the other entities; and

e) predicting the value of one of the attributes associated with the first entity based on a sum, taken over the attribute values associated with all of said entities in the group, of a function of (i) a value of each of the attributes associated with each one of the other entities, and (ii) a degree to which the first entity matches said each one of the other entities.

16. The method of claim 15 wherein the function is a product.

17. The method of claim 16 further comprising the step of:

assigning a default value to any of the attributes not having an associated value before determining the degree to which the first entity and said each one of the other entities match.

18. The method of claim 15 wherein the harmonized set of attributes is defined by a union of (i) the first set of attributes for the first entity and (ii) the set of attributes of every other one of the entities of the group.

19. The method of claim 18 further comprising the step of:

assigning a default value to any of the attributes not having an associated value before determining the degree to which the first entity and said each one of the other entities match.

20. The method of claim 15 further comprising the step of:

assigning a default value to any of the attributes not having an associated value before determining the degree to which the first entity and said each one of the other entities match.

21. The method of claim 15 wherein the step of determining the degree to which the first entity and each other one of the entities match is performed by correlating the attribute values associated with the first entity with the attribute values associated with said each other one of the entities.

22. The method of claim 15 wherein the step of determining the degree to which the first entity and each other one of the entities match is performed by determining similarity between the attribute values associated with the first entity and the attribute values associated with said each other one of the entities.

23. The method of claim 15 further comprising the step of:

for each of said entities in the group, determining a weight based on the degree to which the first entity and said each other one of the entities match, wherein the weight determining step is performed before predicting the value of one of the attributes of the first entity.

24. The method of claim 23 wherein, for each other one of said entities, the weight associated therewith is a normalized value of the degree to which the first entity and said each other one of the entities match.

25. A computer-readable medium having computer executable instructions stored therein, said instructions being executed by a computer for performing the steps of claim 15.

26. Computer-implemented apparatus for providing an indication that specifies a degree to which (i) a first entity having a first set of attributes and (ii) a second entity having a second set of attributes match each other, each of said first and second entities being at least one corresponding computer user, each of said sets of attributes reflecting predefined characteristics of an associated one of the entities, the apparatus comprising:

a processor; and

a storage device, connected to the processor and storing both computer executable instructions and a data structure therein, the data structure storing both a corresponding parameter defining each of said entities and a set of attribute parameters for a corresponding set of the attributes associated with said each entity;

wherein the processor, in response to execution of the instructions implements a collaborative filter match engine which;

a) receives, on a signal bearing medium, data, for use by the collaborative filter match engine, which includes the parameters defining the first and second entities and the set of attribute parameters for each one of the first and second sets of attributes;

b) stores the data in the data structure;

c) manipulates, through interaction with the storage device, at least a portion of the data structure stored within the storage device to form a harmonized set of common attributes by extending at least one of (i) the first set of attributes to form a first extended set of attributes which includes all attributes of the second set of attributes, and (ii) the second set of attributes to form a second extended set of attributes which includes all attributes of the first set of attributes;

d) determines, in response to attribute parameters associated with the first and second entities in the harmonized set of attributes stored within the data structure, a degree to which the first and second entities, at least one of which having a corresponding extended set of attributes, match; and

e) generates the indication, as output, that specifies the degree of match.

27. The apparatus of claim 26 wherein both (i) the first set of attributes is extended to form the first extended set of attributes which includes all attributes of the second set of attributes, and (ii) the second set of attributes is extended to form the second extended set of attributes which includes all attributes of the first set of attributes.

28. The apparatus of claim 27 wherein the first and second extended sets of attributes are defined as a union of the first set of attributes and the second set of attributes.

29. The apparatus of claim 26 wherein at least some of the attribute parameters associated with the first set of attributes have associated values and at least some of the attribute parameters associated with the second set of attributes have associated values;

and

wherein the processor, in response to the stored instructions, assigns a default value to any of the attribute parameters not having an associated value, before determining the degree to which the first and second entities match.

30. The apparatus of claim 26 wherein at least one of the attributes identifies content which may be requested by the first and second entities.

31. Computer-implemented apparatus for predicting a value of an attribute of an entity, having a first set of attributes, based on values of attributes associated with a group of entities, each of the entities of the group being at least one corresponding computer user and having a corresponding set of said attributes which reflect predefined characteristics thereof, the apparatus comprising:

a processor; and

a storage device, connected to the processor and storing both computer executable instructions and a data structure therein, the data structure storing, for each one of said entities, both a corresponding parameter defining said each one entity and attribute values associated with said each one entity;

wherein the processor, in response to execution of the instructions;

a) receives, on a signal bearing medium, data which includes the parameter defining each one of the entities and attribute values for said each one entity;

b) stores the data in the data structure;

c) manipulates, through interaction with the storage device, at least a portion of the data structure stored within the storage device to form a harmonized set of common attributes by extending the first set of attributes to include all attributes associated with at least one other entity in the group of entities;

d) determines, for each one of the entities in the group other than the first entity and in response to values of the attributes, in the harmonized set, associated with the first entity and said each one of the other entities, a degree to which the first entity matches said each one of the other entities; and

e) predicts the value of one of the attributes associated with the first entity based on a sum, taken over the attribute values associated with all of said entities in the group, of a function of (i) a value of each of the attributes associated with each one of the other entities, and (ii) a degree to which the first entity matches said each one of the other entities.

32. The apparatus of claim 31 wherein the function is a product.

33. The apparatus of claim 31 wherein the harmonized set of attributes is defined by a union of (i) the first set of attributes and (ii) the set of attributes of every other one of the entities of the group.

34. The apparatus of claim 31 wherein the processor, in response to execution of the instructions:

assigns a default value to any of the attributes not having an associated value, before determining the degree to which the first entity and said each one of the other entities match.