[josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM

[Dave Hansen]

On Sat, 2009-09-12 at 17:58 +0100, Robert Scott wrote:
> On Saturday 12 September 2009, Dave Hansen wrote:
> > 
> > I've been hacking on the JOSM validator plugin for a while.  One of the
> > repeating "hard problems" that comes up are doing the UnconnectedWays tests.
> > You need to do searches for every segment in a way to see if there are any
> > nearby nodes.  This generally means that you do a number of searches on the
> > same order as the number of nodes that you have.
> ...
> 
> I realize this is quite a crude reply to such a detailed email.
> 
> Did you investigate kd-trees at all?
> 
> http://en.wikipedia.org/wiki/Kd_tree

Nope.  I did some searching to find multidimensional search algorithms
before I started this, but none of them seemed too horribly nice.

kd-trees do like quite nice.  I do believe what I've implemented is
relatively close to what they do, though.  They have the advantage that
they split in a single dimension at each level in the tree.  QuadBuckets
are hard-coded for 2 dimensions and just basically split into those two
dimensions at once.  But, I think there is a lot of similarity.

It also looks like kd-trees are intelligent about the values at which
they decide to split.  This means that if you have a bunch of entries
all bunched up into one end of a bucket and you split it, you'll always
get them split in half.  QuadBuckets will instead force a bunch more
splits until the buckets are well-split.  QuadBuckets are stupid about
where the split: they only do it into geometric quarters of the original
bucket.

I basically chose the algorithm that I did since it modeled something
else that I and other OSMers are familiar with.  It's even possible that
we could use the quadtile indexes in a way to make communication with
the DB server faster, although I'm using slightly different calculations
than it is as it stands now.

If someone knows of any existing Java kd-tree implementations, I'd be
happy to look into it and see if it could be applied here.  I love
nothing more than to throw my own code away.  Seriously. ;)

-- Dave