The Shape of Trees to Come

[former_member181923]

I'm wondering if there's an actual real-world application which must store hundreds of thousands or even millions of persistent linked lists that are relatively static (i.e. change in minor ways fairly infrequently) and that contain no more than a few hundred nodes each.<br><br>

The closest I can imagine is the set of BOMS for a very very large enterprise, but I'm not sure that even in the largest of currently viable enterprises, there are actually millions of BOMS satisfying the above criteria

[former_member181923]

I just thought of an example that actually does occur.

In the United States, the Church of Latter Day Saints (the "Mormons") runs a huge genealogical operation where they keep records of family trees.

Suppose we consider a patriarchal (or matriarchal) family tree. If we order the children of each father (or mother) by birthdate, the result is an ordered tree (NOTE!!!! - not an unordered tree.)

So:

1) these trees obviously don't change very often, and for "extinguished" lineages, don't change at all;

2) there are probably no more than a few hundred nodes in each such tree;

3) as time goes on, the Mormons might well collect millions of such trees in their genealogy center.

Therefore, since I now have a real-world example of the situation, and one whch might be amenable to space vs time trade-offs, I will begin to post a novel way to store trees that trades off time for space. But as in this example, the time trade-off is minimal, since how many children does any father or mother have each year ???

If you're interested in learning about some elementary poset theory and how it permits us to store any "N-free digraph" on n vertices as a permutation of 0,...,n-1, stay tuned.

Note also that we need a more general solution than one for pure ordered trees, since if people aren't careful some descendants may marry other descendants and we therefore have non-tree graphs in which two descendants may trace back to the same ancestor (hopefully very remotely, of course!!!!)

[former_member181923]

PS - the above example can obviously be extended to genetics labs that must keep track of "lineages" of generations of lab species for control purposes.

[Former Member]

As an aside, this practice (of registering parentage info) is maintained in my community in India. We do have records from the time when tree leaves were used instead of paper (ofcourse those are mostly unreadable now).

It has a novel purpose. Since marriages happen within the community, it is verified that nodes upto 7 levels up (parent, grandparent, great grandparent.....) do not clash for the guy/girl, else they are considered blood relatives and the marriage isn't sanctioned. It has scientifically been proved that any genetic issues out of marrying within is almost zero if the distance is 7 generations. But ofcourse this practice pre-dates any such scientific study.

[former_member181923]

Hi Ajay -

We're kind of thinking along the same lines here.

At present, no one really knows what characteristics of a given family F (father, mother, children) can be deduced from the ancestry or genealogy of F. If we had a simple way to compare the "shapes" of the genealogies for various families, we could then use genealogical records to find families with similarly-shaped genealogies and then see if these families had any similar characteristics.

The same goes for any "treed" characteristics that SAP uses in its ERP. Who knows what one could find out about "efficient" and "inefficient" cost estimates in ckis by comparing the actual accuracy of top-level cost estimates in ckis against the shape of the cost estimate trees in ckis that go to making uo these top-level totals?

Same for BOMs - maybe there are BOM trees that are simply "better" due to their shape, e.g. "funny-shaped" BOMs are more difficult to use, process, etc. ?

Anyway, thanks for taking the time to respond.

Regards

djh

[former_member181923]

By the way, those following this thread may have already realized that the topic is closely-related to the notions of sparse distributed memory and content-addressable memories, as discussed here:

<a href="http://www.murrayc.com/learning/AI/sparsedistributedmemory.shtml">DiscussionOfStuffbyKanerva </a>

[Former Member]

hi ajay,

are you sure that your 'theory of 7 generations' is scientifically secured? to me this would imply that you lose your 'genetical fingerprint' over seven generations.

don't dominant genes survive very likely for 7 generations and eventually lead to maladies associated with it?

not that i want to start the big biology discussion of non biologists on this, I was just wondering...

btw, one thing is definitive...marrying alone doesn't do any harm to anyone )

anton

[Former Member]

Will post if I find any links. Essentially the seven generation theory is to negate any weak genes that may otherwise cumulate and result in underdevelopment or other similar birth defects.

Stronger traits are to survive and that is not a problem (eg if two hot-headed people produce a hot-headed child, it doesn't matter whether there was a distance of 7 or 20 generations, however if two people marry within 7 generation with a congenital heart defect, it is likely to add up in the offsprings. This adding-up effect will be minimal if the distance is more than 7 generations is what the studies say.).

David, I am sorry for the aside(s) on your thread. I look forward to any design/solution you post here.

[former_member181923]

Ajay -

No need to apologize. If a "Coffee Corner" thread doesn't have AT LEAST two different conversations going on simultaneously, then the "Coffee Corner" Forum ain't worth a hoot and should be renamed the "Roberts' Rules of Order Forum"!

Of course, if the discussion does eventually get technical and folks stay interested, that's a different matter - only because it's hard enough to follow technical back and forth without digressions.

But right now this thread hasn't even reached the "doodle on a napkin" stage, so any and all digressions are welcome (so far as I'm concerned, anyway.)

Regards

djh

[Former Member]

The process scheduling queue in OS kernel, though it doest remain static.

[former_member181923]

Hi Puru<br><br>

Thanks for taking the time to respond.<br><br>

Although there are a lot of trees in this queue at any given point in time, are they always the same trees? (I may be misunderstanding your example here ...)<br><br>

If the total set is not generally the same, then it's not an example of the situation I'm thinking of.<br><br>

But again, thanks very much for taking the time to respond.<br><br>

Regards<br>

djh

[Former Member]

Well, As far as Linux kernel is concerned, I am pretty sure there arent any trees in the queue.

But lets assume some kernel developer implements it as queue. This will help us to proceed with our discussion. Supopose the root node of the tree is the main process and all its subnodes will its threads. In this case the tree doesnt remain the same.

Regards

Puru