Help

[shashankkr]

Hi,

I am trying to generate hilbert keys for multidimensional indexing:

for example, in z order interleaving bits (11,10) will produce a z-
order key (1110)

I am trying to use this library for the same but somehow its not
working out. Can you please give me an example as how to generate
hilbert and inverse hilbert mapping using this library.

Please help me.

sincerely,
Shashank

[Daniel]

Dear Shashank,

I added a code sample in the section "Compact Hilbert Index Mappings" of the wiki page "HowTo" that should answer your question.

Thanks,

Daniel

[shashankkr]

Hi, Thanks a lott Daniel. You saved my life. I will add your name and this library to my acknowledgement in my thesis and hopefully to my research paper.

[shashankkr]

Hi Daniel,
just one more question,
What i am trying to do is to index multidimensional data (longitude, latitude and time) for location based applications for cloud platforms.
longitude and latitude values ranges from 180.9999999 to -180.9999999 ..or 32 bits binary equivalent. The compact hilbert algorithm and the library works perfectly for all dimensions but when i try to convert a 22 bit 3d value :

CompactHilbertCurve chc = new CompactHilbertCurve(new int[] {22, 22, 22});
.
.
.p[0].copyFrom(0b1001111111111110100111);
        p[1].copyFrom(0b1101111111111110100110);
        p[2].copyFrom(0b1111111111111110100011);
I get some unusual result :
index([1001111111111110100111, 1101111111111110100110, 1111111111111110100011])=size: 66bitset: {2, 3, 4, 5, 7, 11, 13, 14, 15, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 59, 61, 63, 65}

What is this bitset? I will be using a column based store and save the hilbert keys in some tree structure and perform queries. I'll be really helpful to you if you can help me on this.

sincerely,
Shashank Kumar

[Daniel]

Dear Shashank,

Column-oriented stores such as HBase work with the big endian representation of values, and I expect the need to represent the bit vectors in big endian form to be pretty common. I just added the following two methods to BitVector:

byte[] toBigEndianByteArray();

void copyFromBigEndian(byte[] array);


In your example, as a value in the column you just need to put the big endian byte[] representation of the hilbert index. You'll need to update to the latest SVN version for that.

Thanks,
Daniel

[shashankkr]

Hi Daniel,

I couldn't find the updated code as you mentioned so I tried to add the two methods to BitVector and implement it in LongBitVector but it keep giving me errors after days and days of trying. I'll be really grateful to you if you can help me with this. Also,  I am not able to understand what is this bitset {1 ,7, 10 ... } for size > 64.

Thanks again!!

Shashank

[Daniel]

Hi Shashank,

You can find the two new methods by performing an svn checkout or update. You can see them on the web interface at lines 244 and 254 of

http://code.google.com/p/uzaygezen/source/browse/trunk/core/src/main/java/com/google/uzaygezen/core/BitVector.java.

The implementations for up to 64 bits can be found at lines 525 and 548 of http://code.google.com/p/uzaygezen/source/browse/trunk/core/src/main/java/com/google/uzaygezen/core/LongBitVector.java.

For an arbitrary number of bits, you can find the implementation at lines 443 and 468 of http://code.google.com/p/uzaygezen/source/browse/trunk/core/src/main/java/com/google/uzaygezen/core/BitSetBackedBitVector.java.

A BitVector of any size (at least 101 in this case) with bitset {1 ,7, 10, 100} represents the number pow(2, 1) + pow(2, 7) + pow(2, 10) + pow(2, 100).

Take care,

Daniel