PODS program


6:00pm - 8:00pm PODS reception - Rio Grande Terrace


All Monday sessions are in Grand Ballroom 1-3

8:15am - 9:30am PODS opening and keynote
Chair: Jan Van den Bussche

Principles of Dataspace Systems
Alon Halevy (Google)
9:30am - 10:15am PODS award papers
Chair: Jan Van den Bussche

Two-Variable Logic on Data Trees and XML Reasoning (Best paper award)
Mikolaj Bojanczyk (Warsaw University), Claire David, Anca Muscholl (University of Paris 7), Thomas Schwentick (University of Dortmund), Luc Segoufin (INRIA)

An Adaptive Packed-Memory Array (Best newcomer award)
Michael Bender, Haodong Hu (Stony Brook)
10:15am - 10:45am coffee break
10:45am - 12:15pm Data exchange
Chair: Alin Deutsch

The Complexity of Data Exchange
Phokion Kolaitis (IBM), Jonathan Panttaja, Wang-Chiew Tan (UCSC)

Data Exchange: Computing Cores in Polynomial Time
Georg Gottlob (TU Wien), Alan Nash (UCSD)

Inverting schema mappings
Ronald Fagin (IBM)

Data Exchange and Incomplete Information
Leonid Libkin (Toronto)
12:15am - 1:45pm lunch (on your own)
1:45pm - 3:15pm Analysis of queries and workflows
Chair: Alan Fekete

Equivalence of Queries Combining Set and Bag-Set Semantics
Sara Cohen (Technion)

The Containment Problem for "Real" Conjunctive Queries with Inequalities
T.S. Jayram, Phokion Kolaitis, Erik Vee (IBM)

Verification of Communicating Data-Driven Web Services
Alin Deutsch, Liying Sui, Victor Vianu, Dayou Zhou (UCSD)

Analyzing workflows implied by instance-dependent access rules
Toon Calders (University of Antwerp), Stijn Dekeyser (University Southern Queensland), Jan Hidders, Jan Paredaens (University of Antwerp)
3:15pm - 3:45pm coffee break
3:45pm - 4:45pm Invited tutorial
Chair: Dirk Van Gucht

From Statistical Knowledge Bases to Degrees of Belief
Joseph Y. Halpern (Cornell)
4:45pm - 5:30pm Database design
Chair: Dirk Van Gucht

On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF
Solmaz Kolahi, Leonid Libkin (Toronto)

Tractable Database Design through Bounded Treewidth
Georg Gottlob, Reinhard Pichler, Fang Wei (TU Wien)
5:30pm - 5:45pm short break
5:45pm - 6:45pm Alberto Mendelzon memorial session
Chair: Renee Miller

Talks by Mariano Consens, HV Jagadish, and David Maier


8:30am - 10:00am SIGMOD opening and keynote
10:00am - 10:30am coffee break
10:30am - 12 noon Popularity and privacy
Chair: Gerome Miklau
Room: Rhine

Evolution of Page Popularity under Random Web Graph Models
Rajeev Motwani, Ying Xu (Stanford)

Privacy via Pseudorandom Sketches
Nina Mishra (University of Virginia), Mark Sandler (Cornell)

Achieving Anonymity via Clustering in a Metric Space
Gagan Aggarwal (Google), Tomas Feder, Krishnaram Kenthapadi (Stanford), Samir Khuller (Maryland), Rina Panigrahy, Dilys Thomas (Stanford), An Zhu (Google)

On the Efficiency of Checking Perfect Privacy
Ashwin Machanavajjhala, Johannes Gehrke (Cornell)
12 noon - 1:30pm lunch
1:30pm - 3:00pm Query optimisation
Chair: Sara Cohen
Room: Rhine

Finding and Approximating Top-k Answers in Keyword Proximity Search
Benny Kimelfeld, Shuky Sagiv (Hebrew University)

Efficiently Ordering Subgoals with Access Constraints
Guizhen Yang, Vinay K. Chaudhri (SRI), Michael Kifer (Stony Brook)

