Thread

1. RE: [HACKERS] Indexing for geographic objects?

   Franck Martin <franck@sopac.org> — 2000-11-26T23:06:21Z

   It seems that your code is exactly what I want.
   
   I have already created geographical objects which contains MBR(Minimum
   Bounding Rectangle) in their structure, so it is a question of rewriting
   your code to change the access to the cube structure to the MBR structure
   inside my geoobject. (cf http://fmaps.sourceforge.net/) Look in the CVS for
   latest. I have been slack lately on the project, but I'm not forgetting it.
   
   Quickly I ran through the code, and I think your cube is strictly speaking a
   box, which also a MBR.
   
   However I didn't see the case of intersection, which is the main question
   when you want to display object that are visible inside a box.
   
   I suppose your code is under GPL, and you have no problem for me to use it,
   providing I put your name and credits somewhere.
   
   Cheers.
   
   Franck Martin
   Database Development Officer
   SOPAC South Pacific Applied Geoscience Commission
   Fiji
   E-mail: franck@sopac.org
   Web site: http://www.sopac.org/
   
   This e-mail is intended for its recipients only. Do not forward this e-mail
   without approval. The views expressed in this e-mail may not be necessarily
   the views of SOPAC.
   
   -----Original Message-----
   From: selkovjr@mcs.anl.gov [mailto:selkovjr@mcs.anl.gov]
   Sent: Saturday, 25 November 2000 8:56 
   To: Franck Martin
   Subject: Re: [HACKERS] Indexing for geographic objects? 
   
   It is probably possible to hook up an extension directly with the
   R-tree methods available in postgres -- if you stare at the code long
   enough and figure how to use the correct strategies. I chose an easier
   path years ago and I am still satisfied with the results. Check out
   the GiST -- a general access method built on top of R-tree to provide
   a user-friendly interface to it and to allow indexing of more abstract
   types, for which straight R-tree is not directly applicable.
   
   I have a small set of complete data types, of which a couple
   illustrate the use of GiST indexing with the geometrical objects, in:
   
   http://wit.mcs.anl.gov/~selkovjr/pg_extensions/
   
   If you are using a pre-7.0 postrgres, grab the file contrib.tgz,
   otherwise take contrib-7.0.tgz. The difference is insignificant, but
   the pre-7.0 version will not fit the current schema. Unpack the source
   into postgresql-*/contrib and follow instructions in the README
   files. The types of interest for you will be seg and cube. You will
   find pointers to the original sources and docs in the CREDITS section
   of the README file. I also have a version of the original example code
   in pggist-patched.tgz, but I did not check if it works with current
   postgres. It should not be difficult to fix it if it doesn't -- the
   recent development in the optimizer area made certain things
   unnecessary.
   
   You might want to check out a working example of the segment data type at:
   
   http://wit.mcs.anl.gov/EMP/indexing.html
   
   (search the page for 'KM')
   
   I will be glad to help, but I would also recommend to send more
   sophisticated questions to Joe Hellerstein, the leader of the original
   postgres team that developed GiST. He was very helpful whenever I
   turned to him during the early stages of my data type project.
   
   --Gene
   
   

2. Re: [HACKERS] Indexing for geographic objects?

   Hannu Krosing <hannu@tm.ee> — 2000-11-27T11:21:57Z

   Franck Martin wrote:
   > 
   > It seems that your code is exactly what I want.
   > 
   > I have already created geographical objects which contains MBR(Minimum
   > Bounding Rectangle) in their structure, so it is a question of rewriting
   > your code to change the access to the cube structure to the MBR structure
   > inside my geoobject. (cf http://fmaps.sourceforge.net/) Look in the CVS for
   > latest. I have been slack lately on the project, but I'm not forgetting it.
   > 
   > Quickly I ran through the code, and I think your cube is strictly speaking a
   > box, which also a MBR.
   > 
   > However I didn't see the case of intersection, which is the main question
   > when you want to display object that are visible inside a box.
   > 
   > I suppose your code is under GPL, and you have no problem for me to use it,
   > providing I put your name and credits somewhere.
   
   It would be much better if it were under the standard PostgreSQL license
   and 
   if it is included in the standard distribution. 
   
   As Tom said, working Gist would be a great feature. 
   
   Now if only someone would write the regression tests ;)
   
   BTW, the regression tests for pl/pgsql seem to be somewhat sparse as
   well, 
   missing at least some types of loops, possibly more.
   
   > Franck Martin
   > Database Development Officer
   > SOPAC South Pacific Applied Geoscience Commission
   > Fiji
   > E-mail: franck@sopac.org
   > Web site: http://www.sopac.org/
   > 
   > This e-mail is intended for its recipients only. Do not forward this e-mail
   > without approval. The views expressed in this e-mail may not be necessarily
   > the views of SOPAC.
   > 
   > -----Original Message-----
   > From: selkovjr@mcs.anl.gov [mailto:selkovjr@mcs.anl.gov]
   > Sent: Saturday, 25 November 2000 8:56
   > To: Franck Martin
   > Subject: Re: [HACKERS] Indexing for geographic objects?
   > 
   > It is probably possible to hook up an extension directly with the
   > R-tree methods available in postgres -- if you stare at the code long
   > enough and figure how to use the correct strategies. I chose an easier
   > path years ago and I am still satisfied with the results. Check out
   > the GiST -- a general access method built on top of R-tree to provide
   > a user-friendly interface to it and to allow indexing of more abstract
   > types, for which straight R-tree is not directly applicable.
   > 
   > I have a small set of complete data types, of which a couple
   > illustrate the use of GiST indexing with the geometrical objects, in:
   > 
   > http://wit.mcs.anl.gov/~selkovjr/pg_extensions/
   > 
   > If you are using a pre-7.0 postrgres, grab the file contrib.tgz,
   > otherwise take contrib-7.0.tgz. The difference is insignificant, but
   > the pre-7.0 version will not fit the current schema. Unpack the source
   > into postgresql-*/contrib and follow instructions in the README
   > files. The types of interest for you will be seg and cube. You will
   > find pointers to the original sources and docs in the CREDITS section
   > of the README file. I also have a version of the original example code
   > in pggist-patched.tgz, but I did not check if it works with current
   > postgres. It should not be difficult to fix it if it doesn't -- the
   > recent development in the optimizer area made certain things
   > unnecessary.
   > 
   > You might want to check out a working example of the segment data type at:
   > 
   > http://wit.mcs.anl.gov/EMP/indexing.html
   > 
   > (search the page for 'KM')
   > 
   > I will be glad to help, but I would also recommend to send more
   > sophisticated questions to Joe Hellerstein, the leader of the original
   > postgres team that developed GiST. He was very helpful whenever I
   > turned to him during the early stages of my data type project.
   > 
   > --Gene
   
   

3. Re: [HACKERS] Indexing for geographic objects?

   selkovjr@mcs.anl.gov — 2000-11-28T00:03:33Z

   Franck Martin wrote:
   > I have already created geographical objects which contains MBR(Minimum
   > Bounding Rectangle) in their structure, so it is a question of rewriting
   > your code to change the access to the cube structure to the MBR structure
   > inside my geoobject. (cf http://fmaps.sourceforge.net/) Look in the CVS for
   > latest. I have been slack lately on the project, but I'm not forgetting it.
   
   I see where you are aiming. I definitely want to be around when it
   starts working.
   
   > Quickly I ran through the code, and I think your cube is strictly speaking a
   > box, which also a MBR.
   
   Yes, cube is definitely a misnomer -- it suggests things are
   equihedral, which they aren't. I am still looking for a short name or
   an acronym that would indicate it is a box with an arbitrary number of
   dimensions. With your application, you will surely benefit from a
   smaller and faster code geared specifically for 3D.
   
   > However I didn't see the case of intersection, which is the main question
   > when you want to display object that are visible inside a box.
   
   The procedure is there, it is called cube_inter, but there is no
   operator for it.
    
   > I suppose your code is under GPL, and you have no problem for me to use it,
   > providing I put your name and credits somewhere.
   
   No problem at all -- I will be honored if you use it. Was I careless
   enough not to include a license? It's not exactly a GPL -- it's
   completely unrestricted. I should have said that somewhere.
   
   Good luck,
   
   --Gene
   
   

4. Re: Indexing for geographic objects?

   Nathan Myers <ncm@zembu.com> — 2000-11-28T01:56:37Z

   On Mon, Nov 27, 2000 at 06:03:33PM -0600, selkovjr@mcs.anl.gov wrote:
   > Franck Martin wrote:
   > > I suppose your code is under GPL, and you have no problem for me to
   > > use it, providing I put your name and credits somewhere.
   > 
   > No problem at all -- I will be honored if you use it. Was I careless
   > enough not to include a license? It's not exactly a GPL -- it's
   > completely unrestricted. I should have said that somewhere.
   
   Note that (AIUI) placing code in the public domain leaves you liable 
   for damages from somebody misusing it.  You have to retain copyright 
   just to be able to disclaim liability, in the license -- but then you 
   need to actually have a license.  That's why you don't see much public 
   domain software.  (I am not a lawyer.)
   
   Nathan Myers
   ncm@zembu.com
   
   

5. RE: [HACKERS] Indexing for geographic objects?

   Edmar Wiggers <edmar@brasmap.com> — 2000-12-05T13:31:29Z

   It seems that R-trees become inefficient when the number of dimensions
   increase. Has anyone thoght of a transparent way to use Peano codes (hhcode
   in Oracle lingo), and use B-tree indexes instead?
   
   Also, I've read that R-trees sometimes suffer a lot when an update overflows
   a node in the index.
   
   The only initial problem I see with Peano codes is that the index is made on
   real cubes (all dimensions are equal, due to the recursive decomposition of
   space). To overcome that, people have talked about using
   multiple-entry-indexes. That is, an object is decomposed in a number of
   cubes (not too many), which are then indexed.
   
   In this case, there should be a way to make intersection searches be
   transparent. Oracle does it using tables and merge-joins. I have thought of
   using GiST to do that, but it seemed too advanced for me yet.
   
   So I thought of using the Oracle technique (make tables and use joins).
   Problem: I would need a C function to make the cubes describing an spatial
   object, but currently C functions cannot return more than one value (have of
   thoght of returning an array, but have not tried it). And making inserts
   directly from a C function has been described as magic stuff in the
   documentation.
   
   Yours sincerely,
   
   Edmar Wiggers
   BRASMAP Information Systems
   +55 48 9960 2752
   
   
   

6. Re: [GENERAL] RE: Indexing for geographic objects?

   Bernard Frankpitt <frankpit@erols.com> — 2000-12-06T07:43:05Z

   Edmar Wiggers wrote:
   > 
   > It seems that R-trees become inefficient when the number of dimensions
   > increase. Has anyone thoght of a transparent way to use Peano codes (hhcode
   > in Oracle lingo), and use B-tree indexes instead?
   > 
   
   Do you have a reference, or more information on what a Peano code is?
   
   Bernie
   
   

7. RE: [HACKERS] Indexing for geographic objects?

   Edmar Wiggers <edmar@brasmap.com> — 2000-12-06T11:58:39Z

   > Do you have a reference, or more information on what a Peano code is?
   
   Check this out http://www.statkart.no/nlhdb/iveher/hhtext.htm
   
   Shortly, this technique relies on a space filling curve. That is, a
   uni-dimensional curve that, on a given plane, covers every single point, and
   only covers it once. Since the curve is 1-dimensional, one can use B-tree
   indexes on it.
   
   There a number of curves of this type, e.g. Hilbert's and Peano's. The Peano
   curve yelds easier calculations, hence is the one Oracle used to make their
   Spatial Data Option.
   
   Moreover, the Peano curve describes a point in an helical kind of way,
   recursively dividing space. That's why the Norwegian Hydrographic Service
   decided to call it "Helical Hyperspatial Codes" (hhcodes). It was from their
   research that Oracle Spatial Data Option was born, back in 1995.
   
   I'm not sure about the exact applicability of hhcodes to index multimedia
   stuff yet (images, sound), because those are VERY high-dimensional spaces.
   But I've done quite some reading/research, and hhcodes have two very nice
   advantages over R-trees:
   
   - it is easy (and not costly in performance), to index things in 3D or 4D
   (including time too);
   - concurrency is much better, because one does not suffer from costly R-tree
   updates (B-trees are much better in that). When dealing with 3D or 4D, this
   becomes even more important.
   
   By the way, are you Brazilian Bernard? Oddly enough, maybe we live in the
   very same city. Florianopolis, SC, Brazil. It's a small world he? :))