pg.ddx.io  pgsql-students@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Dima Ivanovskiy <dima-iv@mail.ru>
To: pgsql-students@postgresql.org
Subject:  GSOC: Ivanovskii Dmitrii, new detail of proposal
Date: Wed, 25 Mar 2015 01:34:54 +0300
Message-ID: <1427236494.368174906@f30.i.mail.ru> (raw)
List-Unsubscribe:  <mailto:majordomo@postgresql.org?body=unsub%20pgsql-students>


I chose project "Indexing prolonged geometrical objects (i.e. boxes, circles, polygons, not points) with SP-GiST by mapping to 4d-space".

After meeting with Alexander Korotkov, I wrote some plan. What are postgresql developers thinking about it?

According to the  presentation 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.
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.

Message-ID: <1427236494.368174906@f30.i.mail.ru>
Permalink:  ../1427236494.368174906@f30.i.mail.ru/
Also on:    postgresql.org/message-id/1427236494.368174906@f30.i.mail.ru

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-students@postgresql.org
  Cc: dima-iv@mail.ru
  Subject: Re: GSOC: Ivanovskii Dmitrii, new detail of proposal
  In-Reply-To: <1427236494.368174906@f30.i.mail.ru>
  References: <1427236494.368174906@f30.i.mail.ru>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox