Batch nearest neighbor search for video retrieval

Jie Shao, Zi Huang, Shen, Heng Tao, Zhou, Xiaofang, Lim, Ee-Peng and Li, Yijun (2008) Batch nearest neighbor search for video retrieval. IEEE Transactions on Multimedia, 10 3: 409-420. doi:10.1109/TMM.2008.917339

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

Author Jie Shao
Zi Huang
Shen, Heng Tao
Zhou, Xiaofang
Lim, Ee-Peng
Li, Yijun
Title Batch nearest neighbor search for video retrieval
Journal name IEEE Transactions on Multimedia   Check publisher's open access policy
ISSN 1520-9210
Publication date 2008-04-01
Year available 2008
Sub-type Article (original research)
DOI 10.1109/TMM.2008.917339
Open Access Status Not yet assessed
Volume 10
Issue 3
Start page 409
End page 420
Total pages 12
Editor B. J. Sheu
Place of publication Piscataway, NJ, USA
Publisher IEEE
Language eng
Subject C1
0806 Information Systems
890205 Information Processing Services (incl. Data Entry and Capture)
Abstract To retrieve similar videos to a query clip from a large database, each video is often represented by a sequence of high- dimensional feature vectors. Typically, given a query video containing m feature vectors, an independent nearest neighbor (NN) search for each feature vector is often first performed. After completing all the NN searches, an overall similarity is then computed, i.e., a single content-based video retrieval usually involves m individual NN searches. Since normally nearby feature vectors in a video are similar, a large number of expensive random disk accesses are expected to repeatedly occur, which crucially affects the overall query performance. Batch nearest neighbor (BNN) search is stated as a batch operation that performs a number of individual NN searches. This paper presents a novel approach towards efficient high-dimensional BNN search called dynamic query ordering (DQO) for advanced optimizations of both I/O and CPU costs. Observing the overlapped candidates (or search space) of a pervious query may help to further reduce the candidate sets of subsequent queries, DQO aims at progressively finding a query order such that the common candidates among queries are fully utilized to maximally reduce the total number of candidates. Modelling the candidate set relationship of queries by a candidate overlapping graph (COG), DQO iteratively selects the next query to be executed based on its estimated pruning power to the rest of queries with the dynamically updated COG. Extensive experiments are conducted on real video datasets and show the significance of our BNN query processing strategy.
Keyword content-based retrieval
high-dimensional indexing
multimedia databases
query processing
Q-Index Code C1
Q-Index Status Confirmed Code
Grant ID DP0663272
Institutional Status UQ

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 16 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Mon, 13 Apr 2009, 23:33:32 EST by Donna Clark on behalf of School of Information Technol and Elec Engineering