Another question about RavenDb + Spatial Clustering.

[Justin A]

Hi everyone,

I'm also starting to come to the point where clustering lat/long points would be a huge for our project.

I started to read this thread and then this thread (in the RavenDB GG group).

My TL;DR; from it was

1. Using this Cartesian algorithm which basically allocates your lat/long point to a square in a world-grid. The grid (area) is larger, the higher up the 'zoom level' you are. (via a reply from Oren).

2. Simon Bartlett was also going to look into something because he's been thinking about this, too.

3. One of the OP's didn't agree with the Cartesian alg as a valid answer (for his/her problem).

The grid idea sounds very much how i though MS SQL does spatial indexing .. so (me being very dumb) sorta understood this concept pretty quickly. And that makes nice sense to me. the lat/long clustering is 'cached' .. meaning .. we pre-calculate which grid they exist in, once (cause that will never change, until the lat/long changes).

So i'm just checking if this is still probably the best way to do things?

Simon - has any new magical clustering code been added to any secret ravendb things that I might have missed but exists? Have you even had a chance to R&D anything?

Lastly, does this algorithm exist on the net already?

-J-

[Oren Eini (Ayende Rahien)]

We already do just that, pretty much.

When we index things, we split the world into boxes using several options, GeoHash, QuadTree and Bounding Box.

You can issues queries on it, the easiest being just create a rectangle on the specified size and then issue a Within query

-J-

--
You received this message because you are subscribed to the Google Groups "ravendb" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ravendb+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Justin A]

Heya Oren. I don't see how a Within query will help. That's assuming one (square) poly.

I guess I don't understand what you're saying *blush*.

are you saying that there's a way to leverage the spatial index .. which already is splitting everything up into boxes/grids?

for example, given this bounding box (which is the lat/long points of my google map) .. return all the lat longs in there (typical point in poly query) BUT this time, don't give me the lat/long point but give me the GeoHash or the Grid Box thingy it exists in .. for a particular zoom level / layer?

and then i can just reduce that result to group by that grid Id / geohash  and return the counts.

something like that?

[Oren Eini (Ayende Rahien)]

Yeesss... 

Simon would probably be a better person to answer exactly how to do this. What I would probably do is issue a query using dynamic stuff.

If you can create a sample test, I can try figuring it out.

--

[Simon Bartlett]

Hi Justin,

There's no clustering support for RavenDB yet...

This is something I do intend to take a look at, post RavenDB 2.5. You're welcome to assist, if you like!

Still need to finish writing the spatial documentation for the 2.5 release first though.

Simon

[Justin A]

I was secretly hoping you would pop into this thread, Simon :)

I'm not really sure how i can assist. At the very least, can I keep the conversation going in this thread if that's ok.

I also guess the first step would also be to create a sample test for us all, as Oren stated. Something like ... i'll go grab a list of lat/long points from our system because they are generally clustered near each other.

sounds ok?

[Simon Bartlett]

Let's talk functionality...

IMO the ideal solution would be one where RavenDB can run a clustering operation on the results of any spatial query. This would allow for more flexibility, and a infinite number of zoom levels. However, it would mean that we can't precompute clusters at indexing time.

It would work something like:

var clusters = session.Query<GeoShape>

                      .Spatial(x => x.Geometry, x=> x.Within(rectangle))

                      .ToClusteredMarkers();

...allowing you to change the zoom level by changing the bounds of the rectangle.

I also think this might be quite simple to implement - basically re-implementing the google maps or leaflet clustering algorithms.

However... what is it you want to achieve from a UX/UI perspective? How is the user going to interact with the clusters? What happens when a user clicks on a cluster? and does RavenDB need to be able to do anything to support this use case? Client-side clustering is very good in regards to UX - are we wanting to achieve a similar UX?

Also, I was thinking that a clustered query would return a set of Cluster objects - what data does each Cluster result contain (other than coordinates, and object count)?

Lots of questions :)

Simon

[Oren Eini (Ayende Rahien)]

Question, let us assume that we have the following grid.

Orange spots are points of interest.

For each of those points, we would usually generate at least several entries, at various levels.

You can see the red & yellow squares are example of that.

Can we just use those for this purpose?

--

[Simon Bartlett]

We could use the hashes that we generate, but you'd end up with with clusters in a grid formation.

I was thinking along the lines of distance-based clustering which tends to generate clusters that are more accurate and visually pleasing...

I found a nice Google Maps API article on clustering: https://developers.google.com/maps/articles/toomanymarkers

[Justin A]

That's an interesting article u found there Simon :)

I've always been thinking along the lines of grid clustering. given small grid sizes, it's doesn't seem too bad and could be a great first step, probably. This is already been done, right? just having some smarts to leverage it (ie. spatial indexing is sorta doing this).

When it comes to cluster result data, I've always thinking along the lines of a Map/Reduce result .. where it's the schema data for a single result + the centre point + count.

for example, using Grid clustering (just to keep this convo simple).

Q: given a polygon (eg. a rectangle viewport for part of the city of New York) and a zoom level, display/find all the crime stats.

Sln: If a grid section of this polygon returns a cluster, all the properties would be 0/null except centre point + (cluster reduce) count. if a grid section returns a single result (count == 1), then return all the details for that reduce result. Eg. crime committed on, etc

or just like you said, the developer can choose to just return the count and the centre point and maybe a list of Id's, if count == 1 .. maybe.

i'm not very good at this stuff - not sure if i'm helping or wasting both your time. :blush:

[Oren Eini (Ayende Rahien)]

Yes, that is what google calls geo hashing clustering, and I think that this should be possible, right now.

[Oren Eini (Ayende Rahien)]

Justin,

Can you provide us with some sample data? 

That could be a fun thing to try over the weekend

--

[Justin A]

sending email now :)

[Oren Eini (Ayende Rahien)]

Okay, I spent some time over this, and it isn't that easy.

In particular, we need to emit additional information.

However, it seems that it should be easy enough to add.

GeohashUtils.EncodeLatLon(32.4433, 34.919656)

...

And, while writing this email, I figured out a way to do that.

See this passing test.

On Sat, Jun 22, 2013 at 3:51 PM, Justin A <jus...@adler.com.au> wrote:

sending email now :)