An orthogonal drawing of a graph is a planar drawing where each edge is drawn as a sequence of horizontal and vertical line segments. Finding a bend-minimized orthogonal drawing of a planar graph of maximum degree 4 is NP-hard. The problem becomes tractable for planar graphs of maximum degree 3, and the fastest known algorithm takes O(n^5 log n) time. Whether a faster algorithm exists has been a long-standing open problem in graph drawing. In this paper we present an algorithm that takes only O~(n^{17/7}) time, which is a significant improvement over the previous state of the art.

Extractive summarization, a process that automatically picks exemplary sentences from a text (or spoken) document with the goal of concisely conveying key information therein, has seen a surge of attention from scholars and practitioners recently. Using a language modeling (LM) approach for sentence selection has been proven effective for performing unsupervised extractive summarization. However, one of the major difficulties facing the LM approach is to model sentences and estimate their parameters more accurately for each text (or spoken) document. We extend this line of research and make the following contributions in this work. First, we propose a position-aware language modeling framework using various granularities of position-specific information to better estimate the sentence models involved in the summarization process. Second, we explore disparate ways to integrate the positional cues into relevance models through a pseudo-relevance feedback procedure. Third, we extensively evaluate various models originated from our proposed framework and several well-established unsupervised methods. Empirical evaluation conducted on a broadcast news summarization task further demonstrates performance merits of the proposed summarization methods.

We propose a novel layout algorithm to draw clustered graphs. Our algorithm applies a stress model to draw intra-cluster graphs and a spring-electrical force model to place clusters. Our strategy modifies the original stress model in graph drawing by integrating the force from the center to push and pull the intra-cluster nodes based on their outside connectivity. We also apply the idea of torque equilibrium, coupled with some heuristics, to realize our force-directed placement algorithm. To show the effectiveness of our design, we compare the running time and the number of edge crossings experimentally with the one using full stress majorization as well as other clustered graph drawing algorithms available in the literature. Our experimental results look promising.

IEEE 802.11p Wireless Access in the Vehicular Environment (WAVE) has been serving as the de facto wireless protocol for a Vehicular Ad hoc Network (VANET) with the explosive growth of vehicular applications. These applications require guaranteed Quality-of-Service (QoS). However, the fundamental channel access mechanism of WAVE, Enhanced Distributed Channel Access (EDCA), is not able to provide guaranteed QoS due to the unpredictable random access. To remedy this problem, we propose a novel channel access scheme, called Earliest Deadline First based Carrier Sense Multiple Access (EDF-CSMA). EDF-CSMA based on EDCA dynamically adjusts the priority of real-time streaming to avoid collision and introduces an admission control policy according to time constraints to provide guaranteed QoS in multi-channel environments. An analytical model is carried out to study and compare the channel utilization of EDF-CSMA and QoS-aware Hybrid Coordination Function (HCF) controlled channel access (HCCA) method. The result shows that 60 percent of channel utilization is improved by EDF-CSMA. Additionally, real video-based simulations are conducted to evaluate the performance of EDF-CSMA and the existing EDCA method. The results show that EDF-CSMA reaches better QoS support than EDCA while maintaining efficient channel utilization.

Extractive summarization, with the intention of automatically selecting a set of representative sentences from a text (or spoken) document so as to concisely express the most important theme of the document, has been an active area of experimentation and development.A recent trend of research is to employ the language modeling (LM) approach for important sentence selection, which has proven to be effective for performing extractive summarization in an unsupervised fashion.However, one of the major challenges facing the LM approach is how to formulate the sentence models and estimate their parameters more accurately for each text (or spoken) document to be summarized.This paper extends this line of research and its contributions are three-fold.First, we propose a positional language modeling framework using different granularities of position-specific information to better estimate the sentence models involved in summarization.Second, we also explore to integrate the positional cues into relevance modeling through a pseudo-relevance feedback procedure.Third, the utilities of the various methods originated from our proposed framework and several well-established unsupervised methods are analyzed and compared extensively.Empirical evaluations conducted on a broadcast news summarization task seem to demonstrate the performance merits of our summarization methods.

Schematic metro maps provide an effective means of simplifying the geographical configuration of public rapid transportation systems. Nonetheless, travelers still find it difficult to identify routes of a specific topology on the maps because it is usually hidden behind the conventional octilinear layout of the entire map. In this paper, we present an approach to designing schematic maps with loop lines, which are drawn as circles together with annotation labels for guiding different traveling purposes. Our idea here is to formulate the aesthetic criteria as mathematical constraints in the mixed-integer programming model, which allows us to either align stations on the loop line at a grid if they are interchange stations or noninterchange stations on a circle otherwise. We then distribute the annotation labels associated with stations on the loop line evenly to the four side boundary of the map domain in order to make full use of the annotation space, while maximally avoiding intersections between leader lines and the metro network by employing a flow network algorithm. Finally, we present several experimental results generated by our prototype system to demonstrate the feasibility of the proposed approach.

