Method for characterizing information in data sets using multifractals

Claim 2

A computer-implemented method for determining characteristic information relating to a distribution of data items in a data set comprising the steps of: estimating parameters representing a multifractal distribution based on attributes of said data set; and determining said distribution-related characteristic information based on said estimated multifractal parameters.

Claim 3

The method of claim 1 wherein said estimating step further comprises: obtaining first attribute values corresponding to a substantially total number of items in said data set and a number of categories into which said items can be classified; and obtaining at least one second attribute value corresponding to substantially the number of data items classified into at least one respective category having substantially the largest number of data items.

Claim 4

The method of claim 2 wherein said step of obtaining said second attribute value obtain a value corresponding to substantially the number of data set items classified into the category having substantially the largest number of items.

Claim 5

The method of claim 2 wherein said steps of obtaining first and second attribute values comprises the step of estimating at least one of said values.

Claim 6

The method of claim 2 wherein said step of obtaining said second attribute value comprises retrieving said value from a high-biased histogram associated with said data set.

Claim 7

The method of claim 1 wherein said estimating step estimates multifractal bias and order parameters.

Claim 8

The method of claim 1 wherein said distribution-related characteristic information is an estimation of a number of categories in a subset or superset of data items and wherein said determining step further comprises: obtaining an attribute value of substantially a total number of data items in said subset or superset; and determining said distribution-related characteristic information based on said estimated multifractal parameters and said obtained subset or superset attribute values.

Claim 9

The method of claim 1 wherein said statistical distribution-related characteristic information is identifying an amount of categories corresponding to a particular percentile of said data set items and wherein said determining step further comprises: determining a number of data set items that substantially correspond to the desired percentile; obtaining at least one attribute value of substantially the number of data set items classified into at least one respective category having substantially the largest amount of items; and sequentially updating a sum value by summing said obtained at least one attribute value with an estimation of numbers data items classified into respective categories having substantially the next largest number of items based on said multifractal distribution parameters until said sum value is equal to or greater than said determined number of data set items for the desired percentile, wherein a corresponding number of categories to achieve such sum is said desired amount of categories.

Claim 10

The method of claim 8 wherein said step of obtaining said attribute values comprises retrieving said values from a high-biased histogram associated with said data set.

Claim 11

The method of claim 1 wherein said statistical information corresponds to a self-joins selectivity of said data set and wherein said determining step further comprises sequentially updating a sum value by summing a square of the number of data set items classified into the respective categories, wherein said number of items in each category can be either an obtained attribute value or estimated based on said multifractal distribution parameters from said estimating step.

Claim 12

The method of claim 10 wherein said obtained attribute values are retrieved values from a high-biased histogram associated with said data set.

Claim 13

The method of claim 1 wherein said step of estimating said multifractal parameters estimates bias parameter P and order parameter K and further comprises: (a) determining an initial integer value for said order parameter K; (b) determining a value for the bias parameter P based on said order parameter K and attribute values of said data set; (c) determining an expected number F 0 of categories of data items in said data set; (d) increasing the value of the order parameter K and repeating steps (b) (c) and (d), if a difference in the expected number of categories F 0 and a known number of categories F 0 is greater than a tolerance value.

Claim 14

The method of claim 12 wherein said initial value of the order parameter K is an integer determined based substantially on the known number of categories F 0 of data items in said data set.

Claim 15

The method of claim 13 wherein said initial integer value of the order parameter K is determined corresponding to the integer portion of an expression: LOG F 0 !.

Claim 16

The method of claim 12 wherein said step of determining said bias parameter P value determines said parameter P substantially corresponding to a relationship: P=(M MAX /N) 1/K , where the value N is substantially a total number of items in the data set and the value M MAX is the amount of data items classified into a category with substantially the largest amount of data items.

Claim 17

The method of claim 12 wherein said step of determining said expected number of categories of data items F 0 is a value substantially corresponding to a relationship: ##EQU4##