2715587
A scalable peer-to-peer architecture for distributed information monitoring applications
We present PeerCQ, a decentralized architecture for Internet scale information monitoring using a network of heterogeneous peer nodes. PeerCQ uses continual queries (CQs) as its primitives to express information-monitoring requests. The PeerCQ development has three unique characteristics. First, we develop a systematic and serverless approach to large scale information monitoring, aiming at providing a fully distributed, highly scalable, and self-configurable architecture for scalable and reliable processing of a large number of CQs over a network of loosely coupled, heterogeneous, and possibly unreliable nodes (peers). Second, we introduce an effective service partitioning scheme at the P2P protocol layer to distribute the processing of CQs over a peer-to-peer information monitoring overlay network while maintaining a good balance between system utilization and load balance in the presence of peer joins, departures, and failures. A unique feature of our service partitioning scheme is its ability to incorporate strategies for handling hot spot monitoring requests and peer heterogeneity into the load balancing scheme in PeerCQ. Third, but not least, we develop a dynamic passive replication scheme to enable reliable processing of long-running information monitoring requests in an environment of inherently unreliable peers, including an analytical model to discuss its fault tolerance properties. We report a set of experiments demonstrating the feasibility and the effectiveness of the PeerCQ approach to large-scale peer-to-peer information monitoring.
13182282
InfoFilter: Supporting quality of service for fresh information delivery
With the explosive growth of the Internet and World Wide Web comes a dramatic increase in the number of users that compete for the shared resources of distributed system environments. Most implementations of application servers and distributed search software do not distinguish among requests to different web pages. This has the implication that the behavior of application servers is quite unpredictable. Applications that require timely delivery of fresh information consequently suffer the most in such competitive environments. This paper presents a model of quality of service (QoS) and the design of a QoS-enabled information delivery system that implements such a QoS model. The goal of this development is two-fold. On one hand, we want to enable users or applications to specify the desired quality of service requirements for their requests so that application-aware QoS adaptation is supported throughout the Web query and search processing. On the other hand, we want to enable an application server to customize how it should respond to external requests by setting priorities among query requests and allocating server resources using adaptive QoS control mechanisms. We introduce the Infopipe approach as the systems support architecture and underlying technology for building a QoS-enabled distributed system for fresh information delivery.
599285
Differential evaluation of continual queries
We define continual queries as a useful tool for monitoring of updated information. Continual queries are standing queries that monitor the source data and notify the users whenever new data matches the query. In addition to periodic refresh, continual queries include Epsilon Transaction concepts to allow users to specify query refresh based on the magnitude of updates. To support efficient processing of continual queries, we propose a differential re-evaluation algorithm (DRA), which exploits the structure and information contained in both the query expressions and the database update operations. The DRA design can be seen as a synthesis of previous research on differential files, incremental view maintenance, and active databases.
33902172
An Object-Centered Approach for Manipulating Hierarchically Complex Objects
We present an object-centered approach for manipulating hierarchically complex objects, which covers an extended object model and an object-centered query algebra. Extensions of the object model are mainly based on a separation of structural and semantic elements in modeling complex objects, including a general distinction between aggregation reference and association reference, an introduction of type inheritance into aggregation hierarchies and a support for combination of aggregation inheritance with subtype inheritance. Based on the extensions, we develop a query algebra as an integral part of the model. Unlike most of existing algebra-based query languages, our object algebra takes complex object collectively as a unit of high level queries and allows complex objects to be accessed at all levels of aggregation hierarchies without having resort to any kind of path expressions. Features of aggregation hierarchies, such as acyclicity and aggregation inheritance, have played important roles in such a development. We have also formally described the output type of each operator in order for dynamic classification of query results in the IsA type/class lattice. Although the design is based on the chosen object-oriented model, other object-oriented databases are possible. We feel that the proposal largely covers the query requirements for complex objects, and meanwhile provides users with an opportunity to remain within the framework of the model of complex objects while querying database. As a consequence, the flexibility and adaptability of the object-oriented model against schema changes are increased.
9143242
Update Monitoring: The CQ Project
In rapidly growing open environments such as the Internet, users experience information starvation in the midst of data overload, due to difficulties similar to finding the needle in a haystack. Update monitoring is a promising area of research where we bring the right information to the user at the right time, instead of forcing the user through manual browsing or repeated submission of queries. As an example of update monitoring research, we outline our work in the Continual Queries (CQ) project, including its basic concepts, software architecture, and current implementation status.
12589406
VISTA: Validating and Refining Clusters Via Visualization
Clustering is an important technique for understanding of large multidimensional datasets. Most of clustering research to date has been focused on developing automatic clustering algorithms and cluster validation methods. The automatic algorithms are known to work well in dealing with clusters of regular shapes, for example, compact spherical shapes, but may incur higher error rates when dealing with arbitrarily shaped clusters. Although some efforts have been devoted to addressing the problem of skewed datasets, the problem of handling clusters with irregular shapes is still in its infancy, especially in terms of dimensionality of the datasets and the precision of the clustering results considered. Not surprisingly, the statistical indices works ineffective in validating clusters of irregular shapes, too. In this paper, we address the problem of clustering and validating arbitrarily shaped clusters with a visual framework (VISTA). The main idea of the VISTA approach is to capitalize on the power of visualization and interactive feedbacks to encourage domain experts to participate in the clustering revision and clustering validation process. The VISTA system has two unique features. First, it implements a linear and reliable visualization model to interactively visualize multi-dimensional datasets in a 2D star-coordinate space. Second, it provides a rich set of user-friendly interactive rendering operations, allowing users to validate and refine the cluster structure based on their visual experience as well as their domain knowledge.
2470562
Stretch-based tetrahedral mesh manipulation
We present a novel least scaling distortion metric to measure the deformation distortion for tetrahedral meshes. The stretch-like metric is a combination of Jacobian matrix norm and tetrahedron volume and has the properties of good shape preservation and rotation invariance. Based on our metric, we propose a uniform non-linear optimization solution to a variety of tetrahedral mesh manipulation applications including shape deformation, interpolation, deformation transfer, and deformation learning. Our approach can produce volume preserving and flip free tetrahedral mesh results, which performs much better than the previous tetrahedral manipulation approaches. We also demonstrate an efficient and practical application using free-form deformation technique. The object is embedded in a rough control tetrahedral mesh and deformed by editing the tetrahedral mesh with various constraints. Each vertex of the object can be obtained by its barycentric coordinates according to its embedding tetrahedron of the control tetrahedral mesh.
17865149
A framework for specification-based class testing
Class testing is the base of object-oriented software testing. It involves three aspects: testing each method, testing the relations among class methods and testing the inheriting relation between class and subclass. Rather than concerning the whole class testing process, most specification-based class testing focuses on the methods of generating test cases from the class specification. As a result, the class testing process and test cases cannot be unified and managed in a consistent and convenient way. This paper introduces a test class framework (TCF) that is used to structure the test cases and test deriving process of the class under testing. This framework clearly denotes the process of deriving test cases and test suites from a class specification. It facilitates the construction and management of test cases. Object-Z notation is used to express the framework and class specification.
17203041
Tight upper bounds for cell loss probabilities in ATM multiplexers and required bandwidth estimation
Estimating the cell loss probability in an ATM multiplexer is a key issue in network management and traffic control such as call admission control and bandwidth allocation. In this paper, we derive a new approximation to estimate the total and individual cell loss probabilities in an ATM multiplexer fed by a superposition of heterogeneous on-off sources with exponentially distributed on and off periods. Based on this approximation, a simple and accurate method is proposed to estimate the aggregate required bandwidth by a given mix of traffic to guarantee a given cell loss probability.
28219085
Reducing Parametric Automata: A Multimedia Protocol Service Case Study
The Capability Exchange Signalling (CES) protocol is a control protocol for multimedia communications developed by the International Telecommunication Union (ITU) [3]. Our goal is to verify this protocol against the set of allowable sequences of service primitives (i.e. user observable events), known as the service language. Thus the first step to verify the CES protocol is to obtain the CES service language. By using automata reduction techniques [2], our approach is to extract the service language from the Occurrence Graph (OG) of the Coloured Petri Net (CPN) model [4] for the protocol’s service definition. The OG of a CPN model is a directed graph comprising all reachable states (nodes) and state changes (edges) of the model.
17663309
Impact of network resource constraints on the performance of wireless sensor relay networks
This work studies the impact of the network resource constraints on the performance of wireless sensor multi-hop relay networks. A differential space-time coding and the cooperative relay scheme for cross layer design is introduced in multi-hop wireless sensor networks. To analyze the network performance of such a system, the relay system from source to destination is simplified as a virtual bit pipe line, and a Markov chain model as well as an M/G/1 queueing system are used. The closed form expression for throughput and delay are derived in the infinite buffer case. A truncated Markov chain model and an M/G/1/K queueing system are used to model the finite buffer situation. Moreover, the system drop probability and the go through delay are studied based on the models.