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

Institute of Information Science, Academia Sinica

Library

Print

Press Ctrl+P to print from browser

2006 Technical Report

Code

Subject / Author / Abstract

View

Code

TR-IIS-06-001

Subject / Author / Abstract

On the Satisfiability of Modular Arithmetic Formula
Bow-Yaw Wang

Modular arithmetic is the underlying integer computation model in conventional programming languages. In this paper, we discuss the satisfiability problem of modular arithmetic formulae over the finite ring Z2ω . Although an upper bound of 22O(n4) can be obtained by solving alternation-free Presburger arithmetic, it is easy to see that the problem is in fact NP-complete. Further, we give an efficient reduction to integer programming with the number of constraints and variables linear in the length of the given linear modular arithmetic formula. For non-linear modular arithmetic formulae, an additional factor of ? is needed. With the advent of efficient integer programming packages, our word-level encoding could be useful to software verification in practice.

View

Code

TR-IIS-06-002

Subject / Author / Abstract

Smart Pantries for Homes
C.F. Hsu, H.Y.M. Liao, J.W.S. Liu, P.C. Hsiu, C.S. Shih, T.W. Kuo, Y.S. Lin

A smart pantry holds non-perishable household supplies and automates the purchasing and delivery of their replenishments. By relieving its user from the chore of keeping the home stocked of essentials, it provides convenience and peace of mind not only to elderly individuals but also busy people of all ages. This paper describes two alternative smart pantry designs and tradeoffs. Underlying methods and technologies used for their implementation are also described.

View

Code

TR-IIS-06-003

Subject / Author / Abstract

A Scarce Resource Model for Medication Scheduling
P.H. Tsai, H.C. Yeh, P.C. Hsiu, C.S. Shih, T.W. Kuo and J.W.S. Liu

This report describes a resource model for medication scheduling. It is called the General Medication Specification-Scarce Resource (GMS-SR) model. The GMS-SR model assumes that the medication dispenser has sufficient power and capacities to send reminders, dispense medications, and monitor/record medication histories on a timely basis. The user is a scarce resource, however. The dispenser must take into account contention for the user when it dispenses medications. The GMS-SR model puts medication scheduling in the rigorous framework of real-time scheduling. Because medication scheduling algorithms based on the model resemble real-time scheduling algorithms, some concepts and guidelines in real-time scheduling are readily applicable.

View

Code

TR-IIS-06-004

Subject / Author / Abstract

A Test for Interval Graphs on Noisy Data – DNA Fragment Assembly
Wei-Fu Lu and Wen-Lian Hsu

An interval graph is the intersection graph of a collection of intervals. One important application of interval graph is the construction of physical maps 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 is robust enough to accommodate a certain percentage of noisy data and to produce a likely interval model realizing the original graph.

View

Code

TR-IIS-06-005

Subject / Author / Abstract

A Semantic Approach to Internet Tabular Information Extraction
Shih-Hung Wu, Huei-Long Wang, I-Chi Wang, Cheng-Lung Sung, Wei-Kuan Shih and Wen-Lian Hsu

Extracting information from tables is essential for Internet information extraction. However, most web tables are designed in HTML format. To decipher their semantic meanings a system needs to deal with various layouts, which is quite cumbersome. Previous works have two major approaches: layout enumeration approach and wrapper approach. The first approach is to match the table with presorted layout. This approach normally does not perform appropriate information integration since it does not use table semantics. The second approach treats different tables in a case-by-case manner laboriously. We present a semantic approach to automatically recognize tables (in specified knowledge domains) with various layouts. Our system first tags table cells using domain knowledge, solve the multiple tagging ambiguities, and then apply layout-syntax rules to transform tables into database format. Experimental results show that the precision and recall are higher than 93% and 82% respectively in four different domains. Our approach has high precision and is suitable as a front end for wrapper construction.

View

Code

TR-IIS-06-006

Subject / Author / Abstract

Compliance Enforcement of Temporal and Dosage Constraints
P. H. Tsai, H. C. Yeh, C. Y. Yu, P. C. Hsiu, C. S. Shih, and J. W. S. Liu

Medication dispensers treated in this paper are designed to improve medication compliance by individual users who take medications at homes and over long periods of time. The paper first presents an overview of medication specifications that define directions and constraints for dispensers and dispenser components that administer medications as specified. When given a specification, the dispenser scheduler checks for consistency and feasibility of constraints defined by the specification and schedules medications to meet the constraints. Several basic algorithms needed for these purposes are described and evaluated.

View

Code

TR-IIS-06-007

Subject / Author / Abstract

Phylo-mLogo: An interactive multiple-logo visualization tool for large-number sequence alignments
Arthur Chun-Chieh Shih, D.T. Lee, Chin-Lin Peng, and Yu-Wei Wu

