The proceedings contain 33 papers. The special focus in this conference is on Extending database Technology. The topics include: The object management group standardization of object technology;type derivation using t...
ISBN:
(纸本)9783540578185
The proceedings contain 33 papers. The special focus in this conference is on Extending database Technology. The topics include: The object management group standardization of object technology;type derivation using the projection operation;subsumption between queries to object-oriented databases;matrix relation for statistical database management;deductive database support for data visualization;subsumption-free bottom-up evaluation of logic programs with partially instantiated datastructures;virtual schemas and bases;role-based query processing in multidatabase systems;content routing for distributed information servers;a unified approach to concurrency control and transaction recovery;algorithms for flexible space management in transaction systems supporting fine-granularity locking;indexing alternatives for multiversion locking;a rule-based approach for the design and implementation of information systems;on behavioral schema evolution in object-oriented databases;representing and using performance requirements during the development of information systems;a model-theoretic semantics of the multilevel relational model;correctness of ISA hierarchies in object-oriented database schemas;power efficient filtering of data on air;video information contents and architecture;optimizing storage of objects on mass storage systems with robotic devices;on the estimation of join result sizes;DBJ - a dynamic balancing hash join algorithm in multiprocessor database systems;tabu search optimization of large join queries;the implementation and performance evaluation of the ADMS query optimizer;optimization of nested queries in a complex object model;a multi-threaded architecture for prefetching in object bases and supporting full-text information retrieval with a persistent object store.
This paper examines the performance on the Kendall Square Research KSR1 multicomputer of a highly unstructured algorithm for natural language parsing. It describes a Tree Adjoining Grammar parsing algorithm that exhib...
详细信息
This paper examines the performance on the Kendall Square Research KSR1 multicomputer of a highly unstructured algorithm for natural language parsing. It describes a Tree Adjoining Grammar parsing algorithm that exhibits near linear speedup and very high efficiency for grammars of even moderate size. The work reported demonstrates the utility of shared-address-space parallel architectures for algorithms that require shared datastructures. Finally, the paper presents practical guidelines for the efficient use of the KSR1.< >
Previously (Proc. 11th Symp. on Computer Hardware Description Languages and their Application, April 1993), we proposed a reduction technique based on symmetries to alleviate the state explosion problem in automatic v...
详细信息
Previously (Proc. 11th Symp. on Computer Hardware Description Languages and their Application, April 1993), we proposed a reduction technique based on symmetries to alleviate the state explosion problem in automatic verification of concurrent systems. This paper describes the results of testing the technique on a wide range of algorithms and protocols, including realistic multiprocessor synchronization algorithms and cache coherence protocols. Memory requirements were reduced by amounts ranging from 83% to over 99%, and time requirements were often reduced as well. We also consider the effectiveness of the technique on different types of symmetries, such as symmetries in identical system components and symmetries in data values.< >
Symbolic state space traversal techniques are one of the most notable achievements in the fields of formal verification and of automated synthesis. Transition functions and transition relations are two alternative app...
详细信息
Symbolic state space traversal techniques are one of the most notable achievements in the fields of formal verification and of automated synthesis. Transition functions and transition relations are two alternative approaches. In terms of efficiency, transition functions have proven to be superior, although the transition relation is much more expressive. The paper brings the transition relation back to a new life, profiting from recent advancements in the fields of Boolean function representation, simplification, and image computation represented by BDDs and by the generalized cofactor operator. A theoretical result allows us to considerably simplify both the process of building the transition relation and of traversing the state space. Experimental results show that performances similar to those of the transition function are obtained.< >
The author presents storage structures and algorithms for the efficient manipulation of general-purpose large unstructured objects in a database system. The large object is stored in a sequence of variable-size segmen...
详细信息
ISBN:
(纸本)0818625457
The author presents storage structures and algorithms for the efficient manipulation of general-purpose large unstructured objects in a database system. The large object is stored in a sequence of variable-size segments, each of which consists of a large number of physically contiguous disk blocks. A tree structure indexes byte positions within the object. Disk space management is based on the binary buddy system. The scheme supports operations that replace, insert, delete bytes at arbitrary positions within the object, and append bytes at the end of the object.
A description is given of how the authors limited the space complexity of a layout to circuit extractor by: a combination of the scanline technique with the corner stitching technique; a region-based extraction algori...
详细信息
A description is given of how the authors limited the space complexity of a layout to circuit extractor by: a combination of the scanline technique with the corner stitching technique; a region-based extraction algorithm; a judicious choice of netlist format; and a union-find data structure also supporting deletions of elements. The efficiency of the new algorithms and the resulting extractor is confirmed by experimental data. These results are important, since in practice the size of the largest design that can be handled is often hard-limited by available memory.< >
Shared memory multiprocessor systems need efficient dynamic storage allocators, both for system purposes and to support parallel programs. Memory managers are often based on the buddy system, which provides fast alloc...
详细信息
Shared memory multiprocessor systems need efficient dynamic storage allocators, both for system purposes and to support parallel programs. Memory managers are often based on the buddy system, which provides fast allocation and release. Previous parallel buddy memory managers made no attempt to coordinate the allocation, splitting and release of blocks, and as a result needlessly fragment memory. The authors present fast, and simple parallel buddy memory manager that is also as spaceefficient as a serial buddy memory manager. They test their algorithms using memory allocation/deallocation traces their collected from a parallel sparse matrix algorithm.< >
The author presents storage structures and algorithms for the efficient manipulation of general-purpose large unstructured objects in a database system. The large object is stored in a sequence of variable-size segmen...
详细信息
The author presents storage structures and algorithms for the efficient manipulation of general-purpose large unstructured objects in a database system. The large object is stored in a sequence of variable-size segments, each of which consists of a large number of physically contiguous disk blocks. A tree structure indexes byte positions within the object. Disk space management is based on the binary buddy system. The scheme supports operations that replace, insert, delete bytes at arbitrary positions within the object, and append bytes at the end of the object.< >
A fast range search algorithm for visualizing extrema of d-dimensional volume data in real time as the user interactively moves the query range is presented. The algorithm is based on an efficientdata structure, call...
详细信息
ISBN:
(纸本)9780818628962
A fast range search algorithm for visualizing extrema of d-dimensional volume data in real time as the user interactively moves the query range is presented. The algorithm is based on an efficientdata structure, called index heap, which needs only O(N/log N) space and O(d2/sup d/N) preprocessing time to be set up, where N is the size of the d-dimensional data volume. The algorithm can answer an extremum query in O(4/sup d/) expected time, and its worst-case time complexity is O(2/sup d/ log N) per query. For dimensions two and three, the range search for extrema is effected in average O(1) time per query independently of the size of query range. Unlike previous range query algorithms in the computational geometry literature, the proposed algorithm is very simple and can be easily implemented.< >
Presents a scalable algorithm for short-range molecular dynamics which minimizes interprocessor communications at the expense of a modest computational redundancy. The method combines Verlet neighbor lists with coarse...
详细信息
Presents a scalable algorithm for short-range molecular dynamics which minimizes interprocessor communications at the expense of a modest computational redundancy. The method combines Verlet neighbor lists with coarse-grained cells. Each processing node is associated with a cubic volume of space and the particles it owns are those initially contained in the volume. datastructures for 'own' and 'visitor' particle coordinates are maintained in each node. Visitors are particles owned by one of the 26 neighboring cells but lying within an interaction range of a face. The Verlet neighbor list includes pointers to own-own and own-visitor interactions. To communicate, each of the 26 neighbor cells sends a corresponding block of particle coordinates using message-passing cells. The algorithms has the numerical properties of the standard serial Verlet method and is efficient for hundreds to thousands of particles per node allowing the simulation of large systems with millions of particles. Preliminary results on the new CM-5 supercomputer are described.< >
暂无评论