Cartesian tree matching is a recently introduced string matching problem in which two strings match if their corresponding Cartesian trees are the same. It is considered appropriate to find patterns regarding their shapes especially in numerical time series data. While many related problems have been addressed, developing a compact index has received relatively less attention. In this paper, we present a 3n+o(n)-bit index that can count the number of occurrences of a Cartesian tree pattern in 𝒪(m) time where n and m are the text and pattern length. To the best of our knowledge, this work is the first 𝒪(n)-bit compact data structure for indexing for this problem.

Many sequential and temporal data have dependency relationships among their elements, which can be represented as a sequence of pointers. In this paper, we introduce a new string matching problem with a particular type of strings, which we call isodirectional pointer sequence, in which each entry has a pointer to another entry. The proposed problem is not only a formalization of real-world dependency matching problems, but also a generalization of variants of the string matching problem such as parameterized pattern matching and Cartesian tree matching. We present a 2nlgσ+2n+o(n)-bit index that preprocesses the text T[1:n] so as to count the number of occurrences of pattern P[1:m] in 𝒪(mlgσ) where σ is the number of distinct lengths of pointers in T. Our index is also easily implementable in practice because it consists of wavelet trees and range maximum query index, which are widely used building blocks in many other compact data structures. By compressing the wavelet trees, the index can also be stored into 2nH^*₀(T)+2n+o(n) bits where H^*₀(T) is the 0-th order empirical entropy of the distribution of pointer lengths of T.

Abstract Motivation: Tag density plots are very important to intuitively reveal biological phenomena from capture-based sequencing data by visualizing the normalized read depth in a region. Results: We have developed iTagPlot to compute tag density across functional features in parallel using multicores and a grid engine and to interactively explore it in a graphical user interface. It allows us to stratify features by defining groups based on biological function and measurement, summary statistics and unsupervised clustering. Availability and implementation: http://sourceforge.net/projects/itagplot/. Contact: [email protected] and [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

A Social network is a useful model to identify hidden structures and meaningful knowledge among social atoms, which have complicated interactions. Until recently, most studies have focused on the real data of social space, including emails, tweets, and human communities. In this paper, we construct a social network from a fictional space by mapping characters to vertices and their relationship strengths to edges between characters. It is very interesting that the topological structure of SNF is remarkably similar to the common social network based on real people in terms of the power-law distribution of node degree and path distance. The main contribution of this paper is that our SNF model can be exploited to reveal the deep structure of fiction novels by using a graph topology rather than by using traditional categories such as short or long novels.

SUMMARY In Web‐based social media (blogs, Internet forums, etc.), readers express their opinions by attaching reply comments to articles and understand others' perspectives by reading these comments. On Web forums, users discuss and argue with others via reply comments. Thus, a series of comments may provide new information, particularly about disputes among participants. Unfortunately, current systems for viewing reply comments are primitive; it is hard to follow disputes and their relationships by using such systems. We examine the characteristics of disputes by using reply comments and propose a novel system for automatically detecting disputes and their relationships among a large set of reply comments. This paper defines a dispute section as a series of comments where the dispute index is sufficiently high. The dispute index is determined using an exponential model with three control parameters. Next, the dispute relationship can be defined according to a pair of arguing commenters. The basic concept is to exploit the order of comment posting times and comment writer information when detecting dispute sections because the comments tend to appear in ordered pairs. The proposed system detects dispute sections and visualizes them according to dispute relationships among commenters, enabling users to appreciate the controversial structure of comments. To test the performance of our system, we constructed a dataset containing comment sequences associated with 40 articles collected from an Web forum. We constructed the set of dispute comments manually. We found that the detection accuracy of our system for disputes and their relationships were 83% and 78% on average. Copyright © 2012 John Wiley & Sons, Ltd.

Shoulder-surfing is a well-known technique to steal passwords by observing authentication sessions. While researchers have proposed many shoulder-surfing resistant password schemes, there is no general model to illustrate existing schemes and to help developing new schemes. In this paper, we introduce a graph-based model that generally describes shoulder-surfing resistant password schemes. Using this model, we present a method for analyzing some particular security threats and show some properties of, and relationship between certain security measures. Applying our proposed model to existing password systems, we demonstrate how the model can help analyze password schemes. We also discuss the usefulness of our model in designing a new password schemes.

One of the crucial issues in Internet chat is how to manage the corresponding pairs of questions and answers in a sequence of conversations. This paper addresses the problems of ambiguous dialogue logs, lack of a social interaction network of chat agents, and the rupture of the turn sequence in the plain chat room. Therefore we can resolve the ambiguity in rupturing connections between turns and replies. Also, our system supports a graphical visualization interface for tracking the chat dialogue using Chat Flow Graph(CFG)[Park et al. 2008a]. In this paper, we improve our previous work and construct a social network between avatar agents. Our experiment shows that our system is highly effective in a virtual chat environment.

Chat is a crucial function in current virtual worlds. Since virtual worlds are becoming increasingly popular, we need a realistic and efficient communication framework for multi-agents participating in a virtual world. This paper proposes a unified communication framework for multiple avatars in a virtual world, (e.g., second-life). Current chat systems in virtual worlds provide a set of special communication protocols such as pairwise, group and secret chat, independently. Therefore, modern virtual communication systems have adapted artificial chat techniques such as 'one-to-one chat' and 'group chat' to a virtual 3-D space. Our framework exploits spatial relationships (distance, and viewing vector) between several agents, without including a specialized chat protocol layer in communication. The main contribution of our work is threefold. First, we propose a realistic and unified communication framework which enables 'complete chat' and 'partial chat' in terms of spatial relationships between avatar agents without including an additional communication protocol. Second, we propose a single greedy algorithm to find an optimal position in 3-D virtual space which optimizes chat availability. Third, our system reconstructs a dialogue graph which maintains all transcripts in the form of directed graphs with temporal (dialogue sequences) and spatial information (physical positions) about communicating agents.

We propose AVACHAT, a new comic-stylized communication interface for avatar agents. We show that the 3-D word balloon could be successfully exploited to depict chat dialogues and the atmosphere of groups talking, such as cheerful laughing or loud quarrelling without adding any multimedia functions. Finally, we propose a new data structure to manage the chat dialogues among virtual avatars. It can be used to reconstruct the social-graph for chat agents in a virtual world.

It is very important to detect plagiarized programs in the field of computer science education. Therefore, many tools and algorithms have been developed for this purpose. Generally, these tools are operated in two phases. In phase 1, a program plagiarism detecting tool generates an intermediate representation from a given program set. The intermediate representation should reflect the structural characterization of the program. Most tools use the parse tree or token sequence by intermediate representation. In phase 2, the program looks for plagiarized material and evaluates the similarity of two programs. It is helpful to announce the plagiarized metarials between two programs to the instructor. In this paper, we present the static tracing method in order to improve program plagiarism detection accuracy. The static tracing method statically executes a program at the syntax-level and then extracts predefined keywords according to the order of the executed functions. The result of experiment proves this method can detect plagiarism more effectively than the previously released plagiarism detecting method.

Program similarity checking is an important application of programming education fields. Local alignment is one of the typical algorithms for comparing two strings. However local alignment based comparison does not reflect the weights of program keywords. This paper introduces an adaptive local alignment which reflects the frequencies of keywords to the similarity matrix. We experimented this method using a set of programs submitted to more than 10 real programming contests. The experimental result shows that the adaptive local alignment is more robust than greedy-string-tiling adopted in JPlag.

In the post-genomic era, predicting protein function is a challenging problem. It is difficult and burdensome work to unravel the functions of a protein by wet experiments only. In this paper, we propose a novel method to predict protein functions by building a "Protein Interaction Network Dictionary (PIND)". This method deduces the protein functions by searching the most similar "words"(an anagram of functions in neighbor proteins on a protein–protein interaction graph) using global alignments. An evaluation of sensitivity and specificity shows that this PIND approach outperforms previous approaches such as Majority Rule and Chi-Square measure, and that it competes with the recently introduced Random Markov Model approach.

We present an efficient method for rapid animation of mass-spring model with a large number of mass-points. Realistic cloth simulation requires large amount of time in general. This is not only because the calculation for one step requires much time but also because the cloth simulation easily tends to become unstable. Although the implicit method can make the simulation stable, it is still impossible to generate interactive animation when the number of mass-points is sufficiently large enough to represent realistic wrinkles. An efficient animation method proposed by M. Desbrun (1999) also involves O(n/sup 2/)-sized matrix so that it cannot be applied to models with a large number of mass-points. A stable approximate method without matrix operations has been introduced by M. Oshita and A. Makinouchi (2001), but its physical correctness is significantly impaired as the stiffness increases or the timestep becomes large. In this paper we propose a bilayered approach for efficient cloth animation with a large number of mass-points. The proposed method uses two mass-spring meshes. One of them is a rough mesh for representing global motion, and the other is a fine mesh for realistic wrinkles. The experimental results show that the method can be successfully used for real-time animation of plausible cloth models.

