Parallel ILP for Distributed-Memory Architectures

• Author(s): Nuno A. Fonseca ; Ashwin Srinivasan ; Fernando Silva ; Rui Camacho
• Date: 2009
• Persistent ID: http://hdl.handle.net/10216/76194
• Origin: Repositório Aberto da Universidade do Porto
• Subject(s): Ciências Físicas; Ciência de computadores
• Document Type: Article
• Language: English

Description

The growth of machine-generated relational databases, both in thesciences and in industry, is rapidly outpacing our ability to extract useful information from them by manual means. This has brought into focus machine learning techniques like Inductive Logic Programming (ILP) that are able to extract humancomprehensible models for complex relational data. The price to pay is that ILP techniques are not ecient: they can be seen as performing a form of discrete optimisation, which is known to be computationally hard; and the complexity is usually some non-linear function of the number of examples. While little can be done to alter the theoretical bounds on the worst-case complexity of ILP systems, some practical gains may follow from the use of multiple processors. In this paper we survey the state-of-the-art on parallel ILP. We implement several parallel algorithms and study their performance using some standard benchmarks. The principal ndings of interest are these: (1) of the techniques investigated, one that simply constructs models in parallel on each processor using a subset of data and then combines the models into a single one, yields the best results; and (2) sequential (approximate) ILP algorithms based on randomized searches have lower execution times than (exact) parallel algorithms, without sacricing the quality of the solutions found.