Re: GSoC 2015: SP-GIST for geometrical objects - Mailing list pgsql-hackers
From | Arthur Silva |
---|---|
Subject | Re: GSoC 2015: SP-GIST for geometrical objects |
Date | |
Msg-id | CAO_YK0Wv1-7DFS2ai688fgNJXCQMxUNnL7b1rbE-jwchNCWmZQ@mail.gmail.com Whole thread Raw |
In response to | GSoC 2015: SP-GIST for geometrical objects (Dima Ivanovskiy <dima-iv@mail.ru>) |
Responses |
Re[2]: [HACKERS] GSoC 2015: SP-GIST for geometrical objects
|
List | pgsql-hackers |
<p dir="ltr"><br /> On Mar 27, 2015 11:08 AM, "Dima Ivanovskiy" <<a href="mailto:dima-iv@mail.ru">dima-iv@mail.ru</a>>wrote:<br /> ><br /> > Hello, I am Dmitrii, student of MoscowInstitute of Physics and Technology<br /> ><br /> > Abstract:<br /> ><br /> > I chose project "Indexingprolonged geometrical objects (i.e. boxes, circles, polygons, not points) with SP-GiST by mapping to 4d-space".<br /> > According to the presentation<br /> > <a href="https://www.pgcon.org/2011/schedule/attachments/197_pgcon-2011.pdf">https://www.pgcon.org/2011/schedule/attachments/197_pgcon-2011.pdf</a><br />> SP-GIST 3 times faster than GiST in some cases. But GIST supports geometrical data types: <br /> > box, circle,polygon with operators: && &> &< &<| >> << <<| <@ @> @ |&>|>> ~ ~=<br /> > Popular spatial extension PostGIS doesn't include SP-GIST, but has a lot of geometricalfeatures.<br /> ><br /> > Project details:<br /> ><br /> > After meeting with Alexander Korotkov,I wrote some plan. <br /> > Using of K-D-tree and Quadtree in building index for geometrical data types can increasespeed of search in some cases.<br /> > The main idea is representing 2-D geometrical objects in their boundingbox. Set of 2-D boxes is 4-D space. <br /> > New _ops will work with points from 4-D space, for example kd_box_ops,quad_circle_ops and will support all geometrical operators. <br /> > After conversion object to their boundingbox algo has set of tuples (x1, y1, x2, y2). <br /> > Our goal is separate this space the most equally. If wetalk about K-D-tree, on first step K-D-tree algorithm will split space in 2 parts by the first coordinate, in next stepby the second coordinate etc., after 4-th coordinate we repeat this procedure. <br /> > At the end we have index atgeometrical objects and use traversal tree for every search operator. <br /> ><br /> > Postgresql has already hasrealization ideas of MBR in gist/gistproc.c. So I will transfer this realization to other type of tree.<br /> ><br/> > Of cource, I assume that SP-GIST can be not the best decision of this problem. So after testing this clearmethods, I will try to find more effective way. Maybe with using combination of different spatial tree structures.<br/> ><br /> > Project Schedule:<br /> ><br /> > until May 25<br /> ><br /> > Read documentationand source code, clarify details of implementation.<br /> ><br /> > 1st month<br /> ><br /> > Implementnew '_ops' with all geometrical operators for box, circle, polygon<br /> ><br /> > 2nd month<br /> ><br/> > Research new methods for increase speed of geometrical query<br /> ><br /> > 3rd month<br /> ><br/> > Final refactoring, testing and submitting a patch.<br /> ><br /> ><br /> > Links:<br /> ><br />> <a href="http://www.sai.msu.su/~megera/postgres/talks/gist_tutorial.html">http://www.sai.msu.su/~megera/postgres/talks/gist_tutorial.html</a> -about GIST<br /> > <a href="https://toster.ru/q/27135#answer_110197">https://toster.ru/q/27135#answer_110197</a> - peopleneed SP-GIST for cubes<br /> > <a href="http://www.slideshare.net/profyclub_ru/o-lt">http://www.slideshare.net/profyclub_ru/o-lt</a>- presentation about indexes<br/> > <a href="http://pgconf.ru/static/presentations/2015/korotkov_spatial.pdf">http://pgconf.ru/static/presentations/2015/korotkov_spatial.pdf</a> -working with geo objects<br /> ><br /> Nice proposal. <p dir="ltr">Dynamic Kdtrees can perform badly as the splittingmedian can get way off as updates are coming. What are your thoughts about that? <p dir="ltr">Also what's up withthe 4d space? I don't quite get it. These types are 2 or 3 dimensions. <br />
pgsql-hackers by date: