Streaming of linear media objects, such as audio and video, has become ubiquitous on today’s Internet. Large groups of users regularly tune in to a wide variety of online programming, including radio shows, sports events, and news coverage. However, non-linear media objects, such as large 3D computer graphics models and visualization databases, have proven more difficult to stream due to their interactive nature. In this dissertation, I present a complete framework for the efficient streaming of non-linear datasets to large user groups.The framework has several components. First, I present the Representation Graph, an abstract data representation for expressing the semantic and syntactic relationships between elements of information in a non-linear multimedia database. I then present a computational model for achieving multidimensional adaptation. The model is based on a spatially defined utility metric that allows applications to mathematically express trade-offs between different dimensions of adaptivity. The representation graph and adaptation model serve as the foundation for the Generic Adaptation Library (GAL). GAL defines a layered design for non-linear media applications and provides an implementation for the middle adaptation layer. The representation graph, adaptation model, and GAL can be combined to support adaptive non-linear streaming. I evaluate the performance of an experimental prototype based on these principles and show that they can effectively support the adaptive requirements of dynamic and interactive access to non-linear media. I also define Channel Set Adaptation (CSA), an architecture for scalable delivery of non-linear media. CSA maps concepts from the representation graph to a scalable subscription-based network model. CSA provides, in the ideal case, an infinitely scalable streaming solution for non-linear media applications. I include a evaluation of CSA’s performance on both multicast and broadcast networks. In addition, I develop a performance model based on results from the experimental evaluation. The performance model highlights several key properties of the underlying communication model that are most important to CSA performance.