Scalability of inequality filters for multiple fields via Hilbert curve

[Max]

Hi all, 

Would like to know if there are any of you guys ever tried to use space filling curve like Hilbert curve to build index for multiple inequality filters. 

Seems like for any continuous field like long or date, the number of ranges (to be merged) to perform a accurate query is increasing rapidly, which makes this approach not scale. 

Any thought? or shall I build / model like this sample app? Query by partitions of all data and do an in-memory merge?

[Nick Johnson (Google)]

Hi Max,

I'm the author of this post: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves

You're right that this will likely have problems when dealing with arbitrary data rather than geospatial indexing. Hilbert curves work well at returning results with a minimum of false-positives and minimal queries when the region you're searching is (in coordinates on the curve) roughly square, or at least no more than 2:1. With arbitrary indexes, you could easily have queries that don't fit that approximation. At the very least, it would require some tuning.

-Nick Johnson

--
You received this message because you are subscribed to the Google Groups "Google App Engine" group.
To view this discussion on the web visit https://groups.google.com/d/msg/google-appengine/-/MipYkQ1_pvYJ.
To post to this group, send email to google-a...@googlegroups.com.
To unsubscribe from this group, send email to google-appengi...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en.

--
Nick Johnson, Developer Programs Engineer, App Engine

[Max]

Thanks Nick, 

So can I assume that we can't build arbitrary indexes on GAE for multiple inequality filters? We have to build index based on expected future data shape

[Nick Johnson (Google)]

Hi Max,

App Engine does not support filtering on multiple inequalities in a single query. This is a problem with any database using 1-dimensional indexes, and App Engine doesn't execute queries it can't evaluate efficiently.

-Nick

On Tue, Jul 5, 2011 at 6:53 PM, Max <theb...@gmail.com> wrote:

Thanks Nick, 

So can I assume that we can't build arbitrary indexes on GAE for multiple inequality filters? We have to build index based on expected future data shape

--

You received this message because you are subscribed to the Google Groups "Google App Engine" group.

To view this discussion on the web visit https://groups.google.com/d/msg/google-appengine/-/Sd6GqFbz1l8J.

To post to this group, send email to google-a...@googlegroups.com.
To unsubscribe from this group, send email to google-appengi...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en.

[Max]

Thanks Nick, 

So is there a plan to implement multi-dimensional index in GAE? I have checked road map and can't find it http://code.google.com/appengine/docs/roadmap.html