nd_box_array_distribution()

static int nd_box_array_distribution ( const ND_BOX **  nd_boxes, int  num_boxes, const ND_BOX *  extent, int  ndims, double *  distribution  )

static

Calculate how much a set of boxes is homogenously distributed or contentrated within one dimension, returning the range_quintile of of the overlap counts per cell in a uniform partition of the extent of the dimension.

A uniform distribution of counts will have a small range and will require few cells in a selectivity histogram. A diverse distribution of counts will have a larger range and require more cells in a selectivity histogram (to distinguish between areas of feature density and areas of feature sparseness. This measurement should help us identify cases like X/Y/Z data where there is lots of variability in density in X/Y (diversely in a multi-kilometer range) and far less in Z (in a few-hundred meter range).

Definition at line 761 of file gserialized_estimate.c.

References ND_BOX_T::max, ND_BOX_T::min, MIN_DIMENSION_WIDTH, and range_quintile().

Referenced by compute_gserialized_stats_mode().

{
        /* How many bins shall we use in figuring out the distribution? */
        static int num_bins = 50;
        int d, i, k, range;
        int counts[num_bins];
        double smin, smax;   /* Spatial min, spatial max */
        double swidth;       /* Spatial width of dimension */
#if POSTGIS_DEBUG_LEVEL >= 3
        double average, sdev, sdev_ratio;
#endif
        int   bmin, bmax;   /* Bin min, bin max */
        const ND_BOX *ndb;

        /* For each dimension... */
        for ( d = 0; d < ndims; d++ )
        {
                /* Initialize counts for this dimension */
                memset(counts, 0, sizeof(int)*num_bins);

                smin = extent->min[d];
                smax = extent->max[d];
                swidth = smax - smin;

                /* Don't try and calculate distribution of overly narrow dimensions */
                if ( swidth < MIN_DIMENSION_WIDTH )
                {
                        distribution[d] = 0;
                        continue;
                }

                /* Sum up the overlaps of each feature with the dimensional bins */
                for ( i = 0; i < num_boxes; i++ )
                {
                        double minoffset, maxoffset;

                        /* Skip null entries */
                        ndb = nd_boxes[i];
                        if ( ! ndb ) continue;

                        /* Where does box fall relative to the working range */
                        minoffset = ndb->min[d] - smin;
                        maxoffset = ndb->max[d] - smin;

                        /* Skip boxes that our outside our working range */
                        if ( minoffset < 0 || minoffset > swidth ||
                             maxoffset < 0 || maxoffset > swidth )
                        {
                                continue;
                        }

                        /* What bins does this range correspond to? */
                        bmin = num_bins * (minoffset) / swidth;
                        bmax = num_bins * (maxoffset) / swidth;

                        POSTGIS_DEBUGF(4, " dimension %d, feature %d: bin %d to bin %d", d, i, bmin, bmax);

                        /* Increment the counts in all the bins this feature overlaps */
                        for ( k = bmin; k <= bmax; k++ )
                        {
                                counts[k] += 1;
                        }

                }

                /* How dispersed is the distribution of features across bins? */
                range = range_quintile(counts, num_bins);

#if POSTGIS_DEBUG_LEVEL >= 3
                average = avg(counts, num_bins);
                sdev = stddev(counts, num_bins);
                sdev_ratio = sdev/average;

                POSTGIS_DEBUGF(3, " dimension %d: range = %d", d, range);
                POSTGIS_DEBUGF(3, " dimension %d: average = %.6g", d, average);
                POSTGIS_DEBUGF(3, " dimension %d: stddev = %.6g", d, sdev);
                POSTGIS_DEBUGF(3, " dimension %d: stddev_ratio = %.6g", d, sdev_ratio);
#endif

                distribution[d] = range;
        }

        return true;
}

Here is the call graph for this function:

Here is the caller graph for this function: