[GRASS-user] Does v.kernel have to take 16+ hours?

[Markus Metz]

On Sat, Nov 17, 2012 at 4:06 PM, Aren Cambre <aren at arencambre.com> wrote:
> I have a dataset of just over 700,000 incidents that happened in square-ish
> Texas county that's about 30 miles on each side.
>
> Here's the parameters reported by v.kernel as it's executing:
>
> STDDEV: 1000.000000
> RES: 111.419043 ROWS: 458   COLS: 447
>
> Writing output raster map using smooth parameter=1000.000000.
>
> Normalising factor=6482635.018778.
>
>
> I am running this on a Windows 7 x64 machine with 8 GB RAM and an Intel Core
> i7 Q720 1.6 GHz with 4 physical cores. I notice that it's not multithreaded,
> only using 1 core.
>
> It takes about 16 hours to complete. Is this correct? I'd like to use this
> on a dataset with closer to 5 million records, and I'm really concerned how
> long it may take.

The time required by v.kernel is a function of the number of cells and
the input parameter stddeviation. The larger any of these values is,
the more time v.kernel will need. Nevertheless, I think that the 16+
hours are not correct. I tested with a vector with 3 million points
for a grid with 2700 rows and 1087 columns, magnitudes larger than the
grid used by you. v.kernel completes in just over one minute.

>
> I posted my question about the 16+ hours at
> http://gis.stackexchange.com/questions/41058/how-do-i-compute-v-kernel-maps-in-less-than-16-hours/.
> Bill Huber, who si apparently knowledgeable about kernel density
> calculations in general, posted a response, and he felt like a kernel
> density map shouldn't take much time at all. But digging more deeply, turns
> out he had come up with a kernel density calculation method over a decade
> ago using Fourier transforms. See
> http://www.directionsmag.com/features/convolution/129753 and the next two
> articles linked to it (they are short articles). Apparently this transforms
> it from an O(n^2) problem to an O(n ln n) complexity problem.

The approach of Bill Huber is raster-based, not vector based, making
some things easier, at the cost of precision. The coordinate
precision, however, is only needed for kernel functions other than
uniform. In GRASS, you could get something like a raster-based density
map by

- exporting the points with v.out.ascii
- re-importing the points with r.in.xyz method=n to get the number of
points per cell
- running a neighborhood analysis using a circular window with
r.neighbors method=sum -c

Optionally you could use the gauss option of r.neighbors to get an
equivalent to v.kernel kernel=gaussian

HTH,

Markus M

>
> I inspected v.kernel's main.c
> (http://trac.osgeo.org/grass/browser/grass/trunk/vector/v.kernel/main.c),
> and looks like v.kernel uses an output-centric method (using Bill's wording)
> of calculating the output, which seems like O(n^2) complexity.
>
> So I guess what I'm getting at is it appears to me that the algorithm behind
> GRASS GIS's v.kernel is straightforward but is a greedy algorithm
> (http://en.wikipedia.org/wiki/Greedy_algorithm), which is fine, but it make
> take a while to execute. Is this true?
>
> Is there not spatial indexing I could add to the dataset? I've done various
> Google searches on that and can't come up with anything clear.
>
> Aren
>
> _______________________________________________
> grass-user mailing list
> grass-user at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/grass-user
>