subject:"\[sqlite\] R\*Tree module and double precision\?"

Re: [sqlite] R*Tree module and double precision?

2010-11-04 Thread Richard Hipp

On Thu, Nov 4, 2010 at 11:27 AM, Ben Harper <b...@imqs.co.za> wrote:

> Are you sure that double precision in the RTree is necessary for your
> purposes?
>

To put this another way, single-precision RTree is sufficient to locate any
point on the surface of the earth to within less than 2.5 meters.  I'm
curious to know what real-world application needs more precision than that?

Remember that R-Tree is intended as a approximation filter to limit the
search space for a query.  It does not normally yield the definitive
answer.  Instead, R-Tree returns a superset of the answer which is further
refined by lower-level constraints.  Within 2.5 meters over the entire
surface of the earth is not a close enough approximation?


>
> Here is a table of floating point precision at various values:
>
> The 'flip' values are the 'org' values with the lowest bit flipped.
>
> org flip (delta)
>0.01 0.01 ( 0.00) (lowest bit is 10 ^ -9.030900)
>0.10 0.10 ( 0.00) (lowest bit is 10 ^ -8.127810)
>1.00 1.00 ( 0.00) (lowest bit is 10 ^ -7.224720)
>   10.0010.00 ( 0.01) (lowest bit is 10 ^ -6.020600)
>  100.00   100.00 ( 0.08) (lowest bit is 10 ^ -5.117510)
> 1000.00  1000.00 ( 0.61) (lowest bit is 10 ^ -4.214420)
>1.00 1.00 ( 0.000977) (lowest bit is 10 ^ -3.010300)
>9.99 9.98 ( 0.007813) (lowest bit is 10 ^ -2.107210)
>   99.9499.88 ( 0.062500) (lowest bit is 10 ^ -1.204120)
>  999.00   998.00 ( 1.00) (lowest bit is 10 ^ 0.00)
> 9992.00  9984.00 ( 8.00) (lowest bit is 10 ^ 0.903090)
>99936.00 99872.00 (64.00) (lowest bit is 10 ^ 1.806180)
>
>
> -Original Message-
> From: sqlite-users-boun...@sqlite.org [mailto:
> sqlite-users-boun...@sqlite.org] On Behalf Of Black, Michael (IS)
> Sent: 04 November 2010 02:51 PM
> To: General Discussion of SQLite Database
> Subject: Re: [sqlite] R*Tree module and double precision?
>
> I'll send the patched C file to your email address.  I think the 1M patched
> version is a bit much for the email list.
>
> Normally you would just use the "patch" utility to apply the patch to your
> file.
>
> Michael D. Black
> Senior Scientist
> Advanced Analytics Directorate
> Northrop Grumman Information Systems
>
>
> 
>
> From: sqlite-users-boun...@sqlite.org on behalf of
> jsarc...@nanotronicsimaging.com
> Sent: Wed 11/3/2010 10:22 AM
> To: sqlite-users@sqlite.org
> Subject: EXTERNAL:Re: [sqlite] R*Tree module and double precision?
>
>
>
> >From: "Black, Michael (IS)" <michael.bla...@ngc.com> I made a patch
> >which seems to do this for you...
> >Use this switch to enable double precision on RTREE /DRTREE_DOUBLE
>
> I am interested in this as well.  Will this patch be included in a future
> version of SQLite?  Or, if not, how best to make use of this patch if I
> normally use the amalgamation from C++.
> Jeff Archer
> Nanotronics Imaging
> jsarc...@nanotronicsimaging.com
> <330>819.4615
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>
>
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>



-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] R*Tree module and double precision?

2010-11-04 Thread Ben Harper

Are you sure that double precision in the RTree is necessary for your purposes?

Here is a table of floating point precision at various values:

The 'flip' values are the 'org' values with the lowest bit flipped.

 org flip (delta)
0.01 0.01 ( 0.00) (lowest bit is 10 ^ -9.030900)
0.10 0.10 ( 0.00) (lowest bit is 10 ^ -8.127810)
1.00 1.00 ( 0.00) (lowest bit is 10 ^ -7.224720)
   10.0010.00 ( 0.01) (lowest bit is 10 ^ -6.020600)
  100.00   100.00 ( 0.08) (lowest bit is 10 ^ -5.117510)
 1000.00  1000.00 ( 0.61) (lowest bit is 10 ^ -4.214420)
1.00 1.00 ( 0.000977) (lowest bit is 10 ^ -3.010300)
9.99 9.98 ( 0.007813) (lowest bit is 10 ^ -2.107210)
   99.9499.88 ( 0.062500) (lowest bit is 10 ^ -1.204120)
  999.00   998.00 ( 1.00) (lowest bit is 10 ^ 0.00)
 9992.00  9984.00 ( 8.00) (lowest bit is 10 ^ 0.903090)
99936.00 99872.00 (64.00) (lowest bit is 10 ^ 1.806180)


