|
On 11/05/2015 04:56 AM, Achilleas
Mantzios wrote:
On 04/11/2015 17:53, Rob Sargent
wrote:
On 11/04/2015 03:03 AM, Achilleas
Mantzios wrote:
Sorry for being kind of late to
the party (I was in 2015.PgConf.EU !!), and not having read
most of the replies, what we have been successfully doing
for this problem for our app
is do it this way :
parents int[] -- where parents stores the path from the node
to the root of the tree
and then have those indexes :
btree (first(parents))
btree (level(parents)) -- length
btree (last(parents))
gin (parents gin__int_ops) -- the most important
This has been described as "genealogical tree" approach, and
works very good, IMHO much better
than nested sets.
Is there a more complete description of this approach
available? By the title one might assume could be applied to
populations as opposed to phylogeny (the OP's use case). Does
it deal with consanguinity? Does it perform well going "up" the
tree (which is of course branched at every level)?
From here https://en.wikipedia.org/wiki/Phylogenetic_tree
I assume that phylogenetic trees are normal
trees, and I see no reason why not be modeled with the
genealogical approach described. The earliest paper
I based my work on was :
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CCUQFjABahUKEwiR6auUlvnIAhXGvhQKHVyDA-s&url="">
Finding the root is O(1). Going "up" the tree or finding common
ancestry is reduced to the problem
of finding overlap/intersections/contains/contained between
postgresql arrays.
The indexes, functions and operators provided by
contrib/intarray were a basic element for the success of this
approach.
Going "up" a genealogy to me means getting two parents, four
grandparents, 8 great grandparents etc. On a good day, at least
when there are no loops. This isn't, to my understanding, how
phylogeny works (but my genetics degree was thirty year ago) so
perhaps I'm still confused by the titles used. And certainly not
to say that your approach isn't what the OP really needs!
|
