Dan Olteanu

University of Zurich

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Maximilian Schleich

University of Washington

Hung Q. Ngo

Technological University Dublin

Mahmoud Abo Khamis

University of Pittsburgh

Dan Suciu

University of Washington

Ahmet Kara

Hitit Üniversitesi

Christoph Koch

École Polytechnique Fédérale de Lausanne

XuanLong Nguyen

University of Michigan–Ann Arbor

Haozhe Zhang

Yanshan University

Fica

Lyublena Antova

Meta (United States)

Cooperative Institutions

Carol Davila University of Medicine and Pharmacy

Clinical Emergency Hospital Bucharest

University of Oxford

Bucharest Emergency University Hospital

Amita Health St. Mary's Hospital

Spitalul Universitar de Urgență Elias

Emergency University

University of Washington

National Institute of Research and Development for Biological Sciences

Stanford University

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

QirK: Question Answering via Intermediate Representation on Knowledge Graphs

arXiv (Cornell University) (2024)

Jan Luca Scheerer Anton Lykov Moe Kayali Ilias Fountalis Dan Olteanu

We demonstrate QirK, a system for answering natural language questions on Knowledge Graphs (KG). QirK can answer structurally complex questions that are still beyond the reach of emerging Large Language Models (LLMs). It does so using a unique combination of database technology, LLMs, and semantic search over vector embeddings. The glue for these components is an intermediate representation (IR). The input question is mapped to IR using LLMs, which is then repaired into a valid relational database query with the aid of a semantic search on vector embeddings. This allows a practical synthesis of LLM capabilities and KG reliability. A short video demonstrating QirK is available at https://youtu.be/6c81BLmOZ0U.

Representation

Knowledge graph

10.48550/arxiv.2408.07494

Cite

Citations (0)

Multi-layer optimizations for end-to-end data analytics

Amir Shaikhha Maximilian Schleich Alexandru Ghiţă Dan Olteanu

We consider the problem of training machine learning models over multi-relational data. The mainstream approach is to first construct the training dataset using a feature extraction query over input database and then use a statistical software package of choice to train the model. In this paper we introduce Iterative Functional Aggregate Queries (IFAQ), a framework that realizes an alternative approach. IFAQ treats the feature extraction query and the learning task as one program given in the IFAQ's domain-specific language, which captures a subset of Python commonly used in Jupyter notebooks for rapid prototyping of machine learning applications. The program is subject to several layers of IFAQ optimizations, such as algebraic transformations, loop transformations, schema specialization, data layout optimizations, and finally compilation into efficient low-level C++ code specialized for the given workload and data.

Python

Schema (genetic algorithms)

10.1145/3368826.3377923

Cite

Citations (13)

The Complexity of Boolean Conjunctive Queries with Intersection Joins

Mahmoud Abo Khamis George Chichirim Antonia Kormpa Dan Olteanu

Intersection joins over interval data are relevant in spatial and temporal data settings. A set of intervals join if their intersection is non-empty. In case of point intervals, the intersection join becomes the standard equality join. We establish the complexity of Boolean conjunctive queries with intersection joins by a many-one equivalence to disjunctions of Boolean conjunctive queries with equality joins. The complexity of any query with intersection joins is that of the hardest query with equality joins in the disjunction exhibited by our equivalence. This is captured by a new width measure called the ij-width. We also introduce a new syntactic notion of acyclicity called iota-acyclicity to characterise the class of Boolean queries with intersection joins that admit linear time computation modulo a poly-logarithmic factor in the data size. Iota-acyclicity is for intersection joins what alpha-acyclicity is for equality joins. It strictly sits between gamma-acyclicity and Berge-acyclicity. The intersection join queries that are not iota-acyclic are at least as hard as the Boolean triangle query with equality joins, which is widely considered not computable in linear time.

Conjunctive query

Join (topology)

10.1145/3517804.3524156

Cite

Citations (4)

LMFAO: An Engine for Batches of Group-By Aggregates

arXiv (Cornell University) (2020)

Maximilian Schleich Dan Olteanu

LMFAO is an in-memory optimization and execution engine for large batches of group-by aggregates over joins. Such database workloads capture the data-intensive computation of a variety of data science applications. We demonstrate LMFAO for three popular models: ridge linear regression with batch gradient descent, decision trees with CART, and clustering with Rk-means.

Descent (aeronautics)

Cart

10.48550/arxiv.2008.08657

Cite

Citations (4)

Aggregation and Ordering in Factorised Databases

arXiv (Cornell University) (2013)

Nurzhan Bakibayev Tomáš Kočiský Dan Olteanu Jakub Závodný

A common approach to data analysis involves understanding and manipulating succinct representations of data. In earlier work, we put forward a succinct representation system for relational data called factorised databases and reported on the main-memory query engine FDB for select-project-join queries on such databases. In this paper, we extend FDB to support a larger class of practical queries with aggregates and ordering. This requires novel optimisation and evaluation techniques. We show how factorisation coupled with partial aggregation can effectively reduce the number of operations needed for query evaluation. We also show how factorisations of query results can support enumeration of tuples in desired orders as efficiently as listing them from the unfactorised, sorted results. We experimentally observe that FDB can outperform off-the-shelf relational engines by orders of magnitude.

Listing (finance)

Representation

Conjunctive query

Materialized view

10.48550/arxiv.1307.0441

Cite

Citations (1)

[Clinical study of patients hospitalized with urinary infections at the Medical Clinic II of the Bucharest Municipal Clinical Hospital 1980-1984].

PubMed (1987)

Fica D Andronescu Dan Olteanu S Oprescu O Spînu

Source

Cite

Citations (0)

Multi-layer Optimizations for End-to-End Data Analytics

arXiv (Cornell University) (2020)

Amir Shaikhha Maximilian Schleich Alexandru Ghiţă Dan Olteanu

Python

Scala

10.48550/arxiv.2001.03541

Cite

Citations (0)

Transferul internaţional de tehnologie şi capacitatea de absorbţie. Cazul ţărilor europene centrale şi periferice

Revista OEconomica (2005)

Dan Olteanu

This paper aims to analyse the main mechanisms through one achieves international technology transfer and their importance for the core and the peripheral european countries.

Source

Cite

Citations (0)

Tractable Conjunctive Queries over Static and Dynamic Relations

arXiv (Cornell University) (2024)

Ahmet Kara Zheng Luo Miloš Nikolić Dan Olteanu Haozhe Zhang

We investigate the evaluation of conjunctive queries over static and dynamic relations. While static relations are given as input and do not change, dynamic relations are subject to inserts and deletes. We characterise syntactically three classes of queries that admit constant update time and constant enumeration delay. We call such queries tractable. Depending on the class, the preprocessing time is linear, polynomial, or exponential (under data complexity, so the query size is constant). To decide whether a query is tractable, it does not suffice to analyse separately the sub-query over the static relations and the sub-query over the dynamic relations. Instead, we need to take the interaction between the static and the dynamic relations into account. Even when the sub-query over the dynamic relations is not tractable, the overall query can become tractable if the dynamic relations are sufficiently constrained by the static ones.

Conjunctive query

10.48550/arxiv.2404.16224

Cite

Citations (0)

Towards grouping constructs for semistructured data

François Bry Dan Olteanu Sandra Schaffert

Markup languages for semistructured data like XML are of growing importance as a means for data exchange and storage. The authors propose an enhancement for the semistructured data model that allows us to express more semantics and to enhance query answering. A data model is proposed and the implications on pattern matching are investigated.

Data Exchange

RuleML

10.1109/dexa.2001.953043

Cite

Citations (1)