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 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: 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.