Abstract
This work aims at improving the scalability of memory usage in Inductive Logic Programming systems. In this context, we propose two efficient data structures: the Trie, used to represent lists and clauses; and the RL-Tree, a novel data structure used to represent the clauses coverage. We evaluate their performance in the April system using well known datasets. Initial results show a substantial reduction in memory usage without incurring extra execution time overheads. Our proposal is applicable in any ILP system.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Muggleton, S.: Inductive logic programming. In: Proceedings of the 1st Conference on Algorithmic Learning Theory, Ohmsma, Tokyo, Japan, pp. 43–62 (1990)
Muggleton, S.: Inductive logic programming. New Generation Computing 8(4), 295–317 (1991)
Ilp applications, http://www.cs.bris.ac.uk/~ILPnet2/Applications/
Nédellec, C., Rouveirol, C., Adé, H., Bergadano, F., Tausend, B.: Declarative bias in ILP. In: De Raedt, L. (ed.) Advances in Inductive Logic Programming, pp. 82–103. IOS Press, Amsterdam (1996)
Camacho, R.: Improving the efficiency of ilp systems using an incremental language level search. In: Annual Machine Learning Conference of Belgium and the Netherlands (2002)
Blockeel, H., Dehaspe, L., Demoen, B., Janssens, G., Ramon, J., Vandecasteele, H.: Improving the efficiency of Inductive Logic Programming through the use of query packs. Journal of Artificial Intelligence Research 16, 135–166 (2002)
Costa, V.S., Srinivasan, A., Camacho, R.: A note on two simple transformations for improving the efficiency of an ILP system. In: Cussens, J., Frisch, A.M. (eds.) ILP 2000. LNCS (LNAI), vol. 1866, p. 225. Springer, Heidelberg (2000)
Costa, V.S., Srinivasan, A., Camacho, R., Hendrik, Van Laer, W.: Query transformations for improving the efficiency of ilp systems. Journal of Machine Learning Research (2002)
Camacho, R.: Inductive Logic Programming to Induce Controllers. PhD thesis, Univerity of Porto (2000)
Page, D.: ILP: Just do it. In: Cussens, J., Frisch, A.M. (eds.) ILP 2000. LNCS (LNAI), vol. 1866, pp. 3–18. Springer, Heidelberg (2000)
Matsui, T., Inuzuka, N., Seki, H., Itoh, H.: Comparison of three parallel implementations of an induction algorithm. In: 8th Int. Parallel Computing Workshop, Singapore, pp. 181–188 (1998)
Ohwada, H., Mizoguchi, F.: Parallel execution for speeding up inductive logic programming systems. In: Arikawa, S., Furukawa, K. (eds.) DS 1999. LNCS (LNAI), vol. 1721, pp. 277–286. Springer, Heidelberg (1999)
Ohwada, H., Nishiyama, H., Mizoguchi, F.: Concurrent execution of optimal hypothesis search for inverse entailment. In: Cussens, J., Frisch, A.M. (eds.) ILP 2000. LNCS (LNAI), vol. 1866, pp. 165–173. Springer, Heidelberg (2000)
Wang, Y., Skillicorn, D.: Parallel inductive logic for data mining. In: Workshop on Distributed and Parallel Knowledge Discovery, KDD 2000, Boston, ACM Press, New York (2000)
Dehaspe, L., De Raedt, L.: Parallel inductive logic programming. In: Proceedings of the MLnet Familiarization Workshop on Statistics, Machine Learning and Knowledge Discovery in Databases (1995)
Aleph, http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/
Fonseca, N., Camacho, R., Silva, F., Costa, V.S.: Induction with April: A preliminary report. Technical Report DCC-2003-02, DCC-FC, Universidade do Porto (2003)
Fredkin, E.: Trie Memory. Communications of the ACM 3, 490–499 (1962)
Ramakrishnan, I.V., Rao, P., Sagonas, K., Swift, T., Warren, D.S.: Efficient Access Mechanisms for Tabled Logic Programs. Journal of Logic Programming 38(1), 31–54 (1999)
Bachmair, L., Chen, T., Ramakrishnan, I.V.: Associative-Commutative Discrimination Nets. In: Gaudel, M.-C., Jouannaud, J.-P. (eds.) CAAP 1993, FASE 1993, and TAPSOFT 1993. LNCS, vol. 668, pp. 61–74. Springer, Heidelberg (1993)
Graf, P. (ed.): Term Indexing. LNCS (LNAI), vol. 1053. Springer, Heidelberg (1996)
McCune, W.W.: Experiments with Discrimination-Tree Indexing and Path Indexing for Term Retrieval. Journal of Automated Reasoning 9(2), 147–167 (1992)
Ohlbach, H.J.: Abstraction Tree Indexing for Terms. In: Proceedings of the 9th European Conference on Artificial Intelligence, Stockholm, Sweden, pp. 479–484. Pitman Publishing (1990)
Samet, H.: The quadtree and related hierarchical data structures. ACM Computing Surveys (CSUR) 16(2), 187–260 (1984)
Richards, B.L., Mooney, R.J.: Automated refinement of first-order horn-clause domain theories. Machine Learning 19(2), 95–131 (1995)
Cussens, J.: Part-of-speech disambiguation using ilp. Technical Report PRGTR- 25-96, Oxford University Computing Laboratory (1996)
Samet, H.: Data structures for quadtree approximation and compression. Communications of the ACM 28(9), 973–993 (1985)
Costa, V.S., Damas, L., Reis, R., Azevedo, R.: YAP Prolog User’s Manual. Universidade do Porto (1989)
Muggleton, S., Feng, C.: Efficient induction in logic programs. In: Muggleton, S. (ed.) Inductive Logic Programming, pp. 281–298. Academic Press, London (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fonseca, N., Rocha, R., Camacho, R., Silva, F. (2003). Efficient Data Structures for Inductive Logic Programming. In: Horváth, T., Yamamoto, A. (eds) Inductive Logic Programming. ILP 2003. Lecture Notes in Computer Science(), vol 2835. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39917-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-39917-9_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20144-1
Online ISBN: 978-3-540-39917-9
eBook Packages: Springer Book Archive