IV Alberto Mendelzon Workshop on Foundations of Data Management

To be updated.

There are several semantic sources that can be found in the Web that are either explicit, e.g. Wikipedia, or implicit, e.g. derived from Web usage data. Most of them are related to user generated content (UGC) or what is called today the Web 2.0. In this talk we show several applications of mining the wisdom of crowds behind UGC to improve search. We will show live demos to find relations in the Wikipedia or to improve image search as well as our current research in the topic. Our final goal is to produce a virtuous data feedback circuit to leverage the Web itself.

Ricardo Baeza-Yates is VP of Research for Europe and Latin America, leading the Yahoo! Research labs at Barcelona, Spain and Santiago, Chile, and also supervising the lab in Haifa, Israel. Until 2005 he was the director of the Center for Web Research at the Department of Computer Science of the Engineering School of the University of Chile; and ICREA Professor and founder of the Web Research Group at the Dept. of Information and Communication Technologies of Univ. Pompeu Fabra in Barcelona, Spain. He maintains ties with both mentioned universities as a part-time professor for the Ph.D. program. His research interests includes algorithms and data structures, information retrieval, web mining, text and multimedia databases, software and database visualization, and user interfaces.

We present the AgreementMaker system for matching real-world ontologies, which may consist of hundreds or even thousands of concepts. The end users of the system are sophisticated domain experts whose needs have driven the design and implementation of the system: they require a responsive, powerful, and extensible framework to perform, evaluate, and compare matching methods. The system comprises a wide range of matching methods addressing different levels of granularity of the components being matched (conceptual vs. structural), the amount of user intervention that they require (manual vs. automatic), their usage (stand-alone vs. composed), and the types of compo- nents to consider (schema only or schema and instances). Performance measurements (recall, precision, and runtime) are supported by the system, along with the weighted combination of the results provided by those methods. The AgreementMaker has been used and tested in practical applications and in the Ontology Alignment Evaluation Initiative (OAEI) competition. We report here on some of its most advanced features, including its extensible architecture that facilitates the integration and performance tuning of a variety of matching methods, its capability to evaluate, compare, and combine matching results, and its user interface with a control panel that drives all the matching methods and evaluation strategies.

Isabel Cruz is Professor of Computer Science in the College of Engineering at the University of Illinois at Chicago. She holds a PhD degree in Computer Science from the University of Toronto. She has received numerous awards for teaching, service, and research including the NSF Career Award and recently the Great Cities Institute Scholar Award in 2009. She has more than 90 refereed publications in databases, geographic information systems, semantic web, visual languages, graph drawing, user interfaces, multimedia, information retrieval, and security. The broader impact of her research has been demonstrated in several real-world scenarios, including biomedical and geospatial interdisciplinary applications, and in many teaching innovations. She has been general chair, program committee chair or program committee vice/associate chair of several of the most important conferences in her fields of expertise, such as IEEE ICDE, ACM GIS, International Conference on GeoSpatial Semantics, ACM Multimedia, ISWC, and ESWC and served on the program committees of more than 130 conferences. She has been editor to several books and journals and has served in strategic committees including the Mapping Science Committee of the National Academies. She directs the Advances in Information Systems (ADVIS) Lab, has graduated sixteen students in their PhD and MS theses, and has published with fourteen of her undergraduate research advisees. Her leadership roles at UIC include being the CS facilitator of the NSF Advance WISEST program (to increase the number, participation and leadership status of women in academic science and engineering), the chair of the CS faculty search committee, and member of the dean of engineering search committee twice.

To integrate information, data in different formats, from different, potentially overlapping sources, must be related and transformed to meet the users' needs. Ten years ago, Clio introduced a new paradigm for creating declarative schema mappings to describe the relationship between data in heterogeneous schemas. This enabled powerful tools for mapping discovery and integration code generation, greatly simplifying the integration process. In this talk, I take a look at where our field was a decade ago and where it is now in terms of support for data integration. I share a vision for raising the level of abstraction further, to better isolate applications from the details of how the integration is accomplished. Integration independence allows applications to be independent of how, when, and where information integration takes place, making materialization and the timing of transformations an optimization decision that is transparent to applications. I identify a number of research challenges that remain to be addressed in order to ultimately achieve this vision.

Renee J. Miller is a professor of computer science and the Bell Canada Chair of Information Systems at the University of Toronto. She received the US Presidential Early Career Award for Scientists and Engineers (PECASE), the highest honor bestowed by the United States government on outstanding scientists and engineers beginning their careers. She received an NSF CAREER Award, the Premier's Research Excellence Award, and an IBM Faculty Award. She is a fellow of the ACM. Her research interests are in the efficient, effective use of large volumes of complex, heterogeneous data. This interest spans data integration and exchange, inconsistent and uncertain data management, and data curation and cleaning. She serves on the Board of Trustees of the VLDB Endowment and was elected to serve as VLDB President beginning January 2010. She serves on the editorial board for the VLDB Journal, IEEE's TKDE, and the new JIDM. She received her PhD in Computer Science from the University of Wisconsin, Madison and bachelor's degrees in Mathematics and Cognitive Science from MIT.

Self-indexing is a technology that integrates text compression and text indexing, such that a text collection can be simultaneously compressed and indexed. The resulting representation, called a self-index of the text, takes space close to that of the compressed text, is able of reproducing any text substring, and offers indexed searching of the collection. This has been a major breakthrough in the last decade, allowing one to handle huge text collections within main memory and representing them succinctly. In this talk I will, besides presenting the basics of this technique, discuss how it can be extended to index XML collections, where, on one hand, the text has structure and, on the other hand, we wish to support much more complex query languages, XPath at least. I will first describe two plug-and-play solutions, where a text self-index is coupled with compressed data structures that handle trees and sequences. Then I will introduce two more innovative solutions, where the compressed data structures are designed specifically for this problem. This area is full of open challenges and I will conclude by enumerating the most relevant ones.

Gonzalo Navarro earned his PhD in Computer Science in 1998 from the University of Chile, where he is currently Full Professor. His areas of interest include algorithms and data structures, text searching, compression, and metric space searching. He is currently a researcher at the Millennium Institute for Cell Dynamics and Biotechnology; and runs a Fondecyt project funded by CONICYT (the Chilean agency for research funding). He has headed the Center for Web Research (a Millennium Nucleus funded by the Chilean government); RIBIDI, a Latin American project funded by CYTED; a project funded by Yahoo! Research; and other three Fondecyt projects. He has participated in several research projects such as an ECOS/CONICYT (Chile-France cooperation), AMYRI (a previous CYTED project), and five other national projects (Fondecyt and Fondef). He is or has been PC (co-)chair of several conferences: SPIRE 2001, SCCC 2004 and a track of ENC 2007 (published by IEEE CS Press); SPIRE 2005 and IFIP TCS 2006 (published by Springer); and SIGIR 2005 Posters (published by ACM). He co-created conference SISAP in 2008 (published by IEEE CS Press). He is member of the Steering Committee of LATIN and SISAP, and of the Editorial Board of Information Retrieval journal, and of ACM Journal of Experimental Algorithmics. He has been PC member of 45 national and international conferences and reviewer for around 40 international journals. He has given around 45 invited talks at several universities and international conferences, including six plenary talks in conferences. He has coauthored a book published by Cambridge University Press, 15 book chapters, 6 international conference proceedings (editor), a special issue in an international journal (editor), 78 papers in international journals, 142 papers in international conferences, and 24 in national and regional conferences. According to Thompson's ISI, two of his papers rank within the 1% most cited in Computer Science. According to ResearchIndex, he is ranked at position 2,387 among the most cited authors in Computer Science, first within Chile.

Database transformations (queries, views, mappings) take apart, filter, and recombine source data in order to populate warehouses, materialize views, and provide inputs to analysis tools. As they do so, applications often need to track the relationship between parts and pieces of the sources and parts and pieces of the transformations' output. This relationship is what we call database provenance. This tutorial presents an approach to database provenance that relies on two observations. First, provenance is a kind of annotation, and we can develop a general approach to annotation propagation that also covers other applications, for example to uncertainty and access control. In fact, provenance turns out to be the most general kind of such annotation, in a precise and practically useful sense. Second, the propagation of annotation through a broad class of transformations relies on just two operations: one when annotations are jointly used and one when they are used alternatively. This leads to annotations forming a specific algebraic structure, a commutative semiring. The semiring approach works for annotating tuples, field values and attributes in standard relations, in nested relations (complex values), and for annotating nodes in (unordered) XML. It works for transformations expressed in the positive fragment of relational algebra, nested relational calculus, unordered XQuery, as well as for Datalog, GLAV schema mappings, and tgd constraints. Specific semirings correspond to earlier approaches to provenance, while others correspond to forms of uncertainty, trust, cost, and access control.

This is joint work with J.N. Foster, T.J. Green, Z. Ives, and G. Karvounarakis, done in part within the frameworks of the Orchestra and pPOD projects.