Volume 27    Number 2    June 1998  
 Current Issue  XML Edition
 Previous Issues  About Sigmod
 Info for Authors  FAQ
 Record Editors  Credits

 Proceedings of ACM SIGMOD International Conference on Management of Data

June 2-4, 1998, Seattle, Washington, USA

Edited by Laura Haas and Ashutosh Tiwary
SIGMOD Record, Volume 27, Issue 2, June 1998

Table of Contents
ForewordConference Organizing CommitteeProgram CommitteeExternal RefereesResearch SessionsPanel SessionsTutorial SessionsIndustrial SessionsDemonstrationsBest Paper Awards: Award1, Award2


The 1998 ACM SIGMOD International Conference on Management of Data was held June 2-4, 1998, in Seattle, Washington. The SIGMOD Conference, sponsored by the Association of Computing Machinery (ACM) and its Special Interest Group on the Management of Data (SIGMOD), is an annual, international forum for the presentation, discussion and dissemination of new results on database technology and application, and for the demonstration of database prototypes. These proceedings contain the technical papers accepted for presentation at the conference, as well as summaries of the panels, tutorials, industrial papers and demonstrations presented.

Once again, acceptance for submitted papers was extremely competitive, with 42 research papers accepted out of 246 submissions. The submissions covered a broad range of topics, from fundamental database algorithms to database applications and utilities. The largest numbers of submissions were in the general area of getting more information out of data, including data mining (39 papers) and warehousing (22 papers). These comprised 25% of the submissions, without counting the 12 related papers on high dimensional indexing and similarity search. The next largest pools of papers were on query processing, including optimization and statistics (38), and various aspects of transaction management (22). Other popular topics this year included integration of heterogeneous databases (17 papers), querying the World-Wide Web (16), and various access methods (14). Interest in object-oriented, spatial, multimedia and semi-structured databases remained high as well. The accepted papers represent each of these areas, and more.

In addition to the submitted papers, the conference included a panoply of keynotes, industrial talks, tutorials, panels, and demonstrations. Microsoft’s Bill Gates gave the opening address, and Prof. David Patterson of UC Berkeley kicked off the second day. Industrial sessions covered web site management, document systems, data access, push technologies, databases in practice and database systems management. Four tutorials, two panels, and twenty software prototype demonstrations rounded out the program.

A lot of work went into forming this program and producing these proceedings. The program committee, with help from the external referees, reviewed the submissions on a tight schedule. We are particularly indebted to Praveen Seshadri and his student, Brent Young, who built us a program committee management application with easy to use web interfaces on top of Praveen’s Predator system, and administered and maintained it throughout the paper selection process. This system greatly eased the entry and tracking of abstracts, reviewer preferences and reviews. Mike Carey provided additional software to help with these tasks, and to create the reports for the PC meeting. Debbie Sandman provided secretarial support for the Program Committee. Umeshwar Dayal, Christos Faloutsos, and H.V. Jagadish took on the difficult task of choosing a best paper from the excellent accepted program.

Jose Blakeley, Alex Buchmann, and Roger King worked extremely hard to put together this year’s rich industrial program, with help from the Industrial Advisory Committee. Lois Delcambre recruited and organized the Demonstrations Committee to handle an unexpected flood of submissions; the committee had to make many difficult choices, and many exciting proposals could not be accepted. Ali Bahrami dealt with exhibitors and much of the demonstrations’ logistics. Markus Tresch did an excellent job of soliciting and selecting tutorials, and Michael Brodie enthusiastically took on the task of arranging an exciting panel program. Prabhu Ram coordinated the Call for Papers and both the advance and final programs, and kept the Web site current and the mailing lists informed. Mike Crandall, Local Arrangements Chair, Lyman Do, Registration Chair, and Christoph Bussler, Treasurer, worked tirelessly to the benefit of both SIGMOD and PODS, ensuring a smoothly operating conference.
Finally, we would like to thank all the authors who submitted papers and proposals. They provided the material that made it possible to assemble such a distinguished technical program.

Laura Haas Pamela Drew Ashutosh Tiwary
Program Chair General Chair Proceedings Editor

Back to Table of Contents


GENERAL CHAIR: Pamela Drew, The Boeing Company
PROGRAM CHAIR: Laura Haas, IBM Almaden
DEMONSTRATIONS CHAIR: Lois Delcambre, Oregon Graduate Institute
EXHIBITS CHAIR: Ali Bahrami, The Boeing Company
 Jose Blakeley, Microsoft,
Alejandro Buchmann, T.H. Darmstadt,
Roger King, University of Colorado
LOCAL ARRANGEMENTS CHAIR: Mike Crandall, The Boeing Company
PANELS CHAIR: Michael Brodie, GTE
PROCEEDINGS CHAIR: Ashutosh Tiwary, The Boeing Company and Univ. of Washington
PUBLICITY CHAIR: Prabhu Ram, The Boeing Company
REGISTRATION CHAIR: Lyman Do, Oregon Graduate Institute
TUTORIALS CHAIR: Markus Tresch, Swiss Federal Institute of Technology (ETH)
TREASURER: Christoph Bussler, The Boeing Company
Henrique Paques, Paul Benninghoff, Dan Revel, Songtao Xia, Oregeon Graduate Institute
 C. Mohan, Berthold Reinwald, IBM Almaden
James Hamilton, Mark Franks, Microsoft
Umeshwar Dayal, HP Labs
 Umeshwar Dayal, HP Labs
Christos Faloutsos, University of Maryland and CMU
H.V. Jagdish, AT&T Research

Back to Table of Contents


Rafael Alonso, Sarnoff Labs Miron Livny, University of Wisconsin
Catriel Beeri, Hebrew University David Lomet, Microsoft Research
Azer Bestavros, Boston University Frank Manola, Object Services and Consulting
Paul Brown, Informix Meral Ozsoyoglu, Case Western Reserve University
Surajit Chaudhuri, Microsoft Research Kotagiri Ramamohanarao, University of Melbourne
Chin-Wan Chung, KAIST Rajeev Rastogi, Bell Labs (Lucent)
Umeshwar Dayal, HP Labs Elke Rundensteiner, Worcester Polytechnic Institute
Klaus Dittrich, University of Zurich Marek Rusinkiewicz, MCC
Asuman Dogac, Middle Eastern Technical University Giuseppe Santucci, University di Roma 1
Amr El Abbadi, University of California Santa Barbara Sunita Sarawagi, IBM
Shel Finkelstein, Sun Microsystems Donovan Schneider, Red Brick
Shahram Ghandeharizadeh, University of Southern California Praveen Seshadri, Cornell University
Paul W. P. J. Grefen, University of Twente S. Seshadri, IIT Bombay
Theo Haerder, University of Kaiserslautern Amit Sheth, University of Georgia
Ralf Hartmut Gueting, Fernuniversitaet Hagen Keishi Tajima, Kobe University
Eric Hanson, University of Florida Anthony Tomasic, INRIA
Joseph Hellerstein, University of California Berkeley Patrick Valduriez, INRIA
Donald Kossmann, University of Passau Dirk van Gucht, University of Indiana
Yannis Ioannidis, University of Athens & University of Wisconsin Jennifer Widom, Stanford University
Alon Levy, University of Washington Yelena Yesha, CESDIS and University of Maryland, Baltimore
Bruce Lindsay, IBM

Back to Table of Contents


