Paul Frederic Sela

Decision Branches: Efficient Search in Large Databases with Index-Aware Decision Trees

Tuesday, 17. October 2023 - 12:30 to 13:15

Speaker: Christian Lülf

Abstract: The vast amounts of data collected in various domains pose great challenges to modern data exploration and analysis. To find "interesting" objects in large databases, users typically define a query using positive and negative example objects and train a classification model to identify the objects of interest in the entire data catalog. However, this approach requires a scan of all the data to apply the classification model to each instance in the data catalog, making this method prohibitively expensive to be employed in large-scale databases serving many users and queries interactively. In this work, we propose a novel framework for such search-by-classification scenarios that allows users to interactively search for target objects by specifying queries through a small set of positive and negative examples. Unlike previous approaches, our framework can rapidly answer such queries at low cost without scanning the entire database. Our framework is based on an index-aware construction scheme for decision trees and random forests that transforms the inference phase of these classification models into a set of range queries, which in turn can be efficiently executed by leveraging multidimensional indexing structures. Our experiments show that queries over large data catalogs with hundreds of millions of objects can be processed in a few seconds using a single server, compared to hours needed by classical scanning-based approaches. 

This session of the Lunchtime Seminar presents our work that has been recently published at VLDB ’23. We'll also unveil a web prototype of our search framework, highlighting potential application scenarios of our work.

Short Bio: Christian Lülf is a doctoral candidate and research assistant at the chair of Machine Learning and Data Engineering at the University of Münster. His primary research interest lies in the development of machine learning techniques tailored for large-scale applications. Prior to that, he received his degree in Information Systems at the University of Münster and accrued over six years of industry experience with an IT provider in the banking sector.