LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
MacFarlane, A.; Tuson, A. (2009)
Languages: English
Types: Article
Subjects: Z665
There are a number of combinatorial optimisation problems in information retrieval in which the use of local search methods are worthwhile. The purpose of this paper is to show how local search can be used to solve some well known tasks in information retrieval (IR), how previous research in the field is piecemeal, bereft of a structure and methodologically flawed, and to suggest more rigorous ways of applying local search methods to solve IR problems. We provide a query based taxonomy for analysing the use of local search in IR tasks and an overview of issues such as fitness functions, statistical significance and test collections when conducting experiments on combinatorial optimisation problems. The paper gives a guide on the pitfalls and problems for IR practitioners who wish to use local search to solve their research issues, and gives practical advice on the use of such methods. The query based taxonomy is a novel structure which can be used by the IR practitioner in order to examine the use of local search in IR.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • Buckley, C. and Voorhees, E.M. (2004). Retrieval evaluation with Incomplete information. In: Jarvelin, K., Allen, J., Bruza, P. and Sanderson, M. Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval: SIGIR 2004, pp. 25-32.
    • Chen, H. (1995). Machine learning for information retrieval: neural networks, symbolic learning, and genetic algorithms. .
    • Journal of the American Society for Information Science and Technology, Vol. 46, No. 3, pp. 194-216.
    • Chen, H, Shankaranarayanan, G., She, L. and Iyer, A. (1998). A machine learning approach to inductive query by examples: an experiment using relevance feedback, ID3, genetic algorithms, and simulated annealing. Journal of the American Society for Information Science and Technology, Vol. 49, No. 8, pp. 693-705.
    • Chen, H., Yi-Ming, C, Ramsey, M and Yang, C. (1998). An intelligent personal spider (agent) for dynamic Internet/Intranet searching. Decision Support Systems, Vol. 23, No. 1, pp. 41-58.
    • Christiensen, S. (2007). Tutorial Notes: Using Appropriate Statistics. Presented at the Genetic and Evolutionary Computation Conference (GECCO 2003).
    • Cleverdon, C. W. (1967). The Cranfield test on index language devices, ASLIB Proceeding, 19. In: Spark Jones, K and Willet, P. (eds), Readings in Information Retrieval, Morgan Kaufmann, San Francisco, pp. 47- 59.
    • Collins, N.E., Eglese, R.W. and Golden, B.L. (1988). Simulated annealing - an annotated bibliography, American Journal of Mathematical and Management Sciences, Vol. 8, pp. 209-307.
    • Cordon, O. Herrera-Viedma, E. and Luque, M. (2006). Improving the learning of Boolean queries by means of an multiobjective IQBE evolutionary algorithm. Information Processing and Management, Vol. 42, No. 3, pp. 615-632.
    • Cordon, O., Moya, F. and Zarco, C. (2002). A new evolutionary algorithm combining simulated annealing and genetic programming for relevance feedback in fuzzy information retrieval systems. Soft Computing, Vol. 6, No. 5, pp. 308-319.
    • Corne, D. Fang, H.-L. and Mellish, C. (1993). Solving the Module Exam Scheduling Problem with Genetic Algorithms.
    • In: Chung, P.W.H., Lovegrove, G. and Ali, M. (eds), Proceedings of the Sixth International Conference in Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, Gordon and Breach Science Publishers, pp. 370- 373.
    • Cormack, G.V. and Lynam, T.R. (2006). Statistical precision of Information Retrieval evaluation. In: Belkin, N. and van Rijsbergen, K. (eds). 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval: SIGIR 2006, pp 533-540, Darwin, C. (1859). On the Origin of Species, John Murray, London.
    • Dorigo, M. and Gambardella, L.M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66.
    • Downsland, K.A. (1991). Hill-climbing, simulated annealing, and the Stenier problem in graphs. Engineering Optimization, Vol. 17, No. 1, pp. 91-107.
    • Dueck, G. and Scheuer. T. (1990). Threshold Accepting: A General Purpose Optimisation Algorithm Superior to Simulated Annealing, Journal of Computation Physics, Vol. 90, No. 1, pp. 161-175.
    • Dueck, G. (1990). New Optimisation Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel, Technical report, IBM Germany, Heidelburg Scientific Center, Heidelburg.
    • Fan, W. Fox, E.A. Pathak, P. and Wu, H. (2004a). The effects of fitness functions on Genetic Programming-based ranking discovery for web search. Journal of the American Society for Information Science and Technology, Vol. 55, No. 7, pp.
    • Fan, W. Gordon, M.D. and Pathak, P. (2004b). Discovery of context-specific ranking functions for effective information retrieval. IEEE Transaction on Knowledge and Data Engineering, Vol. 16, No. 4, pp. 523-527.
    • Fan, W. Gordon, M.D. and Pathak, P. (2006). An integrated two-stage model for intelligent information routing. Decision Support Systems, Vol. 42, No. 6, pp. 362-374.
    • Feo, T.A. Bard, J.F. and Claflin, R.F. (1991). An overview of GRASP methodology and applications, Technical report, University of Texas at Austin, Austin.
    • Feo, T.A. Venkatraman, K. and Bard, J.F. (1991). A GRASP for a Difficult Single Machine Scheduling Problem.
    • Computers & Operations Research, Vol. 17, No. 8, pp. 635-643.
    • Fernandez-Villacanas Martin, J.L. and Shackleton, M. (2003). Investigation of the importance of the genotype-phenotype mapping in information retrieval, Future Generation Computer Systems, Vol. 19, No. 1, pp. 55-68.
    • Frakes, W. (1992a), Introduction to information storage and retrieval systems, In: Frakes, W.B. and Baeza-Yates (eds), Information Retrieval: Data Structures and Algorithms, Prentice Hall, New Jersey, pp 1-12.
    • Frakes, W. (1992b). Stemming algorithms. In: Frakes, W.B. and Baeza-Yates (eds), Information Retrieval: Data Structures and Algorithms, Prentice Hall, New Jersey, pp 131-160.
    • Fogel, D. B. and Angeline, P. J.. (1997). Guidelines for a Suitable Encoding. In Bäck, T... Fogel, D. B , and Michalewicz, Z. (Eds.), Handbook of Evolutionary Computation, Section C1.7, IOP Publishing and Oxford University Press, Bristol/New York, 1997.
    • Fogel, L.J., Owens, A.J. and Walsh, M.J. (1966). Artificial Intelligence Through Simulated Evolution, John Wiley and Sons.
    • Garey, M.R. and Johnson, D.S. (1979). Computers and Interactability: a Guide to the theory of NP-Completeness, Freeman, San Francisco.
    • Glover. F.W. (1990). Tabu Search: A Tutorial, Interfaces, Vol. 20, No. 4, pp. 445-460.
    • Glover, F.W. (1995). Tabu Thresholding: Improved Search by Nonmonotonic Trajectories. ORSA Journal on Computing, Vol. 7, No. 4, pp. 426-442.
    • Glover, F.W. and Laguna, M. (1997). Tabu Search, Kluwer Academic Publishers, Boston.
    • Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization & Machine Learning. Addison Wesley, Reading.
    • Hajek. B. (1988). Cooling schedules for optimal annealing, Mathematical of Operational Research, Vol. 13, No. 2, pp. 311- 329.
    • Harman, D. (1992a). Relevance feedback and other query modification techniques. In: Frakes, W.B. and Baeza-Yates (eds), Information Retrieval: Data Structures and Algorithms, Prentice Hall, New Jersey, pp 241-263.
    • Harman, D. (1992b). Ranking algorithms. In: Frakes, W.B. and Baeza-Yates (eds), Information Retrieval: Data Structures and Algorithms, Prentice Hall, New Jersey, pp 363-392.
    • Harman, D. (1995). The TREC Conferences, Procedings of HIM'95, In: Spark Jones, K and Willet, P. (eds), Readings in Information Retrieval, Morgan Kaufmann, San Francisco, pp. 247-256.
    • Harman, D, Fox, E., Baeza-Yates, R, and Lee, W. Inverted files. (1992). In: Frakes, W.B. and Baeza-Yates (eds), Information Retrieval: Data Structures and Algorithms, Prentice Hall, New Jersey, pp. 28-43.
    • Hawking, D. and Robertson, S.E. (2003). On collection size and retrieval effectiveness. Information Retrieval, Vol. 6, No.
    • 1, pp 99-150.
    • Hertz, A. and deWerra, D. (1987). Using tabu search techniques for graph coloring, Computing, Vol. 39, No. 4, pp. 345- 351.
    • Hertz, J., Krogh, K. and Palmer, R.G. (1991). Introduction to the Theory of Neural Computation, Addison-Wesley, Reading.
    • Hjorring, C.A. (1995). The Vehicle Routing Problem and Local Search Metaheuristics. PhD thesis, The University of Auckland, New Zealand.
    • Holland, J.H. (1975). Adaptation in Natural and Artificial Systems,The University of Michigan Press, Ann Arbor.
    • Hooker, J.N. (1995). Testing heuristics: We have it all wrong. Journal of Heuristics, Vol. 1, pp 33-42.
    • Horng, J.T. and Yeh, C.C. (2000). Applying genetic algorithms to query optimization in document retrieval, Information Processing and Management, Vol. 36, No. 5, pp. 737-759.
    • Kekäläinen, J and Järvelin, K. (2002). Using Graded Relevance assessments in IR evaluation. Journal of the American Society for Information Science and Technology, Vol. 53, No. 13, pp. 1120-1129.
    • Kirkpatrick, S., Gelatt, Jr., C.D. and Vecchi, M.P. (1983). Optimization by Simulated Annealing, Science, Vol. 220, No.
    • 4598, pp. 671-680.
    • Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge.
    • Kuflik, T., Boger, Z. and Shoval, P. (2006). Filtering search results using an optimal set of terms identified by an artificial neural network, Information Processing and Management, Vol. 42, No. 2, pp. 469-483.
    • Lam, W., Wang, W. and Yue, C. (2003). Web discovery and filtering based on textual relevance feedback learning.
    • Computational Intelligence, Vol. 19, No. 2, 136-163.
    • Lewis, D.D. (1997). The TREC-5 Filtering Track, In: Vooheers, E.M. and Harman, D.K., Proceedings of the Fifth Text Retrieval Conference, Gaithsburg, Maryland, November 20-22, 1996, NIST Special Publication 500-238, pp. 75-96.
    • Lopez-Pujalte, C., Guerrero Bote, V.P. and de Moya Anegon, F. (2002). A test of genetic algorithms in relevance feedback, Information Processing and Management, Vol. 38, No. 6, pp. 793-805.
    • Lopez-Pujalte, C., Guerrero-Bote, V.P. and de Moya-Anegon, F. (2003a). Order-based fitness functions for genetic algorithms applied to relevance feedback. Journal of the American Society for Information Science and Technology, Vol.
    • 54, No. 2, pp. 152-160.
    • Lopez-Pujalte, C., Guerrero-Bote, V.P. and de Moya-Anegon, F. (2003b). Genetic algorithms in relevance feedback: a second test and new contributions, Information Processing and Management, Vol. 39, No. 5, pp. 669-687.
    • Luke, B. T. (1996). An Overview of Genetic Methods. In Devillers, J. (Ed.), Genetic Algorithms in Molecular Modelling, Academic Press, London, pp. 35-66 Lundy, M. and Mees. A. (1986). Convergence of an annealing algorithm. Mathematical Programming, Vol. 34, No. 1, pp.
    • Martin-Bautisata, M.J., Vila, M. and Larsen, H.L. (1999). A Fuzzy genetic algorithm approach to an adaptive information retrieval agent. Journal of the American Society for Information Science and Technology, Vol. 50 No. 9, pp. 760-771.
    • Masters, T. (1993). Practical Neural Network Recipes in C++, Academic Press, London.
    • Motta, E. (1997). Reusable Components in Knowledge Modelling, PhD Thesis, Open University,U.K.
    • Mladenić, D. (2002). Automatic word lemmatization. In: Erjavec, T, and Gros, J. (eds), Proceedings of ISJT'02, Information Society Language Technologies, pp. 153-159. [Available on: http://nl.ijs.si/isjt02/zbornik/sdjt02- 26mladenic.pdf -Visited 15th September 2008] Mock, K.J. (1996). Hybrid Hill-Climbing and Knowledge-Based techniques for Intelligent News Filtering, In: Clancy, W.J, and Weld, D. (eds), Proceedings of the Thirteenth National Conference on Artificial Intelligence, 2-8. Menlo Park, Calif..: AAAI Press, Vol. 1, pp. 48-53.
    • Mock, K.J. and Rao Vemuri, V. (1997). Information filtering via Hill Climbing, Wordnet, and index patterns, Information Processing and Management, Vol. 33 No. 5, pp. 633-644.
    • Newell, A. (1982). The Knowledge Level, Artificial Intelligence, Vol. 18 No. 1, pp. 87-127.
    • Ogbu F.A. and Smith, D.K. (1990). The application of the simulated annealing algorithm to the solution of the n/m/P/Cmax flowshop problem, Computers and Operational Research, Vol. 17 No. 3, pp. 243-253.
    • Oliveira, S. and Stroud, G. (1989). A parallel version of tabu search and the path assignment problem, Heuristics for Combinatorial Optimisation, Vol. 4, No. 1, pp. 1-24.
    • Osman. I.H. and Potts, C.N. (1989). Simulated annealing for permutation flow-shop scheduling, OMEGA, Vol. 17, No. 6, pp. 551-557.
    • Osman, I.H. and Christofides, N. (1994). Capacitated clustering problems by hybrid simulated annealing and tabu search, International Transactions in Operations Research, Vol. 1 No. 3, pp. 317-336.
    • Osman. I.H. (1995). An introduction to Meta-Heuristics. In Lawrence M. and Wilsdon, C. (Eds), Operational Research Tutorial Papers, Operational Research Society, pp. 92-122.
    • Osman. I.H. and Kelly, J.P. (1996). Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, Boston.
    • Osman. I.H. and Laporte, G. (1996). Metaheuristics for combinatorial optimisation problems: An annotated bibliography, Annals of Operational Research, Vol. 63 No. 5, pp. 513-623.
    • Papadimitriou, H., and Steiglitz, K. (1982). Combinatorial Optimisation: Algorithms and Complexity. Prentice-Hall, New Jersey.
    • Pohlheim, H. and Marenbach, P. (1996). Generation of Structured Process Models Using Genetic Programming, In T. C.
    • Fogarty (ed.), Evolutionary Computing: AISB Workshop (LNCS 1143), Springer Verlag, Berlin, pp. 102-109.
    • Radcliffe, N.J. (1992). Non-Linear Genetic Representations. Technical Report, Edinburgh Parallel Computing Centre.
    • Rayward-Smith, V. J (1994). A Unified Approach To Tabu Search, Simulated Annealing and Genetic Algorithms. In: Rayward-Smith, V.J. (ed) The Proceedings of the UNICOM Seminar on Adaptive Computing and Information Processing, Vol. 1, pp. 55-78.
    • Rechenburg, I. (1973). Evolutionstrategie: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution.
    • Reeves, C.R. (1993). Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications, Oxford.
    • Robertson, S. (1990). On term selection for query expansion. Journal of Documentation, Vol. 46, No. 4, pp. 359-364.
    • Robertson, S. (2006). On GMAP - and other transformations. In: Yu, P.S., Tsotras, V.J., Fox, E.A, and Liu, B. (eds) Proceedings of ACM Fifteenth Conference on Information and Knowledge Management: CIKM 2006, pp. 78-83.
    • Robertson, S, Walker, S., Jones, S., Hancock- Beaulieu, M., and Gatford, M. (1995), Okapi at TREC-3, In: Harman, D (ed).
    • Proceedings of the Third Text Retrieval Conference, Gaithersburg, November 1994, NIST SP 500-226, pp 109-126.
    • Robertson, S, Walker, S., Jones, S., Hancock- Beaulieu, M., Gatford, M. and Payne, A. (1996), Okapi at TREC-4, In: Harman, D (ed). Proceedings of the Fourth Text Retrieval Conference, Gaithersburg, November 1995, NIST SP 500-236, pp. 73-96.
    • Sanderson, M. and Zobel, J. (2005). Information retrieval systems evaluation: effort, sensitivity, and reliability. In: Marchionini, G., Moffat, A., Tait, J. Baeza-Yates, Ziviani, N. (eds). Proccedings of the 28th Annual International ACM conference on Research and Development in Information Retrieval: SIGIR 2005, pp. 162-169.
    • Sebastiani, F. (2002). Machine learning in automated text categorization, ACM Computing Surveys, Vol. 34 No. 1, pp. 1- 47.
    • Semet, F. and Taillard. E. (1993). Solving real-life vehicle routing problems effectively using taboo search, Annals of Operational Research, Vol. 41, No. 4, pp. 469-488.
    • Sinclair, M. (1993). Comparison of the performance of modern heuristics for combinatorial problems on real data.
    • Computers and Operations Research, Vol. 20, No. 7, pp. 687-695.
    • Smith, M.P. and Smith, M. (1997). The use of genetic programming to build Boolean queries for text retrieval through relevance feedback, Journal of Information Science, Vol. 23, No. 6, pp. 423-431.
    • Sparck Jones, K., and van Rijsbergen, C.J. (1976). Information retrieval test collections. Journal of Documentation, Vol. 32, No. 1, pp59-75.
    • Stefik, M. (1995). Introduction to Knowledge Systems, Morgan Kaufmann, San Mateo.
    • Taylor, M., Zaragoza, H., Craswell, N., Robertson, S. and Burges, C. (2006). Optimisation methods for ranking functions with multiple parameters. In: Yu, P.S., Tsotras, V.J., Fox, E.A, and Liu, B. (eds) Proceedings of ACM Fifteenth conference on Information and Knowledge Management: CIKM 2006, pp. 585-593.
    • Tamine, L., Chrisment, C. and Boughanem, M. (2003). Multiple query evaluation based on an enhanced genetic algorithm, , Information Processing and Management, Vol. 39, No. 2, pp. 215-231.
    • Thangiah, S.R. (1995). An adaptive clustering method using a geometric shape for vehicle routing problems with time windows. In Eshelman, L.J. (ed), Proceedings of the Sixth International Conference on Genetic Algorithms, San Francisco, Ca., Morgan Kaufmann, pp. 536-544 Trotman, A. (2005). Choosing document structure weights, Information Processing and Management, Vol. 41, No. 2, pp.
    • Tuson, A.L. (2000). No Optimisation Without Representation: A Knowledge-Based Systems Evolutionary/Neighbourhood Search Optimiser Design. PhD Thesis, University of Edinburgh, U.K.
    • Vrajitoru, D. (1998). Crossover improvement for the genetic algorithm in information retrieval. Information Processing and Management, Vol. 34, No. 4, pp. 405-415.
    • Van Laarhoven P.J.M. and Aarts. E.H.L. (1988). Simulated Annealing: Theory and Applications, Kluwer, Dordrecht.
    • Voorhees, E. and Harman D (2000). Overview of the Eighth Text REtrieval Conference. In: Voorhees, E. and Harman D (eds) NIST Special Publication 500-246: The Eighth Text REtrieval Conference, pp. 1-24.
    • Wartik, S. (1992). Boolean Operations. In: Frakes, W.B. and Baeza-Yates (eds), Information Retrieval: Data Structures and Algorithms, Prentice Hall, New Jersey, pp 264-292.
    • Walker, S., Robertson, S, and Boughanem, M. (1998). Okapi at TREC-6: automatic ad hoc, VLC, routing and filtering. In: Voorhees, E. and Harman, D (eds). Proceedings of the Fifth Text Retrieval Conference, Gaithersburg, November 1996, NIST SP 500-240, pp.125-136.
    • Wei L., S.E. Robertson, and A, Macfarlane (2006). Field-Weighted XML Retrieval Based on BM25, In: Fuhr, N., Lalmas, M., Malik, S. and Kazai, G. Proceedings of the 4rh International Workshop of the Initiative for the Evaluation of XML Retrieval, INEX 2005, LNCS 3977, pp. 161-171.
    • Wolpert D.H. and Macready, W.G. (1995). No free lunch theorems for search, Technical report, SFI-TR-95-02-010, Santa Fe Institute.
    • Wong, S.K.M., Cai, Y.J. and Yao. Y.Y. (1993). In: Korfage, R, Rasmussen, E. and Willett, P. (eds). Proceedings of the 16th Annual ACM conference on Research and Development in Information Retrieval: SIGIR'93, pp. 107-115.
    • Yang, C., Yen, J. and Chen, H. (2000). Intelligent Internet searching agent based on hybrid simulated annealing. Decision Support Systems, Vol. 28, No. 3, pp. 269-277.
    • Zweben, M., Davis, E., Daun, B. and Deale, M. (1993). Scheduling and Rescheduling with Iterative Repair, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 23, No. 6, pp. 1588-1596.
  • No related research data.
  • No similar publications.

Share - Bookmark

Download from

Cite this article