Proceedings of ACM SIGMOD
International Conference on Management of Data

May 31 - June 3, 1999, Philadephia, Pennsylvania, USA

Table of Contents

Foreword

Conference Organizing Committee

Program Committee

External Referees

Research Sessions

Panel Sessions

Tutorial Sessions

Industrial Sessions

Demonstrations

 

 

FOREWORD

The 1999 ACM SIGMOD International Conference on Management of Data was held in Philadelphia, Pennsylvania, June 1-3, 1999. The SIGMOD Conference is sponsored by the Associations for Computing Machinery (ACM) and its Special Interest Group on Management of Data (SIGMOD) and is an annual, international forum for the dissemination and discussion of new ideas in database technology and the presentation of database products and prototypes. The Call for Papers attracted 205 submission of research papers, out of which 42 were accepted. Once again, the quality of the competing papers was high, with an impressive count of 9 'best paper' nominations. The conference also included a rich program of tutorials, panels, demonstrations and industrial sessions. The opening address was delivered by Jim Gray and the second day keynote address by Ted Berger. There is a long list of people who volunteered their time and energy to put together such a strong program: Dennis Shasha, Ken Salem, and Guy Lohman selected the tutorials, demos and panels, respectively, covering a broad spectrum of topics, including electronic commerce, database scale-up and scale-down, web mining, to name a few. The Industrial Committee - Divy Agrawal, Surajit Chaudhuri, Misha Rabinovich and Eric Simon - assembled a strong industrial program, bringing together all the major database vendors, as well as companies in telecommunications, e-commerce and manufacturing. The members of the Program Committee did the reviews thoroughly and timely, despite the tight schedule. Daniel Volkovich at CMU and Alex Labrinidis at Maryland did a terri,c job in setting up the website for the electronic submission of abstracts and reviews. Steven Rudich and David Karger pointed us to a wonderful algorithm that automatically assigns reviewers to papers. Dorothy Zaborowski at CMU and Julieta Dela Paz at USC provided impeccable secretarial support. We are also endebted to the many people whose efforts have ensured a smoothly operating conference: Gang Zhou and Jim Wol, for managing the finances; Lew Hassell and Il-Yeol Song for handling local arrangements; Jason Tsong-Li Wang for arranging exhibits; Joachim Hammer for expertly managing the registrations; Sridhar Ramaswamy for publicizing the program and coordinating the Call for Papers and both the advance and final programs; HweeHwa Pang and Daniela Florescu for publicizing the conference in the Far East and Europe; Daniel Barbara for pursuing industrial sponsors; and last but not least, Mary Fernandez for using Strudel to generate and maintain the lovely web site. Finally we would like to thank the authors and contributors for their time and effort in creating such a distinguished program.

Susan Davidson - General Chair
Christos Faloutsos - Program Chair
Shahram Ghandeharizadeh - Program Vice Chair
Alex Delis - Proceedings Chair
Euthimios Panagos - Electronic Proceedings Chair

Back to Table of Contents

CONFERENCE ORGANIZING COMMITTEE

 

SIGMOD GENERAL CHAIR: Susan B. Davidson, Univ. of Pennsylvania

PROGRAM CHAIR: Christos Faloutsos, Carnegie Mellon Univ.

PROGRAM VICE-CHAIR: Shahram Ghandeharizadeh, Univ. of Southern California

BEST PAPER AWARD COMMITTEE:

CORPORATE SPONSORS CHAIR: Daniel Barbara, George Mason University

DEMOSTRATIONS CHAIR: Ken Salem, Univ. of Waterloo

DEMONSTRATION EVALUATION COMMITTEE:

ELECTRONIC PROCEEDINGS CHAIR: Euthimios Panagos, AT & T Labs - Research

EUROPEAN COORDINATOR: Daniela Florescu, INRIA-projet Rodin

EXHIBITS CHAIR: Jason Tsong-Li Wang, New Jersey Institute of Technology

FAR EAST COORDINATOR: HweeHwa Pang, Kent Ridge Digital Labs

