Search SIGMOD Join SIGMOD Feedback What's New Home
SIGMOD/PODS Conferences
DBLP Bibliography
SIGMOD Digital Symposium Collection
SIGMOD Anthology
SIGMOD Digital Review
Industry Pages
The PODS Pages
Post/Read DB World Messages
Volume 28    Number 2    June 1999
Current Issue XML Edition
Previous Issue About SIGMOD
Info for Authors FAQ
Record Editors Credits

 Proceedings of ACM SIGMOD
International Conference on Management of Data

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

Table of Contents


Conference Organizing Committee

Program Committee

External Referees

Research Sessions

Panel Sessions

Tutorial Sessions

Industrial Sessions





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



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


  • Shahram Ghandeharizadeh, Univ. of Southern California
  • Paul Larson, Microsoft Corporation
  • Vassilis Tsotras, Univ. of California, Riverside

CORPORATE SPONSORS CHAIR: Daniel Barbara, George Mason University

DEMOSTRATIONS CHAIR: Ken Salem, Univ. of Waterloo


  • Bobbie Cochrane, IBM Almaden Research Center
  • Amr El Abbadi, Univ. of California, Santa Barbara
  • Nick Koudas, AT & T Labs - Research
  • Patrick Martin, Queens University
  • Renee J. Miller, University of Toronto
  • Bongki Moon, University of Arizona
  • Anisoara Nica, Sybase Canada
  • S. Seshadri, Bell Labs

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


  • Divyakant Agrawal, Univ. of California, Santa Barbara
  • Surajit Chaudhuri, Microsoft Research
  • Misha Rabinovich, AT & T Labs - Research
  • Eric Simon, INRIA


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


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


Swarup Acharya

Steve Kelley Manuel


Charu Aggarwal

Hiroyuki Kitagawa

Eran Segal

Yousef J. Al-Houmaily

Yakov Kogan

S. Seshadri


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


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


"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


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


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


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

Last update: June 26, 2000
Previous Issue: March 1999 Next Issue: September 1999
Send comments or suggestions to Alexandros Labrinidis.

© 2000 Association for Computing Machinery