sigmod_1999_elementary.txt

利用lwp：：get写的

<proceedings><paper><title>Integration of spatial join algorithms for processing multiple inputs</title><author><AuthorName>Nikos Mamoulis</AuthorName><institute><InstituteName>Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong</InstituteName><country></country></institute></author><author><AuthorName>Dimitris Papadias</AuthorName><institute><InstituteName>Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Management of Data</conference><citation><name>Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998</name><name>Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981</name><name>Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States</name><name>Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Parallel Processing of Spatial Joins Using R-trees, Proceedings of the Twelfth International Conference on Data Engineering, p.258-265, February 26-March 01, 1996</name><name>Bureau of the Census. Tiger~Line Precensus Files: 1990 technical documentation, Washington, DC, 1989.</name><name>Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993</name><name>Oliver G&amp;#252;nther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993</name><name>Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts</name><name>Volker Gaede , Oliver G&amp;#252;nther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998</name><name>Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings of the 23rd International Conference on Very Large Data Bases, p.396-405, August 25-29, 1997</name><name>Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, A Cost Model for Estimating the Performance of Spatial Joins Using R-trees, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.30-38, August 11-13, 1997</name><name>Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984</name><name>Kihong Kim , Sang K. Cha, Sibling clustering of tree-based spatial indexes for efficient spatial query processing, Proceedings of the seventh international conference on Information and knowledge management, p.398-405, November 02-07, 1998, Bethesda, Maryland, United States</name><name>Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States</name><name>Nick Koudas , Kenneth C. Sevcik, Size separation spatial join, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.324-335, May 11-15, 1997, Tucson, Arizona, United States</name><name>Ming-Ling Lo , Chinya V. Ravishankar, Spatial joins using seeded trees, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.209-220, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.247-258, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Mamoulis N., Papadias, D. "Synchronous R-tree Traversal". Technical Report, HKUST-CS99-03, 1999.</name><name>Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States</name><name>Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Apostolos N. Papadopoulos , Yannis Manolopoulos, Similarity query processing using disk arrays, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.225-236, June 01-04, 1998, Seattle, Washington, United States</name><name>Dimitris Papadias , Nikos Mamoulis , Vasilis Delis, Algorithms for Querying by Spatial Structure, Proceedings of the 24rd International Conference on Very Large Data Bases, p.546-557, August 24-27, 1998</name><name>Dimitris Papadias , Nikos Mamoulis , Yannis Theodoridis, Processing and optimization of multiway spatial joins using R-trees, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.44-55, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States</name><name>Franco P. Preparata , Michael I. Shamos, Computational geometry:  an introduction, Springer-Verlag New York, Inc., New York, NY, 1985</name><name>Dimitris Papadias , Timos Sellis , Yannis Theodoridis , Max J. Egenhofer, Topological relations in the world of minimum bounding rectangles: a study with R-trees, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.92-103, May 22-25, 1995, San Jose, California, United States</name><name>Jignesh Patel , JieBing Yu , Navin Kabra , Kristin Tufte , Biswadeep Nag , Josef Burger , Nancy Hall , Karthikeyan Ramasamy , Roger Lueder , Curt Ellmann , Jim Kupsch , Shelly Guo , Johan Larson , David De Witt , Jeffrey Naughton, Building a scaleable geo-spatial DBMS: technology, implementation, and evaluation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.336-347, May 11-15, 1997, Tucson, Arizona, United States</name><name>Doron Rotem, Spatial Join Indices, Proceedings of the Seventh International Conference on Data Engineering, p.500-509, April 08-12, 1991</name><name>Nick Roussopoulos , Stephen Kelley , Fr&amp;#233;d&amp;#233;ric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States</name><name>Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States</name><name>Henry F. Korth , Abraham Silberschatz, Database system concepts, McGraw-Hill, Inc., New York, NY, 1986</name><name>Yannis Theodoridis , Emmanuel Stefanakis , Timos K. Sellis, Cost Models for Join Queries in Spatial Databases, Proceedings of the Fourteenth International Conference on Data Engineering, p.476-483, February 23-27, 1998</name><name>Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997</name></citation><abstract>Several techniques that compute the join between two spatial datasets have been proposed during the last decade. Among these methods, some consider existing indices for the joined inputs, while others treat datasets with no index, providing solutions for the case where at least one input comes as an intermediate result of another database operator. In this paper we analyze previous work on spatial joins and propose a novel algorithm, called slot index spatial join (SISJ), that efficiently computes the spatial join between two inputs, only one of which is indexed by an R-tree. Going one step further, we show how SISJ and other spatial join algorithms can be implemented as operators in a database environment that joins more than two spatial datasets. We study the differences between relational and spatial multiway joins, and propose a dynamic programming algorithm that optimizes the execution of complex spatial queries.</abstract></paper><paper><title>Selectivity estimation in spatial databases</title><author><AuthorName>Swarup Acharya</AuthorName><institute><InstituteName>Information Sciences Research Center, Bell Laboratories, Lucent Technologies, 600, Mountain Avenue, Murray Hill, NJ</InstituteName><country></country></institute></author><author><AuthorName>Viswanath Poosala</AuthorName><institute><InstituteName>Information Sciences Research Center, Bell Laboratories, Lucent Technologies, 600, Mountain Avenue, Murray Hill, NJ</InstituteName><country></country></institute></author><author><AuthorName>Sridhar Ramaswamy</AuthorName><institute><InstituteName>Epiphany Inc., 2300 Geng Road, Suite 200, Palo Alto, CA and Information Sciences Research Center, Bell Laboratories, Lucent Technologies, 600, Mountain Avenue, Murray Hill, NJ</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Management of Data</conference><citation><name>Gennady Antoshenkov, Random Sampling from Pseudo-Ranked B+ Trees, Proceedings of the 18th International Conference on Very Large Data Bases, p.375-382, August 23-27, 1992</name><name>Paul M. Aoki, Generalizing "Search" in Generalized Search Trees, University of California at Berkeley, Berkeley, CA, 1997</name><name>Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy, Selectivity estimation in spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.13-24, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States</name><name>ARC/INFO. Understanding GIS--the ARCflNFO method. ARC/INFO, 1993. Rev. 6 for workstations.</name><name>Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995</name><name>Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>Chungmin Melvin Chen , Nick Roussopoulos, Adaptive selectivity estimation using query feedback, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.161-172, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>David J. DeWitt , Navin Kabra , Jun Luo , Jignesh M. Patel , Jie-Bing Yu, Client-Server Paradise, Proceedings of the 20th International Conference on Very Large Data Bases, p.558-569, September 12-15, 1994</name><name>Erol Gelenbe , Dani&amp;#232;le Gardy, The Size of Projections of Relations Satisfying a Functional Dependency, Proceedings of the Eigth International Conference on Very Large Data Bases, p.325-333, September 08-10, 1982</name><name>St&amp;#233;phane Grumbach , Philippe Rigaux , Michel Scholl , Luc Segoufin, DEDALE, A Spatial Constraint Database, Proceedings of the 6th International Workshop on Database Programming Languages, p.38-59, August 18-20, 1997</name><name>Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts</name><name>Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995</name><name>Intergraph Corp. MGE Z O, "hap://www.intergraph.com/iss/products/mge/mge- 7.0.htm", 1997.</name><name>Sanjeev Khanna , S. Muthukrishnan , Steven Skiena, Efficient Array Partitioning, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.616-626, July 07-11, 1997</name><name>Robert Philip Kooi, The optimization of queries in relational databases, 1980</name><name>Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>Maplnfo Corp. The Maplnfo Story, "hap://www.mapinfo.com/mapinfo/mapinfostory.htmr', 1998.</name><name>S. Muthukrishnan , Viswanath Poosala , Torsten Suel, On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications, Proceeding of the 7th International Conference on Database Theory, p.236-256, January 10-12, 1999</name><name>Viswanath Poosala , Yannis E. Ioannidis, Selectivity Estimation Without the Attribute Value Independence Assumption, Proceedings of the 23rd International Conference on Very Large Data Bases, p.486-495, August 25-29, 1997</name><name>Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Viswanath Poosala, Histogram-based estimation techniques in database systems, University of Wisconsin at Madison, Madison, WI, 1997</name><name>Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts</name><name>P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts</name><name>Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990</name><name>H. Street. The Design and Analyses of Spatial Data Structures. Addison Wesley, MA, 1989.</name><name>Michael Stonebraker , Jim Frew , Kenn Gardels , Jeff Meredith, The SEQUOIA 2000 storage benchmark, ACM SIGMOD Record, v.22 n.2, p.2-11, June 1, 1993</name><name>Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987</name><name>Tiger/line files (tm), 1992 technical documentation. Technical report, U. S. Bureau of the Census, 1992.</name><name>Yannis Theodoridis , Timos Sellis, A model for the prediction of R-tree performance, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Michael Ubell, The Montage extensible DataBlade architecture, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.482, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>G.K. Zipf. Human behaviour and the principle of least effort. Addison-Wesley, Reading, MA, 1949.</name></citation><abstract>Selectivity estimation of queries is an important and well-studied problem in relational database systems. In this paper, we examine selectivity estimation in the context of Geographic Information Systems, which manage spatial data such as points, lines, poly-lines and polygons. In particular, we focus on point and range queries over two-dimensional rectangular data. We propose several techniques based on using spatial indices, histograms, binary space partitionings (BSPs), and the novel notion of spatial skew. Our techniques carefully partition the input rectangles into subsets and approximate each partition accurately. We present a detailed experimental study comparing the proposed techniques and the best known sampling and parametric techniques. We evaluate them using synthetic as well as real-life TIGER datasets. Based on our experiments, we identify a BSP based partitioning that we call Min-Skew which consistently provides the most accurate selectivity estimates for spatial queries. The Min-Skew partitioning can be constructed efficiently, occupies very little space, and provides accurate selectivity estimates over a broad range of spatial queries.</abstract></paper><paper><title>Efficient concurrency control in multidimensional access methods</title><author><AuthorName>Kaushik Chakrabarti</AuthorName><institute><InstituteName>Department of Computer Science, University of Illinois at Urbana-Champaign</InstituteName><country></country></institute></author><author><AuthorName>Sharad Mehrotra</AuthorName><institute><InstituteName>Department of Information and Computer Science, University of California at Irvine</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Management of Data</conference><citation><name>Rakesh Agrawal , Michael J. Carey , Miron Livny, Models for studying concurrency control performance: alternatives and implications, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.108-121, May 1985, Austin, Texas, United States</name><name>ANSI. Ansi x3.135-1992, american national standard fi3r information systems - database language- sql. November, 1992.</name><name>Stefan Berchtold , Christian B&amp;#246;hm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States</name><name>Kaushik Chakrabarti , Sharad Mehrotra, Dynamic Granular Locking Approach to Phantom Protection in R-Trees, Proceedings of the Fourteenth International Conference on Data Engineering, p.446-454, February 23-27, 1998</name><name>K. Chakrabarti and S. Mehrotra. Efficient concurrency control in multidimensional access methods. Technical Report TR-MARS- 97-12, Department of Computer Science, University of l,!linoi!s, October 1998.</name><name>K. Chakrabarti and S. Mehrotra. High dimensional feature indexing using hybrid trees. Proc. of the 15th IEEE International Conference on Data Engineering (ICDE), March 1999.</name><name>C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994</name><name>Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992</name><name>Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995</name><name>Marcel Kornacker , C. Mohan , Joseph M. Hellerstein, Concurrency and recovery in generalized search trees, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.62-72, May 11-15, 1997, Tucson, Arizona, United States</name><name>David B. Lomet, Key Range Locking Strategies for Improved Concurrency, Proceedings of the 19th International Conference on Very Large Data Bases, p.655-664, August 24-27, 1993</name><name>Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993</name><name>C. Mohan, ARIES/KVL: a key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes, Proceedings of the sixteenth international conference on Very large databases, p.392-405, September 1990, Brisbane, Australia</name><name>C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992</name><name>Bradford Nichols , Dick Buttlar , Jacqueline Proulx Farrell, Pthreads programming, O'Reilly &amp; Associates, Inc., Sebastopol, CA, 1996</name><name>J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada</name><name>Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987</name><name>Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986</name><name>Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987</name><name>Michael Stonebraker , Jim Frew , Kenn Gardels , Jeff Meredith, The SEQUOIA 2000 storage benchmark, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.2-11, May 25-28, 1993, Washington, D.C., United States</name><name>Michael Stonebraker , Dorothy Moore, Object Relational DBMSs: The Next Great Wave, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1995</name></citation><abstract>The importance of multidimensional index structures to numerous emerging database applications is well established. However, before these index structures can be supported as access methods (AMs) in a &amp;ldquo;commercial-strength&amp;rdquo; database management system (DBMS), efficient techniques to provide transactional access to data via the index structure must be developed. Concurrent accesses to data via index structures introduce the problem of protecting ranges specified in the retrieval from phantom insertions and deletions (the phantom problem). This paper presents a dynamic granular locking approach to phantom protection in Generalized Search Trees(GiSTs), an index structure supporting an extensible set of queries and data types. The granular locking technique offers a high degree of concurrency and has a low lock overhead. Our experiments show that the granular locking technique (1) scales well under various system loads and (2) similar to the B-tree case, provides a significantly more efficient implementation compared to predicate locking for multidimensional AMs as well. Since a wide variety of multidimensional index structures can be implemented using GiST, the developed algorithms provide a general solution to concurrency control in multidimensional AMs. To the best of our knowledge, this paper provides the first such solution based on granular locking.</abstract></paper><paper><title>Snakes and sandwiches: optimal clustering strategies for a data warehouse</title><author><AuthorName>H. V. Jagadish</AuthorName><institute><InstituteName>U of Illinois, Urbana-Champaign</InstituteName><country></country></institute></author><author><AuthorName>Laks V. S. Lakshmanan</AuthorName><institute><InstituteName>IIT, Bombay</InstituteName><country></country></institute></author><author><AuthorName>Divesh Srivastava</AuthorName><institute><InstituteName>AT&amp;T Labs-Research</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Management of Data</conference><citation><name>Elena Baralis , Stefano Paraboschi , Ernest Teniente, Materialized Views Selection in a Multidimensional Database, Proceedings of the 23rd International Conference on Very Large Data Bases, p.156-165, August 25-29, 1997</name><name>Prasad M. Deshpande , Karthikeyan Ramasamy , Amit Shukla , Jeffrey F. Naughton, Caching multidimensional queries using chunks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.259-270, June 01-04, 1998, Seattle, Washington, United States</name><name>Christos Faloutsos, Multiattribute hashing using Gray codes, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.227-238, May 28-30, 1986, Washington, D.C., United States</name><name>C. Faloutsos. Gray codes for partial match and range queries. IEEE Transactions on Software Engineering, 1987.</name><name>C. Faloutsos and Y. Rong. Spatial access methods using fractals: Algorithms and performance evaluation. Technical Report Tech. Report UMIACS- TR-89-31, University of Maryland, 1990.</name><name>C. Faloutsos , S. Roseman, Fractals for secondary key retrieval, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.247-252, March 1989, Philadelphia, Pennsylvania, United States</name><name>Christos Faloutsos , H. v. Jagadish , Yannis Manolopoulos, Analysis of the n-Dimensional Quadtree Decomposition for Arbitrary Hyperrectangles, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.373-383, May 1997</name><name>Ashish Gupta , Venky Harinarayan , Dallan Quass, Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21th International Conference on Very Large Data Bases, p.358-369, September 11-15, 1995</name><name>Himanshu Gupta , Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Index Selection for OLAP, Proceedings of the Thirteenth International Conference on Data Engineering, p.208-219, April 07-11, 1997</name><name>Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou, On the analysis of indexing schemes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.249-256, May 11-15, 1997, Tucson, Arizona, United States</name><name>H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>H. V. Jagadish, Analysis of the Hilbert curve for representing two-dimensional space, Information Processing Letters, v.62 n.1, p.17-22, April 14, 1997</name><name>H. V. Jagadish, L. V. S. Lakshmanan, and D. Srivastava. Snakes and sandwiches: Optimal clustering strategies for a data warehouse. Technical report, ATL:T Labs Research and Concordia University, 1999. (in preparation).</name><name>Xian Liu , Gunther F. Schrack, On the ordering of multiattribute data in information retrieval systems, 1996</name><name>Patrick O'Neil , Dallan Quass, Improved query performance with variant indexes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.38-49, May 11-15, 1997, Tucson, Arizona, United States</name><name>J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada</name><name>Vasilis Samoladas , Daniel P. Miranker, A lower bound theorem for indexing schemes and its application to multidimensional range queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.44-51, June 01-04, 1998, Seattle, Washington, United States</name><name>Peter Scheuermann , Junho Shim , Radek Vingralek, WATCHMAN: A Data Warehouse Intelligent Cache Manager, Proceedings of the 22th International Conference on Very Large Data Bases, p.51-62, September 03-06, 1996</name><name>Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy, Answering Queries with Aggregation Using Views, Proceedings of the 22th International Conference on Very Large Data Bases, p.318-329, September 03-06, 1996</name><name>Sunita Sarawagi , Michael Stonebraker, Efficient Organization of Large Multidimensional Arrays, Proceedings of the Tenth International Conference on Data Engineering, p.328-336, February 14-18, 1994</name><name>Y. Tanaka. Adaptive segmentation schemes for large relational database machines. In Proc. 3rd International Conference on Database Machines, Munich, FRG, 1983.</name></citation><abstract>Physical layout of data is a crucial determinant of performance in a data warehouse. The optimal clustering of data on disk, for minimizing expected I/O, depends on the query workload. In practice, we often have a reasonable sense of the likelihood of different classes of queries, e.g., 40% of the queries concern calls made from some specific telephone number in some month. In this paper, we address the problem of finding an optimal clustering of records of a fact table on disk, given an expected workload in the form of a probability distribution over query classes.