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 Apr2007, Istanbul, Turkey.

DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1109/ICDE.2007.369020
Google Scholar: Look up in Google Scholar

Abstract

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 Item
Academic Unit/Department: Knowledge Media Institute
Item ID: 9049
Depositing User: Aneta Tumilowicz
Date Deposited: 25 Sep 2007
Last Modified: 02 Dec 2010 20:03
URI: http://oro.open.ac.uk/id/eprint/9049
Share this page:

Altmetrics

Scopus Citations

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk