sigmod_1997_elementary.txt

利用lwp：：get写的

<proceedings><paper><title>Fast parallel similarity search in multimedia databases</title><author><AuthorName>Stefan Berchtold</AuthorName><institute><InstituteName>University of Munich, Germany</InstituteName><country></country></institute></author><author><AuthorName>Christian B&amp;#246;hm</AuthorName><institute><InstituteName>University of Munich, Germany</InstituteName><country></country></institute></author><author><AuthorName>Bernhard Braunm&amp;#252;ller</AuthorName><institute><InstituteName>University of Munich, Germany</InstituteName><country></country></institute></author><author><AuthorName>Daniel A. Keim</AuthorName><institute><InstituteName>University of Munich, Germany</InstituteName><country></country></institute></author><author><AuthorName>Hans-Peter Kriegel</AuthorName><institute><InstituteName>University of Munich, Germany</InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Management of Data</conference><citation><name>Altschul S. F., Gish W., Miller W., Myers E. W., Lipman D.J.: 'A Basic Local Alignment Search Tool', Journal of Molecular Biology, Vol. 215, No. 3, 1990, pp. 403-410.</name><name>Sunil Arya, Nearest neighbor searching and applications, University of Maryland at College Park, College Park, MD, 1996</name><name>Norman L. Biggs, Discrete mathematics, Oxford University Press, Inc., New York, NY, 1986</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>Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996</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>H. C. Du , J. S. Sobolewski, Disk allocation for Cartesian product files on multiple-disk systems, ACM Transactions on Database Systems (TODS), v.7 n.1, p.82-101, March 1982</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>Faloutsos C., Bhagwat P.: 'Declustering Using Fractals', PDIS Journal of Parallel and Distributed Information Systems, 1993, pp. 18-25.</name><name>Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977</name><name>Gisli R. Hjaltason , Hanan Samet, Ranking in Spatial Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.83-95, August 06-09, 1995</name><name>H. V. Jagadish, A retrieval technique for similar shapes, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.208-217, May 29-31, 1991, Denver, Colorado, United States</name><name>Karen Kukich, Technique for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992</name><name>Myoung Ho Kim , Sakti Pramanik, Optimal file distribution for partial match retrieval, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.173-182, June 01-03, 1988, Chicago, Illinois, United States</name><name>King Ip Lin , H. V. Jagadish , Christos Faloutsos, The TV-tree: an index structure for high-dimensional data, The VLDB Journal &amp;mdash; The International Journal on Very Large Data Bases, v.3 n.4, October 1994</name><name>Rajiv Mehrotra , James E. Gary, Feature-Based Retrieval of Similar Shapes, Proceedings of the Ninth International Conference on Data Engineering, p.108-115, April 19-23, 1993</name><name>R. Mehrotra , J. Gary, Feature-index-based similar shape retrieval, Proceedings of the third IFIP WG2.6 working conference on Visual database systems 3 (VDB-3), p.46-65, June 1997</name><name>Franco P. Preparata , Michael I. Shamos, Computational geometry:  an introduction, Springer-Verlag New York, Inc., New York, NY, 1985</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>Ramasubramanian V., Paliwal K. K.: 'Fast k- Dimensional Tree Algorithms for Nearest Neighbor Search with Application to Vector Quantization Encoding', IEEE Transactions on Signal Processing, Vol. 40, No. 3, March 1992, pp. 518-531.</name><name>Brian K. Shoichet , Dale L. Bodian , Irwin D. Kuntz, Molecular docking using shape descriptors, Journal of Computational Chemistry, v.13 n.3, p.380-397, April, 1992</name><name>Shawney H., Hafner J.: "Efficient Color Histogram hzdexing', Proc. Int. Conf. on Image Processing, 1994, pp. 66-70.</name><name>T. A. Welch, BOUNDS ON INFORMATION RETRIEVAL EFFICIENCY IN STATIC FILE STRUCTURES., Massachusetts Institute of Technology, Cambridge, MA, 1971</name><name>Wallace T., Wintz P.: 'An Efficient Three- Dimensional Aircraft Recognition Algorithm Using Normalized Fourier Descriptors ', Computer Graphics and Image Processing, Vol. ! 3, pp. 99-126, 1980</name></citation><abstract>Most similarity search techniques map the data objects into some high-dimensional feature space. The similarity search then corresponds to a nearest-neighbor search in the feature space which is computationally very intensive. In this paper, we present a new parallel method for fast nearest-neighbor search in high-dimensional feature spaces. The core problem of designing a parallel nearest-neighbor algorithm is to find an adequate distribution of the data onto the disks. Unfortunately, the known declustering methods to not perform well for high-dimensional nearest-neighbor search. In contrast, our method has been optimized based on the special properties of high-dimensional spaces and therefore provides a near-optimal distribution of the data items among the disks. The basic idea of our data declustering technique is to assign the buckets corresponding to different quadrants of the data space to different disks. We show that our technique - in contrast to other declustering methods - guarantees that all buckets corresponding to neighboring quadrants are assigned to different disks. We evaluate our method using large amounts of real data (up to 40 MBytes) and compare it with the best known data declustering method, the Hilbert curve. Our experiments show that our method provides an almost linear speed-up and a constant scale-up. Additionally, it outperforms the Hilbert approach by a factor of up to 5.</abstract></paper><paper><title>Similarity-based queries for time series data</title><author><AuthorName>Davood Rafiei</AuthorName><institute><InstituteName>Department of Computer Science, University of Toronto</InstituteName><country></country></institute></author><author><AuthorName>Alberto Mendelzon</AuthorName><institute><InstituteName>Department of Computer Science, University of Toronto</InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Management of Data</conference><citation><name>Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993</name><name>Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995</name><name>Rakesh Agrawal , Giuseppe Psaila , Edward L. Wimmers , Mohamed Za&amp;#239;t, Querying Shapes of Histories, Proceedings of the 21th International Conference on Very Large Data Bases, p.502-514, 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>R.D. Edwards and J. Magee. Technical analysis of stock trends. John Magee, Springfield, Massachsetts, 1969.</name><name>C. Faloutsos, H. V. Jagadish, A. O. Mendelzon, and T. Milo. A signature technique for similarity-based queries, technical report 112530-951110-16TM, AT&amp;T, Murray Hill, NJ, November 1995.</name><name>Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>Dina Q. Goldin , Paris C. Kanellakis, On Similarity Queries for Time-Series Data: Constraint Specification and Implementation, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.137-153, September 19-22, 1995</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>H. V. Jagadish, A retrieval technique for similar shapes, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.208-217, May 29-31, 1991, Denver, Colorado, United States</name><name>H. V. Jagadish , Alberto O. Mendelzon , Tova Milo, Similarity-based queries, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.36-45, May 22-25, 1995, San Jose, California, United States</name><name>Alan V. Oppenheim , Ronald W. Schafer, Discrete-time signal processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989</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>William G. Roth. MIMSY: A system for analyzing time series data in the stock market domain. University of Wisconsin, Madison, 1993. Master Thesis.</name><name>Raghu Ramakrishnan , Divesh Srivastava , S. Sudarshan, CORAL - Control, Relations and Logic, Proceedings of the 18th International Conference on Very Large Data Bases, p.238-250, August 23-27, 1992</name><name>David Sankoff and Joseph B. Kruskal. Time Warps, String Edits, and Macromolecules: The Theory and Practice o.f Sequence Comparison. Addison-Wesley Publishing Company, 1983.</name></citation><abstract>We study a set of linear transformations on the Fourier series representation of a sequence that can be used as the basis for similarity queries on time-series data. We show that our set of transformations is rich enough to formulate operations such as moving average and time warping. We present a query processing algorithm that uses the underlying R-tree index of a multidimensional data set to answer similarity queries efficiently. Our experiments show that the performance of this algorithm is competitive to that of processing ordinary (exact match) queries using the index, and much faster than sequential scanning. We relate our transformations to the general framework for similarity queries of Jagadish et al.</abstract></paper><paper><title>Meaningful change detection in structured data</title><author><AuthorName>Sudarshan S. Chawathe</AuthorName><institute><InstituteName>Computer Science Department, Stanford University, Stanford, California</InstituteName><country></country></institute></author><author><AuthorName>Hector Garcia-Molina</AuthorName><institute><InstituteName>Computer Science Department, Stanford University, Stanford, California</InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Management of Data</conference><citation><name>S. Chawathe and H. Garcia-Molina. Meaningful change detection in structured data. Available at URL http://w~ra-db, stanford, edu, 1997. Extended version.</name><name>S. Chawathe, H. Garcia-Molina, J. Hammer, K. Ireland, Y. Papakonstantinou, J. Ullman, and J. Widom. The Tsimmis project: Integration of heterogeneous information sources. In Proceedings of lOOth Anniversary Meeting of the information Processing Society of Japan, pages 7-18, Tokyo, Japan, October 1994.</name><name>Sudarshan S. Chawathe , Anand Rajaraman , Hector Garcia-Molina , Jennifer Widom, Change detection in hierarchically structured information, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.493-504, June 04-06, 1996, Montreal, Quebec, Canada</name><name>M. Haertel, D. Hayes, R. Stallman, L. Tower, P. Eggert., and W. Davison. The GNU diff program. Texinfo system documentation. Available by anonymous FTP from prep. ai .mit. edu.</name><name>E. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.</name><name>Wilburt Labio , Hector Garcia-Molina, Efficient Snapshot Differential Algorithms for Data Warehousing, Proceedings of the 22th International Conference on Very Large Data Bases, p.63-74, September 03-06, 1996</name><name>E. Myers. An O(UO) difference algorithm and its variations. Algorithmica, 1(2):251-266, 1986.</name><name>Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982</name><name>E. Rothberg. The wmatch program for finding a maximum-weight matching for undirected graphs. Live OR collection. Available at URL http ://w~. orsoc, org. uk.</name><name>D. Shasha, J. Wang, K. Zhang, and F. Shih. Exact and approximate algorithms for unordered tree matching. IEEE Transactions on Systems, Man, and Cybernetics, 24(4):668-678, April 1994.</name><name>Dennis Shasha , Kaizhong Zhang, Fast algorithms for the unit cost editing distance between trees, Journal of Algorithms, v.11 n.4, p.581-621, Dec. 1990</name><name>Robert A. Wagner, On the complexity of the Extended String-to-String Correction Problem, Proceedings of seventh annual ACM symposium on Theory of computing, p.218-223, May 05-07, 1975, Albuquerque, New Mexico, United States</name><name>Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974</name><name>S. Wu , U. Manber , G. Myers , W. Miller, An O(NP) sequence comparison algorithm, Information Processing Letters, v.35 n.6, p.317-323, Sep. 1990</name><name>J. Widom and J. Ullman. The C3 project: Changes, consistency, and configurations in heterogeneous distributed information systems. Unpublished manuscript; available at URL http://www-db, stan~ord, edu, 1995.</name><name>K. Zhang , D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, v.18 n.6, p.1245-1262, Dec. 1989</name><name>K. Zhang, J. Wang, and D. Shasha. On the editing distance between undirected acyclic graphs. International Journal of Foundations of Computer Science, 1995.</name></citation><abstract>Detecting changes by comparing data snapshots is an important requirement for difference queries, active databases, and version and configuration management. In this paper we focus on detecting meaningful changes in hierarchically structured data, such as nested-object data. This problem is much more challenging than the corresponding one for relational or flat-file data. In order to describe changes better, we base our work not just on the traditional &amp;ldquo;atomic&amp;rdquo; insert, delete, update operations, but also on operations that move an entire sub-tree of nodes, and that copy an entire sub-tree. These operations allows us to describe changes in a semantically more meaningful way. Since this change detection problem is NP-hard, in this paper we present a heuristic change detection algorithm that yields close to &amp;ldquo;minimal&amp;rdquo; descriptions of the changes, and that has fewer restrictions than previous algorithms. Our algorithm is based on transforming the change detection problem to a problem of computing a minimum-cost edge cover of a bipartite graph. We study the quality of the solution produced by our algorithm, as well as the running time, both analytically and experimentally.</abstract></paper><paper><title>Improved query performance with variant indexes</title><author><AuthorName>Patrick O'Neil</AuthorName><institute><InstituteName>Department of Mathematics and Computer Science, University of Massachusetts at Boston, Boston, MA</InstituteName><country></country></institute></author><author><AuthorName>Dallan Quass</AuthorName><institute><InstituteName>Department of Computer Science, Stanford University, Stanford, CA</InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Management of Data</conference><citation><name>Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979</name><name>Herb Edelstein. Faster Data Warehouses. Information Week, Dec. 4, 1995, pp. 77-88. Give title and author on http://www.techweb.com/search/advsearch.html.</name><name>Clark D. French, &amp;ldquo;One size fits all&amp;rdquo; database architectures do not work for DSS, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.449-450, May 22-25, 1995, San Jose, California, United States</name><name>Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996</name><name>Jim Gray , Franco Putzolu, The 5 minute rule for trading memory for disc accesses and the 10 byte rule for trading memory for CPU time, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.395-398, May 27-29, 1987, San Francisco, California, United States</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>Ralph Kimball. The Data Warehouse Toolkit. John Wiley &amp; Sons, 1996.</name><name>MODEL 204 File Manager's Guide, Version 2, Release 1.0, April 1989, Computer Corporation of America.</name><name>Patrick E. O'Neil, Model 204 Architecture and Performance, Proceedings of the 2nd International Workshop on High Performance Transaction Systems, p.40-59, September 28-30, 1987</name><name>Patrick O'Neil. The Set Query Benchmark. The Benchmark Handbook for Database and Transaction Processing Systems, Jim Gray (Ed.), Morgan Kaufmann, 2nd Ed. 1993, pp. 359-395.</name><name>Patrick O'Neil, Database systems: principles, programming, performance, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994</name><name>Patrick O'Neil , Goetz Graefe, Multi-table joins through bitmapped join indices, ACM SIGMOD Record, v.24 n.3, p.8-11, Sept. 1995</name><name>Patrick O'Neil and Dallan Quass. Improved Query Performance with Variant Indexes. Extended paper, available on h ttp :/www. c s. umb. edu/--po nei I/v ari nde xx. ps</name><name>John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996</name><name>Stanford Technology Group, Inc., An INFORMIX Co.. Designing the Data Warehouse on Relational Databases. lnformix White Paper, 1995, http://www.informix.com.</name><name>TPC Home Page. Descriptions and results of TPC benchmarks, including the TPC-C and TPC-D benchmarks. http://www.tpc.org.</name></citation><abstract>The read-mostly environment of data warehousing makes it possible to use more complex indexes to speed up queries than in situations where concurrent updates are present. The current paper presents a short review of current indexing technology, including row-set representation by Bitmaps, and then introduces two approaches we call Bit-Sliced indexing and Projection indexing. A Projection index materializes all values of a column in RID order, and a Bit-Sliced index essentially takes an orthogonal bit-by-bit view of the same data. While some of these concepts started with the MODEL 204 product, and both Bit-Sliced and Projection indexing are now fully realized in Sybase IQ, this is the first rigorous examination of such indexing capabilities in the literature. We compare algorithms that become feasible with these variant index types against algorithms using more conventional indexes. The analysis demonstrates important performance advantages for variant indexes in some types of SQL aggregation, predicate evaluation, and grouping. The paper concludes by introducing a new method whereby multi-dimensional group-by queries, reminiscent of OLAP/Datacube queries but with more flexibility, can be very efficiently performed.</abstract></paper><paper><title>Highly concurrent cache consistency for indices in client-server database systems</title><author><AuthorName>Markos Zaharioudakis</AuthorName><institute><InstituteName>University of Wisconsin</InstituteName><country></country></institute></author><author><AuthorName>Michael J. Carey</AuthorName><institute><InstituteName>IBM Almaden Research Center</InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Management of Data</conference><citation><name>J. Basu, A. Keller, "Centralized Versus Distributed Index Management in a Page Server OODBMS", Unpublished Manuscript, October 1995.</name><name>R. Bayer, M. Schkolnick, "Concurrency of Operations on B-Trees", A cta Informatica, Vo]. 9, No. 1, 1977.</name><name>Michael J. Carey , Michael J. Franklin , Miron Livny , Eugene J. Shekita, Data caching tradeoffs in client-server DBMS architectures, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.357-366, May 29-31, 1991, Denver, Colorado, United States</name><name>Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>M. Franklin, M. Carey, "Client-Server Caching Revisited", Proc. Int'l Workshop on Distributed Object Mgmt., Edmonton, Canada, Aug. 1992.</name><name>Vibby Gottemukkala , Edward Omiecinski , Umakishore Ramachandran, Relaxed Index Consistency for a Client-Server Database, Proceedings of the Twelfth International Conference on Data Engineering, p.352-361, February 26-March 01, 1996</name><name>John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988</name><name>Charles Lamb , Gordon Landis , Jack Orenstein , Dan Weinreb, The ObjectStore database system, Communications of the ACM, v.34 n.10, p.50-63, Oct. 1991</name><name>Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981</name><name>D. Lomet, "Key Range Locking Strategies for Improved Concurrency", Digital Equipment Corporation, Feb. 1993.</name><name>C. Mohan, F. Levine, UARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging", IBM Research Report RJ 6846, IBM Almaden, 1989.</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 , Inderpal Narang, Recovery and Coherency-Control Protocols for Fast Intersystem Page Transfer and Fine-Granularity Locking in a Shared Disks Transaction Environment, Proceedings of the 17th International Conference on Very Large Data Bases, p.193-207, September 03-06, 1991</name><name>C. Mohan, I. Narang, "Locking and Latching Techniques for Transaction Processing Systems Supporting the Shared Disks Architecture" Unpublished Manuscript, February 1995.</name><name>Yehoshua Sagiv, Concurrent operations on B*-trees with overtaking, Journal of Computer and System Sciences, v.33 n.2, p.275-296, Oct. 1986</name><name>Dennis Shasha , Nathan Goodman, Concurrent search structure algorithms, ACM Transactions on Database Systems (TODS), v.13 n.1, p.53-90, March 1988</name><name>Yongdong Wang , Lawrence A. Rowe, Cache consistency and concurrency control in a client/server DBMS architecture, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.367-376, May 29-31, 1991, Denver, Colorado, United States</name><name>Kevin Wilkinson , Marie-Anne Neitmat, Maintaining consistency of client-cached data, Proceedings of the sixteenth international conference on Very large databases, p.122-134, September 1990, Brisbane, Australia</name><name>Markos Zaharioudakis , Michael J. Carey , Michael J. Franklin, Adaptive, fine-grained sharing in a client-server OODBMS: a callback-based approach, ACM Transactions on Database Systems (TODS), v.22 n.4, p.570-627, Dec. 1997</name></citation><abstract>In this paper, we present four approaches to providing highly concurrent B+-tree indices in the context of a data-shipping, client-server OODBMS architecture. The first performs all index operations at the server, while the other approaches support varying degrees of client caching and usage of index pages. We have implemented the four approaches, as well as the 2PL approach, in the context of the SHORE OODB system at Wisconsin, and we present experimental results from a performance study based on running SHORE on an IBM SP2 multicomputer. Our results emphasize the need for non-2PL approaches and demonstrate the tradeoffs between 2PL, no-caching, and the three caching alternatives.</abstract></paper><paper><title>Concurrency and recovery in generalized search trees</title><author><AuthorName>Marcel Kornacker</AuthorName><institute><InstituteName>U. C. Berkeley</InstituteName><country></country></institute></author><author><AuthorName>C. Mohan</AuthorName><institute><InstituteName>IBM Research Division</InstituteName><country></country></institute></author><author><AuthorName>Joseph M. Hellerstein</AuthorName><institute><InstituteName>U. C. Berkeley</InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Management of Data</conference><citation><name>R. Bayer and M. Schkolnick. Concurrency of Operations on B-Trees. Acta Informatica, 9:1-21, 1977.</name><name>K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976</name><name>Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992</name><name>Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978</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>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>H. V. Jagadish, Spatial Search with Polyhedra, Proceedings of the Sixth International Conference on Data Engineering, p.311-319, February 05-09, 1990</name><name>Theodore Johnson , Dennis Sasha, The performance of current B-tree algorithms, ACM Transactions on Database Systems (TODS), v.18 n.1, p.51-101, March 1993</name><name>Marcel Kornacker , Douglas Banks, High-Concurrency Locking in R-Trees, Proceedings of the 21th International Conference on Very Large Data Bases, p.134-145, September 11-15, 1995</name><name>Won Kim , Kyung-Chang Kim , Alfred Dale, Indexing techniques for object-oriented databases, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989</name><name>H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980</name><name>King Ip Lin , H. V. Jagadish , Christos Faloutsos, The TV-tree: an index structure for high-dimensional data, The VLDB Journal &amp;mdash; The International Journal on Very Large Data Bases, v.3 n.4, October 1994</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>David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990</name><name>David Lomet , Betty Salzberg, Access method concurrency with recovery, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.351-360, June 02-05, 1992, San Diego, California, United States</name><name>Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981</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>C. Mohan , Frank Levine, ARIES/IM: an efficient and high concurrency index management method using write-ahead logging, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.371-380, June 02-05, 1992, San Diego, California, United States</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, Commit-LSN: a novel and simple method for reducing locking and latching in transaction processing systems, Proceedings of the sixteenth international conference on Very large databases, p.406-418, September 1990, Brisbane, Australia</name><name>C. Mohan, Concurrency control and recovery methods for B+-tree indexes: ARIES/KVL and ARIES/IM, Performance of concurrency control mechanisms in centralized database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995</name><name>Yehoshua Sagiv, Concurrent operations on B*-trees with overtaking, Journal of Computer and System Sciences, v.33 n.2, p.275-296, Oct. 1986</name><name>V. Srinivasan , Michael J. Carey, Performance of B-tree concurrency control algorithms, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.416-425, May 29-31, 1991, Denver, Colorado, United States</name><name>Dennis Shasha , Nathan Goodman, Concurrent search structure algorithms, ACM Transactions on Database Systems (TODS), v.13 n.1, p.53-90, March 1988</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></citation><abstract>This paper presents general algorithms for concurrency control in tree-based access methods as well as a recovery protocol and a mechanism for ensuring repeatable read. The algorithms are developed in the context of the Generalized Search Tree (GiST) data structure, an index structure supporting an extensible set of queries and data types. Although developed in a GiST context, the algorithms are generally applicable to many tree-based access methods. The concurrency control protocol is based on an extension of the link technique originally developed for B-trees, and completely avoids holding node locks during I/Os. Repeatable read isolation is achieved with a novel combination of predicate locks and two-phase locking of data records. To our knowledge, this is the first time that isolation issues have been addressed outside the context of B-trees. A discussion of the fundamental structural differences between B-trees and more general tree structures like GiSTs explains why the algorithms developed here deviate from their B-tree counterparts. An implementation of GiSTs emulating B-trees in DB2/Common Server is underway.</abstract></paper><paper><title>Range queries in OLAP data cubes</title><author><AuthorName>Ching-Tien Ho</AuthorName><institute><InstituteName>IBM Almaden Research Center, 650 Harry Road, San Jose, CA</InstituteName><country></country></institute></author><author><AuthorName>Rakesh Agrawal</AuthorName><institute><InstituteName>IBM Almaden Research Center, 650 Harry Road, San Jose, CA</InstituteName><country></country></institute></author><author><AuthorName>Nimrod Megiddo</AuthorName><institute><InstituteName>IBM Almaden Research Center, 650 Harry Road, San Jose, CA</InstituteName><country></country></institute></author><author><AuthorName>Ramakrishnan Srikant</AuthorName><institute><InstituteName>IBM Almaden Research Center, 650 Harry Road, San Jose, CA</InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Management of Data</conference><citation><name>Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996</name><name>Rakesh Agrawal , Ashish Gupta , Sunita Sarawagi, Modeling Multidimensional Databases, Proceedings of the Thirteenth International Conference on Data Engineering, p.232-243, April 07-11, 1997</name><name>Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980</name><name>Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979</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>M. Berger and I. Regoutsos. An algorithm point clustering and grid generation. IEEE Transactions on Systems, Man and Cybernetics, 21(5):1278-86, 1991.</name><name>Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The  arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990</name><name>G.D. Cohen, A.C. Lobstein, and N.j.A. Sloane. b-k~her results on the covering radius of codes. IEJEB Trans. Information Theory, IT-32(5):680- 694, September 1986.</name><name>M. C. Chen , L. P. McNamee, On the Data Model and Access Method of Summary Data Management, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.519-529, December 1989</name><name>E.F. Codd. Providing OLAP (on-line analytical processing) to user-analysts: An IT mandate. Technical report, E. F. Codd and Associates, 1993.</name><name>George Colliat, OLAP, relational, and multidimensional database systems, ACM SIGMOD Record, v.25 n.3, p.64-69, Sept. 1996</name><name>Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979</name><name>B. Chazelle , B. Rosenberg, Computing partial sums in multidimensional arrays, Proceedings of the fifth annual symposium on Computational geometry, p.131-139, June 05-07, 1989, Saarbruchen, West Germany</name><name>Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994</name><name>Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996</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>Ching-Tien Ho , Jehoshua Bruck , Rakesh Agrawal, Partial-sum queries in OLAP data cubes using covering codes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.228-237, May 11-15, 1997, Tucson, Arizona, United States</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>IBM. DB~ SQL Reference ]or Common Servers Version ~, 1995.</name><name>Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988</name><name>T. Johnson and D. Shasha. Hierarchically sprit cube forests for decision support: description and tuned design, 1996. Working Paper.</name><name>D. Lomet, editor. Special Issue on Materialized Views and Data Warehousing. IEEE Data Engineering Bulletin, 18(2), June 1995.</name><name>Kurt Mehlhorn, Data structures and algorithms 3:  multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984</name><name>Zbigniew Michalewicz, Statistical and scientific databases, Ellis Horwood, Upper Saddle River, NJ, 1991</name><name>L. Mitten. Branch and bound methods: General formulation and properties. Operations Research, 18:24-34, 1970.</name><name>The CLAP Council. MD-API the OLAP Applzcation Program Interface Version 0.5 Specification, September 1996.</name><name>E.M. Reingold, J. Nievergelt, and N. Dec. Combinatorial Algorithms. Prentice-Hall, Englewood Cliffs. N J, 1977.</name><name>Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990</name><name>John C. Shafer , Rakesh Agrawal , Manish Mehta, SPRINT: A Scalable Parallel Classifier for Data Mining, Proceedings of the 22th International Conference on Very Large Data Bases, p.544-555, September 03-06, 1996</name><name>P. Schroeter and j. Bigun. Hierarchical image segmentation by multi-dimensional clustering and orientation-adaptive boundary refinement. Pattern Recognition, 25(5):695-709, May 1995.</name><name>Amit Shukla , Prasad Deshpande , Jeffrey F. Naughton , Karthikeyan Ramasamy, Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies, Proceedings of the 22th International Conference on Very Large Data Bases, p.522-531, September 03-06, 1996</name><name>B. Salzberg and A. Reuter. Indexing for aggregation, 1996. Working Paper.</name><name>J. Srivastava , J. S. E. Tan , V. Y. Lum, TBSAM: An Access Method for Efficient Processing of Statistical Queries, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.414-423, December 1989</name><name>P M Vaidya, Space-time tradeoffs for orthogonal range queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.169-174, May 06-08, 1985, Providence, Rhode Island, United States</name><name>Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985</name><name>Andrew Yao. On the complexity of maintaining partial sums. SIAM J. Computing, 14(2):277- 288, May 1985.</name><name>Weipeng P. Yan , Per-&amp;#197;ke Larson, Eager Aggregation and Lazy Aggregation, Proceedings of the 21th International Conference on Very Large Data Bases, p.345-357, September 11-15, 1995</name></citation><abstract>A range query applies an aggregation operation over all selected cells of an OLAP data cube where the selection is specified by providing ranges of values for numeric dimensions. We present fast algorithms for range queries for two types of aggregation operations: SUM and MAX. These two operations cover techniques required for most popular aggregation operations, such as those supported by SQL.
For range-sum queries, the essential idea is to precompute some auxiliary information (prefix sums) that is used to answer ad hoc queries at run-time. By maintaining auxiliary information which is of the same size as the data cube, all range queries for a given cube can be answered in constant time, irrespective of the size of the sub-cube circumscribed by a query. Alternatively, one can keep auxiliary information which is 1/bd of the size of the d-dimensional data cube. Response to a range query may now require access to some cells of the data cube in addition to the access to the auxiliary information, but the overall time complexity is typically reduced significantly. We also discuss how the precomputed information is incrementally updated by batching updates to the data cube. Finally, we present algorithms for choosing the subset of the data cube dimensions for which the auxiliary information is computed and the blocking factor to use for each such subset.