Improvements to Ellipsoidal Fit Based Collision Detection
Yu-Ren Chien and Jing Sin Liu
In the collision detection literature, use of ellipsoidal fits has been successfully made to accelerate the detection beyond polyhedron based methods. In this paper, we propose some improvements to the state-of-the-art work of this methodology. These improvements are made in the following three respects that are crucial to the overall performance of a collision detector. First, object-modeling robustness is enhanced by adopting a recent reliable algorithm for computing the maximum-volume inscribed ellipsoid. Second, detecting efficiency is furthered by avoiding reference to polyhedral models. Third, detecting accuracy is also improved by a correction of ellipsoidal overlap checking. These improvements have been verified by extensive numerical experiments using randomly generated convex polyhedra.
Privacy Protection in Database Linking -- a Logical Viewpoint
Tsan-Sheng Hsu, Churn-Jung Liau, Da-Wei Wang
In this paper, we present a logical model for the privacy protection problem in the database linking context. Assume there
is a large amount of data records in the data center. Each record has some public attributes, the values of which are known to the public and some confidential attributes, the values of which are to be protected. Users may obtain data from the data center by submitting queries to form database linkage. When a data table is released, the data manager must make sure that the receiver will not know the confidential data of any particular individual by linking the released data and information he had before receiving the data.
To solve the problem, we propose a simple epistemic logic to model the user's knowledge. In the model, the concept of safety is rigorously defined and an effective approach is given to test the safety of the released data. It is shown that some generalization operations can be applied to the original data to make it less precise and the release of the generalized data may prevent the violation of privacy. Two kinds of generalization operations are considered. The level-based one is more restrictive. However, a bottom-up search method can be used to find the maximally informative data satisfying the safety requirement. The set-based one, on the other hand, is more flexible. However, this approach would require a search through the whole space and its computational complexity is much higher, though graph theory is used to help simplify the search procedure. As a result, heuristic methods may be needed to improve the efficiency.
Quantitative Models for Privacy Protection
Tsan-Sheng Hsu, Churn-Jung Liau, Da-Wei Wang, Jeremy K.-P. Chen
We assume a database consists of records of individuals with private or sensitive fields. Queries on the distribution of a
sensitive field within a selected population in the database can be submitted to the data center. The answers to the queries leak private information of individuals though no identification information is provided. Inspired by decision theory, we present two quantitative models for the privacy protection problem in such a database query or linkage environment in this paper. One is for modeling the value of information from the viewpoint of the querier and the other is for the damage and compensation of privacy leakage.
In both models, we define the information state by a class of probability distributions on the set of possible confidential
values. These states can be modified and refined by the user's knowledge acquisition actions. In the first model, the value of
information is defined as the expected gain of the privacy receiver and the privacy is protected by imposing costs on the
answers of the queries for balancing the gain. In the second one, the safety is guaranteed by enforcing that anyone misusing the private information must pay more compensation than the possible gain.
Preserving Confidentiality When Sharing Medical Database the Cellsecu System
Yu-Cheng Chiang, Tsan-Sheng Hsu, Sun Kuo, and Da-Wei Wang
We propose a computer system named Cellsecu that maintains not only the anonymity but also the confidentiality of each cell that contains sensitive information in medical database by automatically removing, generalizing, and expanding information. The system is designed to enhance the data privacy protection for the data warehouse to automatically handle queries. In most of the cases health organizations collect medical data with all explicit identifiers, such as name, address, and phone numbers. Simply removing all the explicit identifiers priori to the release of the data is not enough to preserve the data confidentiality, for the remaining data can be used to re-identify individuals by linking or matching the data to other database or by looking at unique characteristics found in the database.
A formal model based on Modal logic is the theoretical foundation of Cellsecu, a new confidentiality criteria called "non uniqueness" is defined and implemented. We believe modeling this problem formally can clarify the issue as well as clearly identify the boundary of current technology. Base on our preliminary performance evaluation, the confidentiality check module and the confidentiality enhancing module only slightly degrade the system performance.
Enhancing Collision Detection Method Based on Enclosed Ellipsoid by Facial Areas Splitting
Wei-Kun Su , Jing-Sin Liu, I-Fan Chen
This paper is aimed at introducing a faster collision detection algorithm for convex polyhedral in a three-dimensional workspace. The problem of collision detection has been researched in the literature of computer graphics, robotics, computational geometry, computer animation, and physically-based modeling. It has been regarded as a computationally demanding task and is often treated as an advanced feature. In this paper, we present a faster way to solve the collision detection problem by using the enclosed ellipsoid method. Enclosed ellipsoid method gets fewer collision error report than the standard bounding volume method, such as boxes or spheres. We split ellipsoids into facial areas and ignore the areas which are always the heavier computational load but impossible to be collided with. There are some computer simulations showing how the facial split method increases the efficiency of the detection in comparison with the original enclosed ellipsoid method.
TCTL Inevitability Analysis of Dense-time Systems
Farn Wang, Geng-Dian Hwang and Fang Yu
Inevitability properties in branching temporal logics are of the syntax "àf, where f is an arbitrary (timed) CTL formula. In the sense that "good things will happen", they are parallel to the "liveness" properties in linear temporal logics. Such inevitability properties in dense-time logics can be analyzed with greatest fixpoint calculation. We present algorithms to model-check inevitability properties both with and without requirement of non-Zeno computations. We discuss a technique for early decision on greatest fixpoints in the temporal logics, and experiment with the effect of non-Zeno computations on the evaluation of greatest fixpoints. We also discuss the TCTL subclass with only universal path quantifiers which allows for the safe abstraction analysis of inevitability properties. Finally, we report our implementation and experiments to show the plausibility of our ideas.
On Modular Transformation of Structural Content
Tyng-Ruey Chuang and Jan-Li Lin
We show that an XML DTD (Document Type Definition) can be viewed as the fixed point of a parametric content model. We then use natural transformations from the source content model to the target content model to derive DTD-aware and validated XML document transformations. Benefits of such transformations include static type-checking of XML transformational programs, automatic validation of target documents, and modular compositions of XML document transformers.
We prototype these modular XML document transformations in Objective Caml. The prototype depends heavily on the parametric module system of Objective Caml and is highly modular. Using Objective Caml to model XML document transformation also allows one to access high-level language constructs and supporting libraries in Objective Caml, hence enhance one's productivity in XML programming.
PSC: A Priority Selected Cache Algorithm for Streaming Video over Internet
Shin-Hung Chang, Ray-I Chang, Jan-Ming Ho, and Yen-Jen Oyang
Proxy technologies are commonly used at boundaries of ISPs (Internet Service Providers) to reduce the bandwidth required in the backbone WAN. By caching portions of a video content in a video proxy closed to clients, the video playback quality can be dramatically improved and insufficient WAN bandwidth defeated. In the loss-less network environment, the OC (Optimal Cache) algorithm is proposed to use minimal cache storage in the video proxy, and to save maximal bandwidth required in the backbone WAN for QoS-guaranteed video playback. However, data packets may be lost while delivering video contents through the Internet that affects video playback quality. Consider an MPEG video in which an I-frame is referenced by all other frames (B- or P-frames) in the same GOP (Group of Picture). Losing packets from an I-frame makes it difficult to decode all of the following frames from the same GOP.
The major goal of this paper is to select the maximal high-priority frames (I-frames) cached into the video proxy in order to defeat decoding error caused by packet loss and improve error recovery while serving QoS-guaranteed video playback. We propose a PSC algorithm for solving this selected cache problem with linear time complexity. The PSC algorithm uses minimal cache storage in the video proxy as well as saves maximal bandwidth required in the backbone WAN (as does the OC algorithm). Additionally, experiments with several benchmark videos show that the PSC algorithm improves the ratio of I-frame data cached in video proxy by over 15% more than conventional OC algorithm.
View
Code
TR-IIS-03-009
Subject / Author / Abstract
Fast Algorithms for Computing Self-Avoiding Walks and Mesh Intersections over Unstructured Meshes
PeiZong Lee, Chih-Hsueh Yang, and Jeng-Renn Yang
This paper is concerned with designing an efficient algorithm for computing the intersection of two unstructured meshes.The algorithm uses a background quadtree of the first unstructured mesh and a self-avoiding walk (SAW) of the second unstructured mesh. Due to the neighboring relationships of consecutive triangles in the triangle sequence of a SAW, we can keep track of the location of each triangle in the second unstructured mesh by means of the background quadtree. This allows us to design a linear time algorithm for computing the mesh intersection. Experimental studies show that our efficient algorithm for computing the mesh intersection can save a lot of execution time in comparison with that needed by other naive algorithms. We also present two new SAW's. Using our first-in-first-out (FIFO) SAW can save an additional 5% of the execution time in comparison with that needed when using other SAW's. This is because our FIFO SAW employs better data locality, which is especially beneficial for the current hierarchical-memory computer architectures.
A Test for Interval Graph on Noisy Data
Wei-Fu Lu, Ruei-Chuan Chang, and Wen-Lian Hsu
An interval graph is the intersection graph of a collection of intervals. One important application of interval graph is physical mapping in genome research, that is, to reassemble the clones to determine the relative position of fragments of DNA along the genome. The linear time algorithm by Booth and Lueker (1976) for this problem has a serious drawback: the data must be error-free. However, laboratory work is never flawless. We devised a new iterative clustering algorithm based on local structure matching, which can accommodate noisy data and produce a likely interval model realizing the original graph.
FT-SOAP: A Fault-tolerant web service
Deron Liang, Chen-Liang Fang, Chyouhwa Chen
Security is the major concern that refrains people from conducting commerce electronically. The security concerns related to electronic commerce (EC) includes transaction security and system security. We can partially address the transaction security issues by message distribution middleware such as simple object access protocol (SOAP), which is one of the information technology (IT) infrastructures that facilitate EC. It requires a comprehensive set of IT in order to address the system security issues where fault-tolerance technology is one of the core technologies to enhance the system survivability after attack. Based on our preliminary investigation, we conclude that the current SOAP architecture is lack of mechanism to build a highly reliable EC system. We propose a comprehensive fault-tolerance framework based on the current SOAP architecture in order to address the system security issues for EC. We consider this research is the continuing effort of our previous work on fault-tolerant CORBA, thought there are similarities and differences between these two technologies. We propose a standard recommendation that outlines a set of interfaces named fault-tolerant SOAP (FT-SOAP). The FT-SOAP includes four functionalities and three basic components. The SOAP architecture needs modifications/extensions to meet the requirements of FT-SOAP. Our design takes the advantages of SOAP features. The new proposed components in SOAP and the extensions of SOAP engine is backward compatible to non-fault-tolerant SOAP system. Our approach can be used to develop other supports on SOAP.
Resistance of Anti-Disclosure Image Watermark to Collusion and Copy Attacks: An Approach of Combining Perceptual Hash and Watermark
Chun-Shien Lu and Chao-Yong Hsu
Robustness is a critical requirement regarding the practicability of a watermarking scheme. Current watermarking methods usually claim a certain degree of robustness against those attacks that aim to destroy the hidden watermark at the expense of degrading the quality of media data. However, there exists a kind of watermark-estimation attack (WEA) such as the collusion attack that can remove watermarks meanwhile the attacked data can be made further transparent to its original. Another kind is the copy attack that can create the protocol ambiguity problem within a watermarking system. The motivation of this paper is dedicated to cope with the WEA that is clever at disclosing hidden information for unauthorized purposes. To this end, we begin by gaining an insight into the WEA that leads to formal definitions of optimal watermark estimation and perfect cover data recovery. Subject to these definitions, content-dependent watermark (CDW) is proposed to resist watermark-estimation attack. The key point is to introduce a media hash as a constituent component of the CDW. Mathematical analyses and experiment results have consistently verified the effectiveness of the content-dependent watermarking scheme. To our knowledge, this anti-disclosure watermark is the first study that has taken resistance to both the collusion and the copy attacks into consideration.
Detail Implementation of FT-SOAP
Deron Liang, Chen-Liang Fang, Chien-Cheng Lin
Security is the major concern that refrains people from conducting commerce electronically. The security concerns related to electronic commerce (EC) includes transaction security and system security. We can partially address the transaction security issues by message distribution middleware such as simple object access protocol (SOAP), which is one of the four information technology (IT) infrastructures that facilitate EC. It requires a comprehensive set of IT in order to address the system security issues where fault-tolerance technology is one of the core technologies to enhance the system survivability after attack. Based on our preliminary investigation, we conclude that the current SOAP architecture is lack of mechanism to build a highly reliable EC system. We propose a comprehensive fault-tolerance framework based on the current SOAP architecture in order to address the system security issues for EC. We consider this research is the continuing effort of our previous work on fault-tolerant CORBA, thought there are similarity and difference between these two technologies. We plan to propose a standard recommendation that outlines a set of interfaces named fault-tolerant SOAP. We also expect to implement two prototypes, one based on Windows 200 and the other is based on Linux, in order to prove the concepts.
Towards Robust Image Watermarking: Combining Content-Dependent Key, Moment Normalization, and Side-Informed Embedding
Chun-Shien Lu
In digital watermarking, robustness is still a challenging problem if different sets of attacks need to be tolerated simultaneously. In this paper, we deal with this problem by using an integrated solution of side-informed embedding, moment normalization, and content-dependent watermarks.First, a new image watermarking method designed based on the concept of communications with side information is proposed. We investigate the characteristics of mean filtering in formulating new watermark embedding and extraction processes. Second, regarding resistance to geometrical attacks we do not rely on the concept of pilot signals because they are vulnerable to synchronization removal attacks. We instead use block-based watermarking and moment normalization mechanisms to recover geometrical distortions. Third, regarding resistance to the copy attack, the content-dependent watermark is employed to avoid treating an un-watermarked image as one that has been watermarked. The robustness of our approach has been verified using both the StirMark and the copy attack.
An Efficient Implementation of the PC-Tree Algorithm of Shih & Hsu's Planarity Test
Wen-Lian Hsu
In Shih & Hsu [9] a simpler planarity test was introduced utilizing a data structure called PC-trees (general-ized from PQ-trees). In this paper we give an efficient implementation of that linear time algorithm and illus-trate in detail how to obtain a Kuratowski subgraph when the given graph is not planar, and how to obtain the embedding alongside the testing algorithm. We have implemented the algorithm using LEDA and an object code is available at http://qa.iis.sinica.edu.tw/graphtheory/. The main part of the implementation is devoted to the treatment of the C-nodes that represent those 2-connected components.
Exponential Stabilization for Caplygin Systems Based on a Simplified Rank Condition
Ti-Chung Lee and Jing-Sin Liu
The paper investigates the global rho-exponential stabilizability of nonholonomic Caplygin systems. A novel decomposition of state is given first. When systems are linear in certain state variables, a simple and easily verified rank condition can be proposed to guarantee the global rho-exponential stabilizability of Caplygin systems. In our design, all parameters can be explicitly determined from the constraint function. Moreover, an interesting coordinate transformation can be used to change a Caplygin system into another one so that the proposed criterion can be applied to various situations. For an important class of Caplygin systems, the rank condition is further reduced to some conditions relating to the degree and non-zero property of the lowest polynomials of constraint function. Several interesting examples including of the knife-edge, the extended power-form, the rolling wheel and hopping robot systems are shown that they can be exponentially stabilized by an easy test.