Help

93 views
Skip to first unread message

shashankkr

unread,
Apr 18, 2012, 4:34:44 AM4/18/12
to Uzaygezen
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

unread,
Apr 18, 2012, 5:34:52 AM4/18/12
to uzay...@googlegroups.com
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

unread,
Apr 21, 2012, 11:19:44 PM4/21/12
to uzay...@googlegroups.com
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

unread,
Apr 25, 2012, 5:36:41 AM4/25/12
to uzay...@googlegroups.com
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

unread,
Apr 25, 2012, 11:19:27 AM4/25/12
to uzay...@googlegroups.com
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

unread,
May 15, 2012, 12:56:52 AM5/15/12
to uzay...@googlegroups.com
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

unread,
May 15, 2012, 2:52:37 AM5/15/12
to uzay...@googlegroups.com
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


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
Reply all
Reply to author
Forward
0 new messages