Ontological Pathfinding
Authors:
Open Access
- 14 June 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 835-846
Abstract
Recent years have seen a drastic rise in the construction of web-scale knowledge bases (e.g., Freebase, YAGO, DBPedia). These knowledge bases store structured information about real-world people, places, organizations, etc. However, due to limitations of human knowledge and information extraction algorithms, these knowledge bases are still far from complete. In this paper, we study the problem of mining first-order inference rules to facilitate knowledge expansion. We propose the Ontological Pathfinding algorithm (OP) that scales to web-scale knowledge bases via a series of parallelization and optimization techniques: a relational knowledge base model to apply inference rules in batches, a new rule mining algorithm that parallelizes the join queries, a novel partitioning algorithm to break the mining tasks into smaller independent sub-tasks, and a pruning strategy to eliminate unsound and resource-consuming rules before applying them. Combining these techniques, we develop the first rule mining system that scales to Freebase, the largest public knowledge base with 112 million entities and 388 million facts. We mine 36,625 inference rules in 34 hours; no existing approach achieves this scale.Keywords
Funding Information
- Defense Advanced Research Projects Agency (FA8750-12-2-0348-2)
- National Science Foundation (1526753)
This publication has 39 references indexed in Scilit:
- YAGO2: A spatially and temporally enhanced knowledge base from WikipediaArtificial Intelligence, 2013
- FlumeJavaACM SIGPLAN Notices, 2010
- MapReduceCommunications of the ACM, 2008
- Finding Frequent Patterns in a Large Sparse Graph*Data Mining and Knowledge Discovery, 2005
- Mining frequent patterns by pattern-growthACM SIGKDD Explorations Newsletter, 2000
- Inverse entailment and progolNew Generation Computing, 1995
- An effective hash-based algorithm for mining association rulesACM SIGMOD Record, 1995
- Inductive logic programmingACM SIGART Bulletin, 1994
- Mining association rules between sets of items in large databasesACM SIGMOD Record, 1993
- On sentences which are true of direct unions of algebrasThe Journal of Symbolic Logic, 1951