Object discovery for virtual worlds
Abstract/Contents
- Abstract
- Metaverses are virtual worlds where everything is user-generated: object appearance, placement, and behavior are all specified by users. Object discovery is one key metaverse service that lets clients and scripted objects learn about other objects inhabiting the world in order to render them and imbue them with complex, interactive behaviors. Unfortunately, current systems that can scale beyond just a few servers commonly limit discovery to a small region. This approach scales trivially because it is highly localized, but gives the appearance of a world that drops off beyond the query region. The open-ended nature of metaverses makes scalably providing clients and objects a complete view of the world challenging. This dissertation presents an object discovery system for virtual worlds that supports the variety of queries required in metaverses with a single data structure, scales to large worlds with millions of objects, and exploits opportunities for efficiency in common metaverse workloads. A novel local query data structure efficiently handles evaluation of solid angle queries for immersive client displays. Naively applying existing data structures performs very poorly, but a small modification reduces the cost to be comparable to distance queries used in other systems. Further modifications add support for continuous queries, dynamic objects, and most importantly, aggregates, which complete the view of the world by acting as substitutes for collections of objects that do not individually satisfy the query. A distributed architecture builds on this local data structure to support large scale worlds. The scalability challenges that arise have an unexpected cause. The interaction of traditional query interfaces using queries and unordered result sets between servers and aggregation leads to redundant creation of aggregates. A novel design avoids this inefficiency with a single globally replicated data structure, trading higher coordination overhead in order to minimize the number of aggregates generated. Despite being globally replicated, this approach remains efficient because weak consistency requirements avoid any truly global operations and permit the use of a simple, pair-wise replication protocol between hosts. Combined with the locality of queries on each server, a multi-level replication scheme that pushes query evaluation to clients, and a prefetching policy which ensures most replication requests can be handled immediately, scalability improves by at least an order of magnitude in terms of number of objects and servers. Two metaverse applications of queries, client display and object scripting, demonstrate the effectiveness of this new design. The resulting system is also more broadly applicable: it supports applications that require interactive exploration of large, geometric datasets and use aggregation to give a complete but simplified view of the data. A final application using different input data, aggregation algorithms, query format, and visualization validates this flexibility.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2013 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Cheslack-Postava, Ewen |
|---|---|
| Associated with | Stanford University, Computer Science Department. |
| Primary advisor | Levis, Philip |
| Thesis advisor | Levis, Philip |
| Thesis advisor | Freedman, Michael J, 1979- |
| Thesis advisor | Rosenblum, Mendel |
| Advisor | Freedman, Michael J, 1979- |
| Advisor | Rosenblum, Mendel |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Ewen Cheslack-Postava. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2013. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2013 by Ewen Leith Cheslack-Postava
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...