large scale ranking
Jethro Bodine
Michael "Kato" Wulf
--
You received this message because you are subscribed to the Google Groups "Firebase Google Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to firebase-tal...@googlegroups.com.
To post to this group, send email to fireba...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Andrew Lee
Seth Caldwell
An Approximate Solution:
“Users”: [{name:”Seth”,bucket:1,highscore:15}]
“buckets”: [ 0:{“numusers”:0, scoreRangeLow:0,scoreRangeHigh:10},1:{“numusers”:1,scoreRangeLow:11,scoreRangeHigh:20}….. and so on ]
Iterating the different buckets to determine Xth out of N wouldn’t take much time, and whenever a user leaves a bucket and falls into a new one, you decrement the user count in the old bucket and increment the user count of the new bucket.
Conceivably, you could create a bucket for every possible point value (10,000 buckets in a 0-10,000 point game), and this would solve your problem, just create a lot of data to load (you could assume the scoreRange of 1 for each bucket, dropping the scoreRange vars).
Processing could of course be saved by keeping track of number of users in bucketcollections; divide the space into however many buckets you want to have to iterate, so you keep track of number of users each 1000 buckets for example.
An Accurate Solution: (will require log(n) firebase loads at worst case)
Use a collapsed tree, and store a user’s path within the tree within their user node.
First user comes into your game, scored 580 points. You add the first node to the tree and create empty left and right pointers. We’ll keep track of the number of nodes to our right and left at each node, and have to update these counts on insert. We also keep track of the number of users with our exact score in this node. (ties).
/Users/0: { name:seth, rankNode:0,highscore:580}
/tree/nodes/0 {left:’’, right:’’ userCount:1, leftCount:0,rightCount:0, score: 580 }
Second user comes into your game, scores 800 points. You traverse the tree putting him to the right (higher rank) of the current node.
/Users/0: { name:seth, treeNode:0,highscore:580}
/Users/1: { name:andrew, treeNode:1,highscore:800}
/tree/nodes/0: {parent:’’, left:’’, right:1 userCount:1, score: 580 }
/tree/nodes/1: {parent:0, left:’’,right:’’,userCount:1, score:800 }
Third user comes into the game, scores 600 points. Tree insertion follows:
/Users/0: { name:seth, treeNode:0,highscore:580}
/Users/1: { name:andrew, treeNode:1,highscore:800}
/Users/2: { name:anant, treeNode:2,highscore:600}
/tree/nodes/0: {parent:’’, left:’’, right:1 userCount:1, leftCount:0,rightCount:2, score: 580 }
/tree/nodes/1: {parent:0, left:2,right:’’,userCount:1, leftCount:1,rightCount:0,score:800 }
/tree/nodes/2: {parent:1, left:’’,right:’’,userCount:1, leftcount:0,rightCount:0,score:600 }
How do we calculate Xth of N in such a structure with a lookup time of O(logn)? Load your tree node, traverse up to the root, using count of left and right adding to count of people you’re less than or greater than. Bring server down for an hour and balance tree every once a week or something, culling inactive users, etc. Depending on your traffic, you could also cache the rank calculations per node, so each node knows its own ranking for a timeout of like 10 mins, and will recalculate/retraverse up to root every 10 mins or so.
I’m sure there are similar structures that could be used probably more optimally.
Seth
From: fireba...@googlegroups.com [mailto:fireba...@googlegroups.com] On Behalf Of Andrew Lee
Sent: Friday, July 26, 2013 2:12 PM
To: fireba...@googlegroups.com
Subject: Re: [Firebase] large scale ranking
Hi Jeffrey -
I'd like to add to Kato's answer. One of the common use cases (and I think part of your question) that people have asked for is an efficient way to say "I'm Xth out of N players". Currently there's no way to do this without either loading all of the scores or having an admin process running somewhere to calculate them.
You could perhaps approximate this yourself though. You could keep a count of the total # of users as well as the highest and lowest score. If you know the general distribution of the distribution of scores you could probably come up with a decent approximation.
Not an ideal solution I admit. We're working on some better ways of doing this, but I don't have anything I can share on this front yet.
-Andrew
On Fri, Jul 26, 2013 at 2:05 PM, Michael "Kato" Wulf <wu...@firebase.com> wrote:
Jethro,
Have you checked out the Firebase leaderboard example? It takes the tact of simply ordering the entries by score, so that highest scores are at the top. It retrieves them with a limit() equal to the number of top ranking users to show and prints them in order.
To speed up your server process, instead of doing a forEach, you can monitor the rank data for "child_changed" and "child_added" events. You wouldn't need to use forEach() to compare, if the score data is too big for memory (it would have to be on the order of multi-millions probably, as long as we're just talking a user id vs score and rank number) then you could fetch results using the priorities (everything between 1000 and 2000 points) to reduce the set you compare to, or even cache some indexed data in a separate Firebase path for quick lookup.
I hope this helps,
Kato