Extractive speech summarization, which purports to select an indicative set of sentences from a spoken document so as to succinctly represent the most important aspects of the document, has garnered much research over the years. In this paper, we cast extractive speech summarization as an ad-hoc information retrieval (IR) problem and investigate various language modeling (LM) methods for important sentence selection. The main contributions of this paper are four-fold. First, we explore a novel sentence modeling paradigm built on top of the notion of relevance, where the relationship between a candidate summary sentence and a spoken document to be summarized is discovered through different granularities of context for relevance modeling. Second, not only lexical but also topical cues inherent in the spoken document are exploited for sentence modeling. Third, we propose a novel clarity measure for use in important sentence selection, which can help quantify the thematic specificity of each individual sentence that is deemed to be a crucial indicator orthogonal to the relevance measure provided by the LM-based methods. Fourth, in an attempt to lessen summarization performance degradation caused by imperfect speech recognition, we investigate making use of different levels of index features for LM-based sentence modeling, including words, subword-level units, and their combination. Experiments on broadcast news summarization seem to demonstrate the performance merits of our methods when compared to several existing well-developed and/or state-of-the-art methods.

Extractive speech summarization, aiming to automatically select an indicative set of sentences from a spoken document so as to concisely represent the most important aspects of the document, has become an active area for research and experimentation. An emerging stream of work is to employ the language modeling (LM) framework along with the Kullback-Leibler divergence measure for extractive speech summarization, which can perform important sentence selection in an unsupervised manner and has shown preliminary success. This paper presents a continuation of such a general line of research and its main contribution is two-fold. First, by virtue of pseudo-relevance feedback, we explore several effective sentence modeling formulations to enhance the sentence models involved in the LM-based summarization framework. Second, the utilities of our summarization methods and several widely-used methods are analyzed and compared extensively, which demonstrates the effectiveness of our methods.

Extractive summarization is intended to automatically select a set of representative sentences from a text or spoken document that can concisely express the most important topics of the document. Language modeling (LM) has been proven to be a promising framework for performing extractive summarization in an unsupervised manner. However, there remain two fundamental challenges facing existing LM-based methods. One is how to construct sentence models involved in the LM framework more accurately without resorting to external information sources. The other is how to additionally take into account the sentence-level structural relationships embedded in a document for important sentence selection. To address these two challenges, in this paper we explore a novel approach that generates overlapped clusters to extract sentence relatedness information from the document to be summarized, which can be used not only to enhance the estimation of various sentence models but also to allow for the sentence-level structural relationships for better summarization performance. Further, the utilities of our proposed methods and several state-of-the-art unsupervised methods are analyzed and compared extensively. A series of experiments conducted on a Mandarin broadcast news summarization task demonstrate the effectiveness and viability of our method. Index Terms: speech summarization, language modeling, clustering, relevance, sentence relatedness

Metro maps with thumbnail photographs serve as common travel guides for providing sufficient information to meet the requirements of travelers in the cities. However, conventional methods attempt to minimize the total distance between stations and labels while maximizing the number of the labels rather than further taking into account the overall balance of the spatial distribution of labels. This paper presents an entropy-based approach for effectively annotating large annotation labels sufficiently close to the metro stations. Our idea is to decompose the entire labeling space intro regions bounded by the metro lines, and then further partition each region into Voronoi cells, each of which is reserved for a station to be annotated. This is accomplished by incorporating a new genetic-based optimization, while the fitness of the decomposition is evaluated by the entropy of the relative coverage ratios of such Voronoi cells. We also include several design examples to demonstrate that the proposed approach successfully distributes large labels around the metro network with minimal user intervention.

Abstract Annotating metro maps with thumbnail photographs is a commonly used technique for guiding travelers. However, conventional methods usually suffer from small labeling space around the metro stations especially when they are interchange stations served by two or more metro lines. This paper presents an approach for aesthetically designing schematic metro maps while ensuring effective placement of large annotation labels that are sufficiently close to their corresponding stations. Our idea is to distribute such labels in a well‐balanced manner to labeling regions around the metro network first and then adjust the lengths of metro line and leader line segments, which allows us to fully maximize the space coverage of the entire annotated map. This is accomplished by incorporating additional constraints into the conventional mixed‐integer programming formulation, while we devised a three‐step algorithm for accelerating the overall optimization process. We include several design examples to demonstrate the spatial efficiency of the map layout generated using the proposed approach through minimal user intervention.

