[
https://issues.apache.org/jira/browse/LUCENE-4922?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
John Berryman updated LUCENE-4922:
--
Attachment: HilbertConverter.zip
This is a Java example of converting from a set of x,y values (within specified
bounds) to a HilbertOrdered value.
The strategy is to
# Convert the x,y value so doubles between 0 and 1.
# Convert these doubles to large integers with max value 256^numBytes (user
specifies numBytes). Note: there's probably a way to do these two last steps
simultaneously and regain some precision. Note: numBytes must be <= 7 for now.
# Interleave the bits so that you get a z-order value (note, I did this the
"obvious way". In the code I've pointed to a website with a much more efficient
method - so called morten numbers.
# Convert the z-ordered value to a hilbert-ordered value.
How to do this last step really deserves a big whiteboard session - it's an
inherently visual discussion. However, as a clue to what's happening in the
code:
* There are only 4 shapes that compose the Hilbert curve. In the code I've
called them "D,U,n, and C" because of the way they look. These are the states
of a state machine.
* I convert from z to hilbert 2 bits at a time.
* On the first iteration I assume that I'm in the "D" state. In this simplistic
case, I convert from 2 z-ordered bits to 2 hilbert-ordered bits based upon a
lookup table that goes with the D state. I replace the z-ordered bits with the
hilbert-ordered bits.
* I then check for which state I should go to next based upon a different
lookup table that goes with the D state. It directs me to another state.
* I then get the next 2 bits from the byte array and repeat this method until
I'm out of bits.
I've spot checked the input/output and it looks good (you'll see where I've
done this in the code). No tests!
Also. This method could be slower than expected because I'm doing all
operations on 2 bits at a time. As is, the method in the python code might even
be faster because (correct me if I'm wrong) a double multiply can take place in
one clock cycle.
That said, the methods here can be extended to operate at the processor word
size.
What's more, I'm working with lookup tables. I suspect that you could use magic
numbers and bitmasks and all that jazz and make something that took up very
little space or time.
Also, I couldn't find them now, but there exist known efficient algorithms for
doing this conversion. (I guess this weekend I just felt like making my
own.:-/) I've run across algorithms that are even for higher dimension Hilbert
Curves
> A SpatialPrefixTree based on the Hilbert Curve and variable grid sizes
> --
>
> Key: LUCENE-4922
> URL: https://issues.apache.org/jira/browse/LUCENE-4922
> Project: Lucene - Core
> Issue Type: New Feature
> Components: modules/spatial
>Reporter: David Smiley
>Assignee: David Smiley
> Labels: gsoc2013, mentor, newdev
> Attachments: HilbertConverter.zip
>
>
> My wish-list for an ideal SpatialPrefixTree has these properties:
> * Hilbert Curve ordering
> * Variable grid size per level (ex: 256 at the top, 64 at the bottom, 16 for
> all in-between)
> * Compact binary encoding (so-called "Morton number")
> * Works for geodetic (i.e. lat & lon) and non-geodetic
> Some bonus wishes for use in geospatial:
> * Use an equal-area projection such that each cell has an equal area to all
> others at the same level.
> * When advancing a grid level, if a cell's width is less than half its
> height. then divide it as 4 vertically stacked instead of 2 by 2. The point
> is to avoid super-skinny cells which occurs towards the poles and degrades
> performance.
> All of this requires some basic performance benchmarks to measure the effects
> of these characteristics.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
-
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
