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 <[email protected]>wrote: > On Sat, Nov 17, 2012 at 4:06 PM, Aren Cambre <[email protected]> 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 > > [email protected] > > http://lists.osgeo.org/mailman/listinfo/grass-user > > >
_______________________________________________ grass-user mailing list [email protected] http://lists.osgeo.org/mailman/listinfo/grass-user
