Caching technologies have been widely employed to boost the performance of Web search engines. Motivated by the correlation between terms in query logs from a commercial search engine, we explore the idea of a caching scheme based on pairs of terms, rather than individual terms (which is the typical approach used by search engines today). We propose an inverted list caching policy, based on the Least Recently Used method, in which the co-occurring correlation between terms in the query stream is accounted for when deciding on which terms to keep in the cache. We consider not only the term co-occurrence within the same query but also the co-occurrence between separate queries. Experimental results show that the proposed approach can improve not only the cache hit ratio but also the overall throughput of the system when compared to existing list caching algorithms.

In this paper, we study binary pattern erasure codes, i.e., binary codes that are resiliant to erasures from a family P of possible erasures. We give an algorithmic proof of the existence of a binary linear code with codewords of length n that is resiliant to erasures from P when P satisfies the properties: every pattern p ϵ P has size m and every letter in the alphabet occurs in at most c patterns. The density of the parity matrix is plays a important role in storage applications, so we also introduce a new low density code basing on graph theory.

The sign of a Latin square is $-1$ if it has an odd number of rows and columns that are odd permutations; otherwise it is $+1$. Let $L^{\text{\scshape{even}}}_n$ and $L^{\text{\scshape{odd}}}_n$ be, respectively, the number of Latin squares of order n with sign $+1$ and $-1$. The Alon–Tarsi conjecture asserts that $L^{\text{\scshape{even}}}_n \neq L^{\text{\scshape{odd}}}_n$ when n is even. We prove that $L_n^{\text{\scshape{even}}}-L_n^{\text{\scshape{odd}}}=(-1)^{n(n-1)/2} \sum_{A \in B_n} (-1)^{\sigma_0(A)} \det(A)^n$, where $B_n$ is the set of $n \times n$ $\,(0,1)$-matrices and $\sigma_0(A)$ is the number of 0 elements in A. We use this formula to give another proof of the Alon–Tarsi conjecture for $n=p-1$ for odd prime p.

MOTIVATION: Bayesian phylogenetic inference can be used to propose a 'tree of life' for a collection of species whose DNA sequences are known. While there are many packages available that implement Bayesian phylogenetic inference, such as the popular MrBayes, running these programs poses significant computational challenges. Parallelized versions of the Metropolis coupled Markov chain Monte Carlo (MC³) algorithm in MrBayes have been presented that can run on various platforms, such as a graphics processing unit (GPU). The GPU has been used as a cost-effective means for computational research in many fields. However, until now, some limitations have prevented the GPU from being used to run MrBayes MC³ effectively. RESULTS: We give an appraisal of the possibility of realistically implementing MrBayes MC³ in parallel on an ordinary four-core desktop computer with a GPU. An earlier proposed algorithm for running MrBayes MC³ in parallel on a GPU has some significant drawbacks (e.g. too much CPU-GPU communication) which we resolve. We implement these improvements on the NVIDIA GeForce GTX 480 as most other GPUs are unsuitable for running MrBayes MC³ due to a range of reasons, such as having insufficient support for double precision floating-point arithmetic. Experiments indicate that run-time can be decreased by a factor of up to 5.4 by adding a single GPU (versus state-of-the-art multicore parallel algorithms). We can also achieve a speedup (versus serial MrBayes MC³) of more than 40 on a sufficiently large dataset using two GPUs. AVAILABILITY: GPU MrBayes (i.e. the proposed implementation of MrBayes MC³ for the GPU) is available from http://mrbayes-gpu.sourceforge.net/.

Major web search engines answer thousands of queries per second requesting information about billions of web pages. The data sizes and query loads are growing at an exponential rate. To manage the heavy workload, we consider techniques for utilizing a Graphics Processing Unit (GPU). We investigate new approaches to improve two important operations of search engines -- lists intersection and index compression. For lists intersection, we develop techniques for efficient implementation of the binary search algorithm for parallel computation. We inspect some representative real-world datasets and find that a sufficiently long inverted list has an overall linear rate of increase. Based on this observation, we propose Linear Regression and Hash Segmentation techniques for contracting the search range. For index compression, the traditional d-gap based compression schemata are not well-suited for parallel computation, so we propose a Linear Regression Compression schema which has an inherent parallel structure. We further discuss how to efficiently intersect the compressed lists on a GPU. Our experimental results show significant improvements in the query processing throughput on several datasets.

In this paper, we study longest lowest-density MDS codes, a simple kind of multi-erasure array code with optimal redundancy and minimum update penalty. We prove some basic structure properties for longest lowest-density MDS codes. We define a "perfect" property for near-resolvable block designs (NRBs) and establish a bijection between 3-erasure longest lowest-density MDS codes (T-Codes) and perfect NRB(3¿ + 1, 3, 2)s. We present a class of NRB(3¿+1, 3, 2)s, and prove that it produces a family of T-Codes. This family is infinite assuming Artin¿s Conjecture. We also test some other NRBs and find some T-Code instances outside of this family.