Search SIGMOD Join SIGMOD Feedback What's New Home
In cooperation with

ACM SIGMOD/PODS 2004 Conference

Maison de la Chimie, Paris, France.
June 13-18, 2004

PODS Program

At a glance

Monday Invited Talk XML Processing Lunch Invited Tutorial I Ranking Data Exchange I
Tuesday SIGMOD/PODS Plenary: Keynote talk Spatial Data Lunch Clustering, Data Mining, Approximations Query Execution and Optimization PODS Business meeting
Wednesday Invited Tutorial II Data Exchange II Lunch SIGMOD Business Meeting Data Streams Foundations of Query Languages Banquet

Monday, June 14   ^

09:00 - 10:30 PODS SESSION 1: Invited Talk

The Lixto Data Extraction Project:  Back and Forth between Theory and Practice
Georg Gottlob

11:00 - 12:30 PODS SESSION 2: XML Processing Chair: Moshe Vardi

Best Paper Award and Best Newcomer Paper Award
Conditional XPath, the first order complete XPath dialect
Maarten Marx

Frontiers of Tractability for Typechecking Simple XML Transformations
Wim Martens, Frank Neven

Positive Active XML
Serge Abiteboul, Omar Benjelloun, Tova Milo

12:30 - 14:00 Lunch
14:00 - 15:30 PODS SESSION 3: Invited Tutorial Chair: Jennifer Widom

The Past, Present and Future of Web Information Retrieval
Monika Henzinger

16:00 - 17:00 PODS SESSION 4: Ranking Chair: Christos Faloutsos

Comparing and aggregating rankings with ties
Ronald Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar, Erik Vee

Using Non-Linear Dynamical Systems for Web Searching and Ranking
Panayiotis Tsaparas

17:30 - 19:00 PODS SESSION 5:  Data Exchange I Chair: Ken Ross

Specification and Verification of Data-driven Web Services
Alin Deutsch, Liying Sui, Victor Vianu

Composing Schema Mappings: Second-Order Dependencies to the Rescue
Ronald Fagin, Phokion Kolaitis, Lucian Popa, Wang-Chiew Tan

Foundations of semantic web databases
Claudio Gutierrez, Carlos Hurtado, Alberto Mendelzon

Tuesday, June 15   ^

09:00 - 10:30 SIGMOD/PODS Plenary: Keynote talk
11:00 - 12:30 PODS SESSION 6: Spatial Data Chair: Luc Segoufin

A characterization of first-order topological properties of planar spatial data
Michael Benedikt, Christof Loeding, Jan Van den Bussche, Thomas Wilke

Roads, Codes, and Spatiotemporal Queries
Sandeep Gupta, Swastik kopparty, Chinya Ravishankar

Replicated Declustering of Spatial Data
Hakan Ferhatosmanoglu, Ali Saman Tosun, Aravind Ramachandran

12:30 - 14:00 Lunch
14:00 - 16:00 PODS SESSION 7: Clustering, Data Mining, Approximations Chair: Jeff Naughton

Clustering via Matrix Powering
Hanson Zhou, David Woodruff

Computational Complexity of Itemset Frequency Satisfiability
Toon Calders

k-Means Projective Clustering
Pankaj Agarwal, Nabil Mustafa

Deterministic Wavelet Thresholding for Maximum-Error Metrics
Minos Garofalakis, Amit Kumar

16:30 - 18:30 PODS SESSION 8: Query Execution and Optimization Chair: Gottfried Vossen

On the memory requirements of evaluating XPath queries over XML streams
Ziv Bar-Yossef, Marcus Fontoura, Vanja Josifovski

Conjunctive Queries over Trees
Georg Gottlob, Christoph Koch, Klaus Schulz

Synopses for Query Optimization: A Space-Complexity Perspective
Raghav Kaushik, Raghu Ramakrishnan, Venkatesan Chakaravarthy

Weighted Hypertree Decompositions and Optimal Query Plans
Francesco Scarcello, Gianluigi Greco, Nicola Leone

18:45 - 20:00 PODS Business meeting

Wednesday, June 16   ^

8:30 - 10:00 PODS SESSION 9: Invited Tutorial Chair: Frank Neven

Trees, Automata and XML
Thomas Schwentick

10:30 - 12:00 PODS SESSION 10: Data Exchange II Chair: Wenfei Fan

On the complexity of optimal k-anonymity
Adam Meyerson, Ryan Williams

Locally Consistent Transformations and Query Answering in Data Exchange
Marcelo Arenas, Pablo Barcelo, Ronald Fagin, Leonid Libkin

Logical Foundations of Peer-To-Peer Data Integration
Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Riccardo Rosati

12:00 - 13:30 Lunch
13:30 - 14:30 SIGMOD Business Meeting
14:45 - 16:45 PODS SESSION 11: Data Streams Chair: Yossi Matias

Adaptive Sampling for Geometric Problems over Data Streams
John Hershberger, Subhash Suri

Flexible Time Management in Data Stream Systems
Utkarsh Srivastava, Jennifer Widom

Power-Conserving Computation of Order-Statistics over Sensor Networks
Michael Greenwald, Sanjeev Khanna

Approximate Quantiles and Frequency Counts over Sliding Windows
Arvind Arasu, Gurmeet Manku

17:15 - 19:15 PODS SESSION 12: Foundations of Query Languages Chair: Michael Benedikt

On the Decidability of Containment of Recursive Datalog Queries - Preliminary report
Piero Bonatti

Processing First-Order Queries under Limited Access Patterns
Alan Nash, Bertram Ludaescher

On preservation under homomorphisms and unions of conjunctive queries
Albert Atserias, Anuj Dawar, Phokion Kolaitis

Multi-valued Dependencies in the Presence of Lists
Sven Hartmann, Sebastian Link

20:30 Banquet

Invited Talk, Monday, June 14   ^

The Lixto Data Extraction Project: Back and Forth between Theory and Practice

Georg Gottlob (TU Wien)


Corporate decision making relies more and more on data available on the Web. Wrapper technology is used to extract structured data from unstructured or poorly structured Web sources of continually changing content and to automatically input this data into corporate information systems. This talk gives a survey of the Lixto Web data extraction project and describes the interaction beteween theoretical and practical research issues of this project. The talk will address issues such as: Logical foundations of data extraction, visual and logical languages for web wrapping, complexity of tree pattern matching, integration of information stemming from different Web sources, successful industrial applications of the Lixto system, and issues for future research. Lixto is a project of the Vienna University of Technology (TU Wien) which gave rise to the spin off company Lixto Software GmbH ( This talk describes joint work with Robert Baumgartner, Sergio Flesca, Marcus Herzog, and Christoph Koch


Georg Gottlob is a Professor of Computer Science at the Technical University of Vienna, Austria, where he currently chairs the Informatioin Systems Institute. His research interests are database theory (in particular, query languages), Web information processing, constraint satisfaction problems, nonmonotonic reasoning, finite model theory, and computational complexity. On the more applied side, he supervises a number of industry projects dealing with expert systems and with multimedia information systems. He is a co-founder of the Lixto Software Corporation.

Gottlob got his Engineer and Ph.D. degrees in Computer Science from TU Vienna, Austria in 1979 and 1981, respectively. He holds his current position since 1988. He recently received the Wittgenstein Award from the Austrian National Science Fund and was elected corresponding Member of the Austrian Academy of Sciences. He recently chaired the Program Committee of ACM PODS 2000 and is the Program Chair of IJCAI 2003.

Invited Tutorial I, Monday, June 14   ^

The Past, Present and Future of Web Information Retrieval

Monika Henzinger (Google)


Web search engines have emerged as one of the central applications on the Internet. In fact, search has become one of the most important activities that people engage in on the the Internet. Even beyond becoming the number one source of information, a growing number of businesses are depending on web search engines for customer acquisition.

The first generation of web search engines used text-only retrieval techniques. Google revolutionized the field by deploy ing the PageRank technology - an eigenvector-based analysis of the hyperlink structure - to analyze the web in order to produce relevant results. Moving forward, our goal is to achieve a better understanding of a page with a view towards producing even more relevant results.

An exciting new form of search for the future is query-free search: While a user performs her daily tasks, searches are automatically performed to supply her with information that is relevant to her activity. We present one type of query-free search, namely query-free news search: While a user watches TV news the system finds in real-time web pages that are relevant to the news stories.


Monika Henzinger is the research director at Google. Prior to joining Google, Henzinger was a member of the research staff at Digital's Systems Research Center in Palo Alto, Calif. from 1996 to the fall of 1999. There she worked on Web information retrieval and systems performance measurements as well as graph algorithms and data structures, which are useful for mapping the topography and behavior of the Web. Henzinger received her Ph.D. from Princeton University in 1993. She then joined the Computer Science Department at Cornell University as an assistant professor and received a National Science Foundation CAREER award in 1995. Henzinger is also a recipient of the Wallace Memorial Honorific Fellowship at Princeton University, a Studienstiftung des deutschen Volkes fellowship and a Siemens Scholarship fellowship.

Invited Tutorial II, Wednesday, June 16   ^

Trees, automata and XML

Thomas Schwentick (University of Marburg)


Formal languages play an important role for many aspects of XML processing. This is obvious for type specifications (as DTD) which use context-free grammars and for navigation in documents (as in XPath) which is based on regular expressions. But the investigation of query, typing, navigation and transformation languages for XML has used many more concepts from Formal Language Theory, in particular many different kinds of string and tree automata.

The close connection between automata and logics helps to allow a declarative specification of queries and transformations that can be evaluated or performed by tree automata. This connection also facilitates the investigation of the expressive power of query and transformation languages. Furthermore, in many cases automata characterizations enable static analysis like containment and satisfiability tests for queries or type checking for transformations.

The tutorial will give a gentle introduction into the connections between XML languages and various kinds of automata and it will survey some classical and recent results in this area.


Thomas Schwentick is Professor of Theoretical Computer Science at the Philipps University in Marburg (Germany). Currently, his primary research interest lies in the theoretical foundations of the tree- and semistructured data model. Another area of interest are topics like finite or algorithmic model theory mostly centered around descriptive complexity. Finally, he also works on more general complexity and automata / formal language questions.

Schwentick received his Diploma and Doctor degrees from the Johannes Gutenberg University in Mainz (Germany) in 1989 and 1995, respectively. After his habilitation in 1999 he became a Professor for Computer Science at the Friedrich-Schiller-University Jena (Germany) in 2001. In the same year he moved to his current position in Marburg.

Welcome | SIGMOD CFP | PODS CFP | SIGMOD Program | PODS Program | Registration | Organization | Venue | Links

Web site by GaŽtan Gaumer - Original design by Michalis Petropoulos - Feedback