JUCS - Journal of Universal Computer Science 13(10): 1411-1433, doi: 10.3217/jucs-013-10-1411
Efficient Access Methods for Temporal Interval Queries of Video Metadata
expand article infoSpyros Sioutas‡, Kostas Tsichlas§, Bill Vassiliadis|, Dimitrios K. Tsolis
‡ Ionian University, Greece§ Aristotle University of Thessaloniki, Thessaloniki, Greece| Hellenic Open University, Patras, Greece¶ University of Patras, Patras, Greece

Corresponding author: Spyros Sioutas ( sioutas@ionio.gr )

© Spyros Sioutas, Kostas Tsichlas, Bill Vassiliadis, Dimitrios Tsolis.
This article is freely available under the J.UCS Open Content License.
Citation: Sioutas S, Tsichlas K, Vassiliadis B, Tsolis DK (2007) Efficient Access Methods for Temporal Interval Queries of Video Metadata. JUCS - Journal of Universal Computer Science 13(10): 1411-1433. https://doi.org/10.3217/jucs-013-10-1411
Open Access
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
video databases, data structures, computational geometry