Thoughts about worldtree

Subject: Thoughts about worldtree
From: Jari P Saukkonen (jsaukkon@cs.Helsinki.FI)
Date: Sun Nov 28 1999 - 23:59:24 EET

I was doing some homework on data structures and had the following idea.

I wonder if it would be more efficient to, instead of having a tree with
fixed height h (13 atm?), dynamically extend the tree when necessary.

We would define a limit on how many objects can the object list in each
leaf contain, let it be 50 in this example. When we try to add an object
to that list, and it already has 50 other objects, the list node is
replaced with branch nod, new leaves (four) are created and the current
object list is divided to the new leaves and the procedure will be

Currently, if things get very crowded in one place the overhead for
searching specific objects gets high (due to long object lists). By
dynamically extending the tree we could enforce a maximum length for
the lists making in-list searches more efficient. However, this doesn't
affect the usual "get-all-objects-in-radius" query much (after the current
system has been optimized to use sibling-links) but if we need to
have different kinds of searches in the future it could prove to be more

Just an idea, go ahead and flame. I've had enough trees for this evening!

++ dazzt

ps. NO, definitely not for 0.4.0 :)

| Jari Saukkonen + : coral   -.
| programming            music          graphics | dolphin   :
| art                  keyboards             web | nah-kolor |
| Babylon5-inspired 'shadow function'        0 <= t <= 4*pi/3
:  x(t) =   (sin 8t)^2 * (5 + 3sin 8t) cos (t/2 + (sin 8t)^2)
.  y(t) = +-(sin 8t)^2 * (5 + 3cos 8t) sin (t/2 + (sin 8t)^2)

This archive was generated by hypermail 2b25 : Tue Feb 12 2002 - 00:00:23 EET