[R-TREE] Aantal entries per node

[Verwijderd]

Een klein vraagje over R-Trees. Voor het aantal entries per node in een R-Tree is het volgende gedefinieerd:

- stel M is het maximum aantal entries dat in 1 node past
- dan is m <= M/2 het minimum aantal entries per node

- elke leaf node bevat tussen m en M entries, behalve wanneer deze de root node is
- iedere niet-leaf node bevat tussen m en M entries, behalve wanneer deze de root node is

Het probleem waar ik mee zit:

Ik heb een hele verzameling van ruimtelijke gegevens die ik wil indexeren met behulp van een R-Tree, zeg dat dat 10000 punten zijn. Hoe verdeel ik deze 10000 punten dan over mijn leaf nodes? Met andere woorden, hoe stel ik mijn M en m vast

In de artikelen die ik over R-Trees heb gelezen wordt dit niet genoemd.

[SWfreak]

Ben niet zo'n R-Tree freak, maar ik denk dat dat empirisch bepaald wordt, ofwel, je zult wat dingen moeten proberen. Waarschijnlijk zal er voor jouw dataset een waarde van M zijn waarvoor je zoeksnelheid het beste is. Bij 10000 kun je best M=10000 kiezen, maar dan moet je alles in de root stoppen, wat niet zo snel/handig is. Als je M=2 kiest, dan heb je een hele berg nodes nodig. Dus moet je een goede waarde hier ergens tussenin kiezen.
Het lijkt me trouwens ook wel mogelijk om een wiskundige formule op te stellen om M te bepalen als je er van uit gaat dat je het aantal entries evenredig over de nodes wil verdelen, maar daar ben ik nog niet wakker genoeg voor .