>On Mar 27, 2015 11:08 AM, "Dima Ivanovskiy" < dima...@mail.ru > wrote:
>>
>> Hello, I am Dmitrii, student of Moscow Institute of Physics and Technology
>>
>> Abstract:
>>
>> I chose project "Indexing prolonged geometrical objects (i.e. boxes,
>> circles, polygons, not points) with SP-GiST by mapping to 4d-space".
>> According to the presentation
>> https://www.pgcon.org/2011/schedule/attachments/197_pgcon-2011.pdf
>> SP-GIST 3 times faster than GiST in some cases. But GIST supports
>> geometrical data types:
>> box, circle, polygon with operators: && &> &< &<| >> << <<| <@ @> @ |&> |>>
>> ~ ~=
>> Popular spatial extension PostGIS doesn't include SP-GIST, but has a lot of
>> geometrical features.
>>
>> Project details:
>>
>> After meeting with Alexander Korotkov, I wrote some plan.
>> Using of K-D-tree and Quadtree in building index for geometrical data types
>> can increase speed of search in some cases.
>> The main idea is representing 2-D geometrical objects in their bounding box.
>> Set of 2-D boxes is 4-D space.
>> New _ops will work with points from 4-D space, for example kd_box_ops,
>> quad_circle_ops and will support all geometrical operators.
>> After conversion object to their bounding box algo has set of tuples (x1,
>> y1, x2, y2).
>> Our goal is separate this space the most equally. If we talk about K-D-tree,
>> on first step K-D-tree algorithm will split space in 2 parts by the first
>> coordinate, in next step by the second coordinate etc., after 4-th
>> coordinate we repeat this procedure.
>> At the end we have index at geometrical objects and use traversal tree for
>> every search operator.
>>
>> Postgresql has already has realization ideas of MBR in gist/gistproc.c. So I
>> will transfer this realization to other type of tree.
>>
>> Of cource, I assume that SP-GIST can be not the best decision of this
>> problem. So after testing this clear methods, I will try to find more
>> effective way. Maybe with using combination of different spatial tree
>> structures.
>>
>> Project Schedule:
>>
>> until May 25
>>
>> Read documentation and source code, clarify details of implementation.
>>
>> 1st month
>>
>> Implement new '_ops' with all geometrical operators for box, circle, polygon
>>
>> 2nd month
>>
>> Research new methods for increase speed of geometrical query
>>
>> 3rd month
>>
>> Final refactoring, testing and submitting a patch.
>>
>>
>> Links:
>>
>> http://www.sai.msu.su/~megera/postgres/talks/gist_tutorial.html - about GIST
>> https://toster.ru/q/27135#answer_110197 - people need SP-GIST for cubes
>> http://www.slideshare.net/profyclub_ru/o-lt - presentation about indexes
>> http://pgconf.ru/static/presentations/2015/korotkov_spatial.pdf - working
>> with geo objects
>>
>Nice proposal.
>Dynamic Kdtrees can perform badly as the splitting median can get way off as
>updates are coming. What are your thoughts about that?
>Also what's up with the 4d space? I don't quite get it. These types are 2 or 3
>dimensions.
I read spgist README one more time . I didn't find the mechanism for
maintaining good balance after updates.
I think we can use Bkd-Tree,
https://www.cs.duke.edu/~pankaj/publications/papers/bkd-sstd.pdf . But It can
be not the best solving.
I include Research time in 2nd month of timeline.
About 4d space. All these types are 2 dimensional.
Just as i n R-tree object is approximated by MBR. MBR for 2d-objects can be
mapped to 4d-point. More general, nd-object MBR can be mapped into 2nd-point.