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

Reply via email to