Realistic representation of various effects which appear in the real world paintings can be used for several applications like animation or education. To generate oriental paintings, numerous studies have focused on model-based approaches. In this paper, a new model-based approach for oriental paintings is described. To represent the diffusion effects, we propose local equilibrium model (LEM) which is a method to calculate the movement of water and ink effectively. In addition, we propose a paper model with fiber mesh structure and three layers structure on each cell. With this layer model, overlapped strokes can be well represented. A brush model proposed supports several brush effects like shading.

In this paper, we present a real-time animation technique for deformable objects based on mass-spring models in virtual reality environments. Many researchers have proposed various techniques for representing the motion and the appearance of deformable objects. However, the animation of deformable objects in virtual reality environments is still a hard problem. One of the most intensively studied deformable objects is virtual cloth. The difficulties in cloth animation mainly lie in the fact that cloth simulation easily tends to become unstable. Although the implicit method can make the simulation stable \citeBaraff98siggraph, it is still impossible to generate interactive animation when the number of mass-points is sufficiently large enough to represent realistic appearance. There have been a few efficient solutions for real-time animation \citeDesbrun99gi,Kang01tvc,Oshita01ca. However, the previous techniques for real-time cloth animation are not capable of generating the plausible motion and appearance because the methods are based on excessive approximations. This paper proposes an efficient technique that can generate realistic animation of complex cloth objects, and the technique makes it possible to integrate realistic deformable objects into the virtual reality systems without violating the interactivity of the system. The proposed method is based on the implicit integration in order to keep the system stable, and the solution of the linear system involved in the implicit integration is efficiently approximated in real-time.

Most illustration systems need a lot of user strokes to generate natural-looking pen-and-ink illustrations. In order to reduce the number of user strokes necessary, we propose a new method for pen-and-ink illustrations using a stroke morphing concept. For this, we introduce a general stroke morphing procedure, which consists of both flow-oriented morphing and shape-oriented morphing. Using this morphing technique, we can make more natural-looking pen-and-ink illustration with fewer user strokes. This work can be applied to generate simplified pictures for dictionary typesetting. The main purpose of this paper is to describe this method, which requires fewer user strokes than other previous methods. Experimental results are given in the final section.

This study introduces a new Triangulated Irregular Network(TIN) compression method and a progressive visualization technique using Delaunay triangulation. The compression strategy is based on the assumption that most triangulated 2.5-dimensional terrains are very similar to their Delaunay triangulation. Therefore, the compression algorithm only needs to maintain a few edges that are not included in the Delaunay edges. An efficient encoding method is presented for the set of edges by using vertex reordering and a general bracketing method. In experiments, the compression method examined several sets of TIN data with various resolutions, which were generated by five typical terrain simplification algorithms. By exploiting the results, the connecting structures of common terrain data are compressed to 0.17 bits per vertex on average, which is superior to the results of previous methods. The results are shown by a progressive visualization method for web-based GIS.

Realistic animation of soft objects such as cloth is essential for plausible character animation. Many techniques have been proposed for the simulation of soft objects, and most of them are based on numerical integration. Among the techniques, the implicit integration method is the most likely technique for real time environments, since it allows large time steps for cloth simulation by ensuring the stability of systems. However the most critical flaw of the implicit method is that it involves a large linear system. The paper presents a fast animation technique for animating soft objects based on a mass-spring model with an approximated implicit method which does not involve linear system solving. The proposed technique stably updates the state of n mass-points in O(n) time when the number of total springs are O(n). Because the mass-spring model shows a superelastic effect, the excessively deformed springs (i.e., super-elongated springs) should be adjusted for reality. The paper presents an efficient inverse dynamics process to adjust the super-elongated springs.

UNLABELLED: PhyloDraw is a unified viewing tool for phylogenetic trees. PhyloDraw supports various kinds of multi-alignment formats (Dialign2, Clustal-W, Phylip format, NEXUS, MEGA, and pairwise distance matrix) and visualizes various kinds of tree diagrams, e.g. rectangular cladogram, slanted cladogram, phylogram, unrooted tree, and radial tree. By using several control parameters, users can easily and interactively manipulate the shape of phylogenetic trees. This program can export the final tree layout to BMP (bitmap image format) and PostScript. AVAILABILITY: http://pearl.cs.pusan.ac.kr/phylodraw/ CONTACT: [email protected]

Modern GIS (geographic information system) application programs and simulation systems have to handle large datasets for rendering. Currently, three dimensional rendering hardware are facing a memory bus bandwidth bottleneck problem at the graphics pipeline. One general solution for this problem is to compress the static three dimensional geometry in a preprocessing phase. We present a new mesh compression/decompression algorithm for this application. Our compression algorithm breaks down a triangle mesh into a set of triangle strips and vertex chains. After decomposition, we encode vertex connectivity with entropy encoding. Our algorithm provides a 32% improvement in the compression ratio over existing "Generalized Triangle Mesh (GTM)" compression and supports parallel decompression. We also proposed a parallelogram prediction method for vertex coordinate compression.

In this paper we introduce a new compression technique for the connectivity of a Triangulated Irregular Network (TIN) by using Delaunay triangulation. The strategy in this paper is based on that most of 2.5 dimensional terrain connection are very similar to plane-projected Delaunay triangulation of their vertex set. We only need to keep the vertex coordinates and a few edges that are not included in the Delaunay edges. We present an efficient encoding method for the set of edges using vertex reordering and general bracketing algorithm. Also we propose progressive visualization method for web-based GIS. In the experiments, the method was examined on several TIN data with various resolutions, which were generated by five typical terrain simplification algorithms. The connectivity information of common terrain data could be compressed by 0.23 bits per vertex.

The most important goal of character animation is to efficiently control the motions of a character. Until now, many techniques have been proposed for human gait animation. Some techniques have been created to control the emotions in gaits such as ‘tired walking’ and ‘brisk walking’ by using parameter interpolation or motion data mapping. Since it is very difficult to automate the control over the emotion of a motion, the emotions of a character model have been generated by creative animators. This paper proposes a human running model based on a one-legged planar hopper with a self-balancing mechanism. The proposed technique exploits genetic programming to optimize movement and can be easily adapted to various character models. We extend the energy minimization technique to generate various motions in accordance with emotional specifications. Copyright © 1999 John Wiley & Sons, Ltd.

The main problem in this paper is how to find the character which is placed on a line or curves of raster map. We give one novel algorithm to group each separated characters in a map. This word grouping is difficult especially in a map, since a map has many different types of character and each word has its own slanting line. For this, we propose the 3D neighborhood graph G from a given set of characters. In this graph, each vertex of G represents the separated characters and it is placed in 3D space according to the size of the character. This makes the bigger characters being located in the upper position, the smaller characters being placed in the bottom. We give an edge if two vertices are nearly placed in that 3D space. By this edge connection strategy we can easily find the words of various different size in a map.

The most important goal of character animation is to efficiently control the motions of a character. Until now, many techniques have been proposed for human gait animation, and some techniques have been created to control the emotions in gaits such as "tired walking" and "brisk walking" by using parameter interpolation or motion data mapping. Since it is very difficult to automate the control over the emotion of a motion, the emotions of a character model have been generated by creative animators. The paper proposes a human running model based on a one-leg-planar hopper with a self-balancing mechanism. The proposed technique exploits genetic programming to find an optimal movement. We extend the energy minimization technique to generate various motions in accordance with emotional specifications, for instance, "brisk running".

So far there have been models for generating handwriting scripts of western languages. Since the basic structure of oriental languages such as Chinese, Japanese and Korean, is quite different from that of alphabet-based western languages, western handwriting models cannot be applied directly to oriental languages except for a few models. In this paper, we propose a new generation model for generating Korean handwriting scripts. For this we choose 11 characteristic parameters which determine the shape of handwriting scripts. These parameters were selected experimentally by investigating ample Korean scripts. Furthermore we propose the Beta-velocity model to simulate the cursive stroke movement by manipulating curvilinear and cursive connection for consecutive strokes within a letter or a word. In order to generate these oriental cursive strokes, we adopted Beta distribution curve basis which enables one to make easy asymmetric velocity profile. By combining all these features, we synthesize various handwriting Korean scripts by controlling 11 characteristic parameters. In the final section of this paper, we give experimental results. These easy-to-synthesize Korean scripts can be used in evaluating off-line character recognition system and a word processor by supporting handwriting-style fonts.