The temporal ordering and the spatial viewpoints of video frames in conventional digital video content are completely determined at the time of authoring. Because of the lack of runtime navigation flexibility in the content, traditional video-on-demand systems have very limited navigation controls, such as fast-forward/rewind etc. In contrast, we have developed a new form of interactive video content called active video, which supports hyper-linking among related video sequences for temporal navigation and interpolation among stored video sequences, that simultaneously capture a dynamic scene, for spatial navigation. Thus active video enables the end user to choose the temporal frame sequencing and the viewing angle (even virtual ones) during playback. This additional navigation flexibility cannot be supported by traditional video distribution systems. The storage and playback of active video poses unique design challenges. Active video delivery requires computation support on the data path, between the storage and the playback application, to interpolate new views based on stored views. Since active video is only a specific instance of a broad class of interactive media, that require computation support on the server, the new distribution system designed for active video should also be programmable and extensible to store and perform runtime processing of other forms of interactive media. A software architecture of the shared programmable computation framework also needs to address performance and data isolation issues. We have designed and implemented a comprehensive active video authoring, compression, storage, and playback system called Memphis. In this paper, we describe the design and implementation of the storage and playback components which address the above design issues.