vldb_1998_elementary.txt

利用lwp：：get写的

 Cambridge University Press 1992</name><name>Nearest Neighbor Queries.</name><name>Efficient User-Adaptable Similarity Search in Large Multimedia Databases.</name><name>Optimal Multi-Step k-Nearest Neighbor Search.</name><name>The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.</name></citation><abstract>Similarity search and content-based retrieval are becoming more and more important for an increasing number of applications including multimedia, medical imaging, 3D molecular and CAD database systems.
As a general similarity model that is particularly adaptable to user preferences and, therefore, fits the subjective character of similarity, quadratic form distance functions have been successfully employed, e.g. for color histograms as well as for 2D and 3D shape histograms.
Although efficient algorithms for processing adaptable similarity queries using multidimensional index structures are available, the quadratic nature of the distance function strongly affects the CPU time which in turn represents a high percentage of the overall runtime.
The basic idea of our approach is to reduce the number of exact distance computations by adapting conservative approximation techniques to similarity range query processing and, in addition, to extend the concepts to k-nearest neighbor search.
As part of a detailed analysis, we show that our methods guarantee no false drops.
Experiments on synthetic data as well as on a large image database containing 112,000 color images demonstrate a significant performance gain, and the CPU time is improved by a factor of up to 6.</abstract></paper><paper><title>MindReader: Querying Databases Through Multiple Examples.</title><author><AuthorName>Yoshiharu Ishikawa</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Ravishankar Subramanya</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Christos Faloutsos</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>The X-tree : An Index Structure for High-Dimensional Data.</name><name>The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.</name><name>Processing Top N and Bottom N Queries.</name><name>Informedia Digital Video Library.</name><name>Efficient and Effective Querying by Image Content.</name><name>Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension.</name><name>FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets.</name><name>Query by Visual Example - Content based Image Retrieval.</name><name>The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries.</name><name>VAGUE: A User Interface to Relational Databases that Permits Vague Queries.</name><name>Efficient User-Adaptable Similarity Search in Large Multimedia Databases.</name><name>The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces.</name></citation><abstract>Users often can not easily express their queries. For example, in a multimedia/image by content setting, the user might want photographs with sunsets; in current systems, like QBIC, the user has to give a sample query, andto specify the relative importance of color, shape and texture. Even worse, the user might want correlations between attributes, like, for example, in a traditional, medical record database, a medical researcher might wantto find "mildly overweight patients", where the implied query would be "weight/height ~ 4 lb/inch".
Our goal is to provide a user-friendly, but theoretically solid method, tohandle such queries. We allow the user to give several examples, and, optionally, their 'goodness' scores, and we propose a novel method to "guess" which attributes are important, which correlations are important, and withwhat weight.
Our contributions are twofold: (a) we formalize the problem as a minimization problem and show how to solve for the optimal solution, completely avoiding the ad-hoc heuristics of the past.
(b) Moreover, we are the first that can handle 'diagonal' queries (like the 'overweight' query above).
Experiments on synthetic and real datasets show that our method estimates quickly and accurately the 'hidden' distance function in the user's mind.</abstract></paper><paper><title>Design and Analysis of Parametric Query Optimization Algorithms.</title><author><AuthorName>Sumit Ganguly</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Dynamic Query Optimization in Rdb/VMS.</name><name>On the Average Number of Maxima in a Set of Vectors and Applications.</name><name>Optimization of Dynamic Query Evaluation Plans.</name><name>Dynamic Query Evaluation Plans.</name><name>Parametric Distributed Query Optimization based on Load Conditions.</name><name>Parametric Query Optimization.</name><name>Access Path Selection in a Relational Database Management System.</name></citation><abstract>Query optimizers normally compile queries into one optimal plan by assuming complete knowledge of all cost parameters such as selectivity and resource availability.
The execution of such plans could be sub-optimal when cost parameters are either unknown at compile time or change significantly between compile time and runtime [Loh89, GrW89].
Parametric query optimization [INS+92, CG94, GK94] optimizes a query into a number of candidate plans, each optimal for some region of the parameterspace.
In this paper, we present parametric query optimization algorithms.
Our approach is based on the property that for linear cost functions, eachparametric optimal plan is optimal in a convex polyhedral region of the parameter space.
This property is used to optimize linear and non-linear cost functions.
We also analyze the expected sizes of the parametric optimal set of plans and the number of plans produced by the Cole and Graefe algorithm [CG94].</abstract></paper><paper><title>Inferring Function Semantics to Optimize Queries.</title><author><AuthorName>Mitch Cherniack</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Stanley B. Zdonik</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Semantic Query Optimization for Methods in Object-Oriented Database Systems.</name><name>Algebraic Optimization of Object-Oriented Query Languages.</name><name>The Object Database Standard: ODMG-93.</name><name>Semantic Query Optimization: Additional Constraints and Control Strategies.</name><name>Query Optimization in the Presence of Foreign Functions.</name><name>Changing the Rules: Transformations for Rule-Based Optimizers.</name><name>Rule Languages and Internal Algebras for Rule-Based Optimizers.</name><name>A Rule-Based View of Query Optimization.</name><name>The Cascades Framework for Query Optimization.</name><name>The Volcano Optimizer Generator: Extensibility and Efficient Search.</name><name>Semantic Query Optimization for Object Databases.</name><name>Knowledge-Based Query Processing.</name><name>On Optimizing an SQL-like Nested Query.</name><name>QUIST: A System for Semantic Query Optimization in Relational Databases.</name><name>Query Optimization by Predicate Move-Around.</name><name>Extensible/Rule Based Query Rewrite Optimization in Starburst.</name><name>A Chase Too Far?</name></citation><abstract>The goal of the COKO-KOLA project [10,9] is to express rules of rule-basedoptimizers in a manner permitting verification with a theorem prover.
In [10], we considered query transformations that were too general to be expressed with rewrite rules.
In this paper, we consider the complementary issue of expressing query transformations that are too specific for rewrite rules.
Such transformations require rewrite rules to be supplemented with semantic conditions to guard rule firing.
This work considers the expression of such transformations using conditional rewrite rules, and the expression of inference rules to guide the optimizer in deciding if semantic conditions hold.
This work differs from existing work in semantic query optimization in that semantic transformations in our framework are verifiable with a theorem prover.
Further, our use of inference rules to guide semantic reasoning makes our optimizer extensible in a manner that is complementary to the extensibility benefits of existing rule-based technology.</abstract></paper><paper><title>TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer.</title><author><AuthorName>Clara Nippl</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Bernhard Mitschang</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>On Transforming a Sequential SQL-DBMS into a Parallel One: First Results and Experiences of the MIDAS Project.</name><name>DB2 Parallel Edition.</name><name>Born To Be Parallel: Why Parallel Origins Give Teradata an Enduring Performance Edge.</name><name>Dynamic Load Balancing in Hierarchical Parallel Database Systems.</name><name>The Query Optimizer in Tandem's new ServerWare SQL Product.</name><name>On the Application of Parallel Database Technology for Large Scale Document Management Systems.</name><name>The Gamma Database Machine Project.</na