Abstract When providing travel guides for a specific route in a metro network, we often place the route around the center of the map and annotate stations on the route with thumbnail photographs. Nonetheless, existing methods do not offer an effective means of customizing the network layout in order to accommodate such large annotation labels while preserving its planar embedding. This paper presents a new approach for designing the metro map layout in order to annotate stations on a specific travel route with large annotation labels. Our idea is to elongate the travel route to be straight along the centerline of the map so that we can systematically annotate such stations with external labels. This is accomplished by extending the conventional mixed‐integer programming technique for computing octilinear layouts where orientations inherent to the metro line segments are plausibly rearranged. The stations are then connected with external labels through leaders while minimizing intersections with metro lines for enhancing visual clarity. We present several design examples of metro maps and user studies to demonstrate that the proposed aesthetic criteria successfully direct viewers’ attention to specific travel routes.

Abstract Constructing a 3D papercraft model from its unfolding has been fun for both children and adults since we can reproduce virtual 3D models in the real world. However, facilitating the papercraft construction process is still a challenging problem, especially when the shape of the input model is complex in the sense that it has large variation in its surface curvature. This paper presents a new heuristic approach to unfolding 3D triangular meshes without any shape distortions, so that we can construct the 3D papercraft models through simple atomic operations for gluing boundary edges around the 2D unfoldings. Our approach is inspired by the concept of topological surgery, where the appearance of boundary edges of the unfolded closed surface can be encoded using a symbolic representation. To fully simplify the papercraft construction process, we developed a genetic‐based algorithm for unfolding the 3D mesh into a single connected patch in general, while optimizing the usage of the paper sheet and balance in the shape of that patch. Several examples together with user studies are included to demonstrate that the proposed approach works well for a broad range of 3D triangular meshes.

Although randomization often increases the degree of flexibility in system design, analyzing system properties in the probabilistic framework introduces additional difficulties and challenges in comparison with their nonprobabilistic counterparts. In this paper, we focus on probabilistic versions of two problems frequently encountered in discrete event systems, namely, the reachability and forbidden-state problems. Our main concern is to see whether there exists a (or for every) non-blocking or fair control policy under which a given finite- or infinite-state system can be guided to reach (or avoid) a set of goal states with probability one. For finite-state systems, we devise algorithmic approaches which result in polynomial time solutions to the two problems. For infinite-state systems modelled as Petri nets, the problems are undecidable in general. For the class of persistent Petri nets, we establish a valuation approach through which the convergence behavior of a system is characterized, which in turn yields solutions to the reachability and forbidden-state problems.

Augmented marked graphs (AMGs) are extensions of marked graphs that allow resource sharing. It has been shown that AMGs are useful for modeling and analyzing certain types of flexible manufacturing systems (FMSs). To our knowledge, the techniques developed for analyzing AMGs are mostly based upon checking certain Petri net structures such as siphons. This article exploits the integer linear programming approach for the analysis of a subclass of AMGs called decomposable AMGs. We show that reachability between two configurations of a decomposable AMG can be equated with solving an instance of integer linear programming. We further extend our technique to model checking a type of branching time temporal logics. Examples arisen in FMSs are used to demonstrate the application of our technique.

The text annotation system of a word processor software provides the user the function of memorandums in editing a document. In the visualization interface of the annotation system, each marked word is connected to a text comment label on the right side of the document by a polygonal line. Such a visualization interface can be viewed as a one-side boundary labeling, in which each point site is uniquely connected to a label placed on the right side of an enclosing rectangle by a leader, which may be a rectilinear or straight line segment. In the literature, there have existed some applications and some theoretical results for the boundary labeling. In this paper, we investigate the boundary labeling from the application on the annotation system. For this kind of labeling, if the number of labels on the right side is large, the leaders may be drawn too densely to be recognized easily. Therefore, in this paper, we propose a polynomial time algorithm for the so-called 1.5-side boundary labeling for the annotation system, in which, in addition to being connected to the right side directly, leaders can be routed to the left side temporarily and then finally to the right side. In addition, we investigate a problem for two-side boundary labeling (for the annotation system) that was not discussed previously. We show the problem to be NP-complete, and then proposed a heuristic based on the genetic algorithm to solve it. The experimental results reveal that our approach performs well.

