> On 22 Mar 2016, at 01:47, Jim Nasby <Jim.Nasby@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
onewill
try to index streets in the city with grid system — a lot of street's bounding boxes will just coincide with bounding
boxfor 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
searchroutines,
then I think none of the mentioned extensions is general enough. Cube barely applicable when dimensions number is
higherthan 10-20,
intarray performs bad on data with big sets of possible coordinates, this patch is also intended to help with specific,
nicheproblem.
While people tends to use machine learning and regressions models more and more it is interesting to have some general
n-dimindexing 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