- 2023
- 2022
- 2020
- 2019
- 2018
- 2017
- 2016
- 2015
- 2014
- 2013
- 2012
- 2011
- 2010
- 2009
- 2008
- 2007
- 2006
- 2005
- 2004
- 2003
- 2002
- 2001
- 2000
- 1999
- 1998
- 1997
- 1996
- 1995
- 1994
- 1993
- 1992
- 1991
- 1990
- 1989
- 1988
- 1987
- 1986
- 1985
- 1984
- 1983
- 1982
- 1981
- 1980
- 1979
Code
Subject / Author / Abstract
View
Code
TR-IIS-02-001
Subject / Author / Abstract
Compression of 3D Objects with Multistage Color-Depth Panoramic Maps
Chang-Ming Tsai, Wen-Yan Chang, Chu-Song Chen, Gregory Y. Tang
We propose a new representation method, the multistage color-depth panoramic map (or panomap), for compressing 3D graphic objects. The idea of the proposed method is to transform a 3D graphic object, including both the shape and color information, into a single image. With a pseudo cylinder (or sphere), the color/depth information of a 3D graphic object can be recorded completely via a main panomap combined with a set of residual panomaps. Then, an index sequence is constructed to index non-redundant blocks in the residual panomaps. A rectangular image, the compact multistage panomap (CMP), is formed based on the panomaps and index sequence. Existing image compression techniques can be applied for compressing the CMP structure, which can achieve a highly efficient representation due to its regularity.
View
Code
TR-IIS-02-002
Subject / Author / Abstract
Statistical Disclosure Control with General Cell Suppressions
Tsan-sheng Hsu, Ming-Yang Kao
This paper studies statistical database problems for two-dimensional tables whose regular cells, row sums, column sums and table sums may be suppressed. Using graph-theoretical techniques, we give optimal or efficient algorithms for the query system problem, the adversary problem and the minimum complementary suppression problem. The three problems are considered for the case of protecting a single cell or a sum of cells against exact or interval disclosures in a positive or general table.
Previously, graph-theoretical techniques are known for the three problems when the row, column and table sums are not suppressed, and when the data are being protected against exact disclosures. This paper provides two generalized graph-theoretical techniques,
which unify previous results, to solve the three statistical database problems
without the above constraints.
View
Code
TR-IIS-02-003
Subject / Author / Abstract
On Maximum Rate Control of Worst-case Weighted Fair Queueing
Jeng Farn Lee, Yeali Sun, Meng-Chang Chen
While exisiting weighted fair scheduling schemes guarantee minimum bandwidths for classes/sessions in a shared channel, maximum rate control, which is critical to service providers and carriers for resource management and business strategies, was generally enforced by employing policing mechanisms. The previous approaches use either a concatenation of rate controller and scheduler, or a policer in front of scheduler. The concatenation method uses two sets of queues and management aparartus, and thus incurs overhead. The other method allows bursty traffic to pass through that can violate maximum rate constraint or cause a high packet loss rate. In this paper, we present a new weighted fair scheduling scheme, WF2Q-M, to simultaneously support maximum rate control and minimum service rate guarantee. WF2Q-M proposes the virtual clock adjustment method to enforce maximum rate control by distributing the excess bandwidths of maximum rate constrained sessions to other sessions without recalculating the virtual starting and finishing times of regular sessionss. In terms of performance metrics, we prove that WF2Q-M is theoretically bounded by a fluid reference model. A procedural scheduling implementation of WF2Q-M is proposed and proof of correctness is given. Finally, we conduct extensive experiments to show the performance of WF2Q-M is just as we claimed.
View
Code
TR-IIS-02-004
Subject / Author / Abstract
Workshop Notes -- Towards the Foundation of Data Mining -- Vol 2
A Workshop held at the 6th Pacific-Asia Conference on Knowledge Discovery and Data Mining
View
Code
TR-IIS-02-005
Subject / Author / Abstract
OC: An Optimal Cache Algorithm for Video Staging
Shin-Hung Chang, Ray-I Chang, Jan-Ming Ho, and Yen-Jen Oyang
The video content for on-demand services is generally stored and streamed in a compressed format. The compressed video is naturally with the VBR (variable-bit-rate) property and the stream traffic is highly burst. Subject to the QoS-guaranteed playback, the WAN bandwidth needs to allocate the video's peak bit rate if there is no client buffer for regulating the video delivery. To reduce the requirement of WAN bandwidth, Video Stagin, first proposed by Zhang et al., caches parts of a video content in the video proxy closed to clients. Therefore, the video can be streamed across the WAN with CBR (constant-bit-rate) services and its bandwidth requirement is significantly reduced.
In this paper, we propose an Optimal Caching (OC) algorithm to handle the Video Staging problem. We also prove that the cache storage computed by our OC algorithm is minimal. Relatively, if the same cache size is given, OC requires less WAN bandwidth than the previous method does to provide streaming services. By doing experiments on several benchmark videos, we show that the OC algorithm can reduce the cache storage requirement by over 30% while comparing to the previous method. With the same proxy cache storage, we can reduce the WAN bandwidth requirement with more than 50%. Additionally, the WAN bandwidth utilization can also be increased by over 30%.
View
Code
TR-IIS-02-006
Subject / Author / Abstract
A Path Planning Method Using Cubic Spiral with Curvature Constraint
Tzu-Chen Liang and Jing-Sin Liu
This paper addresses a new path planning method, whose objective is to build a process to generate a path which connects two configurations of car-like mobile robots. The generated path is constituted by both cubic spirals and straight lines, and has continuous and bounded curvature. We will show the procedure to find the path with theoretical minimal length and to simplify it for the reason of practical use. Mobile robots with forward and backward driving abilities and only uni-direction driving ability are both considered. This method is flexible and is eligible to incorporate with other constraints like wall-collision avoidance. This will also be discussed.
View
Code
TR-IIS-02-007
Subject / Author / Abstract
A Distributed Mobile Robot Simulator and a Ball Passing Strategy
Tzu-Chen Liang and Jing-Sin Liu
This report includes two parts. First we build a mobile robot motion simulator. The simulator provides a platform to develop strategies and control methods for robot soccer games. Second, a strategy for three mobile robots to pass a ball in turn with specific direction intention is suggested and realized by this simulator. In the simulator, the robot motion is simulated by dynamical model of type (2,0) unicycle mobile robot. Kick motion follows physical law, and a simplified collision model is utilized to avoid robot overlapping. Ball passing strategy includes a formation and role change scheme, a trajectory planning method and a tracking controller. It formulates the ball passing movement of robots as a problem of tracking and goal adjusting, just like human soccer players do. The results hint that a human-like behavior pattern is applicable in robot soccer games.
View
Code
TR-IIS-02-008
Subject / Author / Abstract
Symbolic Simulation of Real-Time Concurrent Systems
Farn Wang and Geng-Dian Hwang
We introduce the symbolic simulation function implemented in our model-checker/simulator RED 4.0 for dense-time concurrent systems. By representing and manipulating state-spaces as logic predicates, the technique of symbolic simulation can lead to high performance by encompassing many, even densely many, traces in traditional simulation into one symbolic trace. We discuss how we generate traces with various policies, how we handle the issue of code coverage and functional coverage, how we manipulate the state-predicate, and how we manage the trace trees. Finally, we report experiment with our simulator in the verification of the Bluetooth baseband protocol.
View
Code
TR-IIS-02-009
Subject / Author / Abstract
Efficient Verification of Timed Automata with BDD-like Data-Structures
Farn Wang
We examine the causes of inefficiencies of previous BDD-like data-structures for timed automata state-space representation and manipulation. We identify four issues, which can cause the inefficiencies: variable designs, normal form definitions, zone-containment relation, and normal form computation. We explore the four issues in details and propose to use CRD (Clock-Restriction Diagram) for timed automata state-space representation. Then instead of using the traditional approach of computing canonical form (i.e., unique normal form) for zones representing the same state-space, we propose the new technique of magnitude derivation and downward redundancy elimination to convert zones into a small range of “normalizes” zones. To better understand the complexity of BDD-like data-structures with various techniques, we have carried out extensive experiments and report the performance of BDD-like data-structures w.r.t. various techniques, benchmarks, and other tools.
View
Code
TR-IIS-02-010
Subject / Author / Abstract
Symmetric Symbolic Safety-Analysis of Concurrent Software with Pointer Data Structure
Farn Wang and Karsten Schmidt
Pointer is a very convenient device for constructing dynamic networks and passing parameters in complex software. But with bugs like dirty pointers, it also creates challenges in maintaining system functionality. We formally define the model of software with pointer data structures. Model checking such software may cost tremendous resources because of the dynamic data structure. We developed symbolic algorithms for the manipulation of conditions and assignments with indirect operands for verification with BDD-like data-structures. We rely on two techniques, including inactive variable elimination and process-symmetry reduction in the network configuration, to contain the time and memory complexity. We argue for the indispensability of process-symmetry reduction in model-checking such systems and laid the theoretical groundwork for the discussion of symmetry reduction. We propose the efficient technique of IbSINC ( Incomplete but Sound Isomorphism of Network Configuration ) reduction to avoid the expensive but complete symmetry reduction. We then identify the anomaly of image false reachability of the IbSINC reduction and also define a useful class of symmetric systems, for which the efficient IbSINC reduction works well without the anomaly problem. We implemented the techniques in the RED tool and tested it against the Mellor-Crummy and Scott’s locking algorithms and several other benchmarks. The performance comparison with tool SMC shows that for the special class of pointer-data-structure concurrent systems, our technique can lead to significant performance improvement.
View
Code
TR-IIS-02-011
Subject / Author / Abstract
OVL Assertion-Checking of Embedded Softwares with Dense-Time Semantics
Farn Wang and Fang Yu
OVL (Open Verification library) is designed to become a standard assertion language of the EDA (Electronic Design Automation) industry and has been adopted by many companies. With OVL, verification process can blended seamlessly into the development cycles of complex systems. We investigate how to use OVL assertions for the verification of dense-time concurrent systems. We have designed a C-like language, called TC (timed C), for the description of real-time system with OVL assertions between code lines. We explain how to translate TC programs into optimized timed automata, how to translate OVL assertions into TCTL (Timed Computation-Tree Logic) formulae, and how to analyze assertions when not satisfied. The idea is realized in our translator RG (RED Generator).
In addition, we have developed several new verification techniques to take advantage of the information coming with OVL assertions for better verification performance. The new techniques have been incorporated in our high-performance TCTL model-checker RED 4.0. To demonstrate how our techniques can be used in industry projects, we report our experiments with the L2CAP (Logic Link Control and Adaptation Layer Protocol) of BlueTooth specification.
View
Code
TR-IIS-02-012
Subject / Author / Abstract
Learning Hybrid Poisson Aspect Model for Personalized Shopping Recommendation
Advisor: Professor Chun-Nan Hsu; Student: Hao-Hsiang Chung
Recommendations that really match customers' needs can boost sales. Researchers have proposed and evaluated many approaches for generating recommendations. In this thesis, we proposed a model-based collaborative approach, called Hybrid Poisson Aspect Model (HyPAM ). HyPAM is a hybrid system combining two probabilistic models, cluster and aspect, which model the relationship between customer clusters and product types. Given a new customer and his/her shopping record, HyPAM can estimate his/her degree of preference of each product item accurately. We use the EM algorithm to learn the parameters of HyPAM from customers' shopping records. To evaluate our approach, we apply HyPAM and two well-known recommender systems, GroupLens and IBM, to a shopping-record data set provided by a local supermarket. This data set contains 119,578 transactions of 32,266 distinguishable customers in a four-month period. We adopted two metrics, rank score and lift index, with four protocols, Given 2, Given 5, Given 10, and All but one. Under these evaluation metrics, experimental results show that HyPAM performs much better compared to the other two recommendation approaches for the given data set.
View
Code
TR-IIS-02-013
Subject / Author / Abstract
Open Set Classification Based on Tolerance Interval For Speaker Verification System
Advisor: Professor Chun-Nan Hsu; Student: Hao-Zhong Yu
Speaker verification systems solve the problem of verifying whether a given utterance comes from a claimed speaker. This problem is important because an accurate speaker verification system can be applied to many security systems. Comparing to other biometric methods like fingerprint or face recognition, speaker verification systems do not require expensive specialized equipments and are effective especially for remote identity verification. Previously, Renoylds et al. have proposed a speaker verification system using Gaussian mixture model, but their system is incomplete because their system needs a set of background speaker models, which are constructed using a large speech database of a variety of speakers. It may not be feasible to obtain such a database in the real world. In this thesis, I propose a new solution called OSCILLO, for speaker verification. By applying tolerance interval technique in statistics, OSCILLO can verify a speaker's ID without background speaker models. This greatly reduces the size of the whole system and the time for both training and testing. We compare OSCILLO and Reynolds' method using three standard speech databases: TCC-300, TIMIT and NIST. The experimental results show that OSCILLO performs well for all databases.
View
Code
TR-IIS-02-014
Subject / Author / Abstract
Numerical Coverage Estimation for the Symbolic Simulation of Real-Time Systems
Farn Wang, Geng-Dian Hwang, Fang Yu
Three numerical coverage metrics for the symbolic simulation of dense-time systems and their estimation methods are presented. Special techniques to derive numerical estimations of dense-time state-spaces have also been developed. Properties of the metrics are also discussed w.r.t. four criteria. Implementation and experiments are then reported.
View
Code
TR-IIS-02-015
Subject / Author / Abstract
Hierarchical Peer-to-Peer Networks
H. T. Kung and Chun-Hsin Wu
In this paper, we describe a hierarchical architecture that can potentially scale peer-to-peer (P2P) networks to large numbers of peer nodes and contents. Two principles are followed: network routing reflects content clustering, and content placement reflects usage locality. We reason how these principles can lead to scalable P2P networks, and show techniques of implementing them.
View