Re: GSoC 2015: SP-GIST for geometrical objects

<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 />