Physical Sciences and Mathematics Commons^™

Efficient Mutual Nearest Neighbor Query Processing For Moving Object Trajectories, Yunjun Gao, Baihua Zheng, Gencai Chen, Qing Li, Chun Chen, Gang Chen

Research Collection School Of Computing and Information Systems

Given a set D of trajectories, a query object q, and a query time extent Γ, a mutual (i.e., symmetric) nearest neighbor (MNN) query over trajectories finds from D, the set of trajectories that are among the k1 nearest neighbors (NNs) of q within Γ, and meanwhile, have q as one of their k2 NNs. This type of queries is useful in many applications such as decision making, data mining, and pattern recognition, as it considers both the proximity of the trajectories to q and the proximity of q to the trajectories. In this paper, we first formalize MNN search …

Algorithms For Constrained K-Nearest Neighbor Queries Over Moving Object Trajectories, Yunjun Gao, Baihua Zheng, Gencai Chen, Qing Li, Chun Chen

Research Collection School Of Computing and Information Systems

An important query for spatio-temporal databases is to find nearest trajectories of moving objects. Existing work on this topic focuses on the closest trajectories in the whole data space. In this paper, we introduce and solve constrained k-nearest neighbor (CkNN) queries and historical continuous CkNN (HCCkNN) queries on R-tree-like structures storing historical information about moving object trajectories. Given a trajectory set D, a query object (point or trajectory) q, a temporal extent T, and a constrained region CR, (i) a CkNN query over trajectories retrieves from D within T, the k (≥ 1) trajectories that lie closest to q and …

Computing Prime Harmonic Sums, Eric Bach, Dominic Klyve, Jonathan P. Sorenson

Jonathan P. Sorenson

We discuss a method for computing Σ �≤� 1/�, using time about �2/3 and space about �1/3. It is based on the Meissel-Lehmer algorithm for computing the prime-counting function �(�), which was adapted and improved by Lagarias, Miller, and Odlyzko. We used this algorithm to determine the first point at which the prime harmonic sum first crosses.

Computing Prime Harmonic Sums, Eric Bach, Dominic Klyve, Jonathan P. Sorenson

Jonathan P. Sorenson

We discuss a method for computing Σ �≤� 1/�, using time about �2/3 and space about �1/3. It is based on the Meissel-Lehmer algorithm for computing the prime-counting function �(�), which was adapted and improved by Lagarias, Miller, and Odlyzko. We used this algorithm to determine the first point at which the prime harmonic sum first crosses.

Modular Exponentiation Via The Explicit Chinese Remainder Theorem, Daniel J. Bernstein, Jonathan P. Sorenson

Jonathan P. Sorenson

In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin’s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.

Modular Exponentiation Via The Explicit Chinese Remainder Theorem, Daniel J. Bernstein, Jonathan P. Sorenson

Jonathan P. Sorenson

In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin’s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.

The Pseudosquares Prime Sieve, Jonathan P. Sorenson

Jonathan P. Sorenson

We present the pseudosquares prime sieve, which finds all primes up to n.

Fast Bounds On The Distribution Of Smooth Numbers, Scott T. Parsell, Jonathan P. Sorenson

Jonathan P. Sorenson

In this paper we present improvements to Bernstein’s algorithm, which finds rigorous upper and lower bounds for (x, y).

Dynamic Model Pooling Methodology For Improving Aberration Detection Algorithms, Brenton J. Sellati

Masters Theses 1911 - February 2014

Syndromic surveillance is defined generally as the collection and statistical analysis of data which are believed to be leading indicators for the presence of deleterious activities developing within a system. Conceptually, syndromic surveillance can be applied to any discipline in which it is important to know when external influences manifest themselves in a system by forcing it to depart from its baseline. Comparing syndromic surveillance systems have led to mixed results, where models that dominate in one performance metric are often sorely deficient in another. This results in a zero-sum trade off where one performance metric must be afforded greater …

Computing The Bayes Factor From A Markov Chain Monte Carlo Simulation Of The Posterior Distribution, Martin D. Weinberg

Astronomy Department Faculty Publication Series

Computation of the marginal likelihood from a simulated posterior distribution is central to Bayesian model selection but is computationally difficult. I argue that the marginal likelihood can be reliably computed from a posterior sample by careful attention to the numerics of the probability integral. Posing the expression for the marginal likelihood as a Lebesgue integral, we may convert the harmonic mean approximation from a sample statistic to a quadrature rule. As a quadrature, the harmonic mean approximation suffers from enormous truncation error as consequence . In addition, I demonstrate that the integral expression for the harmonic-mean approximation converges slowly at …

Mpi Enhancements In John The Ripper, Edward R. Sykes, Michael Lin, Wesley Skoczen

Faculty Publications and Scholarship

John the Ripper (JtR) is an open source software package commonly used by system administrators to enforce password policy. JtR is designed to attack (i.e., crack) passwords encrypted in a wide variety of commonly used formats. While parallel implementations of JtR exist, there are several limitations to them. This research reports on two distinct algorithms that enhance this password cracking tool using the Message Passing Interface. The first algorithm is a novel approach that uses numerous processors to crack one password by using an innovative approach to workload distribution. In this algorithm the candidate password is distributed to all participating …

Quantum Algorithm Animator, Lori Eileen Nicholson

CCE Theses and Dissertations

The design and development of quantum algorithms present a challenge, especially for inexperienced computer science students. Despite the numerous common concepts with classical computer science, quantum computation is still considered a branch of theoretical physics not commonly used by computer scientists. Experimental research into the development of a quantum computer makes the use of quantum mechanics in organizing computation more attractive, however the physical realization of a working quantum computer may still be decades away.

This study introduces quantum computing to computer science students using a quantum algorithm animator called QuAL. QuAL's design uses features common to classical algorithm animators …

Multi-Resolution Mean-Shift Algorithm For Vector Quantization, P L. M Bouttefroy, A Bouzerdoum, A Beghdadi, S L. Phung

Faculty of Informatics - Papers (Archive)

The generation of stratified codebooks, providing a subset of vectors at different scale levels, has become necessary with the emergence of embedded coder/decoder for scalable image and video formats. We propose an approach based on mean-shift, invoking the multi-resolution framework to generate codebook vectors. Applied to the entire image, mean-shift is slow because it requires each sample to converge to a mode of the distribution. The procedure can be sped up with three simple assumptions: kernel truncation, code attraction and trajectory attraction. Here we propose to apply the mean-shift algorithm to the four image subbands generated by a DWT, namely …

A Training Algorithm For Sparse Ls-Svm Using Compressive Sampling, Jie Yang, Son Lam Phung, Abdesselam Bouzerdoum

Faculty of Informatics - Papers (Archive)

Least Squares Support Vector Machine (LS-SVM) has become a fundamental tool in pattern recognition and machine learning. However, the main disadvantage is lack of sparseness of solutions. In this article Compressive Sampling (CS), which addresses the sparse signal representation, is employed to find the support vectors of LS-SVM. The main difference between our work and the existing techniques is that the proposed method can locate the sparse topology while training. In contrast, most of the traditional methods need to train the model before finding the sparse support vectors. An experimental comparison with the standard LS-SVM and existing algorithms is given …

A Particle Swarm Optimization Algorithm Based On Orthogonal Design, Jie Yang, Abdesselam Bouzerdoum, Son Lam Phung

Faculty of Informatics - Papers (Archive)

The last decade has witnessed a great interest in using evolutionary algorithms, such as genetic algorithms, evolutionary strategies and particle swarm optimization (PSO), for multivariate optimization. This paper presents a hybrid algorithm for searching a complex domain space, by combining the PSO and orthogonal design. In the standard PSO, each particle focuses only on the error propagated back from the best particle, without “communicating” with other particles. In our approach, this limitation of the standard PSO is overcome by using a novel crossover operator based on orthogonal design. Furthermore, instead of the “generating-and-updating” model in the standard PSO, the elitism …

A Novel Weighted-Graph-Based Grouping Algorithm For Metadata Prefetching, Peng Gu, Jun Wang, Yifeng Zhu, Hong Jiang, Pengju Shang

School of Computing: Faculty Publications

Although data prefetching algorithms have been extensively studied for years, there is no counterpart research done for metadata access performance. Existing data prefetching algorithms, either lack of emphasis on group prefetching, or bearing a high level of computational complexity, do not work well with metadata prefetching cases. Therefore, an efficient, accurate, and distributed metadata-oriented prefetching scheme is critical to leverage the overall performance in large distributed storage systems. In this paper, we present a novel weighted-graph-based prefetching technique, built on both direct and indirect successor relationship, to reap performance benefit from prefetching specifically for clustered metadata servers, an arrangement envisioned …