Horn rule discovery with batched caching and rule identifier for proficient compressor of knowledge data. (18th November 2022)

• Record Type: Journal Article
• Authors: Wang, Ruoyu; Sun, Daniel; Wong, Raymond; Ranjan, Rajiv
• Is Part Of: Software, practice & experience. Volume 53:Number 3(2023)
• Page Start: 682
• Page End: 703
• Publication Date: 2022-11-18
• Subjects: caching -- Horn rules -- knowledge bases -- pruning -- relational databases -- semantic compressor; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.3165
• Languages: English
• ISSNs: 0038-0644

Abstract

Abstract: Knowledge data has been widely applied to artificial intelligence applications for interpretable and complex reasoning. Modern knowledge bases are constructed via automatic knowledge extraction from open‐accessible sources. Thus the sizes of KBs are continuously growing, heavily burdening the maintenance and application of the knowledge data. Besides the grammatical redundancies, semantically repeated information also frequently appears in knowledge bases but is still under‐explored. Existing semantic compressors fail to efficiently discover expressive patterns and thus perform unsatisfyingly on knowledge data. This article proposes SInC, a semantic inductive compressor, to efficiently induce first‐order Horn rules and semantically compress knowledge bases. SInC improves the scalability of top‐down rule mining by batching correlated records in the cache and further optimizes the pruning of duplication and specialization via an identifier structure of Horn rules. SInC was evaluated on real‐world and synthetic datasets and compared against the state‐of‐the‐art. The results show that the batched caching speed up the rule mining procedure by more than two orders while consuming fewer than three times memory space. The identifier technique speeds up the duplication and specialization pruning by orders of magnitude with less than 5‰ and 15% error rates, respectively. SInC outperforms the state‐of‐the‐art from the perspective of overall compression on both scalability and compression effect.