When aligning several hundreds or thousands of sequences, such as HIVs, dengue virus, and influenza viruses, to reconstruct the epidemiological history or to understand the mechanisms of epidemic virus evolution, how to analyze and visualize the large-number alignment results has become a new challenge for computational biologists. Although there are several tools available for visualization of very long sequence alignments, few of them are applicable to the large-number alignments. In this paper, we present a multiple-logo alignment visualization tool, called Phylo-mLogo, which allows the user to visualize the global profile of whole multiple sequence alignment and to hierarchically visualize homologous logos of each clade simultaneously. Phylo-mLogo calculates the variabilities and homogeneities of alignment sequences by base frequencies or entropies. Different from the traditional representations of sequence logos, Phylo-mLogo not only displays the global logo patterns of the whole alignment but also demonstrates their local logos for each clade. In addition, Phylo-mLogo also allows the user to focus only on the analysis of some important structurally or functionally constrained sites in the alignment selected by the user or by built-in automatic calculation. With Phylo-mLogo, the user can symbolically and hierarchically visualize hundreds of aligned sequences simultaneously and easily check the sites of their amino acid changes when analyzing large-number human or avian influenza virus sequences.

View

Code

TR-IIS-06-008

Subject / Author / Abstract

Analysis of Sampling-based Texture Synthesis as a Generalized EM Algorithm
Liu-yuan Lai, Wen-Liang Hwang, Silong Peng

Research on texture synthesis has made substantial progress in recent years, and many patch-based sampling algorithms now produce quality results in an acceptable computation time. However, when such algorithms are applied to textures, whether they provide good results for specific textures, and why they do so, are questions that have yet to be fully resolved. In this paper, we deal specifically with the second question by modeling the synthesis problem as learning from incomplete data. We propose an algorithm and show that the solution of many sampling-based algorithms is an approximation of finding the maximum-likelihood optimum by the generalized expectation and maximization (EM) algorithm.

View

Code

TR-IIS-06-009

Subject / Author / Abstract

Analysis of Opportunistic Networks based on Realistic Network Traces
Yung-Chih Chen, Paruvelli Sreedevi, Kuan-Ta Chen, and Ling-Jyh Chen

Opportunistic network is a type of Delay Tolerant Networks (DTN) where network communication opportunities appear opportunistic, an end-to-end path between source and destination may have never existed, and disconnection and reconnection is common in the network. With numerous emerging opportunistic networking applications, strategies that can enable effective data communication in such challenged networking environments have become increasingly desirable. In particular, knowing fundamental properties of opportunistic networks will soon become the key for the proper design of opportunistic routing schemes and applications. In this study, we investigate opportunistic network scenarios based on two public network traces, namely UCSD and Dartmouth network traces. In this paper, our contributions are the following: First, we identify the censorship issue in network traces that usually leads to strongly skewed distribution of the measurements. Based on this knowledge, we then apply the Kaplan-Meier Estimator to calculate the survivorship of network measurements, which is used in designing our proposed censorship removal algorithm (CRA) that is used to recover censored data. Second, we perform a rich set of analysis illustrating that UCSD and Dartmouth network traces shows strong self-similarity, and can be modeled as such. Third, we pointed out the importance of these newly revealed characteristics in future development and evaluation of opportunistic networks.

View

Code

TR-IIS-06-010

Subject / Author / Abstract

Effective File Transfer for Opportunistic Networks
Chen-Hung Yu, Yung-Chih Chen, Ling-Jyh Chen

As the sheer number of potential opportunistic application continues to surge (i.e., wireless sensor networks, underwater sensor networks, pocket switched networks, vehicular networks, and etc.), proper strategies for dealing with communication in various challenged network environments are of significance and remained desirable. In this study, we investigated two applications in opportunistic networks, namely file transfer and video transfer applications. Based on the H-EC approach, we proposed three message scheduling algorithms to effectively transfer data files in challenged networks. Moreover, targeting video file transfers, we designed LMDC (Layered Multiple Description Coding) based techniques that immensely improve the perceived video quality for end users. Using simulations as well as realistic network scenarios, we evaluated various proposed schemes in terms of latency and PSNR (Peak Signal-to-Noise Ratio). We showed that our proposed schemes can achieve much better latency performance for file transfers. Furthermore, we show that using LMDC-based techniques, the end user can enable lower quality video "previews" before the video file is completely transferred. The effectiveness and robustness of the proposed schemes render them ideal solutions that can go a long way toward effective file transfer in opportunistic networks.

View

Code

TR-IIS-06-011

Subject / Author / Abstract

The Web and Collaborative Geospatial Mapping: A Position Paper
Chin-Lung Chang, Yi-Hong Chang, Tyng-Ruey Chuang, Dong-Po Deng, Andrea Wei-Ching Huang, Chia-Hsin Huang

The initiative of our research is to build a geo-writable web, using open source technologies for people's participation online. This paper is the key underpinning for the new emerging trend “online community mapping” as a conceptualized model combined with information/computer science, geography, and sociology, which we have proposed recently. In particular, we argue that public access to geospatial datasets and tools, as well as mechanism design of collaborative and social software, are crucial factors. We envisage the web as a medium of places, people, and participation (3P), and we outline in this paper an implementation strategy for this vision. A prototype called Web3P is being built to experiment with various design elements and implementation techniques to further facilitate an “online community mapping” process.

View

Code

TR-IIS-06-012

Subject / Author / Abstract