Jaber Al-Marri Peter Apers Budak Arpinar
Sena Arpinar Hurkan Balkir Herman Balsters
Roberto Bayardo Andreas Behm Luc Bouganim
Tolga Bozkaya Sergey Brin Malu Castellanos
Tiziana Catarci Sudarshan S. Chawathe Li Chen
Andrzej Cichocki Jens Claussen Kajal Claypool
Sophie Cluet Latha Colby Yingwei Cui
John Dinsmore Ron Dolin R. Domenig
Ilker Durusoy Martin Erwig Susan Even
Francoise Fabret Usama Fayyad Dana Florescu
Burkhard Freitag Hans Fritschi Steven Geffner
Andreas Geppert Esin Gokkoca Roy Goldman
Goetz Graefe Thomas Grotehen Dimitrios Gunopulos
Himanshu Gupta Peter Haas Yanbo Han
Mike Hatzopoulos Sumi Helal Andreas Henrich
Howard Ho Joanne Holliday H.V. Jagadish
Dirk Jonscher Pinar Karagoz Sudhir Kaushik
Alfons Kemper Andreas Koeller Pinar Koksal
Ravikanth V. Kothuri Markus Kradolfer Tomasz Ksiezyk
Wilburt Labio Paul Larson Ju-Hong Lee
Yong-Ju Lee Henrik Loeser Zongwei Luo
Jason McHugh Thomas Meyer Tova Milo
Michael Minock Rajeev Motwani Hubert Naacke
Daniele Nardi Anisoara Nica Udo Nink
Susumu Nishimura Atsushi Ohori Frank Olken
Gultekin Ozsoyoglu Bernd-Uwe Pagel Ho-Hyun Park
Brad Perry Vishy Poosala Sunil Prabhakar
Paul Purdom Dallan Quass Sridhar Ramaswamy
Norbert Ritter Ed Robertson Norbert Rump
Christian S. Jensen Silvio Salza Martin Schoenhoff
Hans Schuster Timos Sellis Kshitij Shah
Kyuseok Shim Eric Simon Marcin Skubizewski
R. Srikant Ioana Stanoi Hans-Peter Steiert
S. Sudarshan Nesime Tatbul Malcolm Taylor
Hakki Toroslu Ozgur Ulusoy Luc Vandeurzen
Vasilis Vassalos A. Vavouras Janet Wiener
Annita Wilschut Limsoon Wong Daniel Wu
Yi-Leh Wu Jim Wyllie Jun Yang
Adnan Yazici Juergen Zimmermann Roger Zimmermann

Back to Table of Contents

Session: Association Rules
Chair: Rajeev Rastogi, Bell Labs (Lucent)

Query Flocks: A Generalization of Association-Rule Mining


Dick Tsur, Jeffrey D. Ullman, Serge Abiteboul, Chris Clifton, Rajeev Motwani,
Svetlozar Nestorov, Arnon Rosenthal …… Abstract, Paper

Exploratory Mining and Pruning Optimizations of Constrained Associations Rules


Raymond T. Ng, Laks V.S. Lakshmanan, Jiawei Han, Alex Pang…… Abstract, Paper

Parallel Mining Algorithms for Generalized Association Rules with Classification Hierarchy


Takahiko Shintani, Masaru Kitsuregawa…… Abstract, Paper
Session: Query Processing 1
Chair: Ralf Hartmut Gueting, Fernuniversitaet Hagen

Reusing Invariants: A New Strategy for Correlated Queries


Jun Rao, Kenneth A. Ross……….Abstract, Paper

Query Unnesting in Object-Oriented Databases


Leonidas Fegaras…….Abstract, Paper

Changing the Rules: Transformations for Rule-Based Optimizers


Mitch Cherniack, Stan Zdonik……….Abstract, Paper
Session: Mining
Chair: Sunita Sarawagi, IBM Almaden

CURE: An Efficient Clustering Algorithm for Large Databases


Sudipto Guha, Rajeev Rastogi, Kyuseok Shim…….Abstract, Paper

Efficiently Mining Long Patterns from Databases


Roberto J. Bayardo Jr…….. Abstract, Paper

Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications


Rakesh Agrawal, Johannes Gehrke, Dimitrios Gunopulos, Prabhakar Raghavan…Abstract, Paper
Session: Query Processing 2
Chair: Praveen Seshadri, Cornell Univ.

Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans


Navin Kabra, David J. DeWitt……Abstract, Paper

Interaction of Query Evaluation and Buffer Management for Information Retrieval


Bjorn T. Jonsson, Michael J. Franklin, Divesh Srivastava……Abstract, Paper

Cost Based Query Scrambling for Initial Delays


Tolga Urhan, Michael J. Franklin, Laurent Amsaleg……Abstract, Paper
Session: Similarity Search
Chair: David Lomet, Microsoft Research

The Pyramid-Technique: Towards Breaking the Curse of Dimensionality


Stefan Berchtold, Christian Bohm, Hans-Peter Kriegel……Abstract, Paper

Optimal Multi-Step k-Nearest Neighbor Search


Thomas Seidl, Hans-Peter Kriegel………Abstract, Paper

Dimensionality Reduction for Similarity Searching in Dynamic Databases


K.V. Ravi Kanth, Divyakant Agrawal, Ambuj Singh……Abstract, Paper
Session: Integrating Heterogeneous Data Sources
Chair: Elke Rundensteiner, Worcester Polytechnic

Your Mediators Need Data Conversion!


Sophie Cluet, Claude Delobel, Jerome Simeon, Katarzyna Smaga……Abstract, Paper

Using Schematically Heterogeneous Structures


Renee J. Miller……Abstract, Paper

Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity


William W. Cohen…….Abstract, Paper
Session: Spatial and Similarity Query Processing
Chair: Chin-Wan Chung, KAIST

The DEDALE System for Complex Spatial Queries


Stephane Grumbach, Philippe Rigaux, Luc Segoufin……Abstract, Paper

Similarity Query Processing Using Disk Arrays


Apostolos N. Papadopoulos, Yannis Manolopoulos……Abstract, Paper

Incremental Distance Join Algorithms for Spatial Databases


Gisli R. Hjaltason, Hanan Samet………Abstract, Paper
Session: OLAP
Chair: Eric Hanson, Univ. of Florida

An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees


Yannis Kotidis, Nick Roussopoulos…….Abstract, Paper

Caching Multidimensional Queries Using Chunks


Prasad M. Deshpande, Karthikeyan Ramasamy, Amit Shukla, Jeffrey F. Naughton……Abstract, Paper

Simultaneous Optimization and Evaluation of Multiple Dimensional Queries


Yihong Zhao, Prasad M. Deshpande, Jeffrey F. Naughton, Amit Shukla……Abstract, Paper
Session: Semi-Structured Data
Chair: Alon Levy, Univ. of Washington

NoDoSE: A Tool for Semi-Automatically Extracting Structured and Semi-Structured Data from Text Documents


Brad Adelberg……Abstract, Paper

Extracting Schema from Semistructured Data


Svetlozar Nestorov, Serge Abiteboul, Rajeev Motwani………Abstract, Paper

Enhanced Hypertext Categorization Using Hyperlinks


Soumen Chakrabarti, Byron Dom, Piotr Indyk……Abstract, Paper
Session: Techniques for Decision Support
Chair: Surajit Chaudhuri, Microsoft Research

Cost-Based Optimization of Decision Support Queries Using Transient Views


Subbu N. Subramanian, Shivakumar Venkataraman………Abstract, Paper

New Sampling-Based Summary Statistics for Improving Approximate Query Answers


Phillip B. Gibbons, Yossi Matias………Abstract, Paper

Integrating Association Rule Mining with Relational Database Systems: Alternatives and Implications


Sunita Sarawagi, Shiby Thomas, Rakesh Agrawal………Abstract, Paper
Session: Index Design
Chair: Donovan Schneider, Red Brick

Bitmap Index Design and Evaluation


Chee-Yong Chan, Yannis E. Ioannidis………Abstract, Paper

