vldb_1996_elementary.txt

利用lwp：：get写的

or insertion.  In this paper we show how semantically superfluous
coalescing can be eliminated.  We then turn to efficiently performing
coalescing.  We provide a variety of iterative and non-iterative
approaches, via SQL and embedded SQL, that require no changes to the
DBMS, demonstrating that coalescing can be formulated in SQL-89.
Detailed performance studies show that all such approaches are quite
expensive.  We propose a spectrum of coalescing algorithms within a
DBMS, based on nested-loop, explicit partitioning, explicit sorting,
temporal sorting, and combined explicit/temporal sorting, as well as
their hybrid variants.  These algorithms are empirically compared,
paying particular attention to attribute skew and timestamp
distributions.  The experiments show that coalescing can be
implemented with reasonable efficiency, and with modest development
cost.</abstract></paper><paper><title>Effective &amp; Efficient Document Ranking without using a Large Lexicon.</title><author><AuthorName>Yasushi Ogawa</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Fast Evaluation of Structured Queries for Information Retrieval.</name><name>Optimization of Inverted Vector Searches.</name><name>Fast and Quasi-Natural Language Search for Gigabits of Chinese Texts.</name><name>Implementing Ranking Strategies Using Text Signatures.</name><name>Information Retrieval: Data Structures &amp; Algorithms.
 Prentice-Hall 1992, ISBN 0-13-463837-9</name><name>A Comparison of Indexing Techniques for Japanese Text Retrieval.</name><name>Subtopic Structuring for Full-Length Document Access.</name><name>Fast Ranking in Limited Space.</name><name>A New Indexing and Text Ranking Method for Japanese Text Databases Using Simple-Word Compounds as Keywords.</name><name>A New Character-based Indexing Organization using Frequency Data for Japanese Documents.</name><name>Some Simple Effective Approximations to the 2-Poisson Model for Probabilistic Weighted Retrieval.</name><name>SPIDER: A Multiuser Information Retrieval System for Semistructured and Dynamic Data.</name><name></name></citation><abstract>Although a word-based method is commonly used in
document retrieval,
it cannot be directly applicable to languages that have no obvious
word separator.
Given a lexicon, it is possible to identify words in documents,
but a large lexicon is troublesome to maintain and
makes retrieval systems large and complicated.
This paper proposes an effective and efficient ranking
that does not use a large lexicon;
words need not be identified during document registration
because a character-based signature file is used for the access structure.
A user request, during document retrieval, is statistically analyzed
to generate an appropriate query, and the query is evaluated
efficiently in a word-based manner using the character-based index.
We also propose two optimizing techniques to accelerate retrieval.</abstract></paper><paper><title>PESTO : An Integrated Query/Browser for Object Databases.</title><author><AuthorName>Michael J. Carey</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Laura M. Haas</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Vivekananda Maganty</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>John H. Williams</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>OdeView: The Graphical Interface to Ode.</name><name>SNAP: A Graphics-based Schema Manager.</name><name>Towards Heterogeneous Multimedia Information Systems: The Garlic Approach.</name><name>Querying Multimedia Data from Multiple Repositories by Content: the Garlic Project.</name><name>Entity-Relationship Database User Interfaces.</name><name>The Object Database Standard: ODMG-93 (Release 1.1).</name><name>Lessons from a "Living In a Database" Graphical Query Interface.</name><name>G-WHIZ, a Visual Interface for the Functional Model with Recursion.</name><name>Extending SQL-92 for OODB Access: Design and Implementation Experience.</name><name>Pasta-3's Graphical Query Language: Direct Manipulation, Cooperative Queries, Full Expressive Power.</name><name>The Design of KIVIEW: An Object-Oriented Browser.</name><name>The QBIC Project: Querying Images by Content, Using Color, Texture, and Shape.</name><name>Tcl and the Tk Toolkit.
 Addison-Wesley 1994, ISBN 0-201-63337-X</name><name>"Fill-in-the-Form" Programming.</name><name>TIMBER: A Sophisticated Relation Browser (Invited Paper).</name><name>Future Directions in DBMS Research - The Laguna Beach Participants.</name><name>DBMS Research at a Crossroads: The Vienna Update.</name><name>FORMANAGER: An Office Forms Management System.</name><name>Query-by-Example: A Data Base Language.</name></citation><abstract>This paper describes the design and implementation of PESTO
(Portable Explorer of STructured Objects), a user interface that
supports browsing and querying of object databases.  PESTO allows
users to navigate the relationships that exist among objects.
In addition, users can formulate complex object queries through
an integrated query paradigm (``query-in-place'') that presents
uerying as a natural extension of browsing.  PESTO is designed
to be portable to any object database system that supports a
high-level query language; in addition, PESTO is extensible,
providing hooks for specialized predicate formation and object
display tools for new data types (e.g., images or text).</abstract></paper><paper><title>Fast Nearest Neighbor Search in Medical Image Databases.</title><author><AuthorName>Flip Korn</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Nikolaos Sidiropoulos</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Christos Faloutsos</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Eliot Siegel</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Zenon Protopapas</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Efficient Similarity Search In Sequence Databases.</name><name>Optimization for Spatial Query Processing.</name><name>A Visual Information Management System for the Interactive Retrieval of Faces.</name><name>The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.</name><name>Multidimensional Binary Search Trees Used for Associative Searching.</name><name>Visual Reconstruction.
 MIT Press 1987, ISBN 0-262-02271-0</name><name>Fractals for Secondary Key Retrieval.</name><name>Efficient and Effective Querying by Image Content.</name><name>Fast Subsequence Matching in Time-Series Databases.</name><name>Query by Image and Video Content: The QBIC System.</name><name>A Branch and Bound Algorithms for Computing k-nearest Neighbors.</name><name>An Effective Way to Represent Quadtrees.</name><name>An Implementation and Performance Analysis of Spatial Data Access Methods.</name><name>R-Trees: A Dynamic Index Structure for Spatial Searching.</name><name>The Grid File: A Data Structure to Support Proximity Queries on Spatial Objects.</name><name>Spatial Search with Polyhedra.</name><name>Linear Clustering of Objects with Multiple Atributes.</name><name>A Retrieval Technique for Similar Shapes.</name><name>Hilbert R-tree: An Improved R-tree using Fractals.</name><name>The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.</name><name>A Note on Minimal Length Polygongal Approximation to a Digitized Contour.</name><name>Spatial Query Processing in an Object-Oriented Database System.</name><name>The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.</name><name>Nearest Neighbor Queries.</name><name>The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.</name><name>Adaptive Multi-Stage Distance Join Processing.</name></citation><abstract>We examine the problem of finding similar tumor shapes.  Starting
from  a natural similarity function (the so-called `max morpho-
logical distance'), we showed how to lower-bound it  and  how  to
search  for  nearest neighbors in large collections of tumor-like
shapes.
Specifically, we used state-of-the-art concepts from  morphology,
namely  the `pattern spectrum' of a shape, to map each shape to a
point in n-dimensional space. Following
[16, 30], we organized the n-d
points in an R-tree.  We showed that the L_\infty  norm in  the
n-d space lower-bounds the actual distance.  This guarantees no
false dismissals for range queries.  In addition, we developed  a
nearest-neighbor  algorithm  that  also guarantees no false
dismissals.
Finally, we implemented the method, and we tested  it  against  a
testbed  of  realistic  tumor shapes, using an established tumor-
growth model  of  Murray  Eden [13].   The  experiments
showed  that  our  method is roughly an order of magnitude faster
than the straighforward sequential scanning.</abstract></paper><paper><title>Query Decomposition and View Maintenance for Query Languages for Unstructured Data.</title><author><AuthorName>Dan Suciu</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>An Internet Difference Engine and its Applications.</name><name>A Query Language and Optimization Techniques for Unstructured Data.</name><name>Programming Constructs for Unstructured Data.</name><name>A Logical Query Language for Hypertext Systems.</name><name>Fundamental Properties of Infinite Trees.</name><name>Incremental Maintenance of Views with Duplicates.</name><name>W3QS: A Query System for the World-Wide Web.</name><name>Answering Queries Using Views.</name><name>Answering Queries Using Limited External Processors.</name><name>Object Exchange Across Heterogeneous Information Sources.</name><name>Querying Semistructured Heterogeneous Information.</name></citation><abstract>Recently, several query languages have been proposed for querying
information sources whose data is not constrained by a schema, or
whose schema is unknown. Examples include: LOREL (for querying data
combined from several heterogeneous sources), W3QS (for querying the
World Wide Web); and UNQL (for querying unstructured data).
The natural data model for such languages is that of a rooted, labeled
graph. Their main novelty is the ability to express queries which
traverse arbitrarily long paths in the graph, typically described by a
regular expression. Such queries however may prove difficult to
evaluate in the case when the data is distributed on several sites,
with many edges going between sites. A typical case is that of a
collection of WWW sites, with links pointing freely from one site to
another (even forming cycles). A naive query shipping strategy may
force the query to migrate back and forth between the various sites,
leading to poor performance (or even non-termination). We present a
technique for query decomposition, under which the query is shipped
exactly once to every site, computed locally, then the local results
are shipped to the client, and assembled here into the final
result. This technique is efficient, in that (a) only data which is
part of the final result is shipped from the data sites to the client
site, and (b) the total work done locally at all sites does not exceed
that needed for computing the (unoptimized) query on a centralized
version of the same database.
We also show that the query decomposition technique can be adapted to
derive a simple view maintenance method, for two forms of updates
which we introduce for the graph data model.</abstract></paper><paper><title>SchemaSQL - A Language for Interoperability in Relational Multi-Database Systems.</title><author><AuthorName>Laks V. S. Lakshmanan</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Fereidoon Sadri</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Iyer N. Subramanian</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>The Pegasus Heterogeneous Multidatabase System.</name><name>Collections of Objects in SQL3.</name><name>An Amateur's Introduction to Recursive Query Processing Strategies.</name><name>Declarative Definition of Object-Oriented Multidatabase Mappings.</name><name>Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total.</name><name>Query Languages for Relati