Flow Algorithms for Two Pipelined Filter Ordering Problems
Anne Condon (UBC), Amol Deshpande, (University of Maryland), Lisa Hellerstein, Ning Wu (Polytechnic University)

Asking the right questions: Model-driven optimization using probes
Ashish Goel (Stanford), Sudipto Guha (UPenn), Kamesh Munagala (Duke)
3:00pm - 3:30pm coffee break
3:30pm - 4:30pm Invited tutorial
Chair: Frank Neven
Room: Grand Ballroom 6

Processing Queries on Tree-Structured Data Efficiently
Christoph Koch (Saarland University)
4:30pm - 5:15pm Query processing
Chair: Frank Neven
Room: Grand Ballroom 6

Scalable computation of acyclic joins
Anna Pagh, Rasmus Pagh (IT University of Copenhagen)

Cache-Oblivious String B-trees
Michael Bender (Stony Brook), Martin Farach-Colton (Rutgers), Bradley Kuszmaul (MIT)
5:15pm - 5:30pm short break
5:30pm - 7:00pm Stream algorithms and complexity
Chair: Christoph Koch
Room: Rhine

Randomized Computations on Large Data Sets: Tight Lower Bounds
Martin Grohe, Andre Hernich, Nicole Schweikardt (Humboldt-University Berlin)

Counting Triangles in Data Streams
Luciano Buriol (Universidade Federal de Santa Maria), Gereon Frahling (University of Paderborn), Stefano Leonardi, Alberto Marchetti-Spaccamela (University of Rome La Sapienza), Christian Sohler (University of Paderborn)

Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams
Graham Cormode (Bell Labs), Flip Korn, S. Muthukrishnan, Divesh Srivastava (AT&T Research)

Approximate Quantiles and the Order of the Stream
Sudipto Guha, Andrew McGregor (UPenn)
9:00pm - 11:00pm PODS business meeting
Room: Hudson


8:30am - 10:15am SIGMOD awards session
10:15am - 10:45am coffee break
10:45am - 12:15pm Frequency counting and aggregation
Chair: CK Poon
Room: Rhine

Deterministic k-set structure
Sumit Ganguly, Anirban Majumder (IIT Kanpur)

A simpler and more efficient deterministic scheme for finding frequent items over sliding windows
L.K. Lee, H.F. Ting (University of Hong Kong)

Finding Global Icebergs over Distributed Data Sets
Qi Zhao (Georgia Tech), Mitsunori Ogihara (Rochester), Haixun Wang (IBM), Jun Xu (Georgia Tech)

Efficient Gossip-Based Aggregate Computation
Srinivas Kashyap (University of Maryland), Supratim Deb, K.V.M. Naidu, Rajeev Rastogi, Anand Srinivasan (Bell Labs)
12:15pm - 1:45pm lunch & SIGMOD business meeting
1:45pm - 2:00pm short break
2:00pm - 3:30pm Query, update, and mining languages
Chair: Ronald Fagin
Room: Rhine

Structural Characterizations of the Semantics of XPath as Navigation Tool on a Document
Marc Gyssens (Hasselt University), Jan Paredaens (University of Antwerp), Dirk Van Gucht, George Fletcher (Indiana University)

The expressivity of XPath with transitive closure
Balder ten Cate (Universiteit van Amsterdam)

Relational Lenses: A Language for Updatable Views
Aaron Bohannon, Benjamin Pierce, Jeffrey A. Vaughan (UPenn)

Programmable Clustering
Sreenivas Gollapudi (Ebrary), Ravi Kumar (Yahoo!), D. Sivakumar (Google)
3:30pm - 4:00pm coffee break
4:00pm - 5:00pm Invited tutorial
Chair: Michael Kifer
Room: Rhine

The Logic of the Semantic Web
Enrico Franconi (Free University of Bozen-Bolzano)
5:00pm - 5:30pm Incomplete information, and PODS closing
Chairs: Michael Kifer, Jan Van den Bussche
Room: Rhine

On the decidability and finite controllability of query processing in databases with incomplete information
Riccardo Rosati (University of Rome La Sapienza)