16282494
Area Requirements for Drawing Hierarchically Planar Graphs
In this paper, we investigate area requirements for drawing s-t hierarchically planar graphs by straight-lines. Two drawing standards will be discussed: 1) each vertex is represented by a point and 2) grid visibility representation (that is, a line segment is allowed to represent a vertex). For the first drawing standard, we show an exponential area lower bound needed for drawing hierarchically planar graphs. The lower bound holds even for hierarchical graphs without transitive arcs, in contrast to the results for upward planar drawing. Applications of some existing algorithms from upward drawing can guarantee the quadratic drawing area for grid visibility representation but do not necessarily guarantee the minimum drawing area. Motivated by this, we will present another grid visibility drawing algorithm which is efficient and guarantees the minimum drawing area.
17501980
Term Graph Model for Text Classification
Most existing text classification methods (and text mining methods at large) are based on representing the documents using the traditional vector space model. We argue that important information, such as the relationship among words, is lost. We propose a term graph model to represent not only the content of a document but also the relationship among the keywords. We demonstrate that the new model enables us to define new similarity functions, such as considering rank correlation based on PageRank-style algorithms, for the classification purpose. Our preliminary results show promising results of our new model.
14038708
Efficiently computing frequent tree-like topology patterns in a Web environment
Data mining has recently emerged in a number of real life applications, such as banking, supermarketing, and interneting. The authors investigate a novel data mining problem derived from the applications of WWW. They present an efficient algorithm for solving the problem. The initial implementation suggests that the algorithm is very efficient and scalable in practice.
1993887
Locating Motifs in Time-Series Data
Finding motifs in time-series is proposed to make clustering of time-series subsequences meaningful, because most existing algorithms of clustering time-series subsequences are reported meaningless in recent studies. The existing motif finding algorithms emphasize the efficiency at the expense of quality, in terms of the number of time-series subsequences in a motif and the total number of motifs found. In this paper, we formalize the problem as a continuous top-k motif balls problem in an m-dimensional space, and propose heuristic approaches that can significantly improve the quality of motifs with reasonable overhead, as shown in our experimental studies.
4018890
Clustering Moving Objects for Spatio-temporal Selectivity Estimation
Many spatio-temporal applications involve managing and querying moving objects. In such an environment, predictive spatio-temporal queries become an important query class to be processed to capture the nature of moving objects. In this paper, we investigated the problem of selectivity estimation for predictive spatio-temporal queries. We propose a novel histogram technique based on a clustering paradigm. To avoid expensive computation costs, we developed linear time heuristics to construct such a histogram. Our performance study indicated that the new techniques improve the accuracy of the existing techniques by one order of magnitude.
6221918
Efficiently Matching Proximity Relationships in Spatial Databases
Spatial data mining recently emerges from a number of real applications, such as real-estate marketing, urban planning, weather forecasting, medical image analysis, road traffic accident analysis, etc. It demands for efficient solutions for many new, expensive, and complicated problems. In this paper, we investigate a proximity matching problem among clusters and features. The investigation involves proximity relationship measurement between clusters and features. We measure proximity in an average fashion to address possible nonuniform data distribution in a cluster. An efficient algorithm, for solving the problem, is proposed and evaluated. The algorithm applies a standard multistep paradigm in combining with novel lower and upper proximity bounds. The algorithm is implemented in several different modes. Our experiment results do not only give a comparison among them but also illustrate the efficiency of the algorithm.
2250003
ICDAR 2003 robust reading competitions: entries, results, and future directions
Abstract.This paper describes the robust reading competitions for ICDAR 2003. With the rapid growth in research over the last few years on recognizing text in natural scenes, there is an urgent need to establish some common benchmark datasets and gain a clear understanding of the current state of the art. We use the term ‘robust reading’ to refer to text images that are beyond the capabilities of current commercial OCR packages. We chose to break down the robust reading problem into three subproblems and run competitions for each stage, and also a competition for the best overall system. The subproblems we chose were text locating, character recognition and word recognition. By breaking down the problem in this way, we hoped to gain a better understanding of the state of the art in each of the subproblems. Furthermore, our methodology involved storing detailed results of applying each algorithm to each image in the datasets, allowing researchers to study in depth the strengths and weaknesses of each algorithm. The text-locating contest was the only one to have any entries. We give a brief description of each entry and present the results of this contest, showing cases where the leading entries succeed and fail. We also describe an algorithm for combining the outputs of the individual text locators and show how the combination scheme improves on any of the individual systems.
2200679
A Distributed Joint Channel-Assignment, Scheduling and Routing Algorithm for Multi-Channel Ad-hoc Wireless Networks
The capacity of ad hoc wireless networks can be substantially increased by equipping each network node with multiple radio interfaces that can operate on multiple non-overlapping channels. However, new scheduling, channel-assignment, and routing algorithms are required to fully utilize the increased bandwidth in multi-channel multi-radio ad hoc networks. In this paper, we develop a fully distributed algorithm that jointly solves the channel-assignment, scheduling and routing problem. Our algorithm is an online algorithm, i.e., it does not require prior information on the offered load to the network, and can adapt automatically to the changes in the network topology and offered load. We show that our algorithm is provably efficient. That is, even compared with the optimal centralized and offline algorithm, our proposed distributed algorithm can achieve a provable fraction of the maximum system capacity. Further, the achievable fraction that we can guarantee is larger than that of some other comparable algorithms in the literature.
18241581
An Associative Information Visualizer
The following item is made available as a courtesy to scholars by the author(s) and Drexel University Library and may contain materials and content, including computer code and tags, artwork, text, graphics, images, and illustrations (Material) which may be protected by copyright law. Unless otherwise noted, the Material is made available for non profit and educational purposes, such as research, teaching and private study. For these limited purposes, you may reproduce (print, download or make copies) the Material without prior permission. All copies must include any copyright notice originally included with the Material. You must seek permission from the authors or copyright owners for all uses that are not allowed by fair use and other provisions of the U.S. Copyright Law. The responsibility for making an independent legal assessment and securing any necessary permission rests with persons desiring to reproduce or use the Material.
2535403
Visualization for the document space
An information retrieval frame work that promotes graphical displays, and that will make documents in the computer visualizable to the searcher, is described. As examples of such graphical displays, two simulation results of using a Kohonen feature map to generate map displays for information retrieval are presented and discussed. The map displays are a mapping from a high-dimensional document space to a two-dimensional space. They show document relationships by various visual cues, such as dots, links, clusters, and areas, as well as their measurement and spatial arrangement. Using the map displays as an interface for document retrieval systems, the user is provided with richer visual information to support browsing and searching.<<ETX>>
28914040
Low-Complexity Distributed Scheduling Algorithms for Wireless Networks
We consider the problem of distributed scheduling in wireless networks. We present two different algorithms whose performance is arbitrarily close to that of maximal schedules, but which require low complexity due to the fact that they do not necessarily attempt to find maximal schedules. The first algorithm requires each link to collect local queue-length information in its neighborhood, and its complexity is independent of the size and topology of the network. The second algorithm is presented for the node-exclusive interference model, does not require nodes to collect queue-length information even in their local neighborhoods, and its complexity depends only on the maximum node degree in the network.