FINANCE CHAIR: Gang Zhou, Bell Laboratories, Lucent Technologies

INDUSTRIAL CO-CHAIRS:

LOCAL ARRANGEMENTS CHAIR: Lew Hassell, Drexel Univ.

LOCAL DEMO CHAIR: Il-Yeol Song, Drexel Univ.

PANELS CHAIR: Guy M. Lohman, IBM Almaden Research Center

PROCEEDINGS CHAIR: Alex Delis, Polytechnic University

PUBLICITY CHAIR: Sridhar Ramaswamy, Bell Laboratories

REGISTRATION CHAIR: Joachim Hammer, University of Florida

TUTORIAL CHAIR: Dennis Shasha, New York University and Projet Rodin, INRIA

WEB-SITE CHAIR: Mary Fernandez, AT & T Labs - Research

Back to Table of Contents


PROGRAM COMMITTEE

Ricardo Baeza-Yates, Univ. of Chile

Elisa Bertino, Univ. of Milano

Alexandros Biliris, AT & T Labs

Panos K. Chrysanthis, Univ. of Pittsburgh

Anand Deshpande, Persistent Systems Private Ltd.

Curtis Dyreson, Aalborg Univ.

Leana Golubchik, Univ. of Maryland

Luis Gravano, Columbia Univ.

Jiawei Han, Simon Fraser Univ.

Sushil Jajodia, George Mason Univ.

Theodore Johnson, AT & T Labs

Daniel A. Keim, Halle Univ.

Roger King, Univ. of Colorado-Boulder

Masaru Kitsuregawa, Univ. of Tokyo

Paul Larson, Microsoft

Yannis Manolopoulos, Univ. of Thessaloniki

Yossi Matias, Tel Aviv Univ.

Claudia Bauzer Medeiros, UNICAMP

Tova Milo, Tel Aviv Univ.

Guido Moerkotte, Univ. of Mannheim

Amihai Motro, George Mason Univ.

Richard Muntz, UCLA

Jeff Naughton, Univ. of Wisconsin-Madison

Raymond T. Ng, Univ. of British Columbia

Pat O'Neil, Univ. of Massachusetts-Boston

Banu Ozden, Bell Labs

M. Tamer Ozsu, Univ. of Alberta

Yannis Papakonstantinou, UCSD

Raghu Ramakrishnan, Univ. of Wisconsin-Madison

Krithi Ramamritham, ITT, Mumbai, India

Chinya V. Ravishankar, Univ. of Michigan - Ann Arbor

Kenneth A. Ross, Columbia Univ.

Nick Roussopoulos, Univ. of Maryland

Betty Salzberg, Northeastern Univ.

Peter Scheuermann, NSF

Bernhard Seeger, Univ. of Marburg

Kenneth C. Sevcik, Univ. of Toronto

Kyuseok Shim, Bell Labs

Peter Triantafillou, Tech. Univ. of Crete

Vassilis J. Tsotras, UC Riverside

Ouri Wolfson, Univ. of Illinois-Chicago

Masatoshi Yoshikawa, NAIST

Clement Yu, Univ. of Illinois Chicago

Philip S. Yu, IBM-Watson

Pavel Zezula, Univ. of Brno

  

Back to Table of Contents

EXTERNAL REFEREES

Swarup Acharya

Steve Kelley Manuel

Rodriguez-Martinez

Charu Aggarwal

Hiroyuki Kitagawa

Eran Segal

Yousef J. Al-Houmaily

Yakov Kogan

S. Seshadri

A.Balachandran

George Kollios

Uri Shaft

Sujata Banerjee

David Konopnicki

Oded Shmueli

Daniel Barbara

Krzysztof Koperski

Shridhar Shukla

Alberto Belussi

Flip Korn

Lisa Singh

Yoav Benjamini

Yannis Kotidis

A. Prasad Sistla

Sonia Bergamaschi

Nick Koudas

Kostas Stathatos

Bjorn Blohsfeld

Alexandros Labrinidis

Jorge Stolfi

Michael Bohlen

Laks V.S. Lakshmanan

Dan Suciu

Yuri Breitbart

Ana Lelescu

S. Sudarshan

Alex Brodsky

Jin Li

Keishi Tajima

Barbara Catania

Nikos Lorentzos

Jamel Tayeb

Edgar Chavez

Xuebin Lu

Toby J. Teorey

Sonny H. S. Chee

Bertram Ludaescher

Jochen Van den Bercken

Paolo Ciaccia

Subhasish Mazumdar

Vasilis Vassalos

Sara Cohen

Weiyi Meng

T. M. Vijayaraman

Mary Fernandez

Isabella Merlo

Kaladhar Voruganti

Marcelo Finger

Alex Nanopoulos

Alan Wagner

Venkatesh Ganti

Mario Nascimento

Gary Walborn

Minos Garofalakis

Gonzalo Navarro

Wei Wang

Johannes Gehrke

Tadashi Ohmori

X. Sean Wang

Jonathan Goldstein

Edward Omiecinski

Susan Weissman-Lauzac

Giovanna Guerrini

Beng Chin

Ooi Bo Xu

Bruce K. Hillyer

Vincent Oria

Jiong Yang

Alexander Hinneburg

Apostolos Papadopoulos

Yiwen Yin

Yoshiharu Ishikawa

Viswanath Poosala

Haruo Yokota

Linan Jiang

Sridhar Ramaswamy

Osmar R. Zaiane

Simon Kasif

Jun Rao Hua Zhu

 

Back to Table of Contents

RESEARCH SESSIONS

Session: Spatial Databases

Integration of Spatial Join Algorithms for Processing Multiple Inputs

Nikos Mamoulis, Dimitris Papadias ... Abstract, Paper
Selectivity Estimation in Spatial Databases

Swarup Acharya, Viswanath Poosala, Sridhar Ramaswamy... Abstract, Paper
Efficient Concurrency Control in Multidimensional Access Methods

Kaushik Chakrabarti, Sharad Mehrotra ... Abstract, Paper

Session: Clustering

Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse

H. V. Jagadish, Laks V.S. Lakshmanan, Divesh Srivastava ... Abstract, Paper
OPTICS: Ordering Points To Identify the Clustering Structure

Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, J-org Sander ... Abstract, Paper
Fast Algorithms for Projected Clustering

Charu C. Aggarwal, Cecilia Procopiuc, Joel L. Wolf, Philip S. Yu, Jong Soo Park ... Abstract, Paper

Session: Recovery and Concurrency

Logical Logging to Extend Recovery to New Domains

David Lomet, Mark Tuttle ... Abstract, Paper
Efficient Concurrency Control for Broadcast Environments

Jayavel Shanmugasundaram, Arvind Nithrakashyap, Rajendran Sivasankaran, Krithi Ramamritham ... Abstract, Paper
Update Propagation Protocols For Replicated Databases

Yuri Breitbart, Raghavan Komondoor, Rajeev Rastogi, S. Seshadri, Avi Silberschatz ... Abstract, Paper

Session: Languages and Models

Belief Reasoning in MLS Deductive Databases

Hasan M. Jamil ... Abstract, Paper
A Multimedia Presentation Algebra

Sibel Adali, Maria-Luisa Sapino, V.S. Subrahmanian ... Abstract, Paper
Querying Network Directories

H. V. Jagadish, Laks V.S. Lakshmanan, Tova Milo, Divesh Srivastava, Dimitra Vista ... Abstract, Paper

Session: Data Mining - Association Rules and Decision Trees

Online Association Rule Mining

Christian Hidber ... Abstract, Paper
Optimization of Constrained Frequent Set Queries with 2-variable Constraints

Laks V.S. Lakshmanan, Raymond T. Ng, Jiawei Han, Alex Pang ... Abstract, Paper
BOAT-Optimistic Decision Tree Construction

Johannes Gehrke, Venkatesh Ganti, Raghu Ramakrishnan, Wei-Yin Loh ... Abstract, Paper

Session: Histograms

Self-tuning Histograms: Building Histograms Without Looking at Data

Ashraf Aboulnaga, Surajit Chaudhuri ... Abstract, Paper
Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets

Jeffrey Scott Vitter, Min Wang ... Abstract, Paper
Multi-dimensional Selectivity Estimation Using Compressed Histogram Information

Ju-Hong Lee, Deok-Hwan Kim, Chin-Wan Chung ... Abstract, Paper

Session: Selectivities

An Efficient Bitmap Encoding Scheme for Selection Queries

Chee-Yong Chan, Yannis E. Ioannidis ... Abstract, Paper
Query Optimization for Selections Using Bitmaps

Ming-Chuan Wu ... Abstract, Paper
A Comparison of Selectivity Estimators for Range Queries on Metric Attributes

Bjorn Blohsfeld, Dieter Korus, Bernhard Seeger : ... Abstract, Paper

Session: Sampling - Approximate Answers

Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets

Gurmeet Singh Manku, Sridhar Rajagopalan, Bruce G. Lindsay ... Abstract, Paper
On Random Sampling over Joins

Surajit Chaudhuri, Rajeev Motwani, Vivek Narasayya ... Abstract, Paper
Join Synopses for Approximate Query Answering

Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, Sridhar Ramaswamy ... Abstract, Paper

Session: Adaptive Query Optimization

Ripple Joins for Online Aggregation

Peter J. Haas, Joseph M. Hellerstein ... Abstract, Paper
An Adaptive Query Execution System for Data Integration

Zachary G. Ives, Daniela Florescu, Marc Friedman, Alon Levy, Daniel S. Weld ... Abstract, Paper
Query Optimization in the Presence of Limited Access Patterns

Daniela Florescu, Alon Levy, Ioana Manolescu, Dan Suciu ... Abstract, Paper

Session: New Data Types

Query Processing Techniques for Arrays

Arunprasad P. Marathe, Kenneth Salem ... Abstract, Paper
Mind Your Vocabulary: Query Mapping Across Heterogeneous Information Sources

Chen-Chuan K. Chang, Hector Garcia-Molina ... Abstract, Paper
Client-Site Query Extensions

Tobias Mayr, Praveen Seshadri ... Abstract, Paper

Session: Datacubes and Data Warehouses

Bottom-Up Computation of Sparse and Iceberg CUBEs

Kevin Beyer, Raghu Ramakrishnan ... Abstract, Paper
DynaMat: A Dynamic View Management System for Data Warehouses

Yannis Kotidis, Nick Roussopoulos ... Abstract, Paper
Shrinking the Warehouse Update Window

Wilburt Juan Labio, Ramana Yerneni, Hector Garcia-Molina ... Abstract, Paper

Session: Similarity Search

WALRUS: A Similarity Retrieval Algorithm for Image Databases

Apostol Natsev, Rajeev Rastogi, Kyuseok Shim ... Abstract, Paper
A New Method for Similarity Indexing of Market Basket Data

Charu C. Aggarwal, Joel L. Wolf, Philip S. Yu ... Abstract, Paper
Efficient Geometry-based Similarity Search of 3D Spatial Databases

Daniel A. Keim ... Abstract, Paper

Session: Semistructured Data and Mediators

Storing Semistructured Data with STORED

Alin Deutsch, Mary Fernandez, Dan Suciu ... Abstract, Paper
Computing Capabilities of Mediators

Ramana Yerneni, Chen Li, Hector Garcia-Molina, Jeffrey Ullman ... Abstract, Paper
Query Rewriting using Semistructured Data

Yannis Papakonstantinou, Vasilis Vassalos ... Abstract, Paper

Session: Text and Web Databases

Record-Boundary Discovery in Web Documents

D. W. Embley, Y. S. Jiang, Y.-K. Ng ... Abstract, Paper
Automatic Discovery of Language Models for Text Databases

Jamie Callan, Margaret Connell, Aiqun Du ... Abstract, Paper
A Layered Architecture for Querying Dynamic Web Content

Hasan Davulcu, Juliana Freire, Michael Kifer, I.V. Ramakrishnan ... Abstract, Paper

Back to Table of Contents

PANEL SESSIONS

"Honey, I Shrunk the DBMS": Footprint, Mobility, and Beyond

Praveen Seshadri , Cornell University ... Paper
Of Crawlers, Portals, Mice and Men: Is there more to Mining the Web ?

Minos N. Garofalakis, Shridhar Ramaswamy, Rajeev Rastogi, Kyuseok Shim, Bell Labs ... Paper
Data Management Issues in Electronic Commerce

M. Tamer -Ozsu, University of Alberta ... Paper

Back to Table of Contents

TUTORIAL SESSIONS

Petabyte Databases

Dirk D"ullmann, CERN IT/ASD & RD45 ... Slides, Paper
A Database Perspective on Lotus Domino/Notes

C. Mohan, IBM Almaden Research Center ... Slides, Paper
Hypertext Databases and Data Mining

Soumen Chakrabarti, Indian Institute of Technology Bombay ... Slides , Paper
Clustering Methods for Large Databases: From the Past to the Future

Alexander Hinneburg, Daniel A. Keim, University of Halle-Wittenberg ... Slides , Paper
Managing Web Data

Dan Suciu, AT & T Labs - Research ... Slides , Paper

Back to Table of Contents

INDUSTRIAL SESSIONS

Session: Object, Relations, and SQL-3

O-O, What's Happening to DB2?

M. Carey, D. Chamberlin, S. Narayanan, B. Vance, D. Doole, S. Rielau, R. Swagerman, N. Mattos, IBM Almaden Research Center, IBM Toronto Lab, and IBM Database Technology Institute ... Paper
Bringing Object-Relational Technology to Mainstream

Vishu Krishnamurthy, Sandeepan Banerjee, Anil Nori, Oracle Corporation ... Paper
Implementing the Spirit of SQL-99

Paul Brown, INFORMIX Software ... Paper

Session: Database Storage Management

DataBlitz Storage Manager: Main Memory Database Performance for Critical Applications

J. Baulier, P. Bohannon, S. Gogate, C. Gupta, S. Haldar, S. Joshi, A. Khivesera, H. Korth, P. Mcilroy, J. Miller, P.P.S. Narayan, M. Nemeth, R. Rastogi, S. Seshardi, A. Silberschatz, S. Sudarshan, M. Wilder, C. Wei, Bell Laboratories ... Paper
Indexing Medium-dimensionality Data in Oracle

K.V. Ravi Kanth, Siva Ravada, Jayant Sharma, Jay Banerjee, Oracle Corporation ... Paper
EMC Information Sharing: Direct Access to MVS Data from Unix and NT

Walt Kohler, EMC Corporation ... Paper

Session: Database Architectures

Daytona and the Fourth-Generation Language Cymbal

Rick Greer, AT&T Labs - Research ... Paper
Merge Replication in Microsoft's SQL Server 7.0

Brad Hammond, Microsoft Corporation ... Paper
In-Memory Data Management for Consumer Transactions The Times-Ten Approach

The Times Ten Team, TimesTen Performance Software ... Paper

Session: E-Commerce and Repositories

Microsoft Site Server (Commerce Edition)

Bassel Ojjeh, Microsoft Corporation ...
E-Commerce Database Issues and Experience

Anand Rajaraman, Amazon ...
Versions and Workspaces in Microsoft Repository

Thomas Bergstraesser, Philip A. Bernstein, Shankar Pal, David Shutt, Microsoft ... Paper

Session: Database Techniques/Experience

The Need for Distributed Asynchronous Transactions

Lyman Do, Prabhu Ram, Pamela Drew, The Boeing Company ... Paper
Improving OLTP Data Quality Using Data Warehouse Mechanisms

Matthias Jarke, Christoph Quix, Guido Blees, Dirk Lehmann, Gunter Michalk, Stefan Striel,RWTH Aachen and Team4 Systemhaus GmbH ... Paper
Data Integration and Warehousing in Telecom Italia

Stefano Trisolini, Maurizio Lenzerini, Deniele Nardi, Telecom Italia and University of Rome "La Sapienza" ... Paper

Back to Table of Contents

DEMONSTRATIONS

An XML-based Wrapper Generator for Web Information Extraction

Ling Liu, Wei Han, David Buttler, Calton Pu, Wei Tang ... Paper
DBIS-Toolkit: Adaptable Middleware for Large Scale Data Delivery

Mehmet Altinel, Demet Aksoy, Thomas Baby, Michael Franklin, William Shapiro, Stanley B. Zdonik ... Paper
DOMINO: Databases fOr MovINg Objects tracking

Ouri Wolfson, Prasad A. Sistla, Bo Xu, Jutai Zhou, Sam Chamberlain ... Paper
Database Patchwork on the Internet

Reinhard Braumandl, Alfons Kemper, Donald Kossmann ... Paper
Evolvable View Environment (EVE): Non-Equivalent View Maintenance under Schema Changes

Elke A. Rundensteiner, A. Koeller, X. Zhang, A. VanWyk, Y. Li, A.J. Lee, A. Nica ... Paper
Exploratory Mining via Constrained Frequent Set Queries

Raymond Ng, Laks V.S. Lakshmanan, Jiawei Han, Teresa Mah ... Paper
Nodose Version 2.0

Brad Adelberg, Matthew Denny ... Paper
Phoenix: Making Applications Robust

Roger Barga, David B. Lomet ... Paper
PowerBookmarks: A System for Personalizable Web Information Organization, Sharing, and Management

Wen-Syan Li, Quoc Vu, Edward Chang, Divyakant Agrawal, Kyogi Hirata, Sougata Mukherjea, Yi-Len Wu, Corey Bu,, Chen-Chuan Kevin Chang, Yoshinori Hara, Reiko Ito, Yutaka Kimura, Kazuyuki Shimazu, Yukiyoshi Saito ... Paper
SERF: ODMG-Based Generic Re-structuring Facility

Elke A. Rundensteiner, K. Claypool, M. Li, L. Chen, X. Zhang, C. Natarajan, J. Jin, S. De Lima, S. Weiner ... Paper
TAM: A System for Dynamic Transactional Activity Management

Tong Zhou, Ling Liu, Calton Pu ... Paper
The Aqua Approximate Query Answering System

Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, Sridhar Ramaswamy ... Paper
The CCUBE Constraint Object-Oriented Database System

Alexander Brodsky, Victor E. Segal, Jia Chen, Pavel A. Exarkhopoulo ... Paper
The Cornell Jaguar System: Adding Mobility to PREDATOR

Philippe Bonnet, Kyle Buza, Zhiyuan Chen, Victor Cheng, Randolph Chung, Takako Hickey, Ryan Kennedy, Daniel Mahashin, Tobias Mayr, Ivan Oprencak, Praveen Seshadri, Hubert Siu ... Paper
The Active MultiSync Controller of the Cubetree Storage Organization

Nick Roussopoulos, Yannis Kotidis, Yannis Sismanis ... Paper
The Jungle Database Search Engine

Michael Bohlen, Linas Bukauskas, Curtis Dyreson ... Paper
The WASA2 Object-Oriented Workflow Management System

Gottfried Vossen, Mathias Weske ... Paper1 Paper2
A User-Centered Interface for Querying Distributed Multimedia Databases

Isabel F. Cruz, Kimberly M. James ... Paper
World Wide Database - Integrating the Web, CORBA, and Databases

Athman Bouguettaya, Boualem Benatallah, Lily Hendra ... Paper
XML-Based Information Mediation with MIX

Chaitan Baru, Amarnath Gupta, Bertram Lud-ascher, Richard Marciano, Yannis Papakonstantinou, Pavel Velikhov, Vincent Chu ... Paper

Back to Table of Contents