Today, more and more video information can be accessed through internet, satellite, etc.. Retrieving specific video information from large-scale video database has become an important and challenging research topic in the area of multimedia information retrieval. Generally, video retrieval can be categorized by the retrieval of video shot and retrieval of video clip. Up to now, few approaches can support both shot retrieval and clip retrieval efficiently. In this paper, we introduce a new high-dimensional index structure OVA-File, which is a variant of VA-File. In OVA-File, the approximations close to each other in data space are stored in close positions of the approximation file. The benefit is that only a part of approximations near the query vector need to be visited to get the approximate query result. Then, both shot query algorithm and video clip query algorithm are proposed to support video information retrieval efficiently. The experimental results showed that the queries based on OVA-File were much faster than that based on VA-File with small loss of result quality.
Video clip retrieval is a significant research topic of content-base multimedia retrieval. Generally, video clip retrieval process is carried out as following: (1) segment a video clip into shots; (2) extract a key frame from each shot as its representative; (3) denote every key frame as a feature vector, and thus a video clip can be denoted as a sequence of feature vectors; (4) retrieve match clip by computing the similarity between the feature vector sequence of a query clip and the feature vector sequence of any clip in database. To carry out fast video clip retrieval the index structure is indispensable. According to our literature survey, S2-tree  is the one and only index structure having been applied to support video clip retrieval, which combines the characteristics of both X-tree and Suffix-tree and converts the series vectors retrieval to string matching. But S2-tree structure will not be applicable if the feature vector's dimension is beyond 20, because the X-tree itself cannot be used to sustain similarity query effectively when dimensions of vectors are beyond 20. Furthermore, it cannot support flexible similarity definitions between two vector sequences. VA-file represents the vector approximately by compressing the original data and it maintains the original order when representing vectors in a sequence, which is a very valuable merit for vector sequences matching. In this paper, a new video clip similarity model as well as video clip retrieval algorithm based on VA-File are proposed. The experiments show that our algorithm incredibly shortened the retrieval time compared to sequential scanning without index structure.
Many multi-dimensional index structures, such as R-Tree, R*-Tree, X-Tree, SS-Tree, VA-File, etc. have been proposed to support similarity search with l1, l2 or l(infinity ) distance as similarity measure. But they can not support such similarity search with cosine as the similarity measure. In this paper, an index structure Angle-Tree is introduced to resolve the problem. It first projects all the high dimensional points onto the unit hyper-spherical surface, i.e. normalize each original vector in the database into a unit one. Then an index structure similar to R-Tree is built for those projected points. The experimental results show that the Angle-Tree can decrease the cost of disk I/O and support fast similarity search.