Hi Folks,

Well, I never did complete my series of posts describing our indexing scheme.  I guess I ought pick it up again now.

We've gone through some preliminaries so far, describing why we'd like spatial index, what a simple indexing might look like, and how we would use that simple scheme internally.  Over the next few posts, my plan is to describe the actual scheme we use and give some idea how it is used internally.  I'll start with the geometry type, and then cover geography.  There's more alike than not.

First, though, let's look back at where we've been.

Recall our simple grid index: we chose a bounding box, and then broke up space into a set of tiles.  These tiles were numbered using some scheme.  (In our example, we just numbered them in row-major order.)

We can find at least a few points to critique¹:

1. The tigher the bound around an object, the better the primary filter will perform, but small objects---say, points---may not be covered very tightly by a cell.
2. Large objects may have the opposite problem: the fraction of a set of covering cells that actually covers the object may be large, but it may take a lot of cells to do so.  If we have to persist each of those cells, our index is going to get quite large.
3. The index numbering we used doesn't preseve locality very well.  I.e., two close objects by several cells with wildly different numbers.  This has implications for performance, as local spatial operation may have to read values from all over the index.

Given that we want to stick with a tiling scheme, we want to find some scheme that will address these issues.  I should point out that there is no perfect solution to issue (3), but we would still like to do better than we have.

Next time: Our Basic Multi-Level Grids

Cheers,
-Isaac

¹ There are more issues we could pick on, but for the moment, I'm only going to choose the issues we're going to fix.² We'll come back to some others later in the series.
² I may have inadvertanly missed some issues that we will fix as well.  As you can probably tell, it's not like I've planned out these posts too carefully...