I'm able to reproduce reliably here. I'll email you details privately.<div><br></div><div>Aren<br><br><div class="gmail_quote">On Thu, Nov 22, 2012 at 9:02 AM, Markus Metz <span dir="ltr"><<a href="mailto:markus.metz.giswork@gmail.com" target="_blank">markus.metz.giswork@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On Sat, Nov 17, 2012 at 4:06 PM, Aren Cambre <<a href="mailto:aren@arencambre.com">aren@arencambre.com</a>> wrote:<br>
> I have a dataset of just over 700,000 incidents that happened in square-ish<br>
> Texas county that's about 30 miles on each side.<br>
><br>
> Here's the parameters reported by v.kernel as it's executing:<br>
><br>
> STDDEV: 1000.000000<br>
> RES: 111.419043 ROWS: 458 COLS: 447<br>
><br>
> Writing output raster map using smooth parameter=1000.000000.<br>
><br>
> Normalising factor=6482635.018778.<br>
><br>
><br>
> I am running this on a Windows 7 x64 machine with 8 GB RAM and an Intel Core<br>
> i7 Q720 1.6 GHz with 4 physical cores. I notice that it's not multithreaded,<br>
> only using 1 core.<br>
><br>
> It takes about 16 hours to complete. Is this correct? I'd like to use this<br>
> on a dataset with closer to 5 million records, and I'm really concerned how<br>
> long it may take.<br>
<br>
</div>The time required by v.kernel is a function of the number of cells and<br>
the input parameter stddeviation. The larger any of these values is,<br>
the more time v.kernel will need. Nevertheless, I think that the 16+<br>
hours are not correct. I tested with a vector with 3 million points<br>
for a grid with 2700 rows and 1087 columns, magnitudes larger than the<br>
grid used by you. v.kernel completes in just over one minute.<br>
<div class="im"><br>
><br>
> I posted my question about the 16+ hours at<br>
> <a href="http://gis.stackexchange.com/questions/41058/how-do-i-compute-v-kernel-maps-in-less-than-16-hours/" target="_blank">http://gis.stackexchange.com/questions/41058/how-do-i-compute-v-kernel-maps-in-less-than-16-hours/</a>.<br>
> Bill Huber, who si apparently knowledgeable about kernel density<br>
> calculations in general, posted a response, and he felt like a kernel<br>
> density map shouldn't take much time at all. But digging more deeply, turns<br>
> out he had come up with a kernel density calculation method over a decade<br>
> ago using Fourier transforms. See<br>
> <a href="http://www.directionsmag.com/features/convolution/129753" target="_blank">http://www.directionsmag.com/features/convolution/129753</a> and the next two<br>
> articles linked to it (they are short articles). Apparently this transforms<br>
> it from an O(n^2) problem to an O(n ln n) complexity problem.<br>
<br>
</div>The approach of Bill Huber is raster-based, not vector based, making<br>
some things easier, at the cost of precision. The coordinate<br>
precision, however, is only needed for kernel functions other than<br>
uniform. In GRASS, you could get something like a raster-based density<br>
map by<br>
<br>
- exporting the points with v.out.ascii<br>
- re-importing the points with r.in.xyz method=n to get the number of<br>
points per cell<br>
- running a neighborhood analysis using a circular window with<br>
r.neighbors method=sum -c<br>
<br>
Optionally you could use the gauss option of r.neighbors to get an<br>
equivalent to v.kernel kernel=gaussian<br>
<br>
HTH,<br>
<br>
Markus M<br>
<div class="im"><br>
><br>
> I inspected v.kernel's main.c<br>
> (<a href="http://trac.osgeo.org/grass/browser/grass/trunk/vector/v.kernel/main.c" target="_blank">http://trac.osgeo.org/grass/browser/grass/trunk/vector/v.kernel/main.c</a>),<br>
> and looks like v.kernel uses an output-centric method (using Bill's wording)<br>
> of calculating the output, which seems like O(n^2) complexity.<br>
><br>
> So I guess what I'm getting at is it appears to me that the algorithm behind<br>
> GRASS GIS's v.kernel is straightforward but is a greedy algorithm<br>
> (<a href="http://en.wikipedia.org/wiki/Greedy_algorithm" target="_blank">http://en.wikipedia.org/wiki/Greedy_algorithm</a>), which is fine, but it make<br>
> take a while to execute. Is this true?<br>
><br>
> Is there not spatial indexing I could add to the dataset? I've done various<br>
> Google searches on that and can't come up with anything clear.<br>
><br>
> Aren<br>
><br>
</div>> _______________________________________________<br>
> grass-user mailing list<br>
> <a href="mailto:grass-user@lists.osgeo.org">grass-user@lists.osgeo.org</a><br>
> <a href="http://lists.osgeo.org/mailman/listinfo/grass-user" target="_blank">http://lists.osgeo.org/mailman/listinfo/grass-user</a><br>
><br>
</blockquote></div><br></div>