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

[Aren Cambre]

I'm able to reproduce reliably here. I'll email you details privately.

Aren

On Thu, Nov 22, 2012 at 9:02 AM, Markus Metz
<markus.metz.giswork at gmail.com>wrote:

> 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
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/grass-user/attachments/20121122/62b89e52/attachment.html>