Method and system for revealing information structures in collections of data items

• US 5,778,362 A
• Filed: 06/21/1996
• Issued: 07/07/1998
• Est. Priority Date: 06/21/1996
• Status: Expired due to Fees

• Current Assignee: KDL Technologies Limited
• Original Assignee: KDL Technologies Limited
• Inventors: Deerwester, Scott
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/667,520
• Time in Patent Office: 746 Days
• Field of Search: 707/3, 707/5, 707/6, 704/7, 704/9, 395/20
• US Class Current: 1/1
• CPC Class Codes: G06F 16/33 Querying
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

In analyzing a collection of data items to determine data structures, the collection of data items is treated as a two-dimensional map. A query vector with elements of interest is composed with the map to form a result vector. A profile vector formed from the matrix is combined with the result vector to form a discrimination vector representing the degree of expectation that the elements of the query vector related to the map.

Claims

1. A method for retrieving information from a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associated with another of the items in the collection, the method comprising the steps, carried out by a data processor, of:

presenting the collection as a map of tuples of item identifiers, attribute identifiers, and scalar values;

forming a query vector having pairs of attribute identifiers and scalar values; and

composing the query vector and the map to produce a result vector having pairs of item identifiers and corresponding scalar values, the scalar values representing the relationship of the query vector and the map for the items having the corresponding item values.

2. A method for retrieving information from a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associated with another of the items in the collection, the method comprising the steps, carried out by a data processor, of:

presenting the collection as a map of tuples of item identifiers, attribute identifiers, and scalar values;

forming a query vector having pairs of attribute identifiers and scalar values;

composing the query vector and the map to produce a result vector having pairs of item identifiers and corresponding scalar values, the scalar values representing the relationship of the query vector and the map for the items having the corresponding item values;

reducing the map into a profile vector having pairs of item identifiers and corresponding scalar values, the scalar values each representing a global scalar value over all of the attributes in the map for the item having the item identifier corresponding to that scalar value; and

forming a discrimination vector from the result vector and profile vector by comparing the scalar values in the result vector and profile vector corresponding to the same item identifiers in the profile and result vectors.

3. A method for comparing information from a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associated with another of the items in the collection, the method comprising the steps, carried out by a data processor, of:

presenting the collection as a first map of tuples of item identifiers, attribute identifiers, and scalar values;

forming a query vector having pairs of attribute identifiers and scalar values;

composing the query vector and the first map to produce a first result vector having pairs of item identifiers and corresponding scalar values, the scalar values representing the relationship of the query vector and the first map for the items having the corresponding item values;

reducing the first map into a first profile vector having pairs of item identifiers and corresponding scalar values, the scalar values each representing a first global scalar value over all of the attributes in the first map for the item having the item identifier corresponding to that scalar value;

forming a first discrimination vector from the result and profile vectors by comparing the scalar values in the result vector and profile vector corresponding to the same item identifiers in the profile and result vectors;

presenting the collection as a second map of tuples of item identifiers, attribute identifiers, and scalar values, wherein the attribute identifiers of the second map are the item identifiers of the first map; and

composing the discrimination vector and the second map to produce a second result vector having pairs of item identifiers and corresponding scalar values, the scalar values representing the relationship between the items of the first and second maps.

4. A method for analyzing the relationship of an input item and a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associated with another of the items in the collection, the method comprising the steps, carried out by a data processor, of:

presenting the collection as a map of tuples of item identifiers, attribute identifiers, and scalar values;

forming query vectors each having pairs of attribute identifiers and scalar values;

composing the query vectors and the map to produce a set of result vectors for each of the items in the map, the result vectors comprising pairs of item identifiers and corresponding scalar values, and the scalar values representing the relationship of the query vectors and the map for the items having the corresponding item values;

reducing the map into a profile vector having pairs of item identifiers and corresponding scalar values, the scalar values each representing a first global scalar value over all of the attributes in the map for the item having the item identifier corresponding to that scalar value;

forming a set of item discrimination vectors from the profile vector and each of the normalized result vectors in the set by comparing the scalar values in the normalized result vectors and the profile vectors corresponding to the same item identifiers in the profile and result vectors;

forming a discrimination matrix from the set of item discrimination vectors;

forming an attribute vector corresponding to the input item;

