Near Neighbor Index For SVM Retrieval

Mass of multimedia data is produced everyday along with the fast growing of computer power and internet.Especially,most of the data, which is published on internet,comes from images and videos.These kinds of data can deliver abundant semantic information,comparing with text data.But on the other side,they are hard]y to be organized,showed, stored,managed and retrieved.It is a big challenge to the traditional database based on Entity-Relation Model.Understanding how to manage and retrieve them is a crucial problem.Content Base Image Retrieval(CBIR)[8]tries to find similar images using visual features.People have presented many methods to improve the effect of CBIR,but it can not be solved ideally because of semantic gap. A common and popular CBIR method is using Relevance Feedback and Classification:training classifier from training data,classifying the data and return result to the user,getting the feedback from user and refine the classifier[18].The steps iterate until result is satisfied. Support Vector Machine(SVM)[1,11,12]is an excellent classifier and is used on many fields such as text classification[6],image retrieval[4]. But SVM is so slow that using on online system with large dataset is hard. To solve the problem,we introduce near neighbor index,which create index structure base on data points' neighborhood in feature space.We present two algorithms in this paper,one is Clustering based Near Neighbor Index and the other is Markov Random Model based Near Neighbor Index.The first applies clustering on dataset before creating index. When doing retrieval,it applies an iterative search on index to get candidate clusters firstly,and then investigate these clusters one by one to get result.The second directly creates index on dataset based on Markov Random Model[16,24].When doing retrieval,it gets candidate points directly be search index,and then sorts result by computing the weighted sum of minimum distance to support vectors for each point.We apply these two algorithms on a 0.74 million images dataset and a 21k images dataset separately.The experiment results show that these algorithms can improve the SVM retrieval efficiency and accuracy.