18656965
Integrating GIS and Imagery Through XML-Based Information Mediation
In this paper, we investigate a mediation-based approach to integrating information from geospatial information sources such as GIS's and databases of geo-referenced imagery. This approach is based on the use of XML to represent the information at the sources, by exporting XML Document Type Definitions (DTD's) associated with each source, and employing XML-based query languages to query integrated views of information at the mediator. Our goal is to enable users to issue a single query to the mediator, and provide the capability to return a result that seamlessly combines information from multiple sources. This paper describes issues in designing such a mediated system for geospatial data. Our notion of mediation for geospatial data is the "logical integration" of data achieved by creating correspondences between related spatial information, similar to the way mediation is done in "standard" databases. Thus, this notion of mediation does not depend on the development of spatial algorithms that operate on images or vector data and achieve "physical integration" through techniques such as image conflation. However, the mediator architecture does allow for the integration of physical integration techniques. The paper discusses issues related to wrapping of GIS and other geospatial sources and issues in querying such sources using an XML-based query language.
29770608
Ontology services for curriculum development in NSDL
We describe our effort to develop an ontology service on top of an educational digital library. The ontology is developed by relating library holdings to the educational concepts they refer to. The ontology system supports basic services like ontology-based search and complex services such as comparison of multiple curricula.
2635468
A System for Managing Alternate Models in Model-Based Mediation
In [1,3], we have described the problem of model-based mediation (MBM) as an extension of the global-as-view paradigm of information integration. The need for this extension arises in many application domains where the information sources to be integrated not only differ in their export formats, data models, and query capabilities, but have widely different schema with very little overlap in attributes. In scientific applications, the information sources come from different subdisciplines, and despite their poorly overlapping schema, can be integrated because they capture different aspects of the same scientific objects or phenomena, and can be conceptually integrated due to scientific reasons. In the MBM paradigm, a “mediation engineer” consults with domain experts to explicitly model the “glue knowledge” using a set of facts and rules at the mediator. Integrated views are defined in MBM on top of the exported schemas from the information sources together with the glue knowledge source that ties them together. We have successfully applied the MBM technique to develop the KIND mediator or Neuroscience information sources [1]-[4]. To accomplish this, sources in the MBM framework export their conceptual models (CMs), consisting of the logical schema, domain constraints, and object contexts, i.e., formulas that relate their conceptual schema with the global domain knowledge maintained at the mediator. Thus model-based mediation has a hybrid approach to information integration - on the one hand at the mediator integrated views are defined over source CMs and the Knowledge Map using a global-as-view approach; on the other hand, object-contexts of the source are defined as local-as-view.
28954888
Modeling shape and topology of 3D images of biological specimens
This paper presents an efficient way of representing the geometry and topology of 3D images of biological specimens derived from electron microscopy. A vector quantization algorithm is used in order to select a reduced set of interior points that best approximates the probability density function of the original volumetric data. Object's geometry and topology are obtained from the point set by the use of the alpha shapes theory.
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.
14666453
An Interpolated Volume Data Model
Publisher Summary This chapter explores the basic functionality of the volume data model. It considers examples from biology and volumes of measurement from quantum physics. The data model is similar in the two cases, but the operations that are commonly used are quite different. In the second case, for instance, one is often interested in conditions on the behavior of local differential operators, such as zero-flow surfaces, while in the biological case one has a mix of value conditions and geometric condition. With these two application fields, this chapter highlights the generality and flexibility of the model. The system is based on a commercial database, augmented with specialized functions to manipulate the volume data model. The chapter demonstrates various operations specifying queries both using a graphical user interface and entering them directly in structured query language (SQL) augmented with the volume algebra operations.
14357490
A Distributed Self-Stabilizing Algorithm for Finding a Connected Dominating Set in a Graph
A connected dominating set of a graph G is a set of nodes of G such that every node in G is either in the set or is adjacent to some node in the set, and the graph induced by the elements of the set is connected. Connected dominating sets have major applications in routing in wireless ad-hoc networks. In this paper, we present a distributed self-stabilizing algorithm for finding a connected dominating set of a graph. Starting from an arbitrary initial state, the algorithm finds a connected dominating set in O(N^2) time, where N is the number of nodes. We also show detailed simulation results to indicate that in practice, the algorithm finds small-sized connected dominating sets in a short time.
2367227
Parallel Algorithms For Vehicle Routing Problems
Vehicle routing problems involve the navigation of one or more vehicles through a network of locations. Locations have associated handling times as well as time windows during which they are active. The arcs connecting locations have time costs associated with them. In this paper, we consider two different problems in single vehicle routing. The first is to find least time cost routes between all pairs of nodes in a network for navigating vehicles; we call this the all pairs routing problem. We show that there is an O(log3 n) time parallel algorithm using a polynomial number of processors for this problem on a CREW PRAM. We next consider the problem in which a vehicle services all locations in a network. Here, locations can be passed through at any time but only serviced during their time window. The general problem is -complete under even fairly stringent restrictions but polynomial algorithms have been developed for some special cases. In particular, when the network is a line, there is no time cost in servicing a location, and all time windows are unbounded at either their lower or upper end, O(n2) algorithms have been developed. We show that under the same conditions, we can reduce this problem to the all pairs routing problem and therefore obtain an O(log3 n) time parallel algorithm on a CREW PRAM.
5958805
Selective and authentic third-party distribution of XML documents
Third-party architectures for data publishing over the Internet today are receiving growing attention, due to their scalability properties and to the ability of efficiently managing large number of subjects and great amount of data. In a third-party architecture, there is a distinction between the Owner and the Publisher of information. The Owner is the producer of information, whereas Publishers are responsible for managing (a portion of) the Owner information and for answering subject queries. A relevant issue in this architecture is how the Owner can ensure a secure and selective publishing of its data, even if the data are managed by a third-party, which can prune some of the nodes of the original document on the basis of subject queries and access control policies. An approach can be that of requiring the Publisher to be trusted with regard to the considered security properties. However, the serious drawback of this solution is that large Web-based systems cannot be easily verified to be secure and can be easily penetrated. For these reasons, we propose an alternative approach, based on the use of digital signature techniques, which does not require the Publisher to be trusted. The security properties we consider are authenticity and completeness of a query response, where completeness is intended with regard to the access control policies stated by the information Owner. In particular, we show that, by embedding in the query response one digital signature generated by the Owner and some hash values, a subject is able to locally verify the authenticity of a query response. Moreover, we present an approach that, for a wide range of queries, allows a subject to verify the completeness of query results.
6212306
Constraint checking with partial information
Constraints are a valuable tool for managing information across multiple databases, as well as for general purposes of assuring data integrity. However, efficient implementation of constraint checking is difficult. In this paper we explore techniques for assuring constraint satisfaction without performing a complete evaluation of the constraints. We consider methods that use only constraint definitions, methods that use constraints and updates, and methods that use constraints, updates, and “local” data.
5025109
Embedding Complete Binary Trees into Butterfly Networks
The authors present embeddings of complete binary trees into butterfly networks with or without wrap-around connections. Let m be an even integer and q=m+(log m)-1. The authors show how to embed a 2/sup q+1/-1-node complete binary tree T(q) into a (m+1)2/sup m+1/-node wrap-around butterfly B/sub w/(m+1) with a dilation of 4, and how to embed T(q) into a (m+2)2/sup m+2/-node wrap-around butterfly B/sub w/(m+2) with an optimal dilation of 2. They also present an embedding of a wrap-around butterfly B/sub w/(m) into a (m+1)2/sup m/-node no-wrap-around butterfly B(m) with a dilation of 3. Using this embedding it is shown that T(q) can be embedded into a no-wrap butterfly B(m+1) (resp. B(m+2)) with a dilation of 8 (resp. 5). >