Theory and Algorithms Commons^™

Link Lifetimes And Randomized Neighbor Selection In Dhts, Zhongmei Yao, Dmitri Loguinov

Computer Science Faculty Publications

Several models of user churn, resilience, and link lifetime have recently appeared in the literature [12], [13], [34], [35]; however, these results do not directly apply to classical Distributed Hash Tables (DHTs) in which neighbor replacement occurs not only when current users die, but also when new user arrive into the system, and where replacement choices are often restricted to the successor of the failed zone in the DHT space. To understand neighbor churn in such networks, this paper proposes a simple, yet accurate, model for capturing link dynamics in structured P2P systems and obtains the distribution of link lifetimes …

Symbolic Links In The Open Directory Project, Saverio Perugini

Computer Science Faculty Publications

We present a study to develop an improved understanding of symbolic links in web directories. A symbolic link is a hyperlink that makes a directed connection from a web page along one path through a directory to a page along another path. While symbolic links are ubiquitous in web directories such as Yahoo!, they are under-studied, and as a result, their uses are poorly understood. A cursory analysis of symbolic links reveals multiple uses: to provide navigational shortcuts deeper into a directory, backlinks to more general categories, and multiclassification. We investigated these uses in the Open Directory Project (ODP), the …

Prostate Segmentation On Pelvic Ct Images Using A Genetic Algorithm, Payel Ghosh, Melanie Mitchell

Computer Science Faculty Publications and Presentations

A genetic algorithm (GA) for automating the segmentation of the prostate on pelvic computed tomography (CT) images is presented here. The images consist of slices from three-dimensional CT scans. Segmentation is typically performed manually on these images for treatment planning by an expert physician, who uses the “learned” knowledge of organ shapes, textures and locations to draw a contour around the prostate. Using a GA brings the flexibility to incorporate new “learned” information into the segmentation process without modifying the fitness function that is used to train the GA. Currently the GA uses prior knowledge in the form of texture …

Enabling Synergy Between Psychology And Natural Language Processing For E-Government: Crime Reporting And Investigative Interview System, Alicia Iriberri '06, Chih Hao Ku '12, Gondy Leroy

CGU Faculty Publications and Research

We are developing an automated crime reporting and investigative interview system. The system incorporates cognitive interview techniques to maximize witness memory recall, and information extraction technology to extract and annotate crime entities from witness narratives and interview responses. Evaluations of the IE components of the system show that it captures 70 to 77% of information from witness narratives with 93 to 100% precision. Our development goal is for the system to approximate progressively the performance effectiveness of a human investigative interviewer and to generate graphical visualizations of crime report information.

Natural Language Processing And E-Government: Crime Information Extraction From Heterogeneous Data Sources, Chih Hao Ku '12, Alicia Iriberri '06, Gondy Leroy

CGU Faculty Publications and Research

Much information that could help solve and prevent crimes is never gathered because the reporting methods available to citizens and law enforcement personnel are not optimal. Detectives do not have sufficient time to interview crime victims and witnesses. Moreover, many victims and witnesses are too scared or embarrassed to report incidents. We are developing an interviewing system that will help collect such information. We report here on one component, the crime information extraction module, which uses natural language processing to extract crime information from police reports, newspaper articles, and victims’ and witnesses’ crime narratives. We tested our approach with two …

A Multiprocessor Parallel Approach To Bit-Parallel Approximate String Matching, Elias Anwar Chibli

Theses Digitization Project

The purpose of this project is to present with empirical results that a parallel design with the use of multiple processors can be successfully applied along with bit-parallel approximate string matching algorithms to solve practical bioinformatics problems. It will demonstrate that nearly optimal speedup can be achieved with a cluster of between two and eight workstations using MPI (Message Passing Interface), directly decreasing the total latency required to perform a string matching problem.

Morphology Independent Dynamic Locomotion Control For Virtual Characters, Adrian Boeing

Research outputs pre 2011

Physically based animation of virtual characters is an attractive technology for computer games. It enables characters to dynamically react to interactions with the environment. Existing dynamic simulation controllers are often complex to understand and manipulate, and so are of limited use for animators. This paper presents an extended spline-based control strategy similar to splines used in standard keyframe animation techniques. Unlike existing dynamic control strategies, this allows animators to modify the control system parameters in a manner similar to traditional kinematic animation techniques. A genetic algorithm is employed to produce the initial control parameters for the desired gait, and extend …

Traffic Analysis Of Udp-Based Flows In Ourmon, Jim Binkley, Divya Parekh

Computer Science Faculty Publications and Presentations

