Untitled Document

PODS program

Sunday

6:00pm - 8:00pm

PODS reception - Rio Grande Terrace

Monday

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

Tuesday

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

Wednesday

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)