Abstract
Process-Oriented Case-Based Reasoning (PO-CBR) systems often use structured cases, which in turn require effective structure-based retrieval methods, especially when dealing with large processes and/or large case bases. Good retrieval performance can be facilitated by two-phased retrieval methods which first winnow candidate cases with a comparatively inexpensive retrieval phase, and then apply a more expensive strategy to rank the selected cases. Examples of such processes have been shown to provide good retrieval results in limited retrieval time. However, studies of such methods have focused primarily on overall performance, rather than on how the individual contributions of each phase interact to affect overall performance. This misses an opportunity to tune the component algorithms in light of the system task and case base characteristics, for specific task needs. This chapter examines two-phased retrieval as a means of addressing the complexity in many PO-CBR domains, and specifically examines the performance of each phase of two-phased retrieval individually, demonstrating characteristics of the phases’ interaction and providing general lessons for how to design and deploy two-phased retrieval systems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The Structure Access Interface (SAI): http://www.cs.indiana.edu/~jmorwick/SAI
References
Aamodt, A., Plaza, E.: Case-based reasoning: foundational issues, methodological variations, and system approaches. AI Commun. 7(1), 39–52. http://www.iiia.csic.es/People/enric/AICom.pdf (1994)
Leake, D.: CBR in context: the present and future. In: Leake, D. (ed.) Case-Based Reasoning. Experiences, Lessons and Future Directions, pp. 3–30. AAAI Press, Menlo Park (1996)
Mantaras, R., McSherry, D., Bridge, D., Leake, D., Smyth, B., Craw, S., Faltings, B., Maher, M., Cox, M., Forbus, K., Keane, M., Aamodt, A., Watson, I.: Retrieval, reuse, revision, and retention in CBR. Knowl. Eng. Rev. 20(3), 255–260 (2005)
Minor, M., Montani, S.: Proceedings of the ICCBR-2012 workshop on provenance-aware case-based reasoning (2012)
Han, W.S., Pham, M.D., Lee, J., Kasperovics, R., Yu, J.X.: igraph in action: performance analysis of disk-based graph indexing techniques. In: Proceedings of the International Conference on Management of Data, SIGMOD ’11, pp.1241–1242. ACM, New York (2011)
Kendall-Morwick, J., Leake, D.: Facilitating representation and retrieval of structured cases: principles and toolkit. Information Systems (2012, in press)
Leake, D.: An indexing vocabulary for case-based explanation. In: Proceedings of the 9th National Conference on Artificial Intelligence, pp. 10–15. AAAI Press, Menlo Park (1991)
Schank, R., Osgood, R., Brand, M., Burke, R., Domeshek, E., Edelson, D., Ferguson, W., Freed, M., Jona, M., Krulwich, B., Ohmayo, E., Pryor, L.: A content theory of memory indexing. Technical report 1, Institute for the Learning Sciences, Northwestern University (1990)
Reichherzer, T., Leake, D.: Towards automatic support for augmenting concept maps with documents. In: Proceedings of 2nd International Conference on Concept Mapping (2006)
Minor, M., Montani, S.: Preface. In: Proceedings of the ICCBR-12 Workshop on Process-Oriented Case-Based Reasoning (2012)
Floyd, M., Fuchs, B., Gonzlez-Calero, P., Leake, D., Ontañón, S., Plaza, E., Rubin, J.: Preface. In: Proceedings of the ICCBR-12 Workshop on TRUE: Traces for Reusing Users’ Experiences—Cases, Episodes, and Stories (2012)
Leake, D., Roth-Berghofer, T., Smyth, B., Kendall-Morwick, J. (eds.): Proceedings of the ICCBR-2010 workshop on Provenance-Aware Case-Based Reasoning (2010)
Ko, R.K.L.: A computer scientist’s introductory guide to business process management (bpm). Crossroads 15(4), 4:11–4:18 (2009)
Montani, S., Leonardi, G.: Retrieval and clustering for business process monitoring: results and improvements. In: Díaz-Agudo, B., Watson, I. (eds.) ICCBR. Lecture Notes in Computer Science, vol 7466, pp. 269–283. Springer, New York (2012)
Minor, M., Tartakovski, A., Bergmann, R.: Representation and structure-based similarity assessment for agile workflows. In: Proceedings of the 7th International Conference on Case-Based Reasoning: Case-Based Reasoning Research and Development, ICCBR ’07, pp. 224–238. Springer, Berlin (2007)
Kapetanakis, S., Petridis, M., Ma, J., Knight, B., Bacon, L.: Enhanching similarity measures and context provision for the intelligent monitoring of business processes in cbr-wims. In: Proceedings of the ICCBR-11 Workshop on Process-Oriented Case-Based Reasoning (2011)
Oinn, T., Greenwood, M., Addis, M., Alpdemir, M.N., Ferris, J., Glover, K., Goble, C., Goderis, A., Hull, D., Marvin, D., Li, P., Lord, P., Pocock, M.R., Senger, M., Stevens, R., Wipat, A., Wroe, C.: Taverna: lessons in creating a workflow environment for the life sciences: research articles. concurr. Comput. 18(10), 1067–1100 (2006)
Oinn, T., Addis, M., Ferris, J., Marvin, D., Senger, M., Greenwood, M., Carver, T., Glover, K., Pocock, M.R., Wipat, A., Li, P.: Taverna: a tool for the composition and enactment of bioinformatics workflows. Bioinformatics 20(17), 3045–3054 (2004)
Altintas, I., Berkley, C., Jaeger, E., Jones, M., Ludascher, B., Mock, S.: Kepler: An extensible system for design and execution of scientific workflows. In: Proceedings of the 16th International Conference on Scientific and Statistical Database Management, IEEE Computer Society, Washington (2004)
Barga, R., Jackson, J., Araujo, N., Guo, D., Gautam, N., Simmhan, Y.: The trident scientific workflow workbench. In: Proceedings of the 4th IEEE International Conference on eScience, pp. 317–318. IEEE Computer Society, Washington (2008)
Shirasuna, S.: A Dynamic Scientific Workflow System for the Web Services Architecture. PhD thesis, Indiana University (2007)
Goble, C.A., De Roure, D.C.: Myexperiment: social networking for workflow-using e-scientists. In: Proceedings of the 2nd Workshop on Workflows in Support of Large-Scale Science, WORKS ’07, pp. 1–2. ACM, New York (2007)
Bhagat, J., Tanoh, F., Nzuobontane, E., Laurent, T., Orlowski, J., Roos, M., Wolstencroft, K., Aleksejevs, S., Stevens, R., Pettifer, S., Lopez, R., Goble, C.A.: Biocatalogue: a universal catalogue of web services for the life sciences. Nucleic Acids Res. 38(Web-Server-Issue), 689–694 (2010)
Kendall-Morwick, J.: Leveraging Structured Cases: Reasoning from Provenance Cases to Support Authorship of Workflows. PhD thesis, Indiana University (2012)
Mileman, T., Knight, B., Petridis, M., Preddy, K., Mejasson, P.: Maintenance of a case-base for the retrieval of rotationally symmetric shapes for the design of metal castings. In: Proceedings of the 5th European Workshop on Advances in Case-Based Reasoning, EWCBR ’00, pp. 418–430. Springer, London (2000)
Stahl, A., Minor, M., Traphöner, R.: Preface: computer cooking contest. In: Schaaf, M. (ed.) ECCBR Workshops, pp. 197–198 (2008)
Cañas, A.J., Leake, D.B., Maguitman, A.G.: Combining concept mapping with CBR: towards experience-based support for knowledge modeling. In: Proceedings of the 14th International Florida Artificial Intelligence Research Society Conference, pp. 286–290. AAAI Press, Menlo Calif (2001)
Bergmann, R., Gil, Y.: Retrieval of semantic workfows with knowledge intensive similarity measures. In: Proceedings of 19th International Conference on Case-Based Reasoning, Springer, Berlin (2011, in Press)
Bergmann, R., Minor, M., Islam, M.S., Schumacher, P., Stromer, A.: Scaling similarity-based retrieval of semantic workflows. In: Proceedings of the ICCBR-12 Workshop on Process-Oriented Case-Based Reasoning (2012)
Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, STOC ’71, pp. 151–158. ACM, New York (1971)
Minor, M., Bergmann, R., Grg, S., Walter, K.: Adaptation of cooking instructions following the workflow paradigm. In: Marling, C. (ed.) ICCBR 2010 Workshop Proceedings (2010)
Gentner, D., Forbus, K.: MAC/FAC: A model of similarity-based retrieval. In: Proceedings of the 13th Annual Conference of the Cognitive Science Society, pp. 504–509. Cognitive Science Society, Chicago (1991)
Mntaras, R.L.D., Bridge, D., Mcsherry, D.: Case-based reasoning: an overview. AI Commun. 10, 21–29 (1997)
Börner, K.: Structural similarity as guidance in case-based design. In: Selected Papers from the 1st European Workshop on Topics in Case-Based Reasoning, EWCBR ’93, pp. 197–208. Springer, London (1994)
Kendall-Morwick, J., Leake, D.: A toolkit for representation and retrieval of structured cases. In: Proceedings of the ICCBR-11 Workshop on Process-Oriented Case-Based Reasoning (2011)
Bergmann, R., Gil, Y.: Retrieval of semantic workflows with knowledge intensive similarity measures. In: Proceedings of the 19th International Conference on Case-Based Reasoning Research and Development, ICCBR’11, pp. 17–31. Springer, Berlin (2011)
Wang, X., Smalter, A., Huan, J., Lushington, G.H.: G-hash: towards fast kernel-based similarity search in large graph databases. In: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT ’09, pp. 472–480. ACM, New York (2009)
Tian, Y., Patel, J.M., Nair, V., Martini, S., Kretzler, M.: Periscope/GQ: a graph querying toolkit. Proc. VLDB Endow. 1, 1404–1407 (2008)
Yan, X., Yu, P.S., Han, J.: Graph indexing: a frequent structure-based approach. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD ’04, pp. 335–346. ACM, New York (2004)
Giugno, R., Shasha, D.: Graphgrep: a fast and universal method for querying graphs. In: Proceedings of 16th International Conference on Pattern Recognition, vol. 2, pp. 112–115 (2002)
Angles, R., Gutierrez, C.: Survey of graph database models. ACM Comput. Surv. 40, 1:1–1:39 (2008)
Kendall-Morwick, J., Leake, D.: On tuning two-phase retrieval for structured cases. In: Proceedings of the ICCBR-12 Workshop on Process-Oriented Case-Based Reasoning (2012)
Aha, D., Breslow, L., Munoz-Avila, H.: Conversational case-based reasoning. Appl. Intell. 14, 9–32 (2001)
Weber, B., Reichert, M., Wild, W.: Case-base maintenance for ccbr-based process evolution. In: Roth-Berghofer, T., Göker, M.H., Güvenir, H.A. (eds.) ECCBR. Lecture Notes in Computer Science, vol. 4106, pp. 106–120. Springer, Berlin (2006)
Allampalli-Nagaraj, G., Bichindaritz, I.: Automatic semantic indexing of medical images using a web ontology language for case-based image retrieval. Eng. Appl. Artif. Intell. 22(1), 18–25 (2009)
Yan, X., Yu, P.S., Han, J.: Substructure similarity search in graph databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD ’05, pp. 766–777. ACM, New York (2005)
Bogaerts, S., Leake, D.: Formal and experimental foundations of a new rank quality measure. In: Proceedings of the 9th European conference on Advances in Case-Based Reasoning, ECCBR ’08, pp. 74–88. Springer, Berlin (2008)
Leake, D., Kendall-Morwick, J.: Towards case-based support for e-science workflow generation by mining provenance. In: Proceedings of the 9th European Conference on Advances in Case-Based Reasoning, ECCBR ’08, pp. 269–283. Springer, Berlin (2008)
Bolton, E.E., Wang, Y., Thiessen, P.A., Bryant, S.H.: PubChem: integrated platform of small molecules and biological activities. Annu. Rep. Comput. Chem. 4, 217–241 (2008)
Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: Proceedings of the 23rd International Conference on Machine Learning, ICML ’06, pp. 97–104. ACM, New York (2006)
Schaaf, J.W.: Fish and shrink. a next step towards efficient case retrieval in large-scale case bases. In: Proceedings of the 3rd European Workshop on Advances in Case-Based Reasoning, EWCBR ’96, pp. 362–376. Springer, London (1996)
Lenz, M., Burkhard, H.D.: Case retrieval nets: basic ideas and extensions. In: Grz, G., Hldobler, S. (eds.) KI-96: Advances in Artificial Intelligence. Lecture Notes in Computer Science, vol. 1137, pp. 227–239. Springer, Berlin (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kendall-Morwick, J., Leake, D. (2014). A Study of Two-Phase Retrieval for Process-Oriented Case-Based Reasoning. In: Montani, S., Jain, L. (eds) Successful Case-based Reasoning Applications-2. Studies in Computational Intelligence, vol 494. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38736-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-38736-4_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38735-7
Online ISBN: 978-3-642-38736-4
eBook Packages: EngineeringEngineering (R0)