14356634
A service scheduler in a trustworthy system
The aim of the research is to investigate techniques that support efficient service scheduling algorithms in a service-oriented fault-tolerant real-time distributed system. Techniques we developed include deadline-based real-time scheduling, priority-based scheduling, and redundant resource allocation for fault-tolerance. The system model and scheduling algorithms are designed, and a prototype is implemented to facilitate the investigation and experimentation.
3132727
Query Processing over Incomplete Autonomous Databases
Incompleteness due to missing attribute values (aka "null values") is very common in autonomous web databases, on which user accesses are usually supported through mediators. Traditional query processing techniques that focus on the strict soundness of answer tuples often ignore tuples with critical missing attributes, even if they wind up being relevant to a user query. Ideally we would like the mediator to retrieve such possible answers and gauge their relevance by accessing their likelihood of being pertinent answers to the query. The autonomous nature of web databases poses several challenges in realizing this objective. Such challenges include the restricted access privileges imposed on the data, the limited support for query patterns, and the bounded pool of database and network resources in the web environment. We introduce a novel query rewriting and optimization framework QPIAD that tackles these challenges. Our technique involves reformulating the user query based on mined correlations among the database attributes. The reformulated queries are aimed at retrieving the relevant possible answers in addition to the certain answers. QPIAD is able to gauge the relevance of such queries allowing tradeoffs in reducing the costs of database query processing and answer transmission. To support this framework, we develop methods for mining attribute correlations (in terms of Approximate Functional Dependencies), value distributions (in the form of Naive Bayes Classifiers), and selectivity estimates. We present empirical studies to demonstrate that our approach is able to effectively retrieve relevant possible answers with high precision, high recall, and manageable cost.
37282807
Testing Web Services Using Progressive Group Testing
This paper proposes progressive group testing techniques to test large number of Web services (WS) available on Internet. At the unit testing level, the WS with the same functionality are tested in group using progressively increasing number of test cases. A small number of WS that scored best will be integrated into the real environment for operational testing. At the integration testing level, many composite services will be constructed and tested by group integration testing. The results of group testing at both unit and integration levels are verified by weighted majority voting mechanisms. The weights are based on the reliability history of the WS under test. A case study is designed and implemented, where the dependency among the test cases in WS is analyzed and used to generate progressive layers of test cases.
5453537
Testability of Software in Service-Oriented Architecture
Service-oriented architecture (SOA) is a system architecture in which a collection of loosely coupled services communicate with each other using standard interfaces and message-exchanging protocols. As an emerging technology in software development, the SOA presents a new paradigm, and it affects the entire software development cycle including analysis, specification, design, implementation, verification, validation, maintenance and evaluation. This paper proposes several testability evaluation criteria for SOA software, which serves as a reference for both service providers and application builders to evaluate the test support to SOA software. The proposed evaluation criteria are illustrated in a stock-trading case study
5650965
L-Tree: A Dynamic Labeling Structure for Ordered XML Data
With the ever growing use of XML as a data representation format, we see an increasing need for robust, high performance XML database systems While most of the recent work focuses on efficient XML query processing, XML databases also need to support efficient updates To speed up query processing, various labeling schemes have been proposed However, the vast majority of these schemes have poor update performance In this paper, we introduce a dynamic labeling structure for XML data: L-Tree and its order-preserving labeling scheme with O(log n) amortized update cost and O(log n) bits per label L-Tree has good performance on updates without compromising the performance of query processing We present the update algorithm for L-Tree and analyze its complexity.
2511748
QPIAD: Query Processing over Incomplete Autonomous Databases
Incompleteness due to missing attribute values (aka "null values") is very common in autonomous Web databases, on which user accesses are usually supported through mediators. Traditional query processing techniques that focus on the strict soundness of answer tuples often ignore tuples with critical missing attributes, even if they wind up being relevant to a user query. Ideally we would like the mediator to retrieve such relevant uncertain answers and gauge their relevance by accessing their likelihood of being relevant answers to the query. However, the autonomous nature of the databases poses several challenges, such as the restricted access privileges, limited query patterns, and sensitivity of database and network resource consumption in the Web environment. We introduce a novel query rewriting and optimization framework QPIAD that tackles these challenges to retrieve relevant uncertain answers. Our technique involves reformulating the user query based on approximate functional dependencies (AFDs) among the database attributes and ranking these queries using value distributions learned from naive Bayes classifiers. Empirical studies demonstrate the effectiveness of our approach in retrieving relevant uncertain answers with high precision, high recall and manageable cost.
16787369
Fast block matching algorithm based on the winner-update strategy
Block matching is a widely used method for stereo vision, visual tracking, and video compression. Many fast algorithms for block matching have been proposed in the past, but most of them do not guarantee that the match found is the globally optimal match in a search range. This paper presents a new fast algorithm based on the winner-update strategy which utilizes an ascending lower bound list of the matching error to determine the temporary winner. Two lower bound lists derived by using partial distance and by using Minkowski's inequality are described. The basic idea of the winner-update strategy is to avoid, at each search position, the costly computation of the matching error when there exists a lower bound larger than the global minimum matching error. The proposed algorithm can significantly speed up the computation of the block matching because: 1) computational cost of the lower bound we use is less than that of the matching error itself; 2) an element in the ascending lower bound list will be calculated only when its preceding element has already been smaller than the minimum matching error computed so far; 3) for many search positions, only the first several lower bounds in the list need to be calculated. Our experiments have shown that, when applying to motion vector estimation for several widely-used test videos, 92% to 98% of operations can be saved while still guaranteeing the global optimality. Moreover, the proposed algorithm can be easily modified either to meet the limited time requirement or to provide an ordered list of best candidate matches. Our source codes of the proposed algorithm are available at http://smart.iis.sinica.edu.tw/html/winup.html.
230027
Constrained Global Optimization by Constraint Partitioning and Simulated Annealing
In this paper, we present constraint-partitioned simulated annealing (CPSA), an algorithm that extends our previous constrained simulated annealing (CSA) for constrained optimization. The algorithm is based on the theory of extended saddle points (ESPs). By decomposing the ESP condition into multiple necessary conditions, CPSA partitions a problem by its constraints into subproblems, solves each independently using CSA, and resolves those violated global constraints across the subproblems. Because each subproblem is exponentially simpler and the number of global constraints is very small, the complexity of solving the original problem is significantly reduced. We state without proof the asymptotic convergence of CPSA with probability one to a constrained global minimum in discrete space. Last, we evaluate CPSA on some continuous constrained benchmarks
7632435
Multi-level Semantic Analysis for Sports Video
There has been a huge increase in the utilization of video as one of the most preferred type of media due to its content richness for many significant applications including sports. To sustain an ongoing rapid growth of sports video, there is an emerging demand for a sophisticated content-based indexing system. Users recall video contents in a high-level abstraction while video is generally stored as an arbitrary sequence of audio-visual tracks. To bridge this gap, this paper will demonstrate the use of domain knowledge and characteristics to design the extraction of high-level concepts directly from audio-visual features. In particular, we propose a multi-level semantic analysis framework to optimize the sharing of domain characteristics.
39358979
Multi-agent based dynamic scheduling for a flexible assembly system
This paper proposes a multi-agent based dynamic scheduling approach for a flexible assembly system. We first introduce a flexible control system developed by Intelligent Robotics and Automation Laboratory in National Taiwan University. Based on that control system, the agents can communicate with each other conveniently. A generic agent architecture is proposed to model the pieces of equipment in the flexible assembly system. With a distributed architecture, the agents make their scheduling decisions using their local rule base. The agents acquire the resources following the distributed resource allocation protocol. The scheduling complexity is reduced to meet the real-time response requirement in the applications for flexible automated production. The present work is applied to the experimental robotized flexible assembly system in the above laboratory.
8351589
Using automatic clustering to produce high-level system organizations of source code
We describe a collection of algorithms that we developed and implemented to facilitate the automatic recovery of the modular structure of a software system from its source code. We treat automatic modularization as an optimization problem. Our algorithms make use of traditional hill-climbing and genetic algorithms.