The Open UniversitySkip to content

Dynamic batch nearest neighour search in video retrieval

Shao, Jie; Huang, Zi; Shen, Heng Tao; Zhou, Xiaofang and Li, Yijun (2007). Dynamic batch nearest neighour search in video retrieval. In: Proceedings of IEEE 23rd International Conference on Data Engineering (ICDE 2007), 17-20 Apr 2007, Istanbul, Turkey.

DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


To retrieve similar database videos to a query clip, each video is typically represented by a sequence of high-dimensional feature vectors. Given a query video containing m feature vectors, an independent nearest neighbor (NN) search for each feature vector is often first performed. Completing all the NN searches, an overall similarity is then computed, i.e., a single video retrieval usually involves the searches for m times. 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 single operation that performs a batch of individual NN searches. This paper presents a novel approach to efficient high-dimensional BNN search called dynamic query ordering (DQO) for advanced optimizations in both I/O and CPU cost. Observing the overlapped candidates (or search space) of a pervious query may help to further reduce the candidate sets of succeeding queries, DQO aims to progressively find 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 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. The extensive experiments show its significance.

Item Type: Conference or Workshop Item
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Knowledge Media Institute (KMi)
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 9049
Depositing User: Aneta Tumilowicz
Date Deposited: 25 Sep 2007
Last Modified: 07 Dec 2018 09:06
Share this page:


Altmetrics from Altmetric

Citations from Dimensions

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU