We present a general and efficient strategy for computing mtustly on unreliable parallel machines. The model of a parallel machine that we use is a CRCW PRAM with dynamic resource fluctuations: processors can fail dur...
详细信息
With the existence of many autonomous databases widely accessible through computer networks, users will require the capability to jointly manipulate data in different databases. A multidatabase system provides such a ...
详细信息
With the existence of many autonomous databases widely accessible through computer networks, users will require the capability to jointly manipulate data in different databases. A multidatabase system provides such a capability through a multidatabase manipulation language. The authors propose a theoretical foundation for such languages by presenting a multirelational algebra and calculus based on the relational algebra and calculus. The proposal is illustrated by various queries on an example multidatabase.< >
In an approach proposed by V.P. Kumar et al. (see Proc. IEEE Int. Conf. on computer-Aided Design, p.226-9, Nov. 1989) for the yield enhancement of programmable gate arrays (PGAs), an initial placement of a circuit is ...
详细信息
In an approach proposed by V.P. Kumar et al. (see Proc. IEEE Int. Conf. on computer-Aided Design, p.226-9, Nov. 1989) for the yield enhancement of programmable gate arrays (PGAs), an initial placement of a circuit is first obtained using a standard technique such as simulated annealing on a defect-free PGA. In the next step this placement is reconfigured so that the circuit is mapped onto the defect-free portion of a defective PGA chip with the same architecture. In the present work, the authors consider the problem of yield enhancement along the same lines as above not only for PGAs but also for wafer-scale-integrated arrays. A heuristic algorithm for reconfiguration based on a graph-theoretic formulation of the problem and a polynomial-time exact algorithm for a special case of the problem are presented. The reconfiguration algorithms are evaluated by comparing the routability and wire length of the reconfigured and initial placements of the circuit.< >
A view in a database is a subset of records selected from several files to satisfy some condition, e.g. the join of two relations. It has been shown that it is more efficient to store pointers to the satisfying record...
详细信息
A view in a database is a subset of records selected from several files to satisfy some condition, e.g. the join of two relations. It has been shown that it is more efficient to store pointers to the satisfying records of the base relations rather than the complete records of the view. We are interested in efficient caching of such pointers (in effect constructing the view) when the database lies in secondary storage and only a limited number of buffers exists in memory. A view caching is optimal if it is done with the minimum number of reads from secondary storage. We prove that optimal view caching is NP -complete.
We analyze the implementation of set operations using binary tries. Our techniques are substantially simpler than previous techniques used for this problem, and allow us to analysis not only the expected performance b...
详细信息
Window operations serve as the basis of a number of queries that can be posed in a spatial database. Examples of these window-based queries include the exist query (i.e., determining whether or not a spatial feature e...
详细信息
ISBN:
(纸本)0897913523
Window operations serve as the basis of a number of queries that can be posed in a spatial database. Examples of these window-based queries include the exist query (i.e., determining whether or not a spatial feature exists inside a window) and the report query, (i.e., reporting the identity of all the features that exist inside a window). Algorithms are described for answering window queries in Ο(n log logT) time for a window of size n x n in a feature space (e.g., an image) of size T x T (e.g., pixel elements). The significance of this result is that even though the window contains n2 pixel elements, the worst-case time complexity of the algorithms is almost linearly proportional (and not quadratic) to the window diameter, and does not depend on other factors. The above complexity bounds are achieved via the introduction of the incomplete pyramid data structure (a variant of the pyramid data structure) as the underlying representation to store spatial features and to answer queries on them.
We address the problem of a consistent fixpoint semantics for general disjunctive programs restricted to stratifiable programs which do not recurse through negative literals. We apply the nonmonotonic fixpoint theory ...
详细信息
Explicit representations of software processes are needed to improve our ability to develop large software products in a predictable manner. Several languages for representing software processes have been proposed. In...
作者：
SAMET, HComputer Science Department
Center for Automation Research Institute for Advanced Computer Studies University of Maryland College Park 20742 MD United States
An overview is presented of the use of hierarchical spatial data structures such as the quadtree. They are based on the principle of recursive decomposition. The focus is on the representation of data used in image da...
详细信息
Existing formalisms for default reasoning capture some aspects of the nonmonotonicity of human commonsense reasoning. However, Perlis has shown that one of these formalisms, circumscription, is subject to certain coun...
详细信息
暂无评论