A fast parallel matching algorithm for continuous interest management

In recent years, the scale of distributed virtual environments (DVEs) has grown rapidly in terms of number of participants and virtual entities. Many DVEs employ interest management schemes to reduce bandwidth consumption and thus enhance the scalability of the system. Most of the existing interest management approaches, however, have a fundamental disadvantage - they perform interest matching at discrete time intervals. As a result, they would fail to report events between consecutive time-steps of simulation which leads to incorrect simulations. In this paper, we present a new algorithm for interest matching which aims to capture missing events between discrete time-steps. This algorithm facilitates parallelism by distributing the workload of matching process across multiple processors. Since it is increasingly common to deploy commercial DVE applications on shared-memory multiprocessor machines, using the parallel algorithm for these applications would be more suitable than the existing serial algorithms.