Mediaan in een B-Tree bepalen

[Rey Nemaattori]

Ik ben voor school(as usual ) met een apllicatie die instaat is een onbepaald aantal integers op te slaan in een variant op de 2-3 multi-way zoekboom: een 3-5 Boom(beiden beter bekent als B-bomen). Dit is een gebalanceerde(leaves op zelfde level) zoekboom met speciale nodes die meer dan 1 element kunnen bevatten. In een 3-5 boom gaat het on nodes met tussen de 3 en 5 child references en maximaal 4 sleutels.

Nu heb ik de boom zo goed al af, én ik ben instaat om vanuit een txt-file keys in de boom te werpen. Echter, ik zou niet al die moeite doen als ik ook wat met die gegevens wilde

Uit deze collectie ben ik op zoek naar de mediaan(het middelste getal qua positie(niet waarde!), of het eerste getal rechts van het midden bij een even aantal getallen).

Tevens zoek ik het gecorrigeerd gemiddelde van de hele boom, d.w.z. 't gemiddelde van alle keys behalve de de hoogste en laagste twee(qua waarde)

Ik heb echter geen idee hoe ik eficient kan bepalen wat het aantal keys links of rechts van de root is om bij een mediaan uit te komen. Ik neem aan dat de structuur van de boom er voorzorgt dat deze zich om en nabij de root bevind, maar hoe bepaal ik dat?

Ook voor het gecorrigeerd gemdidelde sta ik voor een raadsel, mijn gedachte was iedere key op rangtel volgorde uitlezen in een lineaire datastructuur, de eerste en laatste 2 te droppen en het gemiddelde te bepalen. Het probleem is dat op deze wijze de boomstructuur basically genegeerd word: je zou denken dat er iets efficients net die structuur gedaan kan worden

Als iemand tips of ervaring heeft met statistische applicaties, spui gedachten ^_^


Voor diegenen die nog geen idee hebben wat dit type boom inhoud:
-http://en.wikipedia.org/wiki/B-tree
-http://www.bluerwhite.org/btree/

[The Eagle]

Mogguh
Ik denk dat je jezelf eerst eens even moet gaan verdiepen in zoekalgoritmen. Kun je van daar af verder denken. Als ik even google op btree searching kom ik aardig wat handige links tegen, op de eerste pagina al
Als je weet hoe je handig kunt zoeken, kun je ook makkelijk medianen etc bepalen; da's namelijk een kwestie van de hoogste en de laatste uit een recursieve zoekfunctie door de hele boom als ik me niet vergis
Overigens: in databaseland wordt dit veel gebruikt icm een index. Dat kan je werk een heel stuk versnellen, is alleen een kwestie van goed bijhouden bij inserts in de tree

Suc6

[Rey Nemaattori]

Klopt, maar de vraag is of het wenselijk om de HELE boom uit te pluizen? Stel ik heb een miljard items, dan kost dat eeuwen(bij wijze van).

Ik had gehoopt dat er door de boomstructuur zelf te gebruiken het makkelijker is een mediaan te bepalen. Ma goed, ik zal een kijken wat ik met 't zoeken zelf kan doen.

offtopic:
+1 voor de tijd trouwens...half 4 O.o Ik besloot om 3 uur al dat 't wel genoeg was

[Janoz]

Voor het bepalen van de mediaan is het belangrijk de aantallen te weten. Eigenlijk zou elke node ook bij moeten houden hoeveel elementen hij en zijn kinderen in totaal heeft. Pas dan wordt het heel makkelijk om de mediaan uit te rekenen. In principe is deze metadata makkelijk bij te houden. Zodra ergens een node wordt toegevoegde moet je gewoon even de boom naar boven doorlopen en elke node +1 doen. Voor de rest kun je voor alle andere bewerkingen ook bepalen wat er met het totaal gebeurt.

Voor het gecorrigeerd gemiddelde zul je toch de hele boom moeten doorlopen. Niet de hele boom trouwens. Voor het bepalen van de twee minimale en twee maximale waarden kun je de boomstructuur wel gebruiken, maar vervolgens zul je wel de hele boom tussendoor moeten doorlopen.


