Constant-Time Complexity Interest Management for Online Games

Abstract

Data Distribution Management (DDM) services are very important to online services in general and, in particular, to online Computer Games. Many previous works have addressed the problemof minimizing bandwidth usage by avoiding sending unnecessary data to clients, which is often referred to as InterestManagement. Many good algorithms have been developed to calculate clients’ interests, having O(n2) complexity in worst case, but none of them have paid attention to the time dependencies of the data. In this paper we present a novel algorithm for Interest Management which reaches a O(1) complexity by profiting from time dependencies of data related to clients’ interests. Our results show that this approach improves previously existing ones in time performance, and it is specially suitable for its use in online computer game servers.