  Multiple web-scale Knowledge Bases, e.g., Freebase, YAGO, NELL, have been
constructed using semi-supervised or unsupervised information extraction
techniques and many of them, despite their large sizes, are continuously
growing. Much research effort has been put into mining inference rules from
knowledge bases. To address the task of rule mining over evolving web-scale
knowledge bases, we propose a parallel incremental rule mining framework. Our
approach is able to efficiently mine rules based on the relational model and
apply updates to large knowledge bases; we propose an alternative metric that
reduces computation complexity without compromising quality; we apply multiple
optimization techniques that reduce runtime by more than 2 orders of magnitude.
Experiments show that our approach efficiently scales to web-scale knowledge
bases and saves over 90% time compared to the state-of-the-art batch rule
mining system. We also apply our optimization techniques to the batch rule
mining algorithm, reducing runtime by more than half compared to the
state-of-the-art. To the best of our knowledge, our incremental rule mining
system is the first that handles updates to web-scale knowledge bases.
