Volume 27    Number 2    June 1998

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 Foreword Conference Organizing Committee Program Committee External Referees Research Sessions Panel Sessions Tutorial Sessions Industrial Sessions Demonstrations Best Paper Awards: Award1, Award2     FOREWORD 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 CONFERENCE ORGANIZING COMMITTEE   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 INDUSTRIAL PROGRAM CO-CHAIRS:  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 DEMONSTRATION COMMITTEE: Henrique Paques, Paul Benninghoff, Dan Revel, Songtao Xia, Oregeon Graduate Institute INDUSTRIAL ADVISORY BOARD:  C. Mohan, Berthold Reinwald, IBM Almaden  James Hamilton, Mark Franks, Microsoft  Umeshwar Dayal, HP Labs BEST PAPER AWARD COMMITTEE:  Umeshwar Dayal, HP Labs  Christos Faloutsos, University of Maryland and CMU  H.V. Jagdish, AT&T Research Back to Table of Contents PROGRAM COMMITTEE 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 EXTERNAL REFEREES 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 RESEARCH SESSIONS 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 PANEL SESSIONS 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 TUTORIAL SESSIONS 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   INDUSTRIAL SESSIONS   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 DEMONSTRATIONS   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 DataSplash 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 Last update: June 26, 2000 Previous Issue: March 1998 Next Issue: September 1998 Send comments or suggestions to Alexandros Labrinidis.