Matching algorithms for interest management in distributed virtual environments

Abstract

Interest management in distributed virtual environments (DVEs) is a data filtering technique which is designed to reduce bandwidth consumption and therefore enhances the scalability of the system. This technique usually involves a process called “interest matching", which determines what data should be sent to the participants as well as what data should be filtered. This thesis surveys the state of the art in interest management systems and defines three major design requirements. Based on the requirement analysis, it can be summarised that most of the existing interest matching approaches are developed to solve the trade-off between runtime efficiency and filtering precision. Although these approaches have been shown to meet their runtime performance requirements, they have a fundamental disadvantage - they perform interest matching at discrete time intervals. As a result, they would fail to report events between discrete time-steps. If participants of the DVE ignore these missing events, they would most likely perform incorrect simulations. This thesis presents a new approach called space-time interest matching, which aims to capture the missing events between discrete time-steps. Although this approach requires additional matching effort, a number of novel algorithms are developed to significantly improve its runtime efficiency through the exploitation of parallelism