Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Support vector machines (SVMs) have been widely used in multimedia retrieval to learn a concept in order to find the best matches. In such a SVM active learning environment, the system first processes k sampling queries and top-k uncertain queries to select the candidate data items for training. The user's top-k relevant queries are then evaluated to compute the answer. This approach has shown to be effective. However, it suffers from the scalability problem associated with larger database sizes. To address this limitation, we propose an incremental query evaluation technique for these three types of queries. Based on the observation that most queries are not revised dramatically during the iterative evaluation, the proposed technique reuses the results of previous queries to reduce the computation cost. Furthermore, this technique takes advantage of a tuned index structure to efficiently prune irrelevant data. As a result, only a small portion of the data set needs to be accessed for query processing. This index structure also provides an inexpensive means to process the set of candidates to evaluate the final query result. This technique can work with different kernel functions and kernel parameters. Our experimental results indicate that the proposed technique significantly reduces the overall computation cost, and offers a promising solution to the scalability issue.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 2: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 3: C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines. URL:http://www.csie.ntu.edu.tw/~cjlin/libsvm/.
• 4: Frank Olken , Doron Rotem, Sampling from Spatial Databases, Proceedings of the Ninth International Conference on Data Engineering, p.199-208, April 19-23, 1993
• 5: Navneet Panda , Edward Y. Chang, Efficient top-k hyperplane query processing for multimedia information retrieval, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA [doi>10.1145/1180639.1180712]
• 6: H. Sagan. Space-Filling Curves. Springer, 1994.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models; Selection process; Search process

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
active learning, multimedia retrieval, relevance feedback, support vector machines