SIGMOD Record - web edition / June 1999

Volume 28 Number 2 June 1999

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

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:

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

DEMONSTRATION EVALUATION COMMITTEE:

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

INDUSTRIAL CO-CHAIRS:

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

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

Last update: June 26, 2000

Previous Issue: March 1999

Next Issue: September 1999

Send comments or suggestions to Alexandros Labrinidis.

Sections

Personal tools

SIGMOD Record - web edition / June 1999

Document Actions