We present a custom UDP flow tuple with an IP address key and a set of simple related statistical attributes. Attributes are used to calculate a per host metric called the UDP work weight which roughly measures the amount of network noise caused by a host. The work weight is used to produce a near real-time sorted top N report for UDP host tuples. We also present a derived attribute based on an algorithm called the UDP guesstimator. The UDP guesstimator roughly classifies port report hosts into various traffic categories including security threats (DOS/scanning) or P2P hosts based on high …

Graphics Processor Based Implementation Of Bioinformatics Codes, Andrew Bellenir, Christian Trefftz, Greg Wolffe

Student Summer Scholars Manuscripts

We created a powerful computing platform based on video cards with the goal of accelerating the performance of bioinformatics codes. To satisfy the demands of the video gaming industry, modern graphics processing units (GPUs) have become very advanced computational devices, using a large set of stream processors to render multiple pixels in parallel. Recently, computer scientists have taken interest in a GPU's ability to execute a single instruction on multiple data (SIMD computation) for general applications, as opposed to graphics processing only. This is known as general purpose computation on a graphics processing unit, or GPGPU.

Our project was comprised …

Object Detection And Classification With Applications To Skin Cancer Screening, Jonathan Blackledge, Dmitryi Dubovitskiy

Articles

This paper discusses a new approach to the processes of object detection, recognition and classification in a digital image. The classification method is based on the application of a set of features which include fractal parameters such as the Lacunarity and Fractal Dimension. Thus, the approach used, incorporates the characterisation of an object in terms of its texture.

The principal issues associated with object recognition are presented which includes two novel fast segmentation algorithms for which C++ code is provided. The self-learning procedure for designing a decision making engine using fuzzy logic and membership function theory is also presented and …

Efficient Corona Training Protocols For Sensor Networks, Alan A. Bertossi, Stephan Olariu, Cristina M. Pinotti

Computer Science Faculty Publications

Phenomenal advances in nano-technology and packaging have made it possible to develop miniaturized low-power devices that integrate sensing, special-purpose computing, and wireless communications capabilities. It is expected that these small devices, referred to as sensors, will be mass-produced and deployed, making their production cost negligible. Due to their small form factor and modest non-renewable energy budget, individual sensors are not expected to be GPS-enabled. Moreover, in most applications, exact geographic location is not necessary, and all that the individual sensors need is a coarse-grain location awareness. The task of acquiring such a coarse-grain location awareness is referred to as training. …

Web Search Algorithms And Pagerank, Laleh Samarbakhsh

Theses and Dissertations (Comprehensive)

The mathematical theory underlying the Google search engine is the PageRank algorithm, first introduced by Sergey Brin and Lawrence Page, the founders of Google. A ranking of web pages is made considering many criteria. PageRank exploits the graph structure of the web. The web’s hyperlink structure forms a massive directed graph, where the web pages are presented as nodes and hyperlinks as edges. The PageRank equation finds a score by solving a recursive equation which calculates the PageRank vector. The PageRank vector is the stationary distribution of an ergodic Markov chain. The Perron-Frobenius theorem ensures that the primitive matrix produced …

Vegetation Identification Based On Satellite Imagery, Vamsi K.R. Mantena, Ramu Pedada, Srinivas Jakkula, Yuzhong Shen, Jiang Li, Hamid R. Arabnia (Ed.)

Electrical & Computer Engineering Faculty Publications

Automatic vegetation identification plays an important role in many applications including remote sensing and high performance flight simulations. This paper presents a method to automatically identify vegetation based upon satellite imagery. First, we utilize the ISODATA algorithm to cluster pixels in the images where the number of clusters is determined by the algorithm. We then apply morphological operations to the clustered images to smooth the boundaries between clusters and to fill holes inside clusters. After that, we compute six features for each cluster. These six features then go through a feature selection algorithm and three of them are determined to …

Reed-Solomon Codes Construction & Decoding, Samuel J. Parsons

Honors Capstones

Capstone submitted as a graduation requirement for the BSU Honors Program.

Study Of The Minimum Spanning Hyper-Tree Routing Algorithm In Wireless Sensor Networks, Ting Yang, Yugeng Sun, Zhaoxia Wang, Juwei Zhang, Yingqiang Ding

Research Collection School Of Computing and Information Systems

Designing energy-efficient routing protocols to effectively increase the networks' lifetime and provide the robust network service is one of the important problems in the research of wireless sensor networks. Using the hyper-graph theory, the paper represents large-scale wireless sensor networks into a hyper-graph model, which can effectively decrease the control messages in routing process. Based on this mathematic model, the paper presents the minimum spanning hyper-tree routing algorithm in synchronous wireless sensor networks (MSHT-SN), which builds a minimum energy consumption tree for data collection from multi-nodes to Sink node. The validity of the algorithm is proved by the theatrical analysis. …

Mining Web-Functional Dependencies For Flexible Information Access, Saverio Perugini, Naren Ramakrishnan

Computer Science Faculty Publications

We present an approach to enhancing information access through Web structure mining in contrast to traditional approaches involving usage mining. Specifically, we mine the hardwired hierarchical hyperlink structure of Web sites to identify patterns of term-term co-occurrences we call Web functional dependencies (FDs). Intuitively, a Web FD ‘x y’ declares that all paths through a site involving a hyperlink labeled x also contain a hyperlink labeled y. The complete set of FDs satisfied by a site help characterize (flexible and expressive) interaction paradigms supported by a site, where a paradigm is the set of explorable sequences therein. …

An Adaptive And Non-Linear Technique For Enhancement Of High Contrast Images, Saibabu Arigela

Electrical & Computer Engineering Theses & Dissertations

In night time surveillance, there is a possibility of having extremely bright and dark regions in some image frames of a video sequence. Neither the object details in the low intensity areas nor in the high intensity areas can be clearly interpreted. Several image processing techniques have been developed to retrieve meaningful information under low lighting conditions. The algorithm based on integrated neighborhood dependency of pixel characteristics, and that based on the illuminance reflectance model perform well for improving the visual quality of digital images captured under extremely low and nonuniform lighting conditions. But these techniques cannot perform well in …

Neighborhood Defined Adaboost Based Mixture Of Color Components For Efficient Skin Segmentation, Ramya Reddy Maaram

Electrical & Computer Engineering Theses & Dissertations

A skin segmentation algorithm robust to illumination changes and skin-like backgrounds is developed in this thesis. So far skin pixel classification has been limited to only individual color spaces and there has not been a comprehensive evaluation of which color components or combination of color components would provide the best classification accuracy, Color components in a given color space form the feature set for the classification of skin pixels. The combination of the color components or the features present within a single color space may not be the best when it comes to skin pixel classification as the discriminatory power …

Distributed Cluster-Based Outlier Detection In Wireless Sensor Networks, Swetha Gali

Electrical & Computer Engineering Theses & Dissertations

Wireless sensor networks find several potential applications in a variety of fields, such as environmental monitoring and control, battlefields, surveillance, smart buildings, human health monitoring, etc. These sensor networks consist of a large number of very tiny, inexpensive, and low power sensor nodes, which are deployed in a variety of harsh environments that may result in the sensor data getting corrupted. It is thus critical to detect and report these abnormal values in the sensor data, in order to have a better understanding of the monitored environment. Detection of the abnormal values is of special interest for the sensor network …

Novelty Detection For Cross-Lingual News Stories With Visual Duplicates And Speech Transcripts, Xiao Wu, Alexander G. Hauptmann, Chong-Wah Ngo

Research Collection School Of Computing and Information Systems

An overwhelming volume of news videos from different channels and languages is available today, which demands automatic management of this abundant information. To effectively search, retrieve, browse and track cross-lingual news stories, a news story similarity measure plays a critical role in assessing the novelty and redundancy among them. In this paper, we explore the novelty and redundancy detection with visual duplicates and speech transcripts for cross-lingual news stories. News stories are represented by a sequence of keyframes in the visual track and a set of words extracted from speech transcript in the audio track. A major difference to pure …

A Genetic Algorithm For Cellular Manufacturing Design And Layout, Xiaodan Wu, Chao-Hsien Chu, Yunfeng Wang, Weili Yan

Research Collection School Of Computing and Information Systems

Cellular manufacturing (CM) is an approach that can be used to enhance both flexibility and efficiency in today’s small-to-medium lot production environment. The design of a CM system (CMS) often involves three major decisions: cell formation, group layout, and group schedule. Ideally, these decisions should be addressed simultaneously in order to obtain the best results. However, due to the complexity and NP-complete nature of each decision and the limitations of traditional approaches, most researchers have only addressed these decisions sequentially or independently. In this study, a hierarchical genetic algorithm is developed to simultaneously form manufacturing cells and determine the group …

A Lateral Symmetry Approach To Percentage-Based Hybrid Pattern (Php) Training, Sheng-Uei Guan, Kiruthika Ramanathan

Research Collection School Of Computing and Information Systems

In this paper, we investigate the application of lateral symmetry to supervised learning using genetic algorithms. The hypothesis is motivated by the presence of symmetry in the animal brain and by research results showing approximately equal task division between the two hemispheres of the brain. In this paper, each training pattern is considered a task. By applying the concept of lateral symmetry, we use global training (a typically right brained activity) to learn half the tasks and local training (a left brained activity) to learn the rest of the tasks. We verified the use of this Percentage-based Pattern (PHP) training …

Channel Management In Heterogeneous Cellular Networks, Mohammad Hadi Arbabi

