System and method for searching databases with applications such as peer groups, collaborative filtering, and e-commerce

• US 6,236,985 B1
• Filed: 10/07/1998
• Issued: 05/22/2001
• Est. Priority Date: 10/07/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip Shi-Lung, Wolf, Joel Leonard, Aggarwal, Charu Chandra
• Primary Examiner(s): Alam, Hosain T.
• Application Number:
  US09/168,117
• Time in Patent Office: 958 Days
• Field of Search: 707/5, 707/1-4, 707/6, 707/100, 707/102, 707/104, 705/37, 705/36, 705/38, 705/10, 705/7, 706/45, 706/46
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method of analyzing information in the form of a plurality of data records. Each data record includes one or more data values. The data values are partitioned into a plurality of data signatures. Data values of data signatures are compared to data values of data records. Based on the result of the comparison an index is associated with each data record. A bound corresponding to the index is calculated based on a user defined target value and an objective function. If desired, information may be analyzed for finding peer groups in e-commerce applications.

Claims

1. A method of analyzing information in the form of a plurality of data records, each data record including at least one data value of a plurality of data values, said method comprising the steps of:

(a) partitioning the plurality of data values into a plurality of data signatures;

(b) comparing ones of the plurality of data signatures to a data record of the plurality of data records;

(c) associating an index with the data record based on the result of step (b); and

(d) calculating a bound corresponding to the index and based on a user defined target value and an objective function.

2. The method according to claim 1, wherein the objective function is a function of a match number and a hamming distance.

3. The method according to claim 1, wherein the index is a Boolean index.

4. The method according to claim 1, wherein the step of partitioning the plurality of data values, further comprises the steps of:

calculating a distance between a first data value of the plurality of data values and a second data value of the plurality of data values; and

detecting a plurality of clusters of ones of the plurality of data values based on the distance.

5. The method according to claim 1, wherein

steps (b)-(c) are repeated until each respective data record of the plurality of data records is associated with a respective index of a plurality of indices, and

step (d) is repeated until a respective bound corresponding to each respective index of the plurality of indices is calculated.

6. The method according to claim 5, further comprising the steps of:

(a) sorting respective ones of the plurality of indices based on the respective bound;

(b) searching ones of the plurality of data records based on sorted ones of the plurality of indices; and

(c) detecting at least one of the plurality of data records that is comparable to the user defined target value based on the objective function.

7. A method of analyzing information in the form of a plurality of data records, each data record including at least one data value of a plurality of data values, said method comprising the steps of:

(a) partitioning the plurality of data values into a plurality of data signatures;

(b) comparing ones of the plurality of data signatures to a data record of the plurality of data records;

(c) associating an index with the data record based on the result of step (b); and

(d) calculating a bound corresponding to the index and based on at least one of a plurality of user defined target values and an objective function.

8. The method according to claim 7, wherein the index is a Boolean index.

9. The method according to claim 7, further comprising the steps of:

(e) repeating steps (b)-(c) until each respective data record of the plurality of data records is associated with a respective index of a plurality of indices; and

(f) repeating step (d) until a respective bound corresponding to each respective index of the plurality of indices is calculated.

10. The method according to claim 9, further comprising the steps of:

(g) sorting respective ones of the plurality of indices based on the respective bound;

(h) searching ones of the plurality of data records based on sorted ones of the plurality of indices; and

(i) detecting at least one of the plurality of data records that is comparable to at least one of the plurality of user defined target values based on the objective function.

11. The method according to claim 10, wherein the objective function is chosen by the user.

12. The method according to claim 10, wherein each of the plurality of data records is obtained by measuring physical attributes of a plurality of objects.

13. The method according to claim 10, wherein an interactively defined number L of the plurality of data records that are comparable to m user defined target values of the plurality of user defined target values are detected.

14. The method according to claim 13, wherein the plurality of data values represent a plurality of items for sale, the plurality of data records are a plurality of transaction records associated with a plurality of customers, and the L data records detected are L transaction records of the plurality of transaction records, the L transaction records comprising a peer group of the m user defined target values.

15. The method according to claim 14, wherein ones of the plurality of items for sale are provided to a customer based on an intersection between a promotion list and ones of the plurality of items for sale of ones of the L transaction records of the peer group.

16. The method according to claim 15, further comprising the steps of:

(j) comparing a total number of the ones of the plurality of items for sale provided to the customer with a given value r;

