Computer Sciences Commons^™

Semantics And Efficient Evaluation Of Partial Tree-Pattern Queries On Xml, Xiaoying Wu

Dissertations

Current applications export and exchange XML data on the web. Usually, XML data are queried using keyword queries or using the standard structured query language XQuery the core of which consists of the navigational query language XPath. In this context, one major challenge is the querying of the data when the structure of the data sources is complex or not fully known to the user. Another challenge is the integration of multiple data sources that export data with structural differences and irregularities. In this dissertation, a query language for XML called Partial Tree-Pattern Query (PTPQ) language is considered. PTPQs generalize …

A Randomized Sublinear Time Parallel Gcd Algorithm For The Erew Pram, Jonathan P. Sorenson

Scholarship and Professional Work - LAS

We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1−o(1) that takes O(n log logn/ logn) time using O(n6 + ) processors for any > 0 on the EREW PRAM parallel model of computation. The algorithm either gives a correct answer or reports failure. We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem.

A Species-Conserving Genetic Algorithm For Multimodal Optimization, Michael Scott Brown

CCAC Theses and Dissertations

The problem of multimodal functional optimization has been addressed by much research producing many different search techniques. Niche Genetic Algorithms is one area that has attempted to solve this problem. Many Niche Genetic Algorithms use some type of radius. When multiple optima occur within the radius, these algorithms have a difficult time locating them. Problems that have arbitrarily close optima create a greater problem. This paper presents a new Niche Genetic Algorithm framework called Dynamic-radius Species-conserving Genetic Algorithm. This new framework extends existing Genetic Algorithm research.

This new framework enhances an existing Niche Genetic Algorithm in two ways. As the …

Nearest Neighbor Search With Strong Location Privacy, Stavros Papadopoulos, Spiridon Bakiras, Dimitris Papadias

Publications and Research

The tremendous growth of the Internet has significantly reduced the cost of obtaining and sharing information about individuals, raising many concerns about user privacy. Spatial queries pose an additional threat to privacy because the location of a query may be sufficient to reveal sensitive information about the querier. In this paper we focus on k nearest neighbor (kNN) queries and define the notion of strong location privacy, which renders a query indistinguishable from any location in the data space. We argue that previous work fails to support this property for arbitrary kNN search. Towards this end, we introduce methods that …

Event Coverage In Sparse Mobile Sensor Networks, Mark Snyder, Sriram Chellappan

Computer Science Faculty Research & Creative Works

Autonomous mobile sensors are employed with ever-increasing frequency, in applications ranging from search and rescue, detection of forest fires, and battlefield surveillance. in this paper, we consider a representative surveillance problem wherein a sparse number of mobile sensors are expected to cover events of interest in a deployment field. Each event appears for a certain time and then disappears. Furthermore, the location of each event and its duration is unknown. in this paper, we design a sensor movement strategy based on efficient traversal in the network to fulfill two objectives: maximizing event detection and minimizing detection delay. Analysis and simulations …

Dynamic Load Balancing For I/O-Intensive Applications On Clusters, Xiao Qin, Hong Jiang, Adam Manzanares, Xiaojun Ruan, Shu Yin

School of Computing: Faculty Publications

Load balancing for clusters has been investigated extensively, mainly focusing on the effective usage of global CPU and memory resources. However, previous CPU- or memory-centric load balancing schemes suffer significant performance drop under I/O-intensive workloads due to the imbalance of I/O load. To solve this problem, we propose two simple yet effective I/O-aware load-balancing schemes for two types of clusters: (1) homogeneous clusters where nodes are identical and (2) heterogeneous clusters, which are comprised of a variety of nodes with different performance characteristics in computing power, memory capacity, and disk speed. In addition to assigning I/O-intensive sequential and parallel jobs …

A Fair Assignment Algorithm For Multiple Preference Queries, Leong Hou U, Nikos Mamoulis, Kyriakos Mouratidis

Research Collection School Of Computing and Information Systems

Consider an internship assignment system, where at the end of each academic year, interested university students search and apply for available positions, based on their preferences (e.g., nature of the job, salary, office location, etc). In a variety of facility, task or position assignment contexts, users have personal preferences expressed by different weights on the attributes of the searched objects. Although individual preference queries can be evaluated by selecting the object in the database with the highest aggregate score, in the case of multiple simultaneous requests, a single object cannot be assigned to more than one users. The challenge is …

Operational Verification Of A Relativistic Program, Robert T. Bauer

Computer Science Faculty Publications and Presentations

Engineering eorts to achieve scalable multiprocessor perfor- mance for concurrent reader-writer programs have resulted in a family of algorithms that are non-blocking and that tolerate interprocessor in- terference. Because these algorithms accept a unique frame of reference for each processor's accesses to memory, they typify a concurrent pro- gramming technique for shared memory multicore architectures called relativistic programmming.

Rigorous verification of these algorithms is not possible with existing semantic based approaches because the semantics under approximates multiprocessor behavior and the algorithms rely on abstruse interactions with the operating system that aren't reconciled with language seman- tics.

The Read-Copy Update (RCU) …

P-Code: A New Raid-6 Code With Optimal Properties, Chao Jin, Hong Jiang, Dan Feng, Lei Tian

School of Computing: Conference and Workshop Papers

RAID-6 significantly outperforms the other RAID levels in disk-failure tolerance due to its ability to tolerate arbitrary two concurrent disk failures in a disk array. The underlying parity array codes have a significant impact on RAID-6’s performance. In this paper, we propose a new XOR-based RAID-6 code, called the Partition Code (P-Code). P-Code is a very simple and flexible vertical code, making it easy to understand and implement. It works on a group of (prime – 1) or (prime) disks, and its coding scheme is based on an equal partition of a specified two-integer-tuple set. P-Code has the following properties: …

Blind Deconvolution Through Polarization Diversity Of Long Exposure Imagery, Steven P. James

Theses and Dissertations

The purpose of the algorithm developed in this thesis was to create a post processing method that could resolve objects at low signal levels using polarization diversity and no knowledge of the atmospheric seeing conditions. The process uses a two-channel system, one unpolarized image and one linearly polarized image, in a GEM algorithm to reconstruct the object. Previous work done by Strong showed that a two-channel system using polarization diversity on short exposure imagery could produce images up to twice the diffraction limit. In this research, long exposure images were simulated and a simple Kolmogorov model used. This allowed for …

Range Estimation Algorithm Comparison In 3-D Flash Ladar Data, Steven P. Jordan

Theses and Dissertations

Range estimation algorithms have been applied to Laser Detection and Ranging (LADAR) data to test for accuracy and precision. Data was acquired from Matlab® simulations and an experiment using the Advanced Scientific Concepts 3-D flash LADAR camera. Simulated LADAR data was based on a Gaussian pulse shape model with Poisson noise added. Simulations were performed to test range estimation algorithm performance with respect to waveform position within the range gate. The effectiveness of each algorithm is presented in terms of its average root mean square error and standard deviation in 1000 trials. The measured data experiment examined the effectiveness of …

Evaluating Hydrology Preservation Of Simplified Terrain Representations, Christopher S. Stuetzle, W. Randolph Franklin, Barbara Cutler

Computer and Data Science Faculty Publications

We present an error metric based on the potential energy of water flow to evaluate the quality of lossy terrain simplification algorithms. Typically, terrain compression algorithms seek to minimize RMS (root mean square) and maximum error. These metrics fail to capture whether a reconstructed terrain preserves the drainage network. A quantitative measurement of how accurately a drainage network captures the hydrology is important for determining the effectiveness of a terrain simplification technique. Having a measurement for testing and comparing different models has the potential to be widely used in numerous applications (flood prevention, erosion measurement, pollutant propagation, etc). In this …

Finding Irc-Like Meshes Sans Layer 7 Payloads, Akshay Dua, Jim Binkley, Suresh Singh

Computer Science Faculty Publications and Presentations

We present an algorithm for detecting IRC-like chat networks that does not rely on Layer 7 payload information. The goal is to extract only those meshes from conventional flows where long-term periodic data is being exchanged between an external server and multiple internal clients. Flow data is passed through a series of filters that reduce the memory requirements needed for final candidate mesh sorting. Final outputs consist of two sorted lists including the fanout list, sorted by the number of client hosts in the mesh, and a secondary list called the evil sort. The latter consists of meshes with any …

Alliances In Graphs: Parameterized Algorithms And On Partitioning Series-Parallel Graphs, Rosa Enciso

Electronic Theses and Dissertations

Alliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G = (V, E) is a non empty set S ⊆ V where, for all x ∈ S, |N[x] ∩ S| ≥ |N[x] − S|. Consequently, every vertex that is a member of a defensive alliance has at least as many vertices defending it as there are vertices attacking it. Alliances can …

Localized Monitoring Of Knn Queries In Wireless Sensor Networks, Yuxia Yao, Xueyan Tang, Ee Peng Lim

Research Collection School Of Computing and Information Systems

Wireless sensor networks have been widely used in civilian and military applications. Primarily designed for monitoring purposes, many sensor applications require continuous collection and processing of sensed data. Due to the limited power supply for sensor nodes, energy efficiency is a major performance concern in query processing. In this paper, we focus on continuous kNN query processing in object tracking sensor networks. We propose a localized scheme to monitor nearest neighbors to a query point. The key idea is to establish a monitoring area for each query so that only the updates relevant to the query are collected. The monitoring …

Accelerating Near-Duplicate Video Matching By Combining Visual Similarity And Alignment Distortion, Hung-Khoon Tan, Xiao Wu, Chong-Wah Ngo, Wan-Lei Zhao

Research Collection School Of Computing and Information Systems

In this paper, we investigate a novel approach to accelerate the matching of two video clips by exploiting the temporal coherence property inherent in the keyframe sequence of a video. Motivated by the fact that keyframe correspondences between near-duplicate videos typically follow certain spatial arrangements, such property could be employed to guide the alignment of two keyframe sequences. We set the alignment problem as an integer quadratic programming problem, where the cost function takes into account both the visual similarity of the corresponding keyframes as well as the alignment distortion among the set of correspondences. The set of keyframe-pairs found …

Modeling Video Hyperlinks With Hypergraph For Web Video Reranking, Hung-Khoon Tan, Chong-Wah Ngo, Xiao Wu

Research Collection School Of Computing and Information Systems

In this paper, we investigate a novel approach of exploiting visual-duplicates for web video reranking using hypergraph. Current graph-based reranking approaches consider mainly the pair-wise linking of keyframes and ignore reliability issues that are inherent in such representation. We exploit higher order relation to overcome the issues of missing links in visual-duplicate keyframes and in addition identify the latent relationships among keyframes. Based on hypergraph, we consider two groups of video threads: visual near-duplicate threads and story threads, to hyperlink web videos and describe the higher order information existing in video content. To facilitate reranking using random walk algorithm, the …

An Effective Approach To 3d Deformable Surface Tracking, Jianke Zhu, Steven C. H. Hoi, Zenglin Xu, Michael R. Lyu

Research Collection School Of Computing and Information Systems

The key challenge with 3D deformable surface tracking arises from the difficulty in estimating a large number of 3D shape parameters from noisy observations. A recent state-of-the-art approach attacks this problem by formulating it as a Second Order Cone Programming (SOCP) feasibility problem. The main drawback of this solution is the high computational cost. In this paper, we first reformulate the problem into an unconstrained quadratic optimization problem. Instead of handling a large set of complicated SOCP constraints, our new formulation can be solved very efficiently by resolving a set of sparse linear equations. Based on the new framework, a …

Knowledge Transfer Via Multiple Model Local Structure Mapping, Jing Gao, Wei Fan, Jing Jiang, Jiawei Han

Research Collection School Of Computing and Information Systems

The effectiveness of knowledge transfer using classification algorithms depends on the difference between the distribution that generates the training examples and the one from which test examples are to be drawn. The task can be especially difficult when the training examples are from one or several domains different from the test domain. In this paper, we propose a locally weighted ensemble framework to combine multiple models for transfer learning, where the weights are dynamically assigned according to a model's predictive power on each test example. It can integrate the advantages of various learning algorithms and the labeled information from multiple …

Ranked Reverse Nearest Neighbor Search, Ken C. K. Lee, Baihua Zheng, Wang-Chien Lee

Research Collection School Of Computing and Information Systems

Given a set of data points P and a query point q in a multidimensional space, Reverse Nearest Neighbor (RNN) query finds data points in P whose nearest neighbors are q. Reverse k-Nearest Neighbor (RkNN) query (where k ≥ 1) generalizes RNN query to find data points whose kNNs include q. For RkNN query semantics, q is said to have influence to all those answer data points. The degree of q's influence on a data point p (∈ P) is denoted by κp where q is the κp-th NN of p. We introduce a new variant of RNN query, namely, …

Capacity Constrained Assignment In Spatial Databases, Hou U Leong, Man Lung Yiu, Kyriakos Mouratidis, Nikos Mamoulis

Research Collection School Of Computing and Information Systems

Given a point set P of customers (e.g., WiFi receivers) and a point set Q of service providers (e.g., wireless access points), where each q 2 Q has a capacity q.k, the capacity constrained assignment (CCA) is a matching M Q × P such that (i) each point q 2 Q (p 2 P) appears at most k times (at most nce) in M, (ii) the size of M is maximized (i.e., it comprises min{|P|,P q2Q q.k} pairs), and (iii) the total assignment cost (i.e., the sum of Euclidean distances within all pairs) is minimized. Thus, the CCA problem is …

Algorithms For White-Box Obfuscation Using Randomized Subcircuit Selection And Replacement, Kenneth E. Norman

Theses and Dissertations

Software protection remains an active research area with the goal of preventing adversarial software exploitation such as reverse engineering, tampering, and piracy. Heuristic obfuscation techniques lack strong theoretical underpinnings while current theoretical research highlights the impossibility of creating general, efficient, and information theoretically secure obfuscators. In this research, we consider a bridge between these two worlds by examining obfuscators based on the Random Program Model (RPM). Such a model envisions the use of program encryption techniques which change the black-box (semantic) and white-box (structural) representations of underlying programs. In this thesis we explore the possibilities for white-box transformation. Under an …

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 …

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 …

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. …

Hardness For Explicit State Software Model Checking Benchmarks, Eric G. Mercer, Neha Rungta

Faculty Publications

Directed model checking algorithms focus computation resources in the error-prone areas of concurrent systems. The algorithms depend on some empirical analysis to report their performance gains. Recent work characterizes the hardness of models used in the analysis as an estimated number of paths in the model that contain an error. This hardness metric is computed using a stateless random walk. We show that this is not a good hardness metric because models labeled hard with a stateless random walk metric have easily discoverable errors with a stateful randomized search. We present an analysis which shows that a hardness metric based …

Linear-Time Algorithms For Edge-Based Problems, Alan Jamieson

All Dissertations

There is a dearth of algorithms that deal with edge-based problems in trees, specifically algorithms for edge sets that satisfy a particular parameter. The goal of this thesis is to create a methodology for designing algorithms for these edge-based problems. We will present a variant of the Wimer method [Wimer et al. 1985] [Wimer 1987] that can handle edge properties. We call this variant the Wimer edge variant. The thesis is divided into three sections, the first being a chapter devoted to defining and discussing the Wimer edge variant in depth, showing how to develop an algorithm using this variant, …

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 …

A Day In The Life Of Pubmed: Analysis Of A Typical Day's Query Log, Jorge R Herskovic, Len Y Tanaka, William Hersh, Elmer V Bernstam

Faculty, Staff and Student Publications

OBJECTIVE: To characterize PubMed usage over a typical day and compare it to previous studies of user behavior on Web search engines. DESIGN: We performed a lexical and semantic analysis of 2,689,166 queries issued on PubMed over 24 consecutive hours on a typical day. MEASUREMENTS: We measured the number of queries, number of distinct users, queries per user, terms per query, common terms, Boolean operator use, common phrases, result set size, MeSH categories, used semantic measurements to group queries into sessions, and studied the addition and removal of terms from consecutive queries to gauge search strategies. RESULTS: The size of …

Using Pareto Fronts To Evaluate Polyp Detection Algorithms For Ct Colonography, Adam Huang, Jiang Li, Ronald M. Summers, Nicholas Petrick, Amy K. Hara

Electrical & Computer Engineering Faculty Publications

We evaluate and improve an existing curvature-based region growing algorithm for colonic polyp detection for our CT colonography (CTC) computer-aided detection (CAD) system by using Pareto fronts. The performance of a polyp detection algorithm involves two conflicting objectives, minimizing both false negative (FN) and false positive (FP) detection rates. This problem does not produce a single optimal solution but a set of solutions known as a Pareto front. Any solution in a Pareto front can only outperform other solutions in one of the two competing objectives. Using evolutionary algorithms to find the Pareto fronts for multi-objective optimization problems has been …