Computation of frequent data values

• US 20030167275A1
• Filed: 02/25/2003
• Published: 09/04/2003
• Est. Priority Date: 03/01/2002
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rjaibi, Walid
• Application Number:
  US10/374,548
• Publication Number:
  US 20030167275A1
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

Computing frequent value statistics, such as the top most frequent values in a data column, in a database management system. In one aspect, a list is generated of at least N data values obtained from a data set that comprises data values and associated counts, where the counts are representative of the frequency of occurrence of each data value. For a selected data value, the associated count is compared with a threshold and if the count is greater than the threshold, and the list has N data values, the least frequently occurring data value and associated count in the list are replaced with the selected data value and associated count, and the threshold is modified.

Claims

1. A method for generating a list of at least N frequent data values obtained from a data set comprising a plurality of data values and associated counts representative of frequencies of occurrence of said data values, the method comprising:

(a) comparing the associated count of a selected data value with a threshold; and

(b) if said count is greater than said threshold and said list comprises N data values, replacing the least frequently occurring data value and associated count in said list with said selected data value and associated count, and modifying said threshold.

2. The method of claim 1 wherein if said count is greater than said threshold and said list comprises less than N data values, further comprising the step of inserting said selected data value and associated count into said list.

3. The method of claim 2, wherein modifying said threshold includes copying said count associated with said least frequently occurring data value in said list to said threshold.

4. The method of claim 2, wherein said replacing the least frequently occurring data value and associated count with the selected data value and associated count is performed if the selected data value is not already in said list.

5. The method of claim 3 wherein said selected data value is selected from at least one of:

a database system, and a flat file.

6. The method of claim 1, wherein said method is contained in a database management system.

7. The method of claim 1 wherein said list is used by a query optimization component of a database management system.

8. A method for generating a list of frequent data values obtained from a data set, said data set comprising data values and associated counts, said counts representative of the frequency of occurrence of each said data value in said data set, the method comprising:

(a) comparing said count associated with a selected data value with a threshold; and

(b) if said count is greater than said threshold and said list is full, replacing the most frequently occurring data value and associated count in said list with said selected data value and associated count, and obtaining a new threshold to replace said threshold.

9. The method of claim 8 wherein if said count is less than said threshold and said list is not full, further comprising the step of inserting said selected data value and associated count into said list.

10. The method of claim 9, wherein obtaining a new threshold includes copying said count associated with said most frequent value in said list as said new threshold.

12. The method of claim 10 wherein all the data values in the set of data values are obtained and processed in the method.

13. The method of claim 10, wherein obtaining a new threshold value includes copying said count associated with said least frequent data value in said list to said threshold value.

11. A method for determining the frequency of data values in a set of data values comprising:

(a) obtaining a data value from among data values in a set of data values;

(b) mapping the obtained data value to a position in an array of counts and incrementing a count value associated with the position;

(c) obtaining the next data value if the count value associated with the obtained data value is less than or equal to a threshold value; and

(d) if the associated count value is greater than the threshold value;

(i) if a list of most frequent values is not full, writing the obtained data value and associated count value to the list, and if the list is now full, obtaining a new threshold value;

(ii) if the list of most frequent values is full;

(A) copying the associated count value of the selected data value to the count value associated with a matching data value found in the list, and if the selected data value is not already in the list, replacing the least frequent data value and associated count value in the list with the selected data value and associated count value; and

(B) obtaining a new threshold value;

(iii) obtaining the next data value and returning to step (b).

14. A computer system comprising:

means for selecting a data value and comparing a count associated with said selected unique data value with a threshold;

means for inserting said selected data value and associated count into a list if said count is greater than said threshold and said list is not full;

means for replacing the least frequently occurring data value and associated count in said list with said selected data value and associated count if said count is greater than said threshold, and said list is full; and

means for modifying said threshold.

15. The computer system of claim 14, wherein the means for modifying said threshold further comprises:

means for copying said count associated with said least frequent value in said list to said threshold when said list is full and the least frequent value in said list was updated by said selected data value.

16. The computer system of claim 14 wherein said computer system is configured to operate in conjunction with other computer systems in a network environment.

17. The computer system of claim 16 wherein the network environment is at least one selected from:

an Intranet, an Extranet and the Internet.

18. A computer readable medium including program instructions for determining a list of frequent data values in a database management system, the program instructions for implementing steps comprising:

selecting a data value and comparing a count associated with said selected data value with a threshold;

inserting said selected data value and associated count into said list if said count is greater than said threshold and said list is not full;

replacing the least frequently occurring data value and associated count in said list with said selected data value and associated count, and modifying said threshold, if said count is greater than said threshold and said list is full.

19. The computer readable medium of claim 18, wherein the medium is a recordable data storage medium.

20. The computer readable medium of claim 18, wherein the medium is selected from a group consisting of magnetic, optical, biological and atomic storage media.

21. The computer readable medium of claim 20, wherein the medium is a modulated carrier signal.

22. The computer readable medium of claim 21, wherein the modulated carrier signal is a transmission over a network selected from a group consisting of the Internet, Intranet and Extranet.