Theory and Algorithms Commons^™

Beyond Search: Event-Driven Summarization For Web Videos, Richard Hong, Jinhui Tang, Hung-Khoon Tan, Chong-Wah Ngo, Shuicheng Yan, Tat-Seng Chua

Research Collection School Of Computing and Information Systems

The explosive growth of Web videos brings out the challenge of how to efficiently browse hundreds or even thousands of videos at a glance. Given an event-driven query, social media Web sites usually return a large number of videos that are diverse and noisy in a ranking list. Exploring such results will be time-consuming and thus degrades user experience. This article presents a novel scheme that is able to summarize the content of video search results by mining and threading "key" shots, such that users can get an overview of main content of these videos at a glance. The proposed …

Exploring Tweets Normalization And Query Time Sensitivity For Twitter Search, Zhongyu Wei, Wei Gao, Lanjun Zhou, Binyang Li, Kam-Fai Wong

Research Collection School Of Computing and Information Systems

This paper presents our work for the Realtime Adhoc Task of TREC 2011 Microblog Track. Microblog texts like tweets are generally characterized by the inclusion of a large proportion of irregular expressions, such as ill-formed words, which can lead to significant mismatch between query terms and tweets. In addition, Twitter queries are distinguished from Web queries with many unique characteristics, one of which reflects the clearly distinct temporal aspects of Twitter search behavior. In this study, we deal with the first problem by normalizing tweet texts and the second by capturing the temporal characteristics of topic. We divided topics into …

Isomorph-Free Generation Of 2-Connected Graphs With Applications, Derrick Stolee

School of Computing: Technical Reports

Many interesting graph families contain only 2-connected graphs, which have ear decompositions. We develop a technique to generate families of unlabeled 2-connected graphs using ear augmentations and apply this technique to two problems. In the first application, we search for uniquely Kr-saturated graphs and find the list of uniquely K4-saturated graphs on at most 12 vertices, supporting current conjectures for this problem. In the second application, we verify the Edge Reconstruction Conjecture for all 2-connected graphs on at most 12 vertices. This technique can be easily extended to more problems concerning 2-connected graphs.

Roaming Region For Delaunay Triangulation, Romas James Hada

UNLV Theses, Dissertations, Professional Papers, and Capstones

Delaunay graphs have been used in CAD/CAM, sensor network and geographic information systems. We investigate the reliability properties of nodes in Delaunay graphs. For measuring the reliability we formulate the concept of roaming-region for nodes. A node v with large roaming-region r(v) such that v is positioned near the center of r(v) is identified as a reliable node. We develop algorithms for constructing roaming-regions and present an implementation of the proposed algorithm in the Java programming language.

Improved Algorithms For Ear-Clipping Triangulation, Bartosz Kajak

UNLV Theses, Dissertations, Professional Papers, and Capstones

We consider the problem of improving ear-slicing algorithm for triangulating a simple polygon. We propose two variations of ear-slicing technique for generating “good-quality” triangulation. The first approach is based on searching for the best triangle along the boundary. The second approach considers polygon partitioning on a pre-process before applying the ear-slicing. Experimental investigation reveals that both approaches yield better quality triangulation than the standard ear-slicing method.

Structure And Randomness Of The Discrete Lambert Map, Jingjing Chen, Mark Lotts

Mathematical Sciences Technical Reports (MSTR)

We investigate the structure and cryptographic applications of the Discrete Lambert Map (DLM). The mapping is closely related to the Discrete Log Problem, but has received far less attention since it is considered to be a more complicated map that is likely even harder to invert. However, this mapping is quite important because it underlies the security of the ElGamal Digital Signature Scheme. Using functional graphs induced by this mapping, we were able to find non-random properties that could potentially be used to exploit the ElGamal DSS.

The Square Discrete Exponentiation Map, A Wood

Mathematical Sciences Technical Reports (MSTR)

We will examine the square discrete exponentiation map and its properties. The square discrete exponentiation map is a variation on a commonly seen problem in cryptographic algorithms. This paper focuses on understanding the underlying structure of the functional graphs generated by this map. Specifically, this paper focuses on explaining the in-degree of graphs of safe primes, which are primes of the form p = 2q + 1, where q is also prime.

