High-dimensional Data Set Indexing Technology

In the field of content-based image and video analysis and object recognition, thelocal feature extraction methods such as SIFT have been maturely and widely used inrecent years.The set of local features is extracted from image or the keyframes of video,and the similarity of image or video can be measured by matching the sets of localfeatures. Set of local features tend to have properties of high dimension and largeamount, the traditional high-dimensional indexing technology for data point is nottailor-made for fast set matching. For the efficiency of query in high-dimensional space,a hierarchical framework for indexing high dimensional data point set and queryalgorithms is presented to speed up the set matching of data points, ensuring theaccuracy of matching.In this paper, we introduce the development of high-dimensional indexingtechnology and analyze the difficulty of applying the traditional high-dimensionalindexing technology for data point to set matching. A hierarchical indexing technologysuitable for large scale high-dimensional set matching is proposed. The new approachfirstly maps the high-dimensional data point set to a separate high-dimensional featurevector that is named high-level abstraction feature signature, through which we canmeasure the similarity between sets. Then establish the first index for the high-levelabstraction feature and the secondary index for local features set. A two-stage searchscheme is performed by utilizing high-level abstraction feature for fast filtering in thefirst stage. Only a small set of candidates is accessed for further investigation bypoint-to-point matching in the second stage. Experiment results show that the newapproach can reduce the number of data points accessed during the query, and canprovide a faster search speed than existing high-dimensional indexing methods. Finally,we apply our hierarchical framework to the Online Near-duplicate Video Detection. Ourextensive performance study on a large database of more than10,000video clipsdemonstrates that the hierarchical framework can improve the performance in detectingcopy video in real time.