An Algebra of Dependent Data Types
Tyng-Ruey Chuang, Jan-Li Lin

We extend the standard categorical approach to algebraic data types to dependent algebraic data types, so that dependency between two algebraic data types has natural semantics. Specifically, for two inductive data types S and A characterized by two F-algebra F and G, any natural transformation η : F → G gives rise to a dependency of S on A. This natural dependency is the initial object of what we call a Fη - algebra. The initiality further allows us to describe certain dependencies in functions that both involve S and A. We have used Objective Caml to write functional programs where dependencies among data types (and in the relevant functions) are made explicit. This is done by a systematic mapping of layers of categorical constructions to layers of Objective Caml modules.

View

Code

TR-IIS-06-013

Subject / Author / Abstract

Collaborative Assignment Using BDI Multiagent Negotiation
Kiam Tian Seow, Kwang Mong Sim and Yuan Chia Kwek

In this report, we propose a distributed agent model that embodies belief-desire-intention (BDI) reasoning and negotiation for addressing the linear assignment problem (LAP) collaboratively. In resource allocation, LAP is viewed as seeking a concurrent allocation of one different resource for every task to optimize a linear sum objective function. The proposed model provides a basic agent-based foundation needed for efficient resource allocation in a distributed environment. A distributed agent algorithm realizing the BDI negotiation model is developed and examined both analytically and experimentally. The significance of the model and its algorithm is also discussed in relation to existing multiagent work.

View

Code

TR-IIS-06-014

Subject / Author / Abstract

Design and Implementation of RFID-Based Object Locator
T. S. Chou and J. W. S. Liu

An object locator is a device designed to assist its user in finding misplaced household and personal objects in a home. This paper describes alternative designs and a proof-of-concept prototype of object locators based on the RFID technology. Advantages of such locators include extensibility and low maintenance. The numeric model provided here can be used to determine figures of merits, including costs, search time and energy consumption. The results of analysis based on the model can serve as design guides.

View

Code

TR-IIS-06-015

Subject / Author / Abstract

Bee: A Best Effort Peer-to-Peer Delivery Protocol for Internet Data Dissemination Application
Chi-Jen Wu, Cheng-Ying Li, Kai-Hsiang Yang and Jan-Ming Ho

How to rapidly disseminate a large-sized file to many recipients is a fundamental problem in many applications, such as updating software patches and distributing multimedia content. In this paper, we present the Bee protocol, which is a best-effort peer-to-peer file delivery protocol aiming at minimizing the maximum dissemination time for all peers to obtain the complete file. Bee is a decentralized protocol that organizes peers into a randomized mesh-based overlay and each peer only works with local knowledge. We introduce a slowest peer first strategy to boost the speed of dissemination, and design a topology adaptation algorithm that adapts the number of connections based on upload bandwidth capacity of a peer. Moreover, Bee is designed to support network heterogeneity and deal with the flash crowd arrival pattern without sacrificing the dissemination speed. We present a lower bound analysis and experimental results on the performance of Bee in terms of dissemination time and show that its performance can approaches the lower bound of the maximum dissemination time.

View

Code

TR-IIS-06-016

Subject / Author / Abstract

Smallest Bipartite Bridge-connectivity Augmentation
Pei-Chi Huang, Hsin-Wen Wei, Wan-Chen Lu, Wei-Kuan Shih and Tsan-sheng Hsu

This paper addresses two augmentation problems related to bipartite graphs. The first, a fundamental graph-theoretical problem, is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, and still bipartite. The second problem, which arises naturally from research on the security of statistical data, is how to add edges so that the resulting graph is simple and dose not contain any bridges. In both cases, after adding edges, the graph can be either a simple graph or, if necessary, a multi-graph. Our approach then determines whether or not such an augmentation is possible. We propose a number of simple linear-time algorithms to solve both problems. Given the well-known bridge-block data structure for an input graph, the algorithms run in O(log n) parallel time on an EREW PRAM using a linear number of processors, where n is the number of vertices in the input graph. We note that there is already a polynomial time algorithm that solves the first augmentation problem related to graphs with a given general partition constraint in O(n(m+n log n) log n) time, where m is the number of distinct edges in the input graph. We are unaware of any results for the second problem.

View

Code

TR-IIS-06-017

Subject / Author / Abstract

Extracting Citation Relationships from Web Documents for Author Disambiguation
Kai-Hsiang Yang, Jian-Yi Jiang, Hahn-Ming Lee, Jan-Ming Ho

Disambiguating the citation records of authors with the same name is a very interesting and challenging problem that affects many research and application fields, such as digital libraries. However, current bibliographic digital libraries like CiteSeer can not correctly disambiguate citation records because of two problems: information sparsity (citations for an individual have few or no common features), and information noise (citations for different individuals have the same coauthor names, title words, or venue words). To resolve these problems, we propose a novel author disambiguation scheme that searches for authors’ publication lists on the Web to enrich citation information. A binary classifier and a cluster separator are used to filter out noise. The experiment results show that the disambiguation accuracy improves from 51% to 73% when Web information is used in the disambiguation task. Furthermore, for most datasets, the clustering precision rate is satisfactory (more than 90%).

View