Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Ranking Highscores: Evaluation of a dynamic Bucket with Global Query algorithm
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2016 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

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. , p. 29
Series
UMNAD ; 1060
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:umu:diva-127677OAI: oai:DiVA.org:umu-127677DiVA, id: diva2:1047285
Educational program
Bachelor of Science Programme in Computing Science
Supervisors
Examiners
Available from: 2016-11-17 Created: 2016-11-17 Last updated: 2016-11-30Bibliographically approved

Open Access in DiVA

fulltext(370 kB)299 downloads
File information
File name FULLTEXT01.pdfFile size 370 kBChecksum SHA-512
469a0030ffe14ad03a9c544a4873e174e3f5b30aa09e68ceb0dd7713e126845a44f4b73b37f7ea681922ee4e0c49ef87c65ab973c2a60a6a520e5ad2b816e080
Type fulltextMimetype application/pdf

By organisation
Department of Computing Science
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 299 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 202 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf