3246043
Parallel organization and performance of an information system
This paper investigates a directory structure, based on an M-B-T directory, that provides for parallel retrieval of information with low communication overhead. An information system of documents is assumed. It is compatible with current automatic retrieval and query processing techniques. It is also compatible with any organization of the documents. Weights that are assigned to keywords can be included in the directory with the keywords at no additional cost. In addition, it provides for indexing a secondary keyword within a primary keyword with no additional cost. Given a p-processor massively parallel computer, our organization allows a maximum of p retrievals to be performed concurrently and thus achieves an approximate speed up of p in the best case. The new, revised organization improves on previous work. An eecient parallel searching algorithm and its performance is also discussed.
10426404
Load balanced tree embeddings
Abstract When an n -processor architecture T is embedded into an m -processor architecture H with n > m and every processor of H is assigned at least ⌞n/m⌟ and at most [ n / m ] processors of T , the embedding has a balanced processor load. We present efficient embeddings with a balanced load for the case when both architectures are complete binary trees. We show that T can be embedded into H with a dilation of 1 and congestion of at most min{[ n / m ], 2 log n }. We also consider embeddings that achieve a balanced l/i load; i.e. every processor of H simulates at most [( n + 1)/2 m ] leaves and at most [( n − 1)/2 m ] interior processors of T . We present an embedding that achieves a balanced l/i load, a dilation of 2[log log m ] + 1 and a congestion of O(log n ). We show that every embedding strategy achieving a balanced l/i load must have a dilation of at least 3. We also consider the embedding problem when every edge of T has a weight associated with it.
14459246
On optimal embeddings into incomplete hypercubes
The authors show the embeddings of various types of n-node incomplete binary trees into n-node or (n+1)-node composite hypercubes with dilation of at most 2. They also present lower bound proofs showing optimality of the dilation. They characterize the class of incomplete binary trees which are subgraphs of composite hypercubes. They present dilation 1 embedding of a two-dimensional n-node mesh, where one dimension is a power of two, into its optimal n-node composite hypercube. When neither dimension is a power of two, it is shown that a dilation 1 embedding is not possible; thereby characterizing the class of two-dimensional meshes that can be embedded into composite hypercubes with dilation 1. All two-dimensional meshes are shown to be embeddable with dilation 1 if expansion greater than 1 but less than 2 is allowed. The authors also consider two types of incomplete meshes and their embeddings into their optimal composite hypercubes.<<ETX>>
17006088
An Efficient MAP Classifier for Sensornets
The classification phase is computationally intensive and frequently recurs in tracking applications in sensor networks. Most related work uses traditional signal processing classifiers, such as Maximum A Posterior (MAP) classifier. Naive formulations of MAP are not feasible for resource constraint sensornet nodes. In this paper, we study computationally efficient methods for classification. We propose to use one-sided Jacobi iterations for eigen value decomposition of the covariance matrices, the inverse of which are needed in MAP classifier. We show that this technique greatly simplifies the execution of MAP classifier and makes it a feasible and efficient choice for sensornet applications.
41859107
Preconditioned Conjugate Gradient Solver for Large Sparse Systems on MPI
35215015
Coarse Grain Preconditioned Conjugate Gradient Solver for Large Sparse Systems
We explore a coarse grain parallel algorithm for the solution of large sparse linear systems with symmetric positive definite matrix, based on a preconditioned conjugate gradient method.
28715235
Virage video engine
The temporal and multi-modal nature of video increases the dimensionality of content based retrieval problem. This places new demands on the indexing and retrieval tools required. The Virage Video Engine (VVE) with the default set of primitives provide the necessary frame work and basic tools for video content based retrieval. The video engine is a flexible platform independent architecture which provides support for processing multiple synchronized data streams like image sequences, audio and closed captions. The architecture allows for multi-modal indexing and retrieval of video through the use of media specific primitives. This paper presents the use of the VVE framework for content based video retrieval.
9764286
Time to Leave the Trees: From Syntactic to Conceptual Querying of XML
Current XML query languages operate on XML instances only but ignore valuable conceptual level information that is "buried" inside complex XML Schema documents. For example, XPath queries are evaluated against XML documents based on element names (tags) and their syntactic nesting structure, ignoring the element types and other conceptual level information that is declared in separate XML schemas. We propose an extension to XML query languages for conceptual querying of XML, based on an underlying abstract model of XML Schema (MXS). We show that this approach offers the user new and often more adequate high-level query capabilities beyond the traditional purely syntactic approach of querying XML trees.
206873246
Fast error diagnosis for combinational verification
We address the problem of localizing error sites in a combinational circuit that has been shown to be inequivalent to its specification. In the typical case, it is not possible to identify the error location exactly. We propose a novel diagnosis strategy of gradually increasing the level of detail in the analysis algorithm to ultimately derive a small list of potential error sites in a short time. Our techniques combine the use of simulation, BDDs, and SAT in a novel way to achieve the goal. A limitation of many previous approaches has been that they have been constrained to a specific error model. No such assumption is made in our work. We show through experimental results that these techniques are successful in that the final set of error sites derived is small, contains the actual error sites and is derived in a reasonable amount of time.
31393341
Compiling abstract scientific workflows into Web service workflows
The authors present an approach for compiling "scientist-friendly" abstract workflow specifications into real-world executable workflows of Web service invocations, using a set of abstract-as-view definitions from a repository of abstract tasks. There have been a number of proposals and systems for scientific workflow management. However, our approach features unique aspects, in particular: the separation of abstract and concrete executable workflows; and the use of database mediation techniques to automatically translate AWFs into EWFs.
6738229
A comparison of point-based approaches to qualitative temporal reasoning
We address the problem of implementing general, qualitative, point-based temporal reasoning. Given a database of assertions concerning relative occurrences of points in time, we are interested in various operations on this database, including compiling the assertions into a representation that supports efficient reasoning, determining whether a database is consistent, and computing the strongest entailed relation between two points. We begin by specifying a set of operations and their corresponding algorithms, applicable to general point-based temporal domains. We next consider a special-purpose reasoner, based on series-parallel graphs, which performs very well in a temporal domain with a particular restricted structure. We discuss the notion of a metagraph, which encapsulates local structure inside metaedges and uses special purpose algorithms within such local structures, to obtain a fast general point-based reasoner. That is, specifically, we use a very fast, series-parallel graph reasoner to speed up general point-based reasoning. We also analyse the TimeGraph reasoner of Gerevini and Schubert. For purposes of comparison, we have implemented four approaches: a generic point-based reasoner, the generic point-based reasoner with a ranking heuristic, a reasoner based on series-parallel graphs, and a version of Gerevini and Schubert's TimeGraph reasoner. We compare these different approaches, as well as the original TimeGraph-II reasoner of Gerevini and Schubert, on different data sets. We conclude that the series-parallel graph reasoner provides the best overall performance: our results show that it dominated on domains exhibiting structure, and it degraded gracefully when conditions were less than ideal, in that it did worse than the generic approach by only a constant factor in this case.