Methods and apparatus, using expansion attributes having default, values, for matching entities and predicting an attribute of an entity

• US 6,345,264 B1
• Filed: 01/22/1998
• Issued: 02/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: Breese, John S., Kadie, Carl M.
• Primary Examiner(s): Powell, Mark
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/010,819
• Time in Patent Office: 1,475 Days
• Field of Search: 706/21, 364/468, 395/759, 707/3, 707/5, 707/6, 707/104
• US Class Current: 706/21
• 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 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) accessing the data structure;

b) manipulating, through interaction with the storage device, at least a portion of the data structure stored within the storage device to form an expanded set of attributes by extending at least one of (i) the first set of attributes to form a first extended set of attributes which includes attributes found in neither the first nor second sets of attributes, and (ii) the second set of attributes to form a second extended set of attributes which includes attributes found in neither the first nor second sets of attributes;

c) determining, in response to attribute parameters associated with the first and second entities in the expanded 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

d) 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 attributes found in neither the first set of attributes nor the second set of attributes, and (ii) the second set of attributes is extended to form the second extended set of attributes which includes attributes found in neither the first set of attributes nor the second set of attributes.

3. The method of claim 2 wherein the first and second extended sets of attributes are collectively defined as a union of (a) the first set of attributes, (b) the second set of attributes, and (c) a third set of attributes found in neither the first set of attributes nor 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 expanded 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 expanded 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 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) accessing the data structure;

b) manipulating, through interaction with the storage device, at least a portion of the data structure stored within the storage device to form an expanded set of attributes by extending the first set of attributes to include attributes found in neither the first set of attributes nor associated with at least one other entity in the group of entities;

c) 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 expanded 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

d) 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 expanded 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 and (iii) attributes found in neither the first set of attributes nor the set of attributes of every other one of the entities of the group of entities.

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 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) manipulates, through interaction with the storage device, at least a portion of the data structure stored within the storage device to form an expanded set of attributes by extending at least one of (i) the first set of attributes to form a first extended set of attributes which includes attributes found in neither the first nor second sets of attributes, and (ii) the second set of attributes to form a second extended set of attributes which includes attributes found in neither the first nor second sets of attributes;

b) determines, in response to attribute parameters associated with the first and second entities in the expanded 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

c) 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 attributes found in neither the first set of attributes nor the second set of attributes, and (ii) the second set of attributes is extended to form the second extended set of attributes which includes attributes found in neither the first set of attributes nor the second set of attributes.

28. The apparatus of claim 27 wherein the first and second extended sets of attributes are collectively defined as a union of (i) the first set of attributes, (ii) the second set of attributes, and (iii) attributes found in neither the first set of attributes nor 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 each of the first and second entities are selected from a group consisting of (A) a computer, B) a computer user, (C) a local area computer network, D) an association, E) a network browser, and F) an internetwork browser.

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

32. 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 has 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) manipulates, through interaction with the storage device, at least a portion of the data structure stored within the storage device to form an expanded set of attributes by extending the first set of attributes to include attributes found in neither the first set of attributes nor associated with at least one other entity in the group of entities;

b) 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 expanded 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

c) 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.

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

34. The apparatus of claim 32 wherein the expanded 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 and (iii) attributes found in neither the first set of attributes not the set of attributes of every other one of the entities of the group of entities.

35. The apparatus of claim 32 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.