Improving Hit Ratio of ILP-based Concept Discovery System with Memoization

Mutlu A., Senkul P.

COMPUTER JOURNAL, vol.57, no.1, pp.138-153, 2014 (Peer-Reviewed Journal) identifier identifier

  • Publication Type: Article / Article
  • Volume: 57 Issue: 1
  • Publication Date: 2014
  • Doi Number: 10.1093/comjnl/bxs163
  • Journal Name: COMPUTER JOURNAL
  • Journal Indexes: Science Citation Index Expanded, Scopus
  • Page Numbers: pp.138-153


Although Inductive Logic Programming (ILP)-based concept discovery systems have applications in a wide range of domains, they still suffer from scalability and efficiency issues. One of the reasons for the efficiency problem is the high number of query executions necessary in the concept discovery process. Owing to the refinement operator of ILP-based concept discovery systems, these queries repeat frequently. In this work, we propose a method to improve the look-up table hit ratio for repeating queries of ILP-based concept discovery systems with memoization capabilities. The proposed method introduces modifications on search space evaluation and the covering steps of such systems so that query results of the previous iterations can be exploited. Experimental results show that the proposed method improves the hash table hit ratio of ILP-based concept discovery systems with an affordable cost of extra memory consumption.