Question classification (QC) plays a key role in automated question answering (QA) systems. In Chinese QC, for example, a question is analyzed and then labeled with the question type it belongs to and the expected answer type. In this paper, we propose a novel method of Chinese QC that integrates syntactic tags and semantic tags into an alignment-based approach. We adopt a template alignment (TA) algorithm to process large collections of Chinese questions and compare the classification results with those of INFOMAP, a human annotated knowledge inference engine for Chinese questions. We experimented with two approaches for the proposed system: a majority algorithm and a machine learning method that uses Support Vector Machine (SVM). The TA algorithm performs well with both approaches. The experimental results show that the accuracy achieved by TA (85.5%) is comparable to that of INFOMAP (88%). In contrast, QC based on the SVM approach, which incorporates syntactic features and TA yields an accuracy rate of 91.5%.

The majority of program editors available on the market support the view of a directory-explorer style to display only those code lines of interest. Among them, the fisheye and the fractal views of source code (in which each line has a value reflecting the degree of interest and importance) have received a lot of attention in the literature. In information visualization, drawing trees based on fractal theory also plays an interesting role as the so-called balloon drawing of hierarchical data includes two models: the fractal and the SNS (subtrees with nonuniform sizes) models. It is therefore natural to consider a new source code visualization style based on the SNS model of balloon drawing. A main feature of the SNS view is that the value of each line reflects the number of its descendants when the source code is viewed as a tree structure. Unlike the view of a directory- explorer style, the multiscalable font mode (which was originally utilized in the fractal view of source code) displays all the lines in such a way that each line has the font size proportional to its value. In this paper, we investigate various issues concerning the multiscalable font modes of the fish- eye, the fractal, and the SNS views of source code, in hope of providing guidelines for the programmer to better comprehend the program code in practice.

The conventional force-directed methods for drawing undirected graphs are based on either vertex-vertex repulsion or vertex-edge repulsion. In this paper, we propose a new force-directed method based on edge-edge repulsion to draw graphs. In our framework, edges are modelled as charged springs, and a final drawing can be generated by adjusting positions of vertices according to spring forces and the repulsive forces, derived from potential fields, among edges. Different from the previous methods, our new framework has the advantage of overcoming the problem of zero angular resolution, guaranteeing the absence of any overlapping of edges incident to the common vertex. Given graph layouts probably generated by classical algorithms as the inputs to our algorithm, experimental results reveal that our approach produces promising drawings (especially for trees and hypercubes) not only preserving the original properties of a high degree of symmetry and uniform edge length, but also preventing zero angular resolution. By allowing vertex-vertex overlapping, our algorithm also results in more symmetrical drawings.

IEEE 802.11, the standard of wireless local area networks (WLANs), allows the coexistence of asynchronous and time-bounded traffic using the distributed coordination function (DCF) and point coordination function (PCF) modes of operations, respectively. In spite of its increasing popularity in real-world applications, the protocol suffers from the lack of any priority and access control policy to cope with various types of multimedia traffic, as well as user mobility. To expand support for applications with quality-of-service (QoS) requirements, the 802.11E task group was formed to enhance the original IEEE 802.11 medium access control (MAC) protocol. However, the problem of choosing the right set of MAC parameters and QoS mechanism to provide predictable QoS in IEEE 802.11 networks remains unsolved. In this paper, we propose a polling with nonpreemptive priority-based access control scheme for the IEEE 802.11 protocol. Under such a scheme, modifying the DCF access method in the contention period supports multiple levels of priorities such that user handoff calls can be supported in wireless LANs. The proposed transmit-permission policy and adaptive bandwidth allocation scheme derive sufficient conditions such that all the time-bounded traffic sources satisfy their time constraints to provide various QoS guarantees in the contention free period, while maintaining efficient bandwidth utilization at the same time. In addition, our proposed scheme is provably optimal for voice traffic in that it gives minimum average waiting time for voice packets. In addition to theoretical analysis, simulations are conducted to evaluate the performance of the proposed scheme. As it turns out, our design indeed provides a good performance in the IEEE 802.11 WLAN's environment, and can be easily incorporated into the hybrid coordination function (HCF) access scheme in the IEEE 802.11e standard.

Verification of various properties associated with concurrent/distributed systems is critical in the process of designing and analyzing dependable systems. While techniques for the automatic verification of finite-state systems are relatively well studied, one of the main challenges in the domain of verification is concerned with the development of new techniques capable of coping with problems beyond the finite state framework. We investigate a number of problems closely related to dependability analysis in the context of probabilistic infinite-state systems modelled by probabilistic conflict-free Petri nets. Using a valuation method, we are able to demonstrate effective procedures for solving the termination with probability 1, the self-stabilization with probability 1, and the controllability with probability 1 problems in a unified framework.

