Eureka: Efficient Query Processing over Large Probabilistic Knowledge Bases

ProbKB: Scalable Learning and Inference over Large Probabilistic Knowledge Bases

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 the limitations of human knowledge and extraction algorithms, current knowledge bases are still far from complete. In this project, we design the Ontological Pathfinding (OP) algorithm to mine first-order inference rules from web-scale knowledge bases and apply the rules to uncover implicit facts. The OP algorithm scales up via a series of optimization techniques, including a new parallel rule mining algorithm, a pruning strategy to eliminate unsound and resource-consuming rules before applying them, and a novel partitioning algorithm to break the learning task into smaller independent sub-tasks. Combining these techniques, we develop a 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 system achieves this scale.

Based on the mining algorithm and the optimizations, we develop an efficient inference engine. As a result, we infer 0.9 billion new facts from Freebase in 17.19 hours. We use cross validation to evaluate the inferred facts, and estimate a degree of expansion by 0.6 over Freebase, with a precision approaching 1.0. Our approaches outperform state-of-the-art mining algorithms and inference engines in terms of both performance and quality.

For more details, please visit the ProbKB homepage.

Archer: Query-Driven Machine Learning

Entity resolution (ER) is the process of determining records (mentions) in a database that correspond to the same real-world entity. Leading ER systems solve this problem by resolving every record in the database; however, for large datasets this is an expensive process. Moreover, such approaches are wasteful because in practice, users are interested in only one or a small subset of the entities mentioned in the database. In this work, we introduce new classes of SQL queries involving ER operators — selection-driven ER and join-driven ER. We develop novel variations of Metropolis Hastings algorithm and introduce selectivity-based scheduling algorithms to support the two classes of ER queries.

For more details, please visit the Archer homepage.

DBlytics: Statistical analysis on data parallel frameworks

DBlytics When processing large data, often a large bottleneck to computation is data movement. Moving data across geographical locations for processing is expensive. In-Database Analytics (dblytics) aims to build sophisticated analytic algorithms into data parallel systems, such as relational databases (RDBMS) and massively parallel processing (MPP) systems. Using a database as the ecosystem for analytics we a get declarative query interface, query optimization, transactional operations, efficient catching and fault tolerance. Below we list sub research projects that contribute to this effort.

MADlib MADlib is an open-source library for scalable in-database analytics. It provides data-parallel implementations of mathematical, statistical and machine-learning methods for structured and unstructured data. There are two significant motivations of in-database analytics tools such as MADlib. Firstly, it harness the embarrassing parallel processing power of parallel database and  make the database being a data analytic engine, which is capable of processing massive data. Secondly, In-database analytic tools avoid the time cost of transferring large volume of data between databases and outside tools. MADlib can be installed on Postgres and Greenplum database.

For more details, please visit the DBlytics/MADLib homepage.