Ranking Highscores: Evaluation of a dynamic Bucket with Global Query algorithm
Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
The task of ranking highscores in a computer game may sound like a trivial task. It turns out it is not, because the naive solution have a time complexity not suitable for online applications in terms of response time and running cost. An overview of a few approaches to ranking is presented: how an N-ary tree could be used to do ranking and how to do linear approximation. Two ways of obtaining a model for doing linear approximation are demonstrated, a method called Buckets with Global Queryis described and a method based on Frugal Streaming is elaborated on.Finally, a variant of the Buckets with Global Query algorithm where the buckets are adjusted continuosly according to the changes in the distribution of high scores is evaluated. The dynamic variant of the algorithm performs well in terms of accuracy for at least 100 000 highscore up-dates but have no significant gains in reduced CPU-time.
Place, publisher, year, edition, pages
2016. , 29 p.
Engineering and Technology
IdentifiersURN: urn:nbn:se:umu:diva-127677OAI: oai:DiVA.org:umu-127677DiVA: diva2:1047285
Bachelor of Science Programme in Computing Science
Nieves Sanchez, Juan Carlos