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

Date

2014-01-01

Author

Mutlu, Alev
Karagöz, Pınar

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

137
views

0
downloads

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.

Subject Keywords

Inductive Logic Programming, Concept discovery, Efficiency, Memoization, Hit count

URI

https://hdl.handle.net/11511/62640

Journal

COMPUTER JOURNAL

DOI

https://doi.org/10.1093/comjnl/bxs163

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

Utilizing Coverage Lists as a Pruning Mechanism for Concept Discovery Mutlu, Alev; Doğan, Abdullah; Karagöz, Pınar (2014-10-28) Inductive logic programming (ILP)-based concept discovery systems lack computational efficiency due to the evaluation of the large search spaces they build. One way to tackle this issue is employing pruning mechanisms. In this work, we propose a two-phase pruning mechanism for concept discovery systems that employ an Apriori-like refinement operator and evaluate the goodness of the concept descriptors based on their support value. The first step, which is novel in this work, is computationally inexpensive a...
Improving the scalability of ILP-based multi-relational concept discovery system through parallelization Mutlu, Ayşe Ceyda; Karagöz, Pınar; Kavurucu, Yusuf (2012-03-01) Due to the increase in the amount of relational data that is being collected and the limitations of propositional problem definition in relational domains, multi-relational data mining has arisen to be able to extract patterns from relational data. In order to cope with intractably large search space and still to be able to generate high-quality patterns. ILP-based multi-relational data mining and concept discovery systems employ several search strategies and pattern limitations. Another direction to cope w...
Policy-based memoization for ILP-based concept discovery systems Mutlu, Alev; Karagöz, Pınar (2016-02-01) Inductive Programming Logic (ILP)-based concept discovery systems aim to find patterns that describe a target relation in terms of other relations provided as background knowledge. Such systems usually work within first order logic framework, build large search spaces, and have long running times. Memoization has widely been incorporated in concept discovery systems to improve their running times. One of the problems that memoization brings to such systems is the memory overhead which may be a bottleneck. I...
Using Criticalities as a Heuristic for Answer Set Programming SABUNCU, ORKUNT; Alpaslan, Ferda Nur; AKMAN, VAROL (2004-01-08) Answer Set Programming is a new paradigm based on logic programming. The main component of answer set programming is a system that finds the answer sets of logic programs. During the computation of an answer set, systems are faced with choice points where they have to select a literal and assign it a truth value. Generally, systems utilize some heuristics to choose new literals at the choice points. The heuristic used is one of the key factors for the performance of the system. A new heuristic for answer s...
Improving forecasting accuracy of time series data using a new ARIMA-ANN hybrid method and empirical mode decomposition Buyuksahin, Umit Cavus; Ertekin Bolelli, Şeyda (Elsevier BV, 2019-10-07) Many applications in different domains produce large amount of time series data. Making accurate forecasting is critical for many decision makers. Various time series forecasting methods exist that use linear and nonlinear models separately or combination of both. Studies show that combining of linear and nonlinear models can be effective to improve forecasting performance. However, some assumptions that those existing methods make, might restrict their performance in certain situations. We provide a new Au...

Citation Formats

A. Mutlu and P. Karagöz, “Improving Hit Ratio of ILP-based Concept Discovery System with Memoization,” COMPUTER JOURNAL, pp. 138–153, 2014, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/62640.