KRDB Seminars 2012

We study the size of first-order, positive existential and nonrecursive Datalog rewritings for conjunctive queries over OWL 2 QL ontologies. We establish connections between the size of rewritings and the size of circuits and formulas for monotone Boolean functions. We use known lower bounds and separation results from circuit complexity to prove similar results for the size of rewritings that do not use non-signature constants. For example, we show that, in the worst case, positive existential and nonrecursive Datalog rewritings are exponentially longer than the original queries; nonrecursive Datalog rewritings are in general exponentially more succinct than positive existential rewritings; while first-order rewritings can be superpolynomially more succinct than positive existential rewritings. We then analyse the sources of the exponential blowup and present a novel rewriting technique that takes them into account. We argue that in most, if not all, practical cases the rewritings are in fact of polynomial size. Moreover, we prove some sufficient conditions, imposed on queries and ontologies, that guarantee succinctness of the rewritings. We also support our claim by experimental results.

Reference: Alessandro Artale

We will review state-of-the art methods for information extraction from large natural language corpora of unstructured and semi-structured texts. The special emphasis will be given to learning-based approaches to build extractors especially to bootstrapping methods. We will consider problems such as semantic drift typical for bootstrapping techniques and we will describe how this problems can be resolved. In additions we will discuss how additional knowledge such as ontology knowledge can be used to increas accuracy of bootstrapping methods.

Reference: Enrico Franconi

The e-Health Unit of the Fondazione Bruno Kessler (FBK) of Trento is a a multidisciplinary group of people carrying out research in ICT-based methods and models for the healthcare area: innovative e-health model formulation and applications design, laboratory and on-the-field validation of prototypic applications, studying the effects of these applications in several healthcare settings. The activities of applied research are carried out in strong collaboration with local, national and international research laboratories.

In this talk we will present a panoramic view of the activities carried on in the e-Health Unit involving the collection, representation, management and exploitation of medical knowledge in order to design applications for supporting institutions, citizens, and patients in managing their own health and well being information, and in order to develop applications and systems for supporting healthcare operators in delivering a high quality process of care. In particular, in the first part of the talk we will present the work in the field of vocabularies and terminologies to fill the gap between the lay people and the healthcare professionals language when accessing health information. The second part is devoted to the activities of knowledge management for supporting healthcare professionals, carried on mainly in the domain of oncology. Specifically, after a brief panoramic of workflow modeling activities we will focus on the design and implementation of a guideline-based decision support system for oncology: from knowledge acquisition to the connection of the system with an electronic medical record.

Short Bio:
Elena Cardillo and Claudio Eccher are resp., researcher and senior researcher at the e-Health Unit of FBK, working in (bio)medical terminologies, collaborative (formal) modeling of clinical protocols (Oncocure project) and on applying knowledge representation and formal verification techniques to healthcare quality assurance.

Fondazione Bruno Kessler (FBK)
Via Sommarive 18, 38050 Povo, Trento
phone: +390461314161
e-mail: cleccher@fbk.eu, cardillo@fbk.eu
http://ehealth.fbk.eu/en/home

Reference: Camilo Thorne

In this talk, I will present our recent work on top-k search in social bookmarking applications (popular examples includeDel.icio.us, StumbleUpon or Flickr).

The general setting is the following:

- Users form a weighted social network, which may reflect friendship, similarity, trust, etc.
- Items from a public pool of items (e.g., URLs, blogs, photos, documents) are tagged by users with keywords,
driven by various motivations (description, classification, to facilitate later retrieval, sociality).
- Users search for items having certain tags.

Going beyond the classic search paradigm where data is decoupled from the users querying it, users can now act both as producers and seekers of information. Therefore, finding the most relevant items in response to a query should be done in a network-aware manner: items tagged by users who are closer (more similar) to the seeker should be given more weight than items tagged by distant users. We propose an algorithm that has the potential to scale to current applications. We describe how a key aspect of the problem, which is accessing the closest or most relevant users for a given seeker, can be done on-the-fly (without any pre-computations) for several possible choices - arguably the most natural ones - of proximity computation in a social network. Based on this, our top-k algorithm is sound and complete, and is instance optimal in the case when the search relies exclusively on the social weight of tagging actions. To further improve response time, we then consider approximate techniques. Extensive experiments on real-world data show that these can bring significant benefit, without sacrificing precision.

If time allows, I will also discuss our recent work on signed (trust/distrust) networks, inference of signed links from interactions in Wikipedia, and ideas for future research on search in signed networks.

Short Bio:

I obtained the Bachelor's degree in Computer Science from Politehnica University Bucharest (visiting also Universita degli Studi di Brescia - 1 year - and Ecole Polytechnique - 1 year) and the Master's degree (D.E.A. Algorithmique) from Ecole Polytechnique. From 2004 to 2007 I did a Ph.D. in databases in the Gemo group at INRIA Futurs, advised by Serge Abiteboul and Tova Milo.

Speaker's homepage: http://perso.telecom-paristech.fr/~cautis/
Reference: Evgeny Kharlamov