Here is a brief description of the layout of the Objects in my Project and how the binary search partition is built.

Overview of the Process

1. At the bottom we have points that are either read in or generated randomly
2. The points are collected into cells and the cells make up a grid. Each cell has a density, and number of points associated with it.
3. The grid is put into one bucket whose lowerBound and upperBound are not points, but are designated by cells in the grid. Therefore the lowerBound will always be (0,0,0,0) for the first bucket and (X,X,X,X) where X is the last cell in each dimension.
4. From here on, we deal only with cells
5. A bucket is created to contain all the cells
6. The bucket is split into two buckets until the desired number of buckets is reached.

Defining the Cells

The question is what parameters decide the cell size/shape and grid size and shape? We determine this in the following way:

1. Find the lower and upper bound points in each dimesion lowerBound = (wl,xl,yl,zl) and upperBound = (wu,xu,yu,zu). This may be given by the random point generating function, but most often is determined as we read the points.
2. Given the resolution of the grid we can now determine the size/shape of the cells.

From bucket to buckets

Next the question is how is the first bucket made and how do we split the into more buckets.

Each bucket has:

1. lowerBound and upperBound cells
2. cell partition
3. number of points
4. skew
5. skew reduction

The first bucket is made up of all the cells in the Grid4D object. Bucket = lowerBound(0,0,0,0) and upperBound(X,X,X,X). Notice that these are cell numbers not actual positions.

When a bucket is created it is given cell bounds and the following are calculated:

1. Number of points
2. Skew

Note that we CANNOT CALCULATE THE:

1. partition point - because this creates buckets and that would start an endless loop.
2. skew reduction - because this requires the partition point.

Partitioning the Bucket

A bucket must be refreshed - that is we must calculate the partitionPoint and skewReduction by calling refresh();

The bucket then has a patitionCell. The partitionCell is the upper bound cell execept in the dimension it is split. When a bucket is split the lowerBucket and upperBucket are created as follows:

     lowerBucket = [lowerBoundCell, partitionCell]
     upperBucket = [lowerBoundCell except in the split dimension substitute partitionCell+1, upperBound]

Clearly than the calculation of the skew reduction must be done along this same split.

Running the Simulation

The following steps must be done in order:

1. Create a new DataGrid4D object called g

2. Determine the two query points: Point4D q1, q2

3. Set the number of buckets in the input DataGrid4D.setBuckets(int NumBuckets)

Here we start our actual contribution:

1. Build the parametric functions: DataGrid4D.buildParametricFunctions(Point4D q1,q2)

2. Run the MaxCount algorithm: BSP4D.MaxCount(float from, to)

Collecting statistics

For each run of the program we will collect in a comma seperated values list:

1. Number of buckets (50, 60, 70, 80, 90, 100)
2. Number of points (8K, 12K, 16K, 20K, 24K, 28K, 32K, 36K, 40K)
3. Distance between query points (400, 800, 1200, 1600, 2000)
4. Dense vs. Sparse regions (one each)