Ik weet niet precies wat de verdeling is, maar bij miljarden elementen icm integers ga ik er vanuit dat dezelfde getallen vele malen voor zullen komen. In dat geval zou een datastructuur die het aantal voorkomens bijhoud handiger zijn. Dit werkt echter alleen wanneer er aan een getal verder geen meta gegevens hangen. Gemiddelde is dan gewoon sum(key * voorkomens) / sum(key). Bij gecorrigeerd gemiddelde sla je dan gewoon de eerste twee en de laatste twee keys over. Voor mediaan kun je ongeveer hetzelfde doen. Gewoon doortellen totdat je bij de helft van het totaal zit.

[PrisonerOfPain]

De mediaan van een B-Tree is toch gewoon de mediaan van de root node. Aangezien de nodes altijd gesplit worden vanaf de mediaan en zodra de root node gesplit word bevat de nieuwe root node de mediaan van de oude root node, aldus het aangehaalde artikel.

[Janoz]

Dat geldt alleen wanneer de tree volledig gebalanceerd is. Aangezien de nodes tussen de 3 en 5 childnodes kunnen hebben is dat (afaik) niet gegarandeerd.

[Confusion]

Rey Nemaattori schreef op maandag 23 juni 2008 @ 11:47:
Klopt, maar de vraag is of het wenselijk om de HELE boom uit te pluizen?

Tjah, als je boom alleen de data en de minimale structuurdata van de boomstructuur bevat, dan heb je geen andere keus denk ik. Alleen als je extra meta-data over de structuur aan de nodes hangt, dan kan je aan de hand daarvan een stuk sneller de mediaan vinden. Dat is gewoon een tijd/ruimte trade-off.

Voor dat gecorrigeerde gemiddelde geldt hetzelfde: als je hem vanaf scratch moet uitrekenen zal je de hele boom door moeten. Als je hem als meta-data opslaat (op root niveau of desnoods bij meerdere nodes) en bij iedere insert herberkend, dan gaat het sneller, maar heb je weer met een trade-off te maken. Afhankelijk van je toepassing is het de moeite waard.

[Janoz]

Imho kun je metadata het best bij elke node opslaan. Dat maakt het werken een stuk intuitiever omdat elke subboom weer als dezelfde boom behandeld kan worden. Eerder zei ik al dat het bijhouden van het aantal elementen in de (sub)boom kan helpen bij het bepalen van de mediaan, maar het bijhouden van de som van de elementen is ook makkelijk bij het bepalen van het (gecorrigeerd) gemiddelde.

[PrisonerOfPain]

Janoz schreef op maandag 23 juni 2008 @ 12:48:
Dat geldt alleen wanneer de tree volledig gebalanceerd is. Aangezien de nodes tussen de 3 en 5 childnodes kunnen hebben is dat (afaik) niet gegarandeerd.

Een B-Tree is per definitie gebalanceerd tenzij je halverwege een insert bent.

[Confusion]

Janoz schreef op maandag 23 juni 2008 @ 13:07:
Imho kun je metadata het best bij elke node opslaan. Dat maakt het werken een stuk intuitiever omdat elke subboom weer als dezelfde boom behandeld kan worden. Eerder zei ik al dat het bijhouden van het aantal elementen in de (sub)boom kan helpen bij het bepalen van de mediaan, maar het bijhouden van de som van de elementen is ook makkelijk bij het bepalen van het (gecorrigeerd) gemiddelde.

Alleen zal je voor dat gecorrigeerde gemiddelde ook de max en de (2) min elementen bij moeten houden, waarmee de hoeveelheid extra data misschien aardig op begint te lopen.
maar natuurlijk niet per node, dus deze comment sloeg nergens op...

[ Voor 5% gewijzigd door Confusion op 23-06-2008 14:34 ]

[PrisonerOfPain]

Confusion schreef op maandag 23 juni 2008 @ 13:13:
[...]

Alleen zal je voor dat gecorrigeerde gemiddelde ook de max en de (2) min elementen bij moeten houden, waarmee de hoeveelheid extra data misschien aardig op begint te lopen.

Max en min zijn allebei in logaritmische tijd te vinden dus die zou ik sowieso niet op gaan slaan.

[scorpie]

PrisonerOfPain schreef op maandag 23 juni 2008 @ 13:11:
[...]


Een B-Tree is per definitie gebalanceerd tenzij je halverwege een insert bent.

Onzin, een B-tree is een boom waarbij de nodes ieder maximaal 2 childnodes kennen. Wanneer het een perfect B-tree zou zijn, zou de mediaan dan inderdaad de rootnode zijn, maar dan betekent dat dus dat de B-tree vol is, en alle leafs dezelfde depth hebben.

edit @ hieronder: My bad

[ Voor 3% gewijzigd door scorpie op 23-06-2008 13:47 ]

[PrisonerOfPain]

scorpie schreef op maandag 23 juni 2008 @ 13:17:
[...]

Onzin, een B-tree is een boom waarbij de nodes ieder maximaal 2 childnodes kennen. Wanneer het een perfect B-tree zou zijn, zou de mediaan dan inderdaad de rootnode zijn, maar dan betekent dat dus dat de B-tree vol is, en alle leafs dezelfde depth hebben.

Uit: Introduction to algorithms, p439.
4. All leaves have the same depth, which is the tree's height h.

Het gaat hier niet over een binary tree, maar over een 3, 5 B-tree; dat is een substantieel andere datastructure.

[Soultaker]

Er zijn, mijns inziens, twee mogelijkheden:

1. Je annoteert de nodes met aantallen en gemiddelde waarden (of gesommeerde waarden). Janoz stelde dit al voor om de mediaan te vinden, maar je kunt het ook voor het gemiddelde doen als je B-tree genoeg van je datastructuur weet om waarden te kunnen sommeren.

2. Je houdt die waarden globaal bij en update ze als je elementen toevoegt/verwijdert. Dit is naar mijn mening simpeler te implementeren. Voor het vinden van de mediaan is dit overigens nog wel tricky om efficient te implementeren; het helpt wel als je finger searches o.i.d. support.

PrisonerOfPain schreef op maandag 23 juni 2008 @ 13:11:
Een B-Tree is per definitie gebalanceerd tenzij je halverwege een insert bent.

Hij is wel ongeveer gebalanceerd, maar niet zo perfect dat je het middelste element kunt vinden zonder de hele boom door te gaan.

[ Voor 9% gewijzigd door Soultaker op 23-06-2008 13:30 ]

[Janoz]

De voorkeur zou bij mij trouwens uitgaan naar de som (mits deze binnen de range van het datatype valt). Door het gemiddelde op te slaan verlies je precisie door afrondfouten.

[MSalters]

Het lijkt me dat je de hele boom moet aflopen voor de mediaan. Elke node draagt namelijk bij aan het resultaat. Je kunt geen aannames maken op basis van een parent node. De hoveelheid kinderen varieert tussen de 3^h en 5^h, maar zelfs voor h=1 betekent dat dat je mediaan verschuift.

[zeroxcool]

Even een gedachtesprong, ben niet helemaal bekend met de 3,5-tree die jij gebruikt, maar dit idee werkt op een gewoon balanced binary search tree, volgens mij prima.

Is het geen mogelijkheid om in iedere internal node (non-leaf) het aantal children op te slaan? Een mutatie (insert/delete) kost dan nog steeds log(n), aangezien je alleen de aantallen van de node tot aan de root hoeft up te daten. Je slaat dus dit op: size(x) = size(left(x)) + size(right(x)) + 3 of 5. In jouw geval wordt dit iets anders, aangezien je meerdere childs hebt afhankelijk van de diepte.

De mediaan bepalen is dan de size van je root bepalen, delen door twee (flooren/ceilen, wat je wilt) en dan vanaf de meest linkse child naar rechts lopen en kijken waar de mediaan kan liggen. Een niveau lager gaan betekent de size van alle andere children waar je niet afdaalt afhalen van de gezochte mediaan en dan dalen.

Hopelijk is het idee dat ik schets een beetje duidelijk...

[pkuppens]

MSalters schreef op maandag 23 juni 2008 @ 20:59:
Het lijkt me dat je de hele boom moet aflopen voor de mediaan. Elke node draagt namelijk bij aan het resultaat. Je kunt geen aannames maken op basis van een parent node. De hoveelheid kinderen varieert tussen de 3^h en 5^h, maar zelfs voor h=1 betekent dat dat je mediaan verschuift.