(k) repeating steps (h)-(i) to detect L′

<

L transaction records comprising the peer group of the m user defined target values, if the total number of the ones of the plurality of items for sale provided to the customer is greater than r; and

(l) repeating steps (h)-(i) to detect L′

>

L transaction records comprising the peer group of the m user defined target values, if the total number of the ones of the plurality of items for sale provided to the customer is smaller than r.

17. The method according to claim 10, wherein the objective function is interactively specified by a user.

18. The method according to claim 17, wherein the objective function is interactively specified for each repetition of steps (d)-(i).

19. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for analyzing information in the form of a plurality of data records, each data record including at least one data value of a plurality of data values, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

(a) partitioning the plurality of data values into a plurality of data signatures;

(b) comparing ones of the plurality of data signatures to a data record of the plurality of data records;

(c) associating an index with the data record based on the result of step (b); and

(d) calculating a bound corresponding to the index and based on a user defined target value and an objective function.

20. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for analyzing information in the form of a plurality of data records, each data record including at least one data value of a plurality of data values, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

(a) partitioning the plurality of data values into a plurality of data signatures;

(b) comparing ones of the plurality of data signatures to a data record of the plurality of data records;

(c) associating an index with the data record based on the result of step (b); and

(d) calculating a bound corresponding to the index and based on at least one of a plurality of user defined target values and an objective function.

21. An article of manufacture as recited in claim 20, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect:

(e) repeating steps (b)-(c) until each respective data record of the plurality of data records is associated with a respective index of a plurality of indices; and

(f) repeating step (d) until a respective bound corresponding to each respective index of the plurality of indices is calculated.

22. An article of manufacture as recited in claim 21, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect:

(g) sorting respective ones of the plurality of indices based on the respective bound;

(h) searching ones of the plurality of data records based on sorted ones of the plurality of indices; and

(i) detecting at least one of the plurality of data records that is comparable to at least one of the plurality of user defined target values based on the objective function.

23. An article of manufacture as recited in claim 22, wherein an interactively defined number L of the plurality of data records that are comparable to m user defined target values of the plurality of user defined target values are detected.

24. An article of manufacture as recited in claim 23, wherein the plurality of data values represent a plurality of items for sale, the plurality of data records are a plurality of transaction records associated with a plurality of customers, and the L data records detected are L transaction records of the plurality of transaction records, the L transaction records comprising a peer group of the m user defined target values.

25. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing an analysis of information in the form of a plurality of data records, each data record including at least one data value of a plurality of data values, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

(a) partitioning the plurality of data values into a plurality of data signatures;

(b) comparing ones of the plurality of data signatures to a data record of the plurality of data records;

(c) associating an index with the data record based on the result of step (b); and

(d) calculating a bound corresponding to the index and based on a user defined target value and an objective function.

26. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing an analysis of information in the form of a plurality of data records, each data record including at least one data value of a plurality of data values, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

(a) partitioning the plurality of data values into a plurality of data signatures;

(b) comparing ones of the plurality of data signatures to a data record of the plurality of data records;

(c) associating an index with the data record based on the result of step (b); and

(d) calculating a bound corresponding to the index and based on at least one of a plurality of user defined target values and an objective function.

27. A method of searching a computer database for at least one of a plurality of data records that is comparable to a user defined target value, each data record including at least one data value of a plurality of data values, said method comprising the steps of:

(a) partitioning the plurality of data values into a plurality of data signatures;

(b) comparing ones of the plurality of data signatures to a data record of the plurality of data records;

(c) associating an index with the data record based on the result of step (b);

(d) calculating a bound corresponding to the index and based on the user defined target value and an objective function;

(e) repeating steps (b)-(c) until each respective data record of the plurality of data records is associated with a respective index of a plurality of indices;

(f) repeating step (d) until a respective bound corresponding to each respective index of the plurality of indices is calculated;

(g) sorting respective ones of the plurality of indices based on the respective bound;

(h) searching ones of the plurality of data records based on sorted ones of the plurality of indices; and

(i) detecting said at least one of the plurality of data records that is comparable to the user defined target value based on the objective function.

28. A method of searching a computer database according to claim 27, wherein the plurality of data records are stored on a server computer, and the user defined target value is provided by a client computer.

29. The method of searching a computer database of claim 28, wherein the plurality of data records which are stored on the server computer and said at least one data value included in each data record are collected from the client computer.