Beomjoo Seo

Edge Indexing in a Grid for Highly Dynamic Virtual Environments

Supervisor(s) and Committee member(s): Supervisor: Roger Zimmermann

Newly emerging game-based application systems provide three-dimensional virtual environments where multiple users interact with each other in real-time. Such virtual worlds are filled with autonomous, mutable virtual content which is continuously augmented by the users. To make the systems highly scalable and dynamically extensible, they are usually built on a client-server based grid subspace division where the virtual worlds are partitioned into manageable sub-worlds. In each sub-world, the user continuously receives relevant geometry updates of moving objects via a streaming process from remotely connected servers and renders them according to her viewpoint, rather than retrieving them from a local storage medium.

In such systems, the determination of the set of objects that are visible from a user’s viewpoint is one of the primary factors that affect server throughput and scalability. Specifically, performing real-time visibility tests in extremely dynamic virtual environments is a very challenging task as millions of objects and sub-millions of active users are moving and interacting. We recognize that the described challenges are closely related to a spatial database problem, and hence we map the moving geometry objects in the virtual space to a set of multi-dimensional objects in a spatial database while modeling each avatar both as a spatial object and a moving query. Unfortunately, existing spatial indexing methods are unsuitable for this kind of new environments. The main contribution of this research is an efficient spatial index structure that minimizes unexpected object popping and supports highly scalable real-time visibility determination. We uncovered many useful properties of this structure and have compared the index structure with various spatial indexing methods in terms of query quality, system throughput, and resource utilization. We expect our approach to lay the groundwork for next-generation metaverses and virtual world frameworks where geometry data is continuously streamed to each user.

Data Management Research Laboratory


The research activities at the Data Management Research Lab (DMRL), formerly at the University of Southern California, Los Angeles ( and now at the School of Computing, National University of Singapore, focus on research in the areas of peer-to-peer systems, collaborative environments, streaming media architectures, geospatial data management, and mobile location-based services.

Bookmark the permalink.