We use /spl omega/-automata (i.e., automata over infinite words) as a device for representing bilevel images. A major advantage of our approach, as opposed to using the conventional finite automata, lies in that /spl omega/-automata are capable of representing image objects of zero size, such as lines and points. To demonstrate the feasibility of our approach, we also show how a number of image processing operations, including shift, flip, rotation, complement, boundary, difference, union, intersection, and size, can be effectively carried out in the framework of /spl omega/-automata. In particular, the size of an image represented by an /spl omega/-automaton is measured based on the theory of Markov chains. In comparison with other automata-based image representation schemes reported in the literature, our approach is capable of supporting a richer set of operations, which can be performed on the automata directly and easily.

Compressed pattern matching refers to the process of, given a text in a compressed form and a pattern, finding all the occurrences of the pattern in the text without decompression. To utilize bandwidth more effectively in the Internet environment, it is highly desirable that data be kept and sent over the Internet in compressed form. In order to support information retrieval for compressed data, compressed pattern matching has been gaining increasing attention from both theoretical and practical viewpoints. We design and implement a dictionary-based compressed pattern matching algorithm. Our algorithm takes advantage of the dictionary structure common in the LZ78 family. With the help of a slightly modified dictionary structure, we are able to do 'block decompression' (a key in many existing compressed pattern matching schemes) as well as pattern matching on-the-fly, resulting in performance improvement as our experimental results indicate.

We propose a force-directed approach for drawing graphs in a nearly symmetric fashion. Our algorithm is built upon recent theoretical results on maximum symmetric subgraphs. Knowing the sequence of edge contractions sufficient for turning an asymmetric graph into a symmetric subgraph, our approach to symmetric drawing begins by drawing a graph's maximum symmetric subgraph using a force-directed method; the contracted edges are then re-inserted back into the drawing. By considering symmetry as the underlying aesthetic criterion, our algorithm provides better drawings than conventional spring algorithms, as our experimental results indicate.

The problem of deciding whether an infinite-state system is self-stabilizing or not is investigated from the decidability viewpoint. We develop a unified strategy through which checking self-stabilization is shown to be decidable for one-counter machines and conflict-free Petri nets. Our strategy relies on the reachability sets being semilinear; as well as on the capability of extracting periodic behaviors of infinite computations, which, in turn, facilitates the expression of self-stabilization by Presburger Arithmetic. As fairness is frequently used as a qualitative measure to capture the notion of a quantitative measure of 'something happens with probability one,' it is of interest to examine the fair version of the self-stabilization problem, i.e., the problem of asking whether all 'fair' infinite computations eventually become self-stabilizing. We propose a potential method through which the problem is shown to be decidable for conflict-free Petri nets.

In a paper by Raghavan, Cohoon, and Sahni (see J. Algorithms, vol. 7, p. 232-57, 1986), the single layer single bend wirability problem has been shown to be solvable in polynomial time for two-terminal nets. In this paper, we investigate the problem for a slightly generalized model in which nets are allowed to have two or more terminals. We show that for multiterminal nets, the single bend wirability problem becomes NP-complete, even when all wires are 'short' (i.e. of fixed length).>

In this paper, we define a restricted logspace oracle hierarchy which turns out to be equivalent to the logspace alternation hierarchy (of Chandra, Kozen and Stockmeyer) and thus is contained within the second level of the logspace oracle heirarchy (of Ruzzo, Simon and Tompa). We then examine problems concerning various types of “fair” computations with respect to $\omega $-Finite State Machines ($\omega $-FSM’s) and $\omega $-One Counter Machines ($\omega $-1CM’s). For example, we consider the nonemptiness problem for $\omega $-FSM’s and $\omega $-1CM’s where acceptance is defined in the usual fashion, but with a fairness constraint imposed on accepting computations. Our results yield problems that are complete not only for LOGSPACE and PTIME but the second and third levels of the restricted logspace oracle hierarchy as well. As far as we know, these are the first natural problems shown to be complete for various levels of the logspace alternation hierarchy. The problems are also of independent interest. In fact, the nonemptiness problem (with fairness constraints) for w-machines has been shown to have immediate applications to the verification of concurrent finite state programs. Furthermore, the results can be used to strengthen known results concerning some related fairness problems that involve temporal logic (e.g. model checking).