Met een beetje triviale extra administratie op aantallen in de nodes kun je best in ieder geval binnen orde(h) vinden.
Met soortgelijke administratie op totale som onderliggende boom is een gemiddelde ook wel te vinden. Orde(1).
Met orde(h) zoekwerk zijn de 'linkse' en 'rechtse' leaf te vinden. Bietje lagere school rekenwerk kun je je gecorrigeerde gemiddelde ook wel uitrekenen.

Lijkt mij.

[.oisyn]

PrisonerOfPain schreef op maandag 23 juni 2008 @ 13:11:
[...]


Een B-Tree is per definitie gebalanceerd tenzij je halverwege een insert bent.

Maar niet volledig gebalanceerd, omdat het aantal kinderen variabel is. Als de root 3 kinderen heeft, en elke descendent van het linkerkind heeft 3 kinderen, maar elke descendent van het middenste en rechterkind hebben 5 kinderen, dan is de boom nog steeds gebalanceerd volgens de definitie van de B-tree, maar de mediaan ligt niet meer in de root node.

Als je informatie hebt over die aantallen kun je de mediaan gemakkelijk vinden.

[ Voor 6% gewijzigd door .oisyn op 25-06-2008 11:08 ]

[MSalters]

pkuppens schreef op dinsdag 24 juni 2008 @ 23:06:
[...]
Met een beetje triviale extra administratie op aantallen in de nodes kun je best in ieder geval binnen orde(h) vinden. Met soortgelijke administratie op totale som onderliggende boom is een gemiddelde ook wel te vinden. Orde(1). Met orde(h) zoekwerk zijn de 'linkse' en 'rechtse' leaf te vinden. Bietje lagere school rekenwerk kun je je gecorrigeerde gemiddelde ook wel uitrekenen.

Lijkt mij.

Tja, als je het op die manier doet, dan kan het nog veel simpeler. Het eerste element is de mediaan. En vervolgens kijk je bij elk nieuw element of het groter danwel kleiner dan de huidige mediaan is, en past de mediaan dan eventueel aan. Heb je niet eens extra storage per node voor nodig. Zoals ik het probleem lees is de vraag of het kan met een gegeven B-Tree zonder werk vooraf.

[Nick The Heazk]

Dat gaat niet werken. Ik ben me in ieder geval niet bewust van een incrementele manier om de mediaan te berekenen (met orde 1 extra geheugengebruik). Hoe zou je bijvoorbeeld de mediaan bepalen als deze sequentie gegeven wordt: 1,2,3,4,5,6,7

De voorgestelde methode met de counts per node lijkt me in ieder geval optimaal te zijn (als ik me dat correct herinner stond er in Introduction to Algorithms - Cormen et al ook een oefening waarbij je exact die count manier moest toepassen om zo de mediaan te berekenen).

[ Voor 38% gewijzigd door Nick The Heazk op 25-06-2008 23:56 ]

[zeroxcool]

Nick The Heazk schreef op woensdag 25 juni 2008 @ 23:52:
Dat gaat niet werken. Ik ben me in ieder geval niet bewust van een incrementele manier om de mediaan te berekenen (met orde 1 extra geheugengebruik). Hoe zou je bijvoorbeeld de mediaan bepalen als deze sequentie gegeven wordt: 1,2,3,4,5,6,7

De voorgestelde methode met de counts per node lijkt me in ieder geval optimaal te zijn (als ik me dat correct herinner stond er in Introduction to Algorithms - Cormen et al ook een oefening waarbij je exact die count manier moest toepassen om zo de mediaan te berekenen).

Daar komt mijn methode ook grotendeels uit. Het heet daar volgens mij een order-statistic tree. Let wel, dit gaat over balanced binary search trees.

[edit]
Even opgezocht, het heet inderdaad een order-statistic tree. De functie die hierover gaat heet OS-Rank(T, x). Als je de mediaan wilt weten is het dus gewoon: OS-Rank(T, mediaan).

Google Books heeft een kopie online van dit hoofdstuk: http://books.google.com/b...fTqL3CRP-v7c1CyXMbRQcoc6A

Nu nog aanpassen voor je 3,5-tree en je komt er wel uit denk ik .

[ Voor 23% gewijzigd door zeroxcool op 27-06-2008 01:07 ]