> On 22 Mar 2016, at 01:47, Jim Nasby <jim.na...@bluetreble.com> wrote:
> On 3/21/16 11:57 AM, Teodor Sigaev wrote:
>> A and B are points of intersection of lines. So, box PBCAis a bounding
>> box for points contained in 3-rd (see labeling above). For example X
>> labeled point is not a descendace of child node with centroid  C because
>> it must be in branch of 1-st quad of parent node. So, each node (except
>> root) will have a limitation in its quadrant. To transfer that
>> limitation the traversalValue is used.
> Isn't this basically the same thing that the cube contrib module does? (Which 
> has the added benefit of kNN-capable operators).

Cube and postgres own geometric types are indexed by building R-tree. While 
this is one of the most popular solutions it
degrades almost to linear search when bounding boxes for each index node 
overlaps a lot. This problem will arise when one will
try to index streets in the city with grid system — a lot of street's bounding 
boxes will just coincide with bounding box for whole city.

But that patch use totally different strategy for building index and do not 
suffer from above problem.

> If that's true then ISTM it'd be better to work on pulling cube's features 
> into box?
> If it's not true, I'm still wondering if there's enough commonality here that 
> we should pull cube into core…

There is also intarray module with very common functionality, but it also 
addressing different data pattern.

Optimal indexing and kNN strategy are very sensible to the data itself and if 
we want some general multidimensional search routines,
then I think none of the mentioned extensions is general enough. Cube barely 
applicable when dimensions number is higher than 10-20,
intarray performs bad on data with big sets of possible coordinates, this patch 
is also intended to help with specific, niche problem.

While people tends to use machine learning and regressions models more and more 
it is interesting to have some general n-dim indexing with kNN,
but I think it is different problem and should be solved in a different way.

Stas Kelvich
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:

Reply via email to