Hierarchical indexing structure for efficient similarity search in video retrieval

Lu, Hong, Ooi, B. C., Shen, H. T. and Xue, Xiangyang (2006) Hierarchical indexing structure for efficient similarity search in video retrieval. IEEE Transactions on Knowledge and Data Engineering, 18 11: 1544-1559. doi:10.1109/TKDE.2006.174

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Lu, Hong
Ooi, B. C.
Shen, H. T.
Xue, Xiangyang
Title Hierarchical indexing structure for efficient similarity search in video retrieval
Journal name IEEE Transactions on Knowledge and Data Engineering   Check publisher's open access policy
ISSN 1041-4347
Publication date 2006
Sub-type Article (original research)
DOI 10.1109/TKDE.2006.174
Volume 18
Issue 11
Start page 1544
End page 1559
Total pages 16
Editor F. B. Bastani
S. McConnell
Place of publication Piscataway, NJ, United States
Publisher IEEE Computer Society
Collection year 2006
Language eng
Subject C1
280103 Information Storage, Retrieval and Management
700103 Information processing services
Abstract With the rapid increase in both centralized video archives and distributed WWW video resources, content-based video retrieval is gaining its importance. To support such applications efficiently, content-based video indexing must be addressed. Typically, each video is represented by a sequence of frames. Due to the high dimensionality of frame representation and the large number of frames, video indexing introduces an additional degree of complexity. In this paper, we address the problem of content-based video indexing and propose an efficient solution, called the Ordered VA-File (OVA-File) based on the VA-file. OVA-File is a hierarchical structure and has two novel features: 1) partitioning the whole file into slices such that only a small number of slices are accessed and checked during k Nearest Neighbor (kNN) search and 2) efficient handling of insertions of new vectors into the OVA-File, such that the average distance between the new vectors and those approximations near that position is minimized. To facilitate a search, we present an efficient approximate kNN algorithm named Ordered VA-LOW (OVA-LOW) based on the proposed OVA-File. OVA-LOW first chooses possible OVA-Slices by ranking the distances between their corresponding centers and the query vector, and then visits all approximations in the selected OVA-Slices to work out approximate kNN. The number of possible OVA-Slices is controlled by a user-defined parameter delta. By adjusting delta, OVA-LOW provides a trade-off between the query cost and the result quality. Query by video clip consisting of multiple frames is also discussed. Extensive experimental studies using real video data sets were conducted and the results showed that our methods can yield a significant speed-up over an existing VA-file-based method and iDistance with high query result quality. Furthermore, by incorporating temporal correlation of video content, our methods achieved much more efficient performance.
Keyword Video Retrieval
Index Structure
High-dimensional Data
Ordered Va-file
Similarity Query
Computer Science, Artificial Intelligence
Computer Science, Information Systems
Engineering, Electrical & Electronic
Shot-boundary Detection
Image Databases
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 20 times in Thomson Reuters Web of Science Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 15 Aug 2007, 08:22:51 EST