OPTIMAL BANDWIDTH-BUFFER TRADEOFF FOR VBR MEDIA TRANSMISSION OVER THE RELAY-SERVER
Ray-I Chang, Meng-Chang Chen, Jan-Ming Ho and Ming-Tat Ko
In a client-server system, the minimum bandwidth required to transmit a pre-recorded VBR media can be computed in O(n). As the frame number n is usually very large, this resource management procedure is not suitable for online computation. Although an O(nlogn) algorithm has been proposed to characterize the bandwidth-buffer tradeoff for the optimal resource management (a native algorithm takes O(n^3)), this algorithm is not suitable for a general network system with additional relay-server. In this paper, we extend the problem model to consider the relay-server between client and server. This proposed model is good for scalable multimedia and fault-tolerance. Besides, the additional buffer in relay-server can be utilized to further smooth traffic and support more requests. In this paper, an O(nlogn) algorithm is proposed to decide the optimal bandwidth-buffer tradeoff for the relay-server. Based on the pre-computed tradeoff function, we can simply design a good QoS control procedure to allocate the suitable bandwidth for the available buffer size.
ACIRD : INTELLIGENT INTERNET DOCUMENTS ORGANIZATION AND RETRIEVAL
Shian-Hua Lin, Meng Chang Chen, Jan-Ming Ho and Yueh-Ming Huang
In this paper, we present an intelligent Internet information system ACIRD using machine learning techniques to organize and retrieve Internet Web documents. ACIRD consists of three parts: knowledge acquisition, document classifier and two-phase search engine. The knowledge acquisition of ACIRD automatically learns the classification knowledge from classified Internet Web documents and the classifier applies the classification knowledge to classify newly collected Internet Web documents to one or more classes in a class hierarchy. The experiments show that ACIRD performs as good as or better than human experts in both knowledge extraction and document classification. Based on the learned classification knowledge and the given class hierarchy, the ACIRD two-phase search engine presents hierarchically navigable structured results to the users instead of conventional flat ranked results that greatly helps users in discovering information from diversified Internet documents.
AUTOMATIC VERIFICATION OF POINTER DATA-STRUCTURES SYSTEMS FOR ALL NUMBERS OF PROCESSES
Real-world softwares for concurrent systems may involve data-structures linked together with pointers. Even with such sophistication, they are usually supposed to work regardless of the number of processes. We propose a new automatic approximation method to safely verify algorithms used in such systems. The central idea is to construct a finite collective image set (CIS) which collapses reachable state representations for all implementations of all numbers of processes. Our collapsing scheme filters out unimportant information of system behaviors and results in CIS's with manageable space requirements which allow for efficient verification. Analysis shows our method can automatically generate a CIS of size 657 to verify that a version of Mellor-Crummy & Scott's algorithm preserves mutual exclusion for all numbers of processes.
AUTOMATIC DATA AND COMPUTATION DECOMPOSITION ON DISTRIBUTED MEMORY PARALLEL COMPUTERS
PeiZong Lee, Zvi M. Kedem.
On shared memory parallel computers (SMPCs) it is natural to focus on decomposing the computation (mainly by distributing the iterations of the nested Do-Loops). In contrast, on distributed memory parallel computers (DMPCs) the decomposition of computation and the distribution of data must both be handled---in order to balance the computation load and to minimize the migration of data. We propose and validate experimentally a method for handling computations and data synergistically to optimize the overall execution time. The method relies on a number of novel techniques, also presented in this paper. The core idea is to rank the ``importance'' of data arrays in a program and define some of the dominant. The intuition is that the dominant arrays are the ones whose migration would be the most expensive. Using the correspondence between iteration space mapping vectors and distributed dimensions of the dominant data array in each nested Do-loop, we are able to design algorithms for determining data and computation decompositions at the same time. Based on data distribution, computation decomposition for each nested Do-loop is determined based on either the owner computes rule or the owner stores rule with respect to the dominant data array. If all temporal dependence relations across iteration partitions are regular, we use tiling to allow pipelining and overlapping the computation and communication time. However, to use tiling on DMPCs, we needed to extend the existing techniques for determining tiling vectors and tile sizes, as they were originally suited for SMPCs only. The method is illustrated on programs for the 2D heat equation and for the 2D fast Fourier transform both on a linear processor array.
A NEW WATERMARKING TECHNIQUE FOR MULTIMEDIA PROTECTION
Chun-Shien Lu, Shih-Kun Huang, Chwen-Jye Sze, Hong-Yuan Mark Liao
A robust watermarking scheme for hiding binary or gray-scale
watermarks in digital images is proposed in this chapter. Motivated
by the fact that a detector response (a correlation value) only provides
a soft evidence for convincing jury in courtroom, embedded watermarks
are designed to be visually recognizable after retrieval. To strengthen
the existence confidence of a watermark, visually significant
transformed components are selected. In addition, a relocation
technique is presented to tackle geometric-distortion-based attacks
without using any registration scheme.Finally, a semi-public
watermark detector which does not require use of the original
source is proposed for the purpose of authentication. Experimental
results demonstrate that our approach satisfies the common
requirements of image watermarking, and that the performance
SEGMENTATION OF PERSPECTIVE TEXTURED PLANES THROUGH THE RIDGES OF CONTINUOUS WAVELET TRANSFOR
Hwang, Wen-Liang Lu, Chun-Shien Chung, Pau-Choo
A common assumption of the shape from texture problem is that a perceived image mainly contains only one type of texture with the same surface orientations. Unfortunately, a natural image is often composed of textures with different surface orientations. In order to deal with the shape from texture problem in a practical manner, we need to segment these surface orientations. The ridges are wavelet attributes in which information about spatial frequencies resides. In this paper, we propose a robust method for treating this problem from the ridges of continuous wavelet transform. We demonstrate the performance of our method on textured images synthesized from the Brodatz texture and several natural images.
A RELATIONAL DATABASE APPROACH TO BAYESIAN NETWORK KNOWLEDGE DISCOVERY
Wong, Tau-Tsung Hsu, Chun-Nan Ma Chia-Che
A Bayesian network is a powerful formalism for decision-making and knowledge
discovery. An approach to Bayesian network training for large scaled
real-world applications is important. Bayesian network training includes the
following two steps. Experts first select appropriate parameters consistent
with their confidence to transform the conditional probabilities into
Dirichlet priors. Then the conditional posteriors for the variables in the
network can be obtained by Bayesian updating. In this paper, we present a
database scheme to store and manipulate a large Bayesian network as well as
training data sets in a relational database. This scheme facilitates
Bayesian network training and allows the system to take advantage of the
benefits of relational data models. Other features of this scheme are that
it tolerates incomplete training data and is generally applicable for
Bayesian networks with arbitrary graph structures. Since RDBMS are widely
available, this scheme greatly simplifies the construction of a Bayesian
network based KDD system.
COCKTAIL WATERMARKING FOR DIGITAL IMAGE PROTECTION
Lu, Chun-Shien Huang, Shih-Kun Sze, Chwen-Jye Hong-Yuan Mark Liao
A novel image protection scheme called ``cocktail watermarking'' is proposed in this paper. We
analyze and point out the inadequacy of the modulation techniques commonly used in ordinary
spread spectrum watermarking methods and the visual model-based ones. To resolve the inadequacy,
two watermarks which play complementary roles are simultaneously embedded into a host image.
The new watermarking scheme guarantees that, no matter what kind of attack is encountered, at
least one watermark can survive well. We also conduct a statistical analysis to derive the lower
bound of the worst likelihood that the better watermark (out of the two) can be extracted. With
this ``high'' lower bound, it is ensured that a ``better'' extracted watermark is always obtained. From
extensive experiments, results indicate that our cocktail watermarking scheme is remarkably effective
in resisting various attacks, including combined ones.
EFFICIENT DATA STRUCTURE FOR FULLY SYMBOLIC VERIFICATION OF REAL-TIME SOFTWARE SYSTEMS
A new data-structure called DDD (Data-Decision Diagram) for the fully
symbolic model-checking of real-time software systems is proposed.
DDD is a BDD-like structure for the encoding of regions. Unlike DBM
which records differences between pairs of clock readings, DDD only
uses one auxiliary binary variable for each clock. Thus the number of
variables used in DDD is always linear to the number of clocks declared
in the input system description. Experiment has been carried out to
compare DDD with previous technologies.
NATURAL LANGUAGE AGENTS : AN AGENT SOCIETY ON THE INTERNET
WEN-LIAN HSU, YI-SHIOU CHEN AND YUAN-KAI WANG.
As the Internet is flooded with different types of documents (unstructured, semi-structured texts) and heterogeneous databases, information retrieval and extraction become increasingly difficult. We propose to deal with the information service problem on the Internet by creating an agent society in which agents act as spokesperson for various web pages, databases and provide information integration services in a cooperative manner. Furthermore, these agents can communicate with restricted natural language. The natural language used by these agents is sufficiently constrained so as to avoid ambiguity as much as possible while retaining its richness and flexibility. We use KQML as the communication protocol. The restricted natural language sentences are placed in the content parameter. These agents are particularly useful in information retrieval, extraction and integration services where interfaces in natural language are appropriate. The basic framework for our agent society is a context sensitive model for concept understanding. Such a model allows us to set up a natural language protocol so that each agent can advertise what it is capable of as well as "understand" and utilize those services other agents can provide. There are two important features of such an agent society: (1) heterogeneous databases can be naturally integrated; (2) human-computer interface will be friendlier since retrieval and extraction based on natural language descriptions (rather than keywords) can be handled more smoothly. Several prototype agent systems are being constructed based on the architecture proposed in this paper. Preliminary experiments show that this approach is very promising.