Efficient Access Methods for Temporal Interval Queries of Video Metadata

Spyros Sioutas (Ionian University, Greece)

Kostas Tsichlas (Aristotle University of Thessaloniki, Greece)

Bill Vassiliadis (Hellenic Open University, Greece)

Dimitrios Tsolis (University of Patras, Greece)

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.

Keywords: computational geometry, data structures, video databases

Categories: E.1, E.5, H.3.1, H.3.3, M.9