Re: AW: AW: [sqlite] Re: spatial sqlite anyone ?
Martin Pfeifle wrote: Hello Noel, I think you can find more information on the computation of the upper hull values in [FFS00] "Implementing Geospatial Operations in an Object-Relational Database System". Yes I'm already reading that. For testing, we used oracle, where we had transient tables. I am not sure whether we have transient memory tables in SQLite. If yes, you can use them. I think sqlite has it The simple box elimination always goes along with a full table scan. Assume you have the polygons of complete Europe in your database and you do a selective spatial query, you still have to evaluate all bounding boxes of all polygons. In that case a hierarchical organization of the data, e.g. by the Relational Quadtree or the Relational R-tree, is certainly much more efficient. If you always select let's say more than 10% of all polygons, then the box filtering might be enough. I'm going to use the quadtree approach, will see if its already usable Do you already have working code on sqlite ? Best regards Best Martin - Ursprüngliche Mail Von: Noel Frankinet <[EMAIL PROTECTED]> An: sqlite-users@sqlite.org Gesendet: Freitag, den 19. Mai 2006, 09:38:13 Uhr Betreff: Re: AW: [sqlite] Re: spatial sqlite anyone ? Martin Pfeifle wrote: Hi, I think the simplest solution would be to put a spatial index on top of the B-tree, that's what e.g. Oracle does in their Spatial Cartridge. Basically you store the index data in relations and index these relations by B-trees. In this case, you do not have to change the core code of SQLite. You can already do this now. Nevertheless, it would be nice, if SQlite supports somehow the "extensible indexing interface". So, you ask a spatial query and in the background the system uses the index data stored in relations. We have done a lot of research on that topic. To get acquainted to the basic idea, you might have a look at "The Paradigm of Relational Indexing: A Survey". In my opinion, a direct integration of a spatial index is of course preferable, but who is going to do that? Best Martin Hello Martin, hello All, Thank you for the above link, it is very useful. I definitely want to go the spatial index map to btree index way. I especially like the quad-tree select because I understand it and I already have most of the building blocks : SELECT DISTINCT idx.id FROM polygons_quadtree idx, TABLE(ZDecompose(BOX()) titles, Table(ZupperHull(tiles.zval)) uh WHERE (idx.zval BETWEEN tiles.zval AND ZHi(tiles.zval)) OR (idx.zval = uh.zval); Well almost, I know how to make ZDecompose, I still not sure about ZHi, ZUpperHul, do you have any more pointers ? I didn't konw the TABLE statement to return a pseudo table, unfortunately, it seems not available in sqlite, can it be emulated by a transient memory table ? Do you think that such a complex statement has any chance to be speedier than a simple bbox elimination ? Thanks again, Best regards -- Noël Frankinet Gistek Software SA http://www.gistek.net
Re: AW: [sqlite] Re: spatial sqlite anyone ?
Martin Pfeifle wrote: Hi, I think the simplest solution would be to put a spatial index on top of the B-tree, that's what e.g. Oracle does in their Spatial Cartridge. Basically you store the index data in relations and index these relations by B-trees. In this case, you do not have to change the core code of SQLite. You can already do this now. Nevertheless, it would be nice, if SQlite supports somehow the "extensible indexing interface". So, you ask a spatial query and in the background the system uses the index data stored in relations. We have done a lot of research on that topic. To get acquainted to the basic idea, you might have a look at "The Paradigm of Relational Indexing: A Survey". In my opinion, a direct integration of a spatial index is of course preferable, but who is going to do that? Best Martin Hello Martin, hello All, Thank you for the above link, it is very useful. I definitely want to go the spatial index map to btree index way. I especially like the quad-tree select because I understand it and I already have most of the building blocks : SELECT DISTINCT idx.id FROM polygons_quadtree idx, TABLE(ZDecompose(BOX()) titles, Table(ZupperHull(tiles.zval)) uh WHERE (idx.zval BETWEEN tiles.zval AND ZHi(tiles.zval)) OR (idx.zval = uh.zval); Well almost, I know how to make ZDecompose, I still not sure about ZHi, ZUpperHul, do you have any more pointers ? I didn't konw the TABLE statement to return a pseudo table, unfortunately, it seems not available in sqlite, can it be emulated by a transient memory table ? Do you think that such a complex statement has any chance to be speedier than a simple bbox elimination ? Thanks again, Best regards -- Noël Frankinet Gistek Software SA http://www.gistek.net
Re: AW: AW: [sqlite] Re: spatial sqlite anyone ?
Martin Pfeifle wrote: Hi, the baisc idea of the Relational R-tree is to map the hierarchical relationship between the R-tree nodes to a (father, son) relation where a b-tree is on father. You can the traverse the relation preferable using recursive SQL, if not available, you have to do it on your own. The Idea of the Relational Quadtree is to select the Quad numbers according to a space filling curve,e.g. z-values. that's what I had in mind, mapping a quadtree key to an integer key (I have seen something about morton code). However I still get a key set, what kind of sql may I use to avoid one by one select ? Do you have any pointer for that ? Then again you can use ordinary SQL. - Ursprüngliche Mail Von: Noel Frankinet <[EMAIL PROTECTED]> An: sqlite-users@sqlite.org Gesendet: Donnerstag, den 18. Mai 2006, 09:50:56 Uhr Betreff: Re: AW: [sqlite] Re: spatial sqlite anyone ? Martin Pfeifle wrote: Hi, I think the simplest solution would be to put a spatial index on top of the B-tree, that's what e.g. Oracle does in their Spatial Cartridge. Basically you store the index data in relations and index these relations by B-trees. In this case, you do not have to change the core code of SQLite. You can already do this now. Nevertheless, it would be nice, if SQlite supports somehow the "extensible indexing interface". So, you ask a spatial query and in the background the system uses the index data stored in relations. We have done a lot of research on that topic. To get acquainted to the basic idea, you might have a look at "The Paradigm of Relational Indexing: A Survey". In my opinion, a direct integration of a spatial index is of course preferable, but who is going to do that? Best Martin Not me, Thank you for the article, If I get the key from the quadtree/rtree index, what is the way to get the data while staying "on top" of sqlite ? If can see the following schema: select data according to normal sql rule (all the non spatial rules) then filter it spatailly (that's what I do now, simple bbox filtering, no indice). I would prefer the other way around, use spatial index, get a subset (a key set ?) then apply sql alphanumerical filter. Do you know a way to do that in sqlite ? Best regards - Ursprüngliche Mail Von: George Ionescu <[EMAIL PROTECTED]> An: sqlite-users@sqlite.org Gesendet: Donnerstag, den 18. Mai 2006, 08:28:39 Uhr Betreff: [sqlite] Re: spatial sqlite anyone ? Hello dear Noel, hello all sqlite users, a spatial extension for sqlite would be nice, although I think that replacing the indexing scheme (e.g. replace the current b-tree with a quad-tree or another spatial index) is alot of work. Just some questions / thoughts: 1. How would you handle indexing? Would you replace completely the btree with a spatial index (the hardest thing to do)? And if so, btree indexing would still be available or not? 2. Go for GEOS's STRTree. It's the fastest spatial index I could find (I did some research awhile ago on open-source solutions regarding spatial indexes). 3. You might want to take a look at SpatialIndex (http://u-foria.org/marioh/spatialindex/). The library is pretty clever designed and it supports RSTAR-tree, MVR-tree and TPR-tree. The problem I found with this library was that it was slower than GEOS at the time I last checked. One of the features I like is that it allows persisting the index. This might be an intermediate solution: you could store the index as a blob in the database. It would not be very efficient (as efficient as replacing indexing) but it would be a place to start. 4. Another nice library who might do the job is CGAL (http://www.cgal.org/). I didn't benchmarked it mostly because GEOS suited my needs just fine, but how knows, it might be better than the ones I mentioned. George. -- Noël Frankinet Gistek Software SA http://www.gistek.net
AW: AW: [sqlite] Re: spatial sqlite anyone ?
Hi, the baisc idea of the Relational R-tree is to map the hierarchical relationship between the R-tree nodes to a (father, son) relation where a b-tree is on father. You can the traverse the relation preferable using recursive SQL, if not available, you have to do it on your own. The Idea of the Relational Quadtree is to select the Quad numbers according to a space filling curve,e.g. z-values. Then again you can use ordinary SQL. - Ursprüngliche Mail Von: Noel Frankinet <[EMAIL PROTECTED]> An: sqlite-users@sqlite.org Gesendet: Donnerstag, den 18. Mai 2006, 09:50:56 Uhr Betreff: Re: AW: [sqlite] Re: spatial sqlite anyone ? Martin Pfeifle wrote: >Hi, >I think the simplest solution would be to put a spatial index on top of the >B-tree, that's what e.g. Oracle does in their Spatial Cartridge. >Basically you store the index data in relations and index these relations by >B-trees. >In this case, you do not have to change the core code of SQLite. You can >already do this now. >Nevertheless, it would be nice, if SQlite supports somehow the "extensible >indexing interface". >So, you ask a spatial query and in the background the system uses the index >data stored in relations. >We have done a lot of research on that topic. To get acquainted to the basic >idea, you might have a look at >"The Paradigm of Relational Indexing: A Survey". > >In my opinion, a direct integration of a spatial index is of course >preferable, but who is going to do that? > >Best Martin > > > Not me, Thank you for the article, If I get the key from the quadtree/rtree index, what is the way to get the data while staying "on top" of sqlite ? If can see the following schema: select data according to normal sql rule (all the non spatial rules) then filter it spatailly (that's what I do now, simple bbox filtering, no indice). I would prefer the other way around, use spatial index, get a subset (a key set ?) then apply sql alphanumerical filter. Do you know a way to do that in sqlite ? Best regards >- Ursprüngliche Mail >Von: George Ionescu <[EMAIL PROTECTED]> >An: sqlite-users@sqlite.org >Gesendet: Donnerstag, den 18. Mai 2006, 08:28:39 Uhr >Betreff: [sqlite] Re: spatial sqlite anyone ? > > >Hello dear Noel, >hello all sqlite users, > >a spatial extension for sqlite would be nice, although I think that >replacing the indexing scheme (e.g. replace the current b-tree with a >quad-tree or another spatial index) is alot of work. > >Just some questions / thoughts: > >1. How would you handle indexing? Would you replace completely the btree >with a spatial index (the hardest thing to do)? And if so, btree indexing >would still be available or not? > >2. Go for GEOS's STRTree. It's the fastest spatial index I could find (I did >some research awhile ago on open-source solutions regarding spatial >indexes). > >3. You might want to take a look at SpatialIndex >(http://u-foria.org/marioh/spatialindex/). The library is pretty clever >designed and it supports RSTAR-tree, MVR-tree and TPR-tree. The problem I >found with this library was that it was slower than GEOS at the time I last >checked. One of the features I like is that it allows persisting the index. >This might be an intermediate solution: you could store the index as a blob >in the database. It would not be very efficient (as efficient as replacing >indexing) but it would be a place to start. > >4. Another nice library who might do the job is CGAL (http://www.cgal.org/). >I didn't benchmarked it mostly because GEOS suited my needs just fine, but >how knows, it might be better than the ones I mentioned. > >George. > > > > -- Noël Frankinet Gistek Software SA http://www.gistek.net
Re: AW: [sqlite] Re: spatial sqlite anyone ?
Martin Pfeifle wrote: Hi, I think the simplest solution would be to put a spatial index on top of the B-tree, that's what e.g. Oracle does in their Spatial Cartridge. Basically you store the index data in relations and index these relations by B-trees. In this case, you do not have to change the core code of SQLite. You can already do this now. Nevertheless, it would be nice, if SQlite supports somehow the "extensible indexing interface". So, you ask a spatial query and in the background the system uses the index data stored in relations. We have done a lot of research on that topic. To get acquainted to the basic idea, you might have a look at "The Paradigm of Relational Indexing: A Survey". In my opinion, a direct integration of a spatial index is of course preferable, but who is going to do that? Best Martin Not me, Thank you for the article, If I get the key from the quadtree/rtree index, what is the way to get the data while staying "on top" of sqlite ? If can see the following schema: select data according to normal sql rule (all the non spatial rules) then filter it spatailly (that's what I do now, simple bbox filtering, no indice). I would prefer the other way around, use spatial index, get a subset (a key set ?) then apply sql alphanumerical filter. Do you know a way to do that in sqlite ? Best regards - Ursprüngliche Mail Von: George Ionescu <[EMAIL PROTECTED]> An: sqlite-users@sqlite.org Gesendet: Donnerstag, den 18. Mai 2006, 08:28:39 Uhr Betreff: [sqlite] Re: spatial sqlite anyone ? Hello dear Noel, hello all sqlite users, a spatial extension for sqlite would be nice, although I think that replacing the indexing scheme (e.g. replace the current b-tree with a quad-tree or another spatial index) is alot of work. Just some questions / thoughts: 1. How would you handle indexing? Would you replace completely the btree with a spatial index (the hardest thing to do)? And if so, btree indexing would still be available or not? 2. Go for GEOS's STRTree. It's the fastest spatial index I could find (I did some research awhile ago on open-source solutions regarding spatial indexes). 3. You might want to take a look at SpatialIndex (http://u-foria.org/marioh/spatialindex/). The library is pretty clever designed and it supports RSTAR-tree, MVR-tree and TPR-tree. The problem I found with this library was that it was slower than GEOS at the time I last checked. One of the features I like is that it allows persisting the index. This might be an intermediate solution: you could store the index as a blob in the database. It would not be very efficient (as efficient as replacing indexing) but it would be a place to start. 4. Another nice library who might do the job is CGAL (http://www.cgal.org/). I didn't benchmarked it mostly because GEOS suited my needs just fine, but how knows, it might be better than the ones I mentioned. George. -- Noël Frankinet Gistek Software SA http://www.gistek.net
AW: [sqlite] Re: spatial sqlite anyone ?
Hi, I think the simplest solution would be to put a spatial index on top of the B-tree, that's what e.g. Oracle does in their Spatial Cartridge. Basically you store the index data in relations and index these relations by B-trees. In this case, you do not have to change the core code of SQLite. You can already do this now. Nevertheless, it would be nice, if SQlite supports somehow the "extensible indexing interface". So, you ask a spatial query and in the background the system uses the index data stored in relations. We have done a lot of research on that topic. To get acquainted to the basic idea, you might have a look at "The Paradigm of Relational Indexing: A Survey". In my opinion, a direct integration of a spatial index is of course preferable, but who is going to do that? Best Martin - Ursprüngliche Mail Von: George Ionescu <[EMAIL PROTECTED]> An: sqlite-users@sqlite.org Gesendet: Donnerstag, den 18. Mai 2006, 08:28:39 Uhr Betreff: [sqlite] Re: spatial sqlite anyone ? Hello dear Noel, hello all sqlite users, a spatial extension for sqlite would be nice, although I think that replacing the indexing scheme (e.g. replace the current b-tree with a quad-tree or another spatial index) is alot of work. Just some questions / thoughts: 1. How would you handle indexing? Would you replace completely the btree with a spatial index (the hardest thing to do)? And if so, btree indexing would still be available or not? 2. Go for GEOS's STRTree. It's the fastest spatial index I could find (I did some research awhile ago on open-source solutions regarding spatial indexes). 3. You might want to take a look at SpatialIndex (http://u-foria.org/marioh/spatialindex/). The library is pretty clever designed and it supports RSTAR-tree, MVR-tree and TPR-tree. The problem I found with this library was that it was slower than GEOS at the time I last checked. One of the features I like is that it allows persisting the index. This might be an intermediate solution: you could store the index as a blob in the database. It would not be very efficient (as efficient as replacing indexing) but it would be a place to start. 4. Another nice library who might do the job is CGAL (http://www.cgal.org/). I didn't benchmarked it mostly because GEOS suited my needs just fine, but how knows, it might be better than the ones I mentioned. George.
