您的瀏覽器不支援JavaScript語法,網站的部份功能在JavaScript沒有啟用的狀態下無法正常使用。

Institute of Information Science, Academia Sinica

Library

Print

Press Ctrl+P to print from browser

1999 Technical Report

:::

Code
Subject / Author / Abstract
View

Code

TR-IIS-99-001

Subject / Author / Abstract

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.

View

Fulltext

Code

TR-IIS-99-002

Subject / Author / Abstract

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.

View

Fulltext

Code

TR-IIS-99-003

Subject / Author / Abstract

AUTOMATIC VERIFICATION OF POINTER DATA-STRUCTURES SYSTEMS FOR ALL NUMBERS OF PROCESSES
FARN WANG.

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.

View

Fulltext

Code

TR-IIS-99-004

Subject / Author / Abstract

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.

View

Fulltext

Code

TR-IIS-99-005

Subject / Author / Abstract

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 is superb.

View

Fulltext

Code

TR-IIS-99-006

Subject / Author / Abstract

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.

View

Fulltext

Code

TR-IIS-99-007

Subject / Author / Abstract

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.

View

Fulltext

Code

TR-IIS-99-008

Subject / Author / Abstract

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.

View

Fulltext

Code

TR-IIS-99-009

Subject / Author / Abstract

EFFICIENT DATA STRUCTURE FOR FULLY SYMBOLIC VERIFICATION OF REAL-TIME SOFTWARE SYSTEMS
Wang, Farn

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.

View

Fulltext

Code

IM-IIS-99-001

Subject / Author / Abstract

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.

View

not for public 原文請洽圖書室

Code

IM-IIS-99-002

Subject / Author / Abstract

資訊所出勤系統
資訊室 高曉瑩 王秋鳳

View

not for public 原文請洽圖書室

Code

IM-IIS-99-003

Subject / Author / Abstract

資訊所人事系統
資訊室 高曉瑩 王秋鳳

View

not for public 原文請洽圖書室