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 330819.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?
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 330819.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?
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 330819.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?
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 330819.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
[sqlite] R*Tree module and double precision?
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?
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] = (i56)0xFF; + p[1] = (i48)0xFF; + p[2] = (i40)0xFF; + p[3] = (i32)0xFF; + p[4] = (i24)0xFF; + p[5] = (i16)0xFF; + p[6] = (i 8)0xFF; + p[7] = (i 0)0xFF; + return 8; + #endif } static int writeInt64(u8 *p, i64 i){ p[0] = (i56)0xFF; *** *** 117365,117371 --- 117400,117410 int iCoord, RtreeCoord *pCoord /* Space to write result to */ ){ + #ifndef RTREE_DOUBLE readCoord(pNode-zData[12 + pRtree-nBytesPerCell*iCell + 4*iCoord], pCoord); + #else + readCoord(pNode-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].fcell.aCoord[ii+1].f ){ rc = SQLITE_CONSTRAINT; goto constraint; *** *** 119746,119752 --- 119790,119800 pRtree-zDb = (char *)pRtree[1]; pRtree-zName = pRtree-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(node, 0, sizeof(RtreeNode)); memset(tree, 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; iiNCELL(node); ii++){ Michael D. Black Senior Scientist Advanced Analytics Directorate Northrop Grumman Information Systems ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users