Computer Science Theses & Dissertations

Motivated by the need to increase system capacity in the face of tight FCC regulations, modem cellular systems are under constant pressure to increase the sharing of the frequency spectrum among the users of the network.

Key to increasing system capacity is an efficient channel management strategy that provides higher capacity for the system while, at the same time, providing the users with Quality of Service guarantees. Not surprisingly, dynamic channel management has become a high profile topic in wireless communications. Consider a highly populated urban area, where mobile traffic loads are increased due to highway backups or sporting events. …

Near-Duplicate Keyframe Retrieval With Visual Keywords And Semantic Context, Xiao Wu, Wan-Lei Zhao, Chong-Wah Ngo

Research Collection School Of Computing and Information Systems

Near-duplicate keyframes (NDK) play a unique role in large-scale video search, news topic detection and tracking. In this paper, we propose a novel NDK retrieval approach by exploring both visual and textual cues from the visual vocabulary and semantic context respectively. The vocabulary, which provides entries for visual keywords, is formed by the clustering of local keypoints. The semantic context is inferred from the speech transcript surrounding a keyframe. We experiment the usefulness of visual keywords and semantic context, separately and jointly, using cosine similarity and language models. By linearly fusing both modalities, performance improvement is reported compared with the …

A Framework For Dynamizing Succinct Data Structures, Ankur Gupta, Wing K. Hon, Rahul Shah, Jeffery S. Vitter

Scholarship and Professional Work - LAS

We present a framework to dynamize succinct data structures, to encourage their use over non-succinct versions in a wide variety of important application areas. Our framework can dynamize most stateof-the-art succinct data structures for dictionaries, ordinal trees, labeled trees, and text collections.

Efficient Gps Position Determination Algorithms, Thao Nguyen

Theses and Dissertations

This research is aimed at improving the state of the art of GPS algorithms, namely, the development of a closed-form positioning algorithm for a standalone user and the development of a novel differential GPS algorithm for a network of users. The stand-alone user GPS algorithm is a direct, closed-form, and efficient new position determination algorithm that exploits the closed-form solution of the GPS trilateration equations and works in the presence of pseudorange measurement noise for an arbitrary number of satellites in view. A two-step GPS position determination algorithm is derived which entails the solution of a linear regression and updates …

A Multi-Scale Tikhonov Regularization Scheme For Implicit Surface Modeling, Jianke Zhu, Steven C. H. Hoi, Michael R. Lyu

Research Collection School Of Computing and Information Systems

Kernel machines have recently been considered as a promising solution for implicit surface modelling. A key challenge of machine learning solutions is how to fit implicit shape models from large-scale sets of point cloud samples efficiently. In this paper, we propose a fast solution for approximating implicit surfaces based on a multi-scale Tikhonov regularization scheme. The optimization of our scheme is formulated into a sparse linear equation system, which can be efficiently solved by factorization methods. Different from traditional approaches, our scheme does not employ auxiliary off-surface points, which not only saves the computational cost but also avoids the problem …

Residual-Based Measurement Of Peer And Link Lifetimes In Gnutella Networks, Xiaoming Wang, Zhongmei Yao, Dmitri Loguinov

Computer Science Faculty Publications

Existing methods of measuring lifetimes in P2P systems usually rely on the so-called create-based method (CBM), which divides a given observation window into two halves and samples users "created" in the first half every Delta time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we flrst derive a model for CBM and show that small window size or large Delta may lead to highly inaccurate lifetime distributions. We then show that create-based sampling exhibits an inherent …

On Node Isolation Under Churn In Unstructured P2p Networks With Heavy-Tailed Lifetimes, Zhongmei Yao, Xiaoming Wang, Dmitri Loguinov

Computer Science Faculty Publications

Previous analytical studies [12], [18] of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces the probability of user isolation and graph partitioning compared to uniform selection of neighbors. In fact, the second strategy based on random walks on age-weighted graphs demonstrates that for lifetimes with infinite variance, the system …

Enhancing The Performance Of Semi-Supervised Classification Algorithms With Bridging, Jason Yuk Hin Chan, Josiah Poon, Irena Koprinska

Research Collection School Of Computing and Information Systems

Traditional supervised classification algorithms require a large number of labelled examples to perform accurately. Semi-supervised classification algorithms attempt to overcome this major limitation by also using unlabelled examples. Unlabelled examples have also been used to improve nearest neighbour text classification in a method called bridging. In this paper, we propose the use of bridging in a semi-supervised setting. We introduce a new bridging algorithm that can be used as a base classifier in any supervised approach such as co-training or selflearning. We empirically show that classification performance increases by improving the semi-supervised algorithm’s ability to correctly assign labels to previouslyunlabelled …