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

ABSTRACT

Adaptive search engines (ASE), used in the retrieval of multimedia objects adapt their behavior depending on the user feedback in order to eventually converge to the optimal answer. The adaptive architecture has been shown to improve the performance in case of multimedia objects retrieval, when pre-indexing techniques are costly or can be applied only partially. The continuous user feedbacks on the lists of returned objects are used to filter out irrelevant objects and promote the relevant ones. This work propose an original dealer/opponent game model for ASE. The system/user interactive process which takes place in ASE can be modeled as a discovery game between a dealer, the user community which holds a secret consisting in the optimal answer to a query, and an opponent, i.e. the system, which tries to discover the secret by submitting tentative solutions on which it receives the user/dealer feedback. It is shown how the complexity of the game can be related to known games. An evolutionary approach to solve the ASE game is also presented. Experimental results shows convergence to the optimal solution with acceptable performance for real domain size. The proposed schema is quite general and can fit other adaptive search architectures which appear in e-business and e-commerce applications.

REFERENCES

• 1: Clement H. Leung , Jiming Liu , Alice W. Chan , Alfredo Milani, An Architectural Paradigm for Collaborative Semantic Indexing of Multimedia Data Objects, Proceedings of the 10th international conference on Visual Information Systems: Web-Based Visual Information Search and Management, September 11-12, 2008, Salerno, Italy [doi>10.1007/978-3-540-85891-1_24]
• 2: Jiang Bian , Yandong Liu , Eugene Agichtein , Hongyuan Zha, Finding the right facts in the crowd: factoid question answering over social media, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367561]
• 3: Shan-Tai Chen and Shun-Shii Lin. Optimal algorithms for 2 x n mastermind games---a graph-partition approach. The Computer Journal, 47(5):602--611, 2004.
• 4: Christian Deppe, Strategies for the Renyi-Ulam game with fixed number of lies, Theoretical Computer Science, v.314 n.1, p.45-55, 25 February 2004 [doi>10.1016/j.tcs.2003.10.036]
• 5: Alan Mislove , Massimiliano Marcon , Krishna P. Gummadi , Peter Druschel , Bobby Bhattacharjee, Measurement and analysis of online social networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298311]
• 6: José Luis Bernier , C. Ilia Herráiz , Juan J. Merelo Guervós , S. Olmeda , Alberto Prieto, Solving Master Mind Using GAs and Simulated Annealing: A Case of Dynamic Constraint Optimization, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.554-563, September 22-26, 1996
• 7: Le Chen , Lei Zhang , Feng Jing , Ke-Feng Deng , Wei-Ying Ma, Ranking web objects from multiple communities, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183670]
• 8: Shumeet Baluja , Rohan Seth , D. Sivakumar , Yushi Jing , Jay Yagnik , Shankar Kumar , Deepak Ravichandran , Mohamed Aly, Video suggestion and discovery for youtube: taking random walks through the view graph, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367618]
• 9: Yashmeet Khopkar et al. Search engine personalization, an exploratory study. First Monday, 8(7), July 07 2003.
• 10: Paolo Ferragina , Giovanni Manzini, Indexing compressed text, Journal of the ACM (JACM), v.52 n.4, p.552-581, July 2005 [doi>10.1145/1082036.1082039]
• 11: Michael J. Fischer and Rebecca N. Wright. R.n.: An application of game-theoretic techniques to cryptography. In Discrete Mathematics and Theoretical Computer Science 13, pages 99--118. American Mathematical Society, 1993.
• 12: Wayne Goddard. Static mastermind. J. Combin. Math. Combin. Comput., 47(1):225--236, 2003.
• 13: Martin J. Halvey , Mark T. Keane, Exploring social dynamics in online media sharing, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242804]
• 14: Eszter Hargittai. Do you "google"? understanding search engine use beyond the hype. First Monday, 9(3), March 01 2004.
• 15: Seikyung Jung , Kevin Harris , Janet Webster , Jonathan L. Herlocker, SERF: integrating human recommendations with search, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031277]
• 16: Gillat Kol and Moni Naor. Cryptography and game theory: Designing protocols for exchanging information. TCC.
• 17: Kristina Lerman, User Participation in Social Media: Digg Study, Proceedings of the 2007 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology - Workshops, p.255-258, November 02-05, 2007
• 18: Maass and Nowak. Text indexing with errors. In CPM: 16th Symposium on Combinatorial Pattern Matching, 2005.
• 19: C. Dianne Martin, Blogger ethics and YouTube common sense, ACM SIGCSE Bulletin, v.39 n.4, December 2007 [doi>10.1145/1345375.1345379]
• 20: Xiannong Meng , Ty Clark, An Empirical User Rating of Popular Search Engines Using RankPower, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume II, p.521-525, April 04-06, 2005 [doi>10.1109/ITCC.2005.76]
• 21: Alfredo Milani. Online genetic algorithms. In International Journal of Information Theories and Applications, volume 11, pages 20--28, 2004.
• 22: Shun-Shii Lin Shan-Tai Chen and Li-Te Huang. Exact-bound analyzes and optimal strategies for mastermind with a lie. LNCS, 4250:195--209, 2006.
• 23: Shan-Tai Chen , Shun-Shii Lin , Li-Te Huang, A Two-Phase Optimization Algorithm For Mastermind, The Computer Journal, v.50 n.4, p.435-443, July 2007 [doi>10.1093/comjnl/bxm006]
• 24: Jeff Stuckman and Guo qiang Zhang. Mastermind is np-complete. INFOCOMP J. Comput. Sci, 5:25--28, 2006.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games

General Terms:
Algorithms, Theory

Keywords:
adaptive information retrieval, collective knowledge, evolutionary computation, game theory