LongRange Query with 64 bit precision

[shashankkr]

Hi Daniel,
I am facing few problems in running the range query code.
Earlier I asked about index to string conversion because I am using a p2p structure called P-Grid (http://www.p-grid.org/) which operates on binary strings. Anyways, I took care of that, however I am not able to run the range query using your code.
Here is the code :
https://github.com/shashankkr/M-Grid/blob/master/MGrid/src/edu/mst/mapreduce/dataset/hilbert/LongVersion.java

I am generating small uniform data-set [(0,0)(1,1) - (4,4)] and running a range query as (1,1) (4,4) [(xmin,ymin) (xmax,ymax)] and keeping the precision as 64 bits [32.32].
When I run the code, I get the following output :

Nov 15, 2013 12:28:07 AM edu.mst.mapreduce.dataset.hilbert.LongVersion main
INFO: Populating table with up to 5 rows.
Nov 15, 2013 12:28:07 AM edu.mst.mapreduce.dataset.hilbert.LongVersion main
INFO: ranges=[[1, 1], [4, 4]]
Nov 15, 2013 12:33:11 AM edu.mst.mapreduce.dataset.hilbert.LongVersion queryAndFilter
INFO: indexRanges=[FilteredIndexRange[indexRange=LongRange[start=0,end=1],filter=,potentialOverSelectivity=false]]
Nov 15, 2013 12:33:29 AM edu.mst.mapreduce.dataset.hilbert.LongVersion main
INFO: actual.size()=0

So I can see that the ranges are not getting converted to indexRanges properly. Its been few weeks since I am trying to fix this error but I couldn't. I'll be really really grateful to you if you can help me or guide me in the right direction.

thanks

-cheers

Shashank Kumar

[Daniel]

For the long types, the total number of bits must be at most 62 (if you need more bits, you can use BigInteger). You need to change from 32, 32 to 31, 31 on line 75, and you also need ranges[0][1] = 4 on line 145 and ranges[1][0] = 1 on line 146. After that you'll get the expected 4 points.

[shashankkr]

Hi Daniel,

Thanks, that worked like a charm :) 

I am also adding the code which calculates k-nearest neighbor from a point : https://github.com/shashankkr/M-Grid/blob/master/MGrid/src/edu/mst/mapreduce/dataset/hilbert/LongVersion.java

The idea is to first calculate window of the Range according to the formula presented in this paper : http://www.cse.cuhk.edu.hk/~taoyf/paper/tkde04.pdf

and keep increasing the window until k points are found.

There is just one thing I need to clarify, how exactly are you calculating the Range? Suppose we have query like ( xmin, ymin ) - ( xmax , ymax), then according to my understanding you are calculating the Hvalue of (xmin, xmax) - (ymin, ymax) and while searching for the points in the db you are ignoring the points which  lies inside this query? 

Thanks again for your help and support.

have a great day ahead.

cheers

Shashank