Image Processing – I: Pointing And Target Selection Of Object Using Color Detection Algorithm Through Dsp Processor Tms320c6711, Waseem Ahmed, M. Irfan, Mr. Muzammil, Mr. Yaseen

International Conference on Information and Communication Technologies

In the field of robotic and image vision technologies, the embedded computing and optimization of the image processing algorithm is quite significant in order to provide the real time processing. In the current era, for making the real time system for such high extensive computation and processing for providing the high speed and real time standalone system, several industrial giants continuously providing the solutions which are in the form of dedicated DSP processors and generalized FPGAs. Beside such high speed processor implementation, the image processing based algorithm plays significant role in machine vision based solution for industries, robotic and field …

Network Security: Privacy-Preserving Data Publication: A Review On “Updates” In Continuous Data Publication, Adeel Anjum, Guillaume Raschia

International Conference on Information and Communication Technologies

Preserving the privacy of individuals while publishing their relevant data has been an important problem. Most of previous works in privacy preserving data publication focus on one time, static release of datasets. In multiple publications however, where data is published multiple times, these techniques are unable to ensure privacy of the concerned individuals as just joining either of the releases could result in identity disclosure. In this work, we tried to investigate the major findings in the scenario of continuous data publication, in which the data is not only published multiple times but also modified with INSERTS, UPDATES and DELETE …

Image Processing – I: Automated System For Fingerprint Image Enhancement Using Improved Segmentation And Gabor Wavelets, Amna Saeed, Anam Tariq, Usman Jawaid

International Conference on Information and Communication Technologies

This research revolves around the fingerprint image enhancement. It is used for automated fingerprint identification systems (AFIS) for extracting the best quality fingerprint images. Accurate feature extraction and identification is the basic theme of this enhancement. This paper is on the fingerprint image enhancement using wavelets. Wavelets are famous for their special localization property and orientation flow estimation. The proposed technique is basically comprises of three main steps: segmentation followed by image sharpening and then Gabor wavelet filtering. Segmentation distinguishes between image background and foreground which in turn reduces processing time. Our sharpening stage of enhancement algorithm sharpens the edges …

Application Of Ict: Fram Based Tmr (Triple Modular Redundancy) For Fault Tolerance Implementation, Kashif Sagheer Siddiqui, Mirza Altamash Baig

International Conference on Information and Communication Technologies

The main objective of this paper is to design a Triple modular redundancy test bench using FRAM (Ferroelectric RAM) based memory module for main driver of OBDH (On Board Data Handling) system of LEO (Lower Earth Orbit) Satellite that enables the fast detection of error in driver data when implied with FPGA (Field Programmable Gate Array) and provides more realistic and tolerant way of fault finding for Single Event Upset (SEU) in highly radiated space environment. The scope of paper embraces development of TMR test bench, software algorithms, functional simulations, timing simulations and conclusion of comparison of FRAM based memory …

Artificial Intelligence - I: Adaptive Automated Teller Machines - Part Ii, Ghulam Mujtaba, Tariq Mahmood

International Conference on Information and Communication Technologies

Nowadays, the banking sector is increasingly relying on Automated Teller Machines (ATMs) in order to provide services to its customers. Although thousands of ATMs exist across many banks and different locations, the GUI and content of a typical ATM interface remains, more or less, the same. For instance, any ATM provides typical options for withdrawal, electronic funds transfer, viewing of mini-statements etc. However, such a static interface might not be suitable for all ATM customers, e.g., some users might not prefer to view all the options when they access the ATM, or to view specific withdrawal amounts less than, say, …

Automatic Content Generation For Video Self Modeling, Ju Shen, Anusha Raghunathan, Sen-Ching S. Cheung, Ravi R. Patel

Computer Science Faculty Publications

Video self modeling (VSM) is a behavioral intervention technique in which a learner models a target behavior by watching a video of him or herself. Its effectiveness in rehabilitation and education has been repeatedly demonstrated but technical challenges remain in creating video contents that depict previously unseen behaviors. In this paper, we propose a novel system that re-renders new talking-head sequences suitable to be used for VSM treatment of patients with voice disorder. After the raw footage is captured, a new speech track is either synthesized using text-to-speech or selected based on voice similarity from a database of clean speeches. …

Algorithms Analysis System: Recurrences, Anchit Sharma