AutoAdmin `What-if’ Index Analysis Utility


Surajit Chaudhuri, Vivek Narasayya………Abstract, Paper
Session: Functions
Chair: Joseph Hellerstein, Univ. of California, Berkeley

On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS


Michael Jaedicke, Bernhard Mitschang………Abstract, Paper

Secure and Portable Database Extensibility


Michael Godfrey, Tobias Mayr, Praveen Seshadri, Thorsten von Eicken……Abstract, Paper
Session: Algebras for New Needs
Chair: Meral Ozsoyoglu, Case Western Reserve Univ.

A Multi-Similarity Algebra


Sibel Adali, Pietro Bonatti, Maria Luisa Sapino, V. S. Subrahmanian………Abstract, Paper

Catching the Boat with Strudel: Experiences with a Web-Site Management System


Mary Fernandez, Daniela Florescu, Jaewoo Kang, Alon Levy, Dan Suciu…..Abstract, Paper
Session: DB Statistics
Chair: Yannis Ioannidis, Univ. of Wisconsin and Univ. of Athens

Approximate Medians and other Quantiles in One Pass and with Limited Memory


Gurmeet Singh Manku, Sridhar Rajagopalan, Bruce G. Lindsay………Abstract, Paper

Random Sampling for Histogram Construction: How much is enough?


Surajit Chaudhuri, Rajeev Motwani, Vivek Narasayya………Abstract, Paper

Wavelet-Based Histograms for Selectivity Estimation


Yossi Matias, Jeffrey Scott Vitter, Min Wang………Abstract, Paper
Session: Database Algorithms
Chair: Theo Haerder, Univ. of Kaiserslautern

Efficient Transparent Application Recovery in Client-Server Information Systems


David Lomet, Gerhard Weikum………Abstract, Paper

Memory Management during Run Generation in External Sorting


Per-Ake Larson, Goetz Graefe………Abstract, Paper

Replication, Consistency, and Practicality: Are These Mutually Exclusive?


Todd Anderson, Yuri Breitbart, Henry F. Korth, Avishai Wool………Abstract, Paper

Back to Table of Contents

Are We Working on the Right Problems?
Chair: Michael Stonebraker, Informix………Abstract, Paper
Next Generation Database Systems Won’t Work Without Semantics!
Chair: John Mylopoulos, Univ. of Toronto……Abstract, Paper

Back to Table of Contents

Electronic Commerce
Nabil R. Adam, Yelena Yesha………Abstract, Paper, Slides
SAP R/3: A Database Application System
Alfons Kemper, Donald Kossmann, Florian Matthes………Abstract, Paper, Slides1, Slides2, Slides3
JAVA and Relational Databases: SQLJ
Gray Clossman, Phil Shaw, Mark Hapner, Johannes Klein, Richard Pledereder, Brian Becker…Abstract, Paper, Slides
High-Dimensional Index Structures, Database Support for Next Decade’s Applications
Stefan Berchtold, Daniel A. Keim……Abstract, Paper, Slides

Back to Table of Contents


Session: The Next Generation of Data Access
Chair: Anil Nori, Oracle

Microsoft Universal Data Access Platform


Jose A. Blakeley, Michael J. Pizzo, Microsoft……..Abstract, Paper

Enterprise Java(TM) Platform Data Access


Seth White, Rick Cattell, Shel Finkelstein, Sun Microsystems………Abstract, Paper

SQL Open Heterogeneous Data Access


Berthold Reinwald, Hamid Pirahesh, IBM Almaden………Abstract, Paper
Session: Database Systems Management
Chair: Alejandro Buchmann, T.H. Darmstadt

Managing Large Systems with DB2 UDB


Chris Eaton, IBM………Abstract, Paper

Database Systems Management and Oracle8


C. Gregory Doherty, Oracle……Abstract, Paper

Ubiquitous, Self-tuning, Scalable Servers


Peter Spiro, Microsoft………Abstract, Paper
Session: Information Dissemination
Chair: Umeshwar Dayal, HP Laboratories

“Data in Your Face”: Push Technology in Perspective


Michael Franklin, Univ. of Maryland and Stan Zdonik, Brown Univ………Abstract, Paper

The PointCast Network


Satish Ramakrishnan, Vibha Dayal, PointCast………Abstract, Paper

Transactional Publish/Subscribe: The Proactive Multicast of Database Changes


Arvola Chan. Tibco Software……….Abstract, Paper
Session: Databases in Practice
Chair: Roger King, Univ. of Colorado, Boulder

A Data Mining Application: Customer Retention at the Port of Singapore Authority (PSA)


KianSing Ng, Huan Liu, Nat’l Univ. of Singapore, HweeBong Kwah, PSA……Abstract, Paper

Oracle Rdb’s Record Caching Model


Richard Anderson, Gopalan Arun, Richard Frank, Oracle………Abstract, Paper

50,000 Users on an Oracle8 Universal Server Database


Tirthankar Lahiri, Ashok Joshi, Amit Jasuja, Sumanta Chatterjee, Oracle………Abstract, Paper
Session: Document Systems
Chair: Roger King, Univ. of Colorado, Boulder

About Quark Digital Media System


Kamar Aulakh, Quark…….Abstract, Paper

FileNet Integrated Document Management: Database Usage and Issues


Daniel S. Whelan, FileNet………Abstract, Paper
Session: Web Applications
Chair: Jose Blakeley, Microsoft

Developing a High Traffic, Read-Only Web Site


John Nauman, Ray Suorsa, Infoseek………Abstract, Paper

Real Business Processing Meets the Web


James Chong, Charles Schwab………Abstract, Paper
Session: Web Site Management and Applications
Chair: James Hamilton, Microsoft

Olympic Records for Data at the 1998 Nagano Games


Edwin R. Lassettre, IBM………Abstract, Paper

Delivering High Availability for Inktomi Search Engines


Eric A. Brewer, Inktomi………Abstract, Paper

Microsoft.com: A High-Scale Data Management and Transaction Processing Solution


Sherri Kennamer, Microsoft………Abstract, Paper

Back to Table of Contents


Free Parallel Data Mining


Bin Li, Dennis Shasha………Abstract, Paper

The ARANEUS Web-Base Management System


Giansalvatore Mecca, Paolo Atzeni, Alessandro Masci, Paolo Merialdo, Giuseppe Sindoni…..Abstract, Paper

CQ: A Personalized Update Monitoring Toolkit


Ling Liu, Calton Pu, Wei Tang, David Buttler, John Biggs, Tong Zhou, Paul Benninghoff,
Wei Han, Fenghua Yu………Abstract, Paper



Chris Olston, Allison Woodruff, Alexander Aiken, Michael Chu, Vuk Ercegovac, Mark Lin,
Mybrid Spalding, Michael Stonebraker………Abstract, Paper

Microsoft Index Tuning Wizard for SQL Server 7.0


Surajit Chaudhuri, Vivek Narasayya………Abstract, Paper

FlowBack: Providing Backward Recovery for Workflow Management Systems


Bartek Kiepuszewski, Ralf Muhlberger, Maria E. Orlowska………Abstract, Paper

Providing Database-like Access to the Web Using Queries Based on Textual Similarity


William Cohen………Abstract, Paper

ARIADNE: A System for Constructing Mediators for Internet Sources


Jose-Luis Ambite, Naveen Ashish, Greg Barish, Craig A. Knoblock, Steven Minton,
Pragnesh J. Modi, Ion Muslea, Andrew Philpot, Sheila Tejada………Abstract, Paper

Capability Based Mediation in TSIMMIS


Chen Li, Ramana Yerneni, Vasilis Vassalos, Hector Garcia-Molina,
Yannis Papakonstantinou, Jeffrey Ullman, Murty Valiveti………Abstract, Paper

CONTROL: Continuous Output and Navigation Technology with Refinement On-Line


Ron Avnur, Joseph M. Hellerstein, Bruce Lo, Chris Olston, Bhaskaran Raman,
Vijayshankar Raman, Tali Roth, Kirk Wylie…………Abstract, Paper

amdb: An Access Method Debugging Tool


Marcel Kornacker, Mehul Shah, Joseph M. Hellerstein………Abstract, Paper

User-oriented smart-cache for the Web: What You Seek is What You Get!


Zoe Lacroix, Arnaud Sahuguet, Raman Chandrasekar………Abstract, Paper

The Multidimensional Database System RasDaMan


Peter Baumann, Andreas Dehmel, Paula Furtado, Roland Ritsch, Norbert Widmann……Abstract, Paper

Xmas: An Extensible Main-Memory Storage System for High-Performance Applications


Jang Ho Park, Yong Sik Kwon, Ki Hong Kim, Sang Ho Lee,
Byoung Dae Park, Sang Kyun Cha………Abstract, Paper

MultiMediaMiner: A System Prototype for MultiMedia Data Mining


Osmar R. Zaiane, Jiawei Han, Ze-Nian Li, Sonny H. Chee, Jenny Y. Chiang………Abstract, Paper

SuperSQL: An Extended SQL for Database Publishing and Presentation


Motomichi Toyama…………Abstract, Paper

The IDEA Web Lab


Stefano Ceri, Piero Fraternali, Stefano Paraboschi…………Abstract, Paper

DTL’s DataSpot: Database Exploration as Easy as Browsing the Web


Shaul Dar, Gadi Entin, Shai Geva, Eran Palmon………Abstract, Paper

A Protein Patent Query System Powered By Kleisli


Jing Chen, Limsoon Wong, Louxin Zhang………Abstract, Paper
If you have any questions or comments about the SIGMOD’98 Electronic Proceedings, please send mail to Ashutosh Tiwary.

Back to Table of Contents

  Previous Issue: March 1998
Next Issue: September 1998