-Original Message-
From: sqlite-users-boun...@sqlite.org [mailto:sqlite-users-boun...@sqlite.org] 
On Behalf Of Black, Michael (IS)
Sent: 04 November 2010 02:51 PM
To: General Discussion of SQLite Database
Subject: Re: [sqlite] R*Tree module and double precision?

I'll send the patched C file to your email address.  I think the 1M patched 
version is a bit much for the email list.
 
Normally you would just use the "patch" utility to apply the patch to your file.
 
Michael D. Black
Senior Scientist
Advanced Analytics Directorate
Northrop Grumman Information Systems
 



From: sqlite-users-boun...@sqlite.org on behalf of 
jsarc...@nanotronicsimaging.com
Sent: Wed 11/3/2010 10:22 AM
To: sqlite-users@sqlite.org
Subject: EXTERNAL:Re: [sqlite] R*Tree module and double precision?



>From: "Black, Michael (IS)" <michael.bla...@ngc.com> I made a patch 
>which seems to do this for you...
>Use this switch to enable double precision on RTREE /DRTREE_DOUBLE

I am interested in this as well.  Will this patch be included in a future 
version of SQLite?  Or, if not, how best to make use of this patch if I 
normally use the amalgamation from C++.
Jeff Archer
Nanotronics Imaging
jsarc...@nanotronicsimaging.com
<330>819.4615
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users


___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] R*Tree module and double precision?

2010-11-04 Thread Black, Michael (IS)

I'll send the patched C file to your email address.  I think the 1M patched 
version is a bit much for the email list.
 
Normally you would just use the "patch" utility to apply the patch to your file.
 
Michael D. Black
Senior Scientist
Advanced Analytics Directorate
Northrop Grumman Information Systems
 



From: sqlite-users-boun...@sqlite.org on behalf of 
jsarc...@nanotronicsimaging.com
Sent: Wed 11/3/2010 10:22 AM
To: sqlite-users@sqlite.org
Subject: EXTERNAL:Re: [sqlite] R*Tree module and double precision?



>From: "Black, Michael (IS)" <michael.bla...@ngc.com>
>I made a patch which seems to do this for you...
>Use this switch to enable double precision on RTREE /DRTREE_DOUBLE

I am interested in this as well.  Will this patch be included in a future
version of SQLite?  Or, if not, how best to make use of this patch if I normally
use the amalgamation from C++.
Jeff Archer
Nanotronics Imaging
jsarc...@nanotronicsimaging.com
<330>819.4615
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users


___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] R*Tree module and double precision?

2010-11-04 Thread jsarcher

>From: "Black, Michael (IS)" 
>I made a patch which seems to do this for you...
>Use this switch to enable double precision on RTREE /DRTREE_DOUBLE

I am interested in this as well.  Will this patch be included in a future 
version of SQLite?  Or, if not, how best to make use of this patch if I 
normally 
use the amalgamation from C++.
Jeff Archer
Nanotronics Imaging
jsarc...@nanotronicsimaging.com
<330>819.4615 
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] R*Tree module and double precision?

2010-11-02 Thread Black, Michael (IS)

I made a patch which seems to do this for you...once in a while it's fun to do 
a bit of programming like this...I didn't do extensive testing on this so you 
may want to do some yourself.
 
It's going to just about double the RTREE size of course.
 
SQLite version 3.7.3
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> CREATE VIRTUAL TABLE demo_index USING rtree(
   ...>id,  -- Integer primary key
   ...>minX, maxX,  -- Minimum and maximum X coordinate
   ...>minY, maxY   -- Minimum and maximum Y coordinate
   ...> );
sqlite> INSERT INTO demo_index VALUES(
   ...> 1,   -- Primary key
   ...> -80.7749, -80.7747,  -- Longitude range
   ...> 30.3776, 30.3778 -- Latitude range
   ...> );
sqlite> INSERT INTO demo_index VALUES(
   ...> 2,
   ...> -81.0, -79.6,
   ...> 35.0, 36.2
   ...> );
sqlite> INSERT INTO demo_index VALUES(3,-80.77491234,-80.77471234,30.37761234,30
.37781234);
sqlite> select * from demo_index;
1|-80.7749|-80.7747|30.3776|30.3778
2|-81.0|-79.6|35.0|36.2
3|-80.77491234|-80.77471234|30.37761234|30.37781234
 
Use this switch to enable double precision on RTREE
/DRTREE_DOUBLE
 
*** ..\..\sqlite3.c Thu Oct 07 22:36:26 2010
--- sqlite3.c Tue Nov 02 10:43:16 2010
***
*** 116902,116909 
--- 116902,116914 
  };
  
  union RtreeCoord {
+ #ifndef RTREE_DOUBLE
float f;
int i;
+ #else
+   double f;
+   u64 i;
+ #endif
  };
  
  /*
***
*** 117006,117011 
--- 117011,117017 
return (p[0]<<8) + p[1];
  }
  static void readCoord(u8 *p, RtreeCoord *pCoord){
+ #ifndef RTREE_DOUBLE
u32 i = (
  (((u32)p[0]) << 24) +
  (((u32)p[1]) << 16) +
***
*** 117013,117018 
--- 117019,117037 
  (((u32)p[3]) <<  0)
);
*(u32 *)pCoord = i;
+ #else
+   u64 i = (
+ (((u64)p[0]) << 56) +
+ (((u64)p[1]) << 48) +
+ (((u64)p[2]) << 40) +
+ (((u64)p[3]) << 32) +
+ (((u64)p[4]) << 24) +
+ (((u64)p[5]) << 16) +
+ (((u64)p[6]) <<  8) +
+ (((u64)p[7]) <<  0)
+   );
+   *(u64 *)pCoord = i;
+ #endif
  }
  static i64 readInt64(u8 *p){
return (
***
*** 117038,117043 
--- 117057,117063 
return 2;
  }
  static int writeCoord(u8 *p, RtreeCoord *pCoord){
+ #ifndef RTREE_DOUBLE
u32 i;
assert( sizeof(RtreeCoord)==4 );
assert( sizeof(u32)==4 );
***
*** 117047,117052 
--- 117067,117087 
p[2] = (i>> 8)&0xFF;
p[3] = (i>> 0)&0xFF;
return 4;
+ #else
+   u64 i;
+   assert( sizeof(RtreeCoord)==8 );
+   assert( sizeof(u64)==8 );
+   i = *(u64 *)pCoord;
+   p[0] = (i>>56)&0xFF;
+   p[1] = (i>>48)&0xFF;
+   p[2] = (i>>40)&0xFF;
+   p[3] = (i>>32)&0xFF;
+   p[4] = (i>>24)&0xFF;
+   p[5] = (i>>16)&0xFF;
+   p[6] = (i>> 8)&0xFF;
+   p[7] = (i>> 0)&0xFF;
+   return 8;
+ #endif
  }
  static int writeInt64(u8 *p, i64 i){
p[0] = (i>>56)&0xFF;
***
*** 117365,117371 
--- 117400,117410 
int iCoord,
RtreeCoord *pCoord   /* Space to write result to */
  ){
+ #ifndef RTREE_DOUBLE
readCoord(>zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], 
pCoord);
+ #else
+   readCoord(>zData[12 + pRtree->nBytesPerCell*iCell + 8*iCoord], 
pCoord);
+ #endif
  }
  
  /*
***
*** 119463,119470 
--- 119502,119514 
  assert( nData==(pRtree->nDim*2 + 3) );
  if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
for(ii=0; ii<(pRtree->nDim*2); ii+=2){
+ #ifndef RTREE_DOUBLE
  cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]);
  cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]);
+ #else
+ cell.aCoord[ii].f = sqlite3_value_double(azData[ii+3]);
+ cell.aCoord[ii+1].f = sqlite3_value_double(azData[ii+4]);
+ #endif
  if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
rc = SQLITE_CONSTRAINT;
goto constraint;
***
*** 119746,119752 
--- 119790,119800 
pRtree->zDb = (char *)[1];
pRtree->zName = >zDb[nDb+1];
pRtree->nDim = (argc-4)/2;
+ #ifndef RTREE_DOUBLE
pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2;
+ #else
+   pRtree->nBytesPerCell = 8 + pRtree->nDim*8*2;
+ #endif
pRtree->eCoordType = eCoordType;
memcpy(pRtree->zDb, argv[1], nDb);
memcpy(pRtree->zName, argv[2], nName);
***
*** 119818,119824 
--- 119866,119877 
memset(, 0, sizeof(RtreeNode));
memset(, 0, sizeof(Rtree));
tree.nDim = sqlite3_value_int(apArg[0]);
+ #ifndef RTREE_DOUBLE
tree.nBytesPerCell = 8 + 8 * tree.nDim;
+ #else
+   tree.nBytesPerCell = 8 + 16 * tree.nDim;
+ #endif
+ 
node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
  
for(ii=0; ii

[sqlite] R*Tree module and double precision?

2010-11-02 Thread Wiebke Timm

Hi everyone,

I want to use an R*tree table in sqlite. Unfortunately, it turned out that
it saves data always as single precision (32-bit) float, no matter what type
is specified. For my application, that is not precise enough. Does anyone
know of an r*tree implementation for sqlite that supports higher precision?
Or is there a patch about somewhere?

Thanks,
   Wiebke
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] R*Tree module and double precision?

Re: [sqlite] R*Tree module and double precision?

Re: [sqlite] R*Tree module and double precision?

Re: [sqlite] R*Tree module and double precision?

Re: [sqlite] R*Tree module and double precision?

[sqlite] R*Tree module and double precision?

6 matches

Site Navigation

Mail list logo

Footer information