Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I'm currently in Afghanistan and need some geospatial support. I have a customer that needs to know where Areas of Interest (AOI) exist. AOIs are defined as 3 types of events within 1KM of each other within 30 days. I can figure out how to find X number of events within Y kilometers, but can't figure out the time part. Any ideas?

Also, the 30 days does not mean within the last 30 days. An AOI may have existed back in 15May-15June, for example.

It is a vast amount of data, and I cannot share it, but I have an MGRS, lat/long in DD, and a date field.

I really appreciate any advice on how to tackle this. On the network I operate on, I only have the base install of ArcGIS 10, and the data is stored in a file geodatabase. I won't be able to install any other software such as PostGIS, but we do have python installed.

Thanks!

share|improve this question

1 Answer 1

Analysis

This can be seen as a problem of identifying cylindrical regions in a 2+1 dimensional spacetime that contain a minimum number of events. If you have a 3D (voxel-based) system you can solve this fairly easily by means of a 3D focal sum based on this cylindrical neighborhood: just pick out the voxels where the sum exceeds your threshold (of, say, three events). Each voxel identifies a central point (plus all points within 1/2 km of it) and a central time (plus all times up to 15 days before or after), thereby locating groups of events simultaneously in space and time.

Solution

Using an ordinary (2D) GIS, this method isn't available but we can still use the approach to guide us, because we can construct the 3D focal sum by assembling a stack of 2D slices (represented as rasters). It's not going to be quick, but with a tiny amount of scripting (to code a loop over time) it will be fairly straightforward and won't take too much time. Here is the workflow:

  1. For each day create a focal sum of the events, beginning with the earliest day in the dataset. Since the events need to be one kilometer from each other, use a circular neighborhood of 1/2 km radius. Thus, the count in each cell will include only groups of events that are definitely within 2*(1/2) = 1 km of each other.

    Your region is small enough that you probably should use a raster cellsize much finer than the one kilometer radius: 100 meters ought to give reasonable precision and accuracy.

  2. Starting at 30 days, compute a local sum of those focal sums. Values in this raster count the number of events occurring within 1 km of each other within 30 days. Identify all cells where the counts exceed the threshold. (Record their locations, their counts, and the range of days reflected by this raster, which consists of days 1 through 30.)

  3. For each successive day, add the next focal sum to the previous result and subtract the focal sum from 31 days ago. As before, identify all cells where the counts exceed the threshold. Repeat until the last day is reached, and then keep going for another 29 days, until the cumulative grid reflects only the very last day, then stop.

Computational considerations

You can compute these focal sums on the fly and throw them away at the point they are last used, thereby reducing the storage (or RAM) requirements to just 33 rasters: 31 daily focal sums, the cumulative space-time sum, and working memory to update it. With limited RAM it might be even faster just to compute each daily focal sum twice: once as it is added in and again to subtract it off the end of each 30-day window. That reduces RAM requirements to just three rasters at a time. At (say) a 100 m resolution you can cover all of Afghanistan (say) with a 10,000 by 10,000 cell grid, requiring about 0.4 GB RAM, so 1.2 GB RAM is all that's necessary. The focal sum and local sum/difference operations are so fast that with an efficient raster-based GIS each day can be processed in at most a few seconds (maybe much faster if there are few events and the underlying algorithms are good).

This workflow is simple enough and uses such simple basic operations that it can be coded directly in Python, without any built-in raster support. The key is to implement a good focal sum operation. If events are sparse, do this by looping over the events (and "spreading" their counts into their neighborhoods in the raster) rather than by FFT or otherwise.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.