A Method for Fast Leaderboard Calculations in Massive Online Game-Based Environments

摘要

Leaderboards and other game elements are present in many online environments, not just in videogames. When such environments have relatively few users, the implementation of those leaderboards is not usually a problem; however, that is no longer the case when they have dozens of thousands or more. For those situations we propose a method that is easy and cheap to implement. It is based on two particular data structures, a Self-Balanced Ordering Statistic Tree and a hash table, to perform proper leaderboard calculations in a fast and cheap way. More specifically, our proposal has O(log_2N) time complexity, whereas other approaches also based on in-memory data structures like linked lists have O(N), and others based on Hard Disk Drive operations like a relational database have O(Nlog_2N). Such improvement with regard to the other approaches is corroborated with experimental results for several scenarios, also presented in this paper.