vldb_1998_elementary.txt

利用lwp：：get写的

 Addison-Wesley 1973, ISBN 0-201-03803-X</name><name>The Optimization of Queries in Relational Databases.
Ph.D. thesis,  Case Western Reserve University 1980</name><name>Why Decision Support Fails and How To Fix It.</name><name>Practical Selectivity Estimation through Adaptive Sampling.</name><name>Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries.</name><name>Selectivity Estimation Without the Attribute Value Independence Assumption.</name><name>Improved Histograms for Selectivity Estimation of Range Predicates.</name><name>Accurate Estimation of the Number of Tuples Satisfying a Condition.</name><name>Optimization of Query Evaluation Algorithms.</name></citation><abstract>In a recent paper, we proposed adding a STOP AFTER clause to SQL to permitthe cardinality of a query result to be explicitly limited by query writers and query tools.
We demonstrated the usefulness of having this clause, showed how to extenda traditional cost-based query optimizer to accommodate it, and demonstrated via DB2-based simulations that large performance gains are possible when STOP AFTER queries are explicitly supported by the database engine.
In this paper, we present several new strategies for efficiently processing STOP AFTER queries.
These strategies, based largely on the use of range partitioning techniques, offer significant additional savings for handling STOP AFTER queries that yield sizeable result sets.
We describe classes of queries where such savings would indeed arise and present experimental measurements that show the benefits and tradeoffs associated with the new processing strategies.</abstract></paper><paper><title>Querying Continuous Time Sequences.</title><author><AuthorName>Ling Lin</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Tore Risch</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Efficient Similarity Search In Sequence Databases.</name><name>Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases.</name><name>Querying Shapes of Histories.</name><name>Processing Queries for First Few Answers.</name><name>Semantic Assumptions and Query Evaluation in Temporal Databases.</name><name>Shoring Up Persistent Applications.</name><name>Formal Semantics for Time in Databases.</name><name>A Framework for the Management of Past Experiences with Time-Extended Situations.</name><name>HierarchyScan: A Hierarchical Similarity Search Algorithm for Databases of Long Sequences.</name><name>Indexing Values of Time Sequences.</name><name>Using a Sequential Index in Terrain-Aided Navigation.</name><name>Logical Modeling of Temporal Data.</name><name>Access Path Selection in a Relational Database Management System.</name><name>Sequence Query Processing.</name><name>The Design and Implementation of a Sequence Database System.</name><name>The Case for Enhanced Abstract Data Types.</name><name>Approximate Queries and Representations for Large Data Sequences.</name><name>Temporal Data Management.</name><name>Object-Relational DBMSs: The Next Great Wave.</name><name>The Design of the POSTGRES Storage System.</name><name>Temporal Databases: Theory, Design, and Implementation.
 Benjamin/Cummings 1993, ISBN 0-8053-2413-5</name></citation><abstract>Time sequences appear in various application domains.
Many applications require time sequences to be seen as continuous where implicit values can be derived from explicit values by arbitrary user-defined interpolation functions.
This paper describes the implementation of an extended SELECT operator, o*, that retrieves implicit values from a discrete time sequence under various user-defined interpolation assumptions.
The c* operator is efficiently supported by an indexing technique termed the IP-index.
Possible optimizations of the o* operator are investigated and verified byexperiments on SHORE.
The o* operator is applicable to any 1-D sequence data.</abstract></paper><paper><title>Low-Cost Compensation-Based Query Processing.</title><author><AuthorName>{\O}ystein Gr{\o}vlen</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Svein-Olaf Hvasshovd</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>{\O}ystein Torbj{\o}rnsen</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>On Mixing Queries and Transactions via Multiversion Locking.</name><name>The Oracle Universal Server Buffer.</name><name>The Implementation of an Integrated Concurrency Control and Recovery Scheme.</name><name>Parallel Database Systems: The Future of High Performance Database Systems.</name><name>Transaction Processing: Concepts and Techniques.</name><name>The ClustRa Telecom Database: High Availability, High Throughput, and Real-Time Response.</name><name>Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions.</name><name>On-Line Warehouse View Maintenance.</name><name>An Introduction to Disk Drive Modeling.</name><name>Compensation-Based On-Line Query Processing.</name><name>On-Line Extraction of SCSI Disk Drive Parameters.</name><name>Dynamic Finite Versioning: An Effective Versioning Approach to Concurrent Transaction and Query Processing.</name></citation><abstract>Compensation-based query processing has been proposed in order to avoid lock contention between updating transactions and ad-hoc queries.
This paper presents an algorithm based on undo /no-redo compensation.
A query will read an inconsistent version of the database, but updates made by concurrent transactions are later undone to make the query result transaction-consistent.
By processing the database internal log to obtain information on concurrent updates, queries impose no extra work on updating transactions.
A simulation study shows that response times for query execution is significantly improved compared to the earlier compensation-based algorithms.
Compared to executing queries with no consistency requirements, the algorithm gives only a small increase in query response times, while the effectson transaction response times are negligible.</abstract></paper><paper><title>A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces.</title><author><AuthorName>Roger Weber</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Hans-J{\"o}rg Schek</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Stephen Blott</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>The New Jersey Data Reduction Report.</name><name>The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.</name><name>Data Structures for Range Searching.</name><name>Fast Parallel Similarity Search in Multimedia Databases.</name><name>A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space.</name><name>Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations.</name><name>The X-tree : An Index Structure for High-Dimensional Data.</name><name>Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems.</name><name>Multi-Step Processing of Spatial Joins.</name><name>M-tree: An Efficient Access Method for Similarity Search in Metric Spaces.</name><name>Access Methods for Text.</name><name>Description and Performance Analysis of Signature File Methods for Office Filing.</name><name>Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension.</name><name>Quad Trees: A Data Structure for Retrieval on Composite Keys.</name><name>Query by Image and Video Content: The QBIC System.</name><name>An Algorithm for Finding Best Matches in Logarithmic Expected Time.</name><name>R-Trees: A Dynamic Index Structure for Spatial Searching.</name><name>On the Analysis of Indexing Schemes.</name><name>Ranking in Spatial Databases.</name><name>The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries.</name><name>The TV-Tree: An Index Structure for High-Dimensional Data.</name><name>The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.</name><name>The Grid File: An Adaptable, Symmetric Multikey File Structure.</name><name>The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.</name><name>The Design and Analysis of Spatial Data Structures.
 Addison-Wesley 1990</name><name>The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.</name><name>Refinements to Nearest-Neighbor Searching in k-Dimensional Trees.</name><name>Similarity of Color Images.</name><name>Principles of Database  and Knowledge-Base Systems, Volume I.
 Computer Science Press 1988, ISBN 0-7167-8158-1</name><name>On Optimizing Nearest Neighbor Queries in High-Dimensional Data Spaces.</name></citation><abstract>For similarity search in high-dimensional vector spaces (or 'HDVSs'), researchers have proposed a number of new methods (or adaptations of existing methods) based, in the main, on data-space partitioning.
However, the performance of these methods generally degrades as dimensionality increases.
Although this phenomenon - known as the 'dimensional curse'- is well known, little or no quantitative analysis of the phenomenon is available.
In this paper, we provide a detailed analysis of partitioning and clustering techniques for similarity search in HDVSs.
We show formally that these methods exhibit linear complexity at high dimensionality, and that existing methods are outperformed on average by a simple sequential scan if the number of dimensions exceeds around 10.
Consequently, we come up with an alternative organization based on approximations to make the unavoidable sequential scan as fast as possible. We describe a simple vector approximation scheme, called VA-file, and report on an experimental evaluation of this and of two tree-based index methods (an R*-tree and an X-tree).</abstract></paper><paper><title>Improving Adaptable Similarity Query Processing by Using Approximations.</title><author><AuthorName>Mihael Ankerst</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Bernhard Braunm{\"u}ller</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Hans-Peter Kriegel</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Thomas Seidl</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Efficient Similarity Search In Sequence Databases.</name><name>Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases.</name><name>A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space.</name><name>Fast Parallel Similarity Search in Multimedia Databases.</name><name>The X-tree : An Index Structure for High-Dimensional Data.</name><name>Approximations for a Multi-Step Processing of Spatial Joins.</name><name>S3: Similarity Search in CAD Database Systems.</name><name>Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems.</name><name>The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.</name><name>Efficient and Effective Querying by Image Content.</name><name>Fast Subsequence Matching in Time-Series Databases.</name><name>Multidimensional Access Methods.</name><name>Similar shape retrieval using a structural feature index.</name><name>R-Trees: A Dynamic Index Structure for Spatial Searching.</name><name>Efficient Color Histogram Indexing for Quadratic Form Distance Functions.</name><name>Ranking in Spatial Databases.</name><name>A Retrieval Technique for Similar Shapes.</name><name>Fast Nearest Neighbor Search in Medical Image Databases.</name><name>3D Similarity Search by Shape Approximation.</name><name>Numerical Recipes in C, 2nd Edition.