forming an attribute discrimination vector from the attribute and profile vectors; and

comparing the attribute discrimination vector and each discrimination vector in the discrimination matrix to determine a relationship between the input item and the collection.

5. A method for analyzing a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associates with another of the items in the collection, the method comprising the steps, carried out by a data processor, of:

presenting the collection as a map of tuples of item identifiers, attribute identifiers, and scalar values;

forming query vectors each having pairs of attribute identifiers and scalar values;

composing the query vectors and the map to produce a set of result vectors for each of the items in the map, the result vectors having pairs of item identifiers and corresponding scalar values, and the scalar values representing the relationship of the first query vector and the first map for the items having the corresponding item values;

reducing the map into a profile vector having pairs of item identifiers and corresponding scalar values, the scalar values each representing a first global scalar value over all of the attributes in the first map for the item having the item identifier corresponding to that scalar value;

forming a set of item discrimination vectors from the profile vector and each of the normalized result vectors in the set by comparing the scalar values in the normalized result vectors and the profile vectors corresponding to the same item identifiers in the profile and result vectors;

forming a discrimination matrix from the set of item discrimination vectors; and

comparing each of the discrimination vectors in the discrimination matrix with the other ones of the discrimination vectors in the discrimination matrix to produce a similarity metric for each pair of discrimination vectors, the similarity metric for each of the pairs of discrimination vectors indicating the similarity of the corresponding items.

6. The method of claim 5 wherein the step of comparing discrimination vectors includes the substep of

forming dot products of pairs of discrimination vectors.

7. The method of claim 5 wherein the step of comparing discrimination vectors includes the substep of

forming cosine products of pairs of discrimination vectors.

8. A method for organizing a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associates with another of the items in the collection, the method comprising the steps, carried out by a data processor, of

presenting the collection as a map of tuples of item identifiers, attribute identifiers, and scalar values;

forming query vectors each having pairs of attribute identifiers and scalar values;

composing the query vectors and the map to produce a set of result vectors for each of the items in the map, the result vectors having pairs of item identifiers and corresponding scalar values, and the scalar values representing the relationship of the first query vector and the first map for the items having the corresponding item values;

reducing the map into a profile vector having pairs of item identifiers and corresponding scalar values, the scalar values each representing a first global scalar value over all of the attributes in the first map for the item having the item identifier corresponding to that scalar value;

forming a set of item discrimination vectors from the profile vector and each of the normalized result vectors in the set by comparing the scalar values in the normalized result vectors and the profile vectors corresponding to the same item identifiers in the profile and result vectors;

forming a discrimination matrix from the set of item discrimination vectors;

comparing each of the discrimination vectors in the discrimination matrix with the other ones of the discrimination vectors in the discrimination matrix to produce a similarity metric for each pair of discrimination vectors, the similarity metric for each of the pairs of discrimination vectors indicating the similarity of the corresponding items;

forming a similarity matrix from the similarity metrics; and

using the similarity matrix as an input to a multivariant statistical analysis package.

9. A method for determining characteristics in a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associates with another of the items in the collection, the method comprising the steps, carried out by a data processor, of:

presenting the collection as a first map of tuples of item identifiers, attribute identifiers, and scalar values;

presenting the collection as a second map of tuples of item identifiers, attribute identifiers, and scalar values, wherein the attribute identifiers of the second map are the item identifiers of the first map and the item identifiers of the second map are the attribute identifiers of the first map;

reducing the first map into a first profile vector having pairs of item identifiers and corresponding scalar values, the scalar values each representing a first global scalar value over all of the attributes in the first map for the item having the item identifier corresponding to that scalar value; and

analyzing the relationship of each item having an identifier in the first map, the analyzing step including the substeps, for each of the items of

forming a query vector having pairs of attribute identifiers and scalar values,

composing the query vector and the second map to produce a first result vector having pairs of item identifiers and corresponding scalar values, the scalar values representing the relationship of the first query vector and the first map for the items having the corresponding item values,

forming a discrimination vector from the first result and profile vectors by comparing the scalar values in the result vectors and profile vectors corresponding to the same item identifiers in the profile and result vectors,

composing the discrimination vector and the first map to produce a second result vector,

continuing the composing step and the discrimination forming steps with the second result vector as the query vector if the similarity between the query vector and the second result vector is below a first predetermined threshold, and

adding the tuple of the query vector and the discrimination vector to a list of stored tuples if the similarity between the query vector and the second result vector exceeds the first predetermined threshold and the similarity between the discrimination vector and other discrimination vectors in the stored tuples is below a second predetermined threshold.

10. A computer system for deriving structure from sets of information, the computer system comprising:

an agent coupled to the set of information to retrieve tuples of information from the sets;

a kernel, coupled to the agent, for deriving structure from the tuples of information received from the agents, the kernel including

means for forming the tuples of information into a map of item identifiers, attribute identifiers, and scalar values,

means for forming a query vector from a user input, the query vector having pairs of attribute identifiers and scalar values, and

means for composing the query vector and the map to produce a result vector having pairs of item identifiers and corresponding scalar values; and

a front end unit, coupled to the kernel, for receiving the user input.

11. The computer system of claim 10, further including a plurality of agents each coupled to a different set of information.

12. A system for retrieving information from a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associated with another of the items in the collection, comprising:

means for presenting the collection as a map of tuples of item identifiers, attribute identifiers, and scalar values;

means for forming a query vector having pairs of attribute identifiers and scalar values; and

means for composing the query vector and the map to produce a result vector having pairs of item identifiers and corresponding scalar values, the scalar values representing the relationship of the query vector and the map for the items having the corresponding item values.

13. A system for retrieving information from a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associated with another of the items in the collection, comprising:

means for presenting the collection as a map of tuples of item identifiers, attribute identifiers, and scalar values;

means for forming a query vector having pairs of attribute identifiers and scalar values;

means for composing the query vector and the map to produce a result vector having pairs of item identifiers and corresponding scalar values, the scalar values representing the relationship of the query vector and the map for the items having the corresponding item values;

means for reducing the map into a profile vector having pairs of item identifiers and corresponding scalar values, the scalar values each representing a global scalar value over all of the attributes in the map for the item having the item identifier corresponding to that scalar value; and

means for forming a discrimination vector from the result vector and profile vector by comparing the scalar values in the result vector and profile vector corresponding to the same item identifiers in the profile and results vectors.

14. An article of manufacture for causing a computer to derive structure from sets of information, comprising:

means, coupled to the set of information, for causing a computer to retrieve tuples of information from the sets;

means, coupled to the agent, for causing a computer to derive structure from the tuples of information received from the agents, including

means for causing a computer to form the tuples of information into a map of item identifiers, attribute identifiers, and scalar values,

means for causing a computer to form a query vector from a user input, the query vector having pairs of attribute identifiers and scalar values, and

means for causing a computer to compose the query vector and the map to produce a result vector having pairs of item identifiers and corresponding scalar values; and

means, coupled to the kernel, for causing a computer to receive the user input.

15. An article of manufacture for causing a computer to retrieve information from a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associated with another of the items in the collection, comprising:

means for causing a computer to present the collection as a map of tuples of item identifiers, attribute identifiers, and scalar values;

means for causing a computer to form a query vector having pairs of attribute identifiers and scalar values; and

means for causing a computer to compose the query vector and the map to produce a result vector having pairs of item identifiers and corresponding scalar values, the scalar values representing the relationship of the query vector and the map for the items having the corresponding item values.

16. An article of manufacture for causing a computer to retrieve information from a collection of items each having a corresponding item identifier and each being associated by a scalar value with an attribute having a corresponding attribute identifier, at least one of the attributes also being associated with another of the items in the collection, the method comprising:

means for causing a computer to present the collection as a map of tuples of item identifiers, attribute identifiers, and scalar values;

means for causing a computer to form a query vector having pairs of attribute identifiers and scalar values;

means for causing a computer to compose the query vector and the map to produce a result vector having pairs of item identifiers and corresponding scalar values, the scalar values representing the relationship of the query vector and the map for the items having the corresponding item values;

means for causing a computer to reduce the map into a profile vector having pairs of item identifiers and corresponding scalar values, the scalar values each representing a global scalar value over all of the attributes in the map for the item having the item identifier corresponding to that scalar value; and

means for causing a computer to form a discrimination vector from the result vector and profile vector by comparing the scalar values in the result vector and profile vector corresponding to the same item identifiers in the profile and result vectors.