Master's Projects

Algorithms which are recursive have running times which can be described by

recurrence equations or recurrences. These equations determine the overall running time complexity of the algorithm. This project intends to create a mechanism for

• auto generating recurrence equations of the form T(n) = a(T(n)/b) + f(n)

• creating a computational method for solving them and generating running times

  i.e. O (f(n)) or Ω (f(n)).

• presenting students with a way to verify their manually computed answers with

  the solution generation by the project

• generating grading and feedback for their solution

  The exercises will utilize the ‘Substitution Method’ and the ‘Master Method’ …

  ---

  Go to article

Online Auc Maximization, Peilin Zhao, Steven C. H. Hoi, Rong Jin, Tianbo Yang

Research Collection School Of Computing and Information Systems

Most studies of online learning measure the performance of a learner by classification accuracy, which is inappropriate for applications where the data are unevenly distributed among different classes. We address this limitation by developing online learning algorithm for maximizing Area Under the ROC curve (AUC), a metric that is widely used for measuring the classification performance for imbalanced data distributions. The key challenge of online AUC maximization is that it needs to optimize the pairwise loss between two instances from different classes. This is in contrast to the classical setup of online learning where the overall loss is a sum …

Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang

Research Collection School Of Computing and Information Systems

Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, balanced two-way number partitioning variant, whereas the most effective approximate algorithm, BLDM, may produce widely varying subset sums. In this paper, we introduce the LRM algorithm that lowers the expected spread in subset sums to one third that of BLDM for uniformly distributed numbers and odd subset cardinalities. We also propose Meld, a novel strategy for …

Estimating Anthropometric Marker Locations From 3-D Ladar Point Clouds, Matthew J. Maier

Theses and Dissertations

An area of interest for improving the identification portion of the system is in extracting anthropometric markers from a Laser Detection and Ranging (LADAR) point cloud. Analyzing anthropometrics markers is a common means of studying how a human moves and has been shown to provide good results in determining certain demographic information about the subject. This research examines a marker extraction method utilizing principal component analysis (PCA), self-organizing maps (SOM), alpha hulls, and basic anthropometric knowledge. The performance of the extraction algorithm is tested by performing gender classification with the calculated markers.

Resizable, Scalable, Concurrent Hash Tables, Josh Triplett, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We present algorithms for shrinking and expanding a hash table while allowing concurrent, wait-free, linearly scalable lookups. These resize algorithms allow the hash table to maintain constant-time performance as the number of entries grows, and reclaim memory as the number of entries decreases, without delaying or disrupting readers.

We implemented our algorithms in the Linux kernel, to test their performance and scalability. Benchmarks show lookup scalability improved 125x over readerwriter locking, and 56% over the current state-of-the-art for Linux, with no performance degradation for lookups during a resize.

To achieve this performance, this hash table implementation uses a new concurrent …

A Feature Based Frequency Domain Analysis Algorithm For Fault Detection Of Induction Motors, Zhaoxia Wang, C. S. Chang, Zhang Yifan

Research Collection School Of Computing and Information Systems

This paper studies the stator currents collected from several inverter-fed laboratory induction motors and proposes a new feature based frequency domain analysis method for performing the detection of induction motor faults, such as the broken rotor-bar or bearing fault. The mathematical formulation is presented to calculate the features, which are called FFT-ICA features in this paper. The obtained FFT-ICA features are normalized by using healthy motor as benchmarks to establish a feature database for fault detection. Compare with conventional frequency-domain analysis method, no prior knowledge of the motor parameters or other measurements are required for calculating features. Only one phase …

Smoothly Varying Affine Stitching, Wen-Yan Lin, Siying Liu, Yasuyuki Matsuhita, Tian-Tsong Ng, Loong-Fah Cheong

Research Collection School Of Computing and Information Systems

Traditional image stitching using parametric transforms such as homography, only produces perceptually correct composites for planar scenes or parallax free camera motion between source frames. This limits mosaicing to source images taken from the same physical location. In this paper, we introduce a smoothly varying affine stitching field which is flexible enough to handle parallax while retaining the good extrapolation and occlusion handling properties of parametric transforms. Our algorithm which jointly estimates both the stitching field and correspondence, permits the stitching of general motion source images, provided the scenes do not contain abrupt protrusions.