Keynotes

 (slides are available, see below.)

We are pleased to announce this year's joint EDBT/ICDT keynote speakers:
Elisa Bertino, Gustavo Alonso, Floris Geerts, Yufei Tao, David Woodruff.


Data Security and Privacy in the IoT

 [slides]

The Internet of Things (IoT) paradigm refers to the network of physical objects or "things" embedded with electronics, software, sensors, and connectivity to enable objects to exchange data with servers, centralized systems,  and/or other connected devices based on a variety of communication infrastructures. IoT makes it possible to sense and control objects creating opportunities for more direct integration between the physical world and computer-based systems. IoT will usher automation in a large number of application domains, ranging from manufacturing and energy management (e.g. SmartGrid), to healthcare management and urban life (e.g. SmartCity). However, because of its fine-grained, continuous and pervasive data acquisition and control capabilities, IoT raises concerns about the security and privacy of data. Deploying existing data security solutions to IoT is not straightforward because of device heterogeneity, highly dynamic and possibly unprotected environments, and large scale. In this talk, after outlining key challenges in data security and privacy, we present initial approaches to securing IoT data, including efficient and scalable encryption protocols, software protection techniques for small devices, and fine-grained data packet loss analysis for sensor networks.

Elisa Bertino

Elisa Bertino is professor of computer science at Purdue University, and serves as Director of Purdue Cyber Center and Research Director of the Center for Information and Research in Information Assurance and Security (CERIAS). She is also an adjunct professor of Computer Science & Info Tech at RMIT. Prior to joining Purdue in 2004, she was a professor and department head at the Department of Computer Science and Communication of the University of Milan. She has been a visiting researcher at the IBM Research Laboratory (now Almaden) in San Jose, at the Microelectronics and Computer Technology Corporation, at Rutgers University, at Telcordia Technologies. Her recent research focuses on data security and privacy, digital identity management, policy systems, and security for drones and embedded systems. She is a Fellow of ACM and of IEEE. She received the IEEE Computer Society 2002 Technical Achievement Award, the IEEE Computer Society 2005 Kanai Award and the 2014 ACM SIGSAC outstanding contributions award. She is currently serving as EiC of IEEE Transactions on Dependable and Secure Computing.


Data Processing in Modern Hardware

 [slides]

Data processing is changing in radical ways. On the one hand, data science and big data have brought an unprecedented growth and variety in data sizes, demanding workloads, data types, and applications. On the other hand, hardware is no longer a source of performance as it has been in the last decades. Instead, it has become a complex, fast evolving, highly specialized, and heterogeneous platform that requires considerable tuning and effort to use optimally.
In this talk I will discuss the issues in data processing that arise as a result of modern hardware: the need to deal with parallelism and distribution, the increasing importance of networking, the proliferation of accelerators, and the raise of heterogeneity in the machine. These issues are both a threat and a challenge, demanding a radical redesign of many aspects of data processing and database engines. Using examples from recent work, I will present several exciting and radically new directions that are opening up for database research.

Gustavo Alonso

Gustavo Alonso is a professor at the Department of Computer Science of ETH Zurich (ETHZ) in Switzerland, where he is a member of the Systems Group. Gustavo has a M.S. and a Ph.D. in Computer Science from UC Santa Barbara. Before joining ETH, he was at the IBM Almaden Research Center.
His research interests encompass almost all aspects of systems, from design to run time. His applications of interest are distributed systems and databases, with an emphasis on system architecture. Current research is related to multi-core architectures, large clusters, FPGAs, and big data, mainly working on adapting traditional system software (OS, database, middleware) to modern hardware platforms.
Gustavo is a Fellow of the ACM and of the IEEE. He has received numerous awards, the most recent include the FCCM 2013 Best Paper Award, the AOSD 2012 Most Influential Paper Award, the VLDB 2010 Ten Year Best Paper Award, and the 2009 ICDCS Best Paper Award. He was the Chair of ACM EuroSys (the European Chapter of SIGOPS), and PC-Chair of a number of conferences in several areas, among others: Middleware (2004), VLDB (2006), Business Process Management (2007), ICDE (2008), VLDB Experimental and Analisys Track (2012), ICDCS (2014), EDBT (2015), VLDB Industrial Track (2016).


Scale Independence: Using Small Data to Answer Queries on Big Data

 [slides]

