14.00, room 455, PCRI

Abstract
In this talk, I will start by recalling the basics of ontology-based data access, focusing on ontologies formulated in lightweight description logics. Afterwards, I will give a brief description of my recent work on this topic, evoking the results in the following papers:

Tractable Approximations of Consistent Query Answering for Robust Ontology-based Data Access
with Riccardo Rosati (IJCAI’13)

Conjunctive Regular Path Queries in Lightweight Description Logics
with Magdalena Ortiz, Mantas Simkus (IJCAI’13)

Tractable Queries for Lightweight Description Logics
with Meghyn Bienvenu, Magdalena Ortiz, Mantas Simkus, Guohui Xiao (IJCAI’13)

First Order-Rewritability of Atomic Queries in Horn Description Logics
with Carsten Lutz, Frank Wolter (IJCAI’13)

Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP
with Balder ten Cate, Carsten Lutz, and Frank Wolter (PODS’13)

10.30, room 445, PCRI

Résumé
AS-Index est une nouvelle structure pour la recherche exacte de chaîne de caractères dans des bases de données textuelles résidant sur le disque. Il repose sur le hachage contrairement à d’autres solutions basées soit sur des arbres ou des treillis. Il indexe chaque n-gram de la base dans sa version initiale, alors qu’une variante autorise une indexation non-dense et un gain d’espace conséquent. La fonction de hachage utilise les signatures algébriques des n-grams. L’utilisation du hachage permet de garantir des temps constants de recherche pour des patterns recherchés de tailles quelconque, contrairement aux structures connues dont le coût est au mieux logarithmique. Le coût de stockage de l’AS-index est de 500-600% la taille des données, similaire aux solutions connues. Nos expériences et nos comparaisons avec des structures connues confirment le bon comportement de notre structure.