Efficient Access Methods for Temporal Interval Queries of Video Metadata

Abstract: Indexing video content is one of the most important problems in video databases. In this paper we present linear time and space algorithms for handling video metadata that represent objects or events present in various frames of the video sequence. To accomplish this, we make a straightforward reduction of this problem to the intersection problem in Computational Geometry. Our first result is an improvement over the one of V. S. Subrahmanian [Subramanian, 1998] by a logarithmic factor in storage. This is achieved by using different basic data structures. Then, we present two other interesting time-efficient approaches. Finally a reduction to a special geometric problem is considered according to which we can achieve two optimal in time and space solutions in main and external memory model of computation respectively. We also present an extended experimental evaluation.