Large datasets introduce challenges to the scalability of query answering. Given a query Q and a dataset D, it is often prohibitively costly to compute the query answers Q(D) when D is big. To this end, one may want to use heuristics, "quick and dirty" algorithms which return approximate answers. However, in many applications it is a must to find exact query answers. So, how can we efficiently compute Q(D) when D is big or when we only have limited resources?
One idea is to find a small subset D' of D such that Q(D')=Q(D) where the size of D' is independent of the size of the underlying dataset D. Intuitively, when such a D' can be found for a query Q, the query is said to be scale independent. Indeed, for answering such queries the size of the underlying database does not matter,i.e., query processing is independent of the scale of the database.
In this talk, I will survey various formalisms that enable large classes of queries to be scale independent. These formalisms primarily rely on the availability of access constraints, a combination of indexes and cardinality constraints, on the data. We will take a closer look at how, in the presence of such constraints, queries can often be compiled into efficient query plans that access a bounded amount data, and how these techniques relate to query processing in the presence of access patterns. Finally, we illustrate that scale independent queries are quite common in practice and that they indeed can be efficiently answered on big datasets when access constraints are present.

Floris Geerts

Floris Geerts holds a research professor position at the University of Antwerp, Belgium. Before that, he held a senior research fellow position in the database group at the University of Edinburgh, and a postdoc position in the data mining group at the University of Helsinki. He received his PhD in 2001 at the University of Hasselt, Belgium. His research interests include the theory and practice of databases and the study of data quality in particular. He received several best paper awards (ICDM 2001, ICDE 2007, ADBIS 2015) and was recipient of the 2015 Alberto O. Mendelzon Test of Time Award (PODS 2015). He is an associate editor of ACM TODS, was general chair of EDBT/ICDT 2015 and will be PODS PC chair in 2017.







Top-k Indexes Made Small and Sweet

 [slides]

Top-k queries have become extremely popular in the database community. Such a query, which is issued on a set of elements each carrying a real-valued weight, returns the k elements with the highest weights among all the elements that satisfy a predicate. As usual, an index structure is necessary to answer a query substantially faster than accessing the whole input set.
The existing research on top-k queries can be classified in two categories. The first one, which is system-oriented, aims to devise indexes that are simple to understand and easy to implement. These indexes, typically designed with heuristics, are reasonably fast in practical applications, but do not necessarily offer strong performance guarantees --- in other words, they are small but not sweet. The other category, which is theory-oriented, aims to develop indexes that promise attractive bounds on the space consumption and query overhead (sometimes also update cost). These indexes, unfortunately, are often excessively sophisticated in the adopted techniques, and are rarely applied in practice --- they are sweet but not small.
This talk will discuss the progress of an on-going project that strives to take down the barrier between the two categories, by crafting a framework for acquiring simple top-k indexes with excellent performance guarantees---namely, small and sweet. This is achieved with reductions that produce top-k indexes automatically from the existing data structures for conventional reporting queries on unweighted elements (i.e., finding all elements satisfying a predicate), and/or the existing data structures on top-1 queries. Our reductions promise nearly no performance deterioration with respect to those existing structures, are general enough to be applicable to a huge variety of top-k problems, and work in both the external memory model and the RAM model.

Yufei Tao

Yufei Tao is a Professor in the School of Information Technology and Electrical Engineering, the University of Queensland (UQ). He received two SIGMOD best paper awards (in 2013 and 2015, respectively), and a Hong Kong Young Scientist Award in 2002. He served as an associate editor of ACM Transactions on Database Systems (TODS) from 2008 to 2015, and of IEEE Transactions on Knowledge and Data Engineering (TKDE) from 2012 to 2014. He was a PC co-chair of International Conference on Data Engineering (ICDE) 2014, and of International Symposium on Spatial and Temporal Databases (SSTD) 2011. He will be a group leader of SIGMOD 2017, was an area chair of ICDE 2011, 2016, and was a senior PC member of CIKM 2010-2012, 2015.







New Algorithms for Heavy Hitters in Data Streams

 [slides]

An old and fundamental problem in databases and data streams is that of finding the heavy hitters, also known as the top-k, most popular items, frequent items, elephants, or iceberg queries. There are several variants of this problem, which quantify what it means for an item to be frequent, including what are known as the ℓ_1-heavy hitters and ℓ_2-heavy hitters. There are a number of algorithmic solutions for these problems, starting with the work of Misra and Gries, as well as the CountMin and CountSketch data structures, among others.
In this paper (accompanying an invited talk) we cover several recent results developed in this area, which improve upon the classical solutions to these problems. In particular, we develop new algorithms for finding ℓ_1-heavy hitters and ℓ_2-heavy hitters, with significantly less memory required than what was known, and which are optimal in a number of parameter regimes.

David Woodruff

David Woodruff joined IBM Almaden Research Center in 2007 right after completing his Ph.D. at MIT in theoretical computer science. He has been at IBM Almaden ever since. His research interests include communication complexity, data stream algorithms, machine learning, numerical linear algebra, sketching, and sparse recovery. He is the recipient of the 2014 Presburger Award and Best Paper Awards at STOC 2013 and PODS 2010. At IBM he is a member of the Academy of Technology and a Master Inventor.