Lightweight Data Indexing and Compression in External Memory

In this paper we describe algorithms for computing the Burrows-Wheeler Transform (bwt) and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are lightweight in the sense that, for an input of size n, they use only n bits of working space on disk while all previous approaches use Θ(nlog n) bits. This is achieved by building the bwt directly without passing through the construction of the Suffix Array/Tree data structure. Moreover, our algorithms access disk data only via sequential scans, thus they take full advantage of modern disk features that make sequential disk accesses much faster than random accesses. We also present a scan-based algorithm for inverting the bwt that uses Θ(n) bits of working space, and a lightweight internal-memory algorithm for computing the bwt which is the fastest in the literature when the available working space is o(n) bits. Finally, we prove lower bounds on the complexity of computing and inverting the bwt via sequential scans in terms of the classic product: internal-memory space × number of passes over the disk data, showing that our algorithms are within an O(log n) factor of the optimal.     

A personalized search engine based on Web‐snippet hierarchical clustering

We propose a (meta‐)search engine, called SnakeT (SNippet Aggregation for Knowledge ExtracTion), which queries more than 18 commodity search engines and offers two complementary views on their returned results. One is the classical flat‐ranked list, the other consists of a hierarchical organization of these results into folders created on‐the‐fly at query time and labeled with intelligible sentences that capture the themes of the results contained in them. Users can browse this hierarchy with various goals: knowledge extraction, query refinement and personalization of search results. In this novel form of personalization, the user is requested to interact with the hierarchy by selecting the folders whose labels (themes) best fit her query needs. SnakeT then personalizes on‐the‐fly the original ranked list by filtering out those results that do not belong to the selected folders. Consequently, this form of personalization is carried out by the users themselves and thus results fully adaptive, privacy preserving, scalable and non‐intrusive for the underlying search engines. We have extensively tested SnakeT and compared it against the best available Web‐snippet clustering engines. SnakeT is efficient and effective, and shows that a mutual reinforcement relationship between ranking and Web‐snippet clustering does exist. In fact, the better the ranking of the underlying search engines, the more relevant the results from which SnakeT distills the hierarchy of labeled folders, and hence the more useful this hierarchy is to the user. Vice versa, the more intelligible the folder hierarchy, the more effective the personalization offered by SnakeT on the ranking of the query results. Copyright © 2007 John Wiley & Sons, Ltd.     

String Search in Coarse-Grained Parallel Computers

Given a text string T[1,n] , the multistring search problem consists of determining which of k pattern strings {X ₁ [1,m], X ₂ [1,m], . . ., X _k [1,m]} , provided on-line, occur in T . We study this problem in the BSP model [27], and then extend our analysis to other coarse-grained parallel computational models. We refer to the relevant and difficult case of long patterns, that is m≥p , where p is the number of available processors, and provide an optimal result with respect to both computation and communication times, attaining a constant number of supersteps. We then study single string search (i.e., k=1 ), and show how the multistring search algorithm can be employed to speed up the process and balance the communication cost. The proposed solution takes a constant number of supersteps, and achieves optimal communication time if the string to be searched is longer than p ² . Our results are based on the distribution of a proper data structure among the p processors, to reduce and balance the communication cost. We also indicate how short patterns can be efficiently dealt with, through a completely different algorithmic approach. Received June 1, 1997; revised March 10, 1998.     

On Optimally Partitioning a Text to Improve Its Compression

In this paper we investigate the problem of partitioning an input string T in such a way that compressing individually its parts via a base-compressor C gets a compressed output that is shorter than applying C over the entire T at once. This problem was introduced in Buchsbaum et al. (Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175–184, 2000; J. ACM 50(6):825–851, 2003) in the context of table compression, and then further elaborated and extended to strings and trees by Ferragina et al. (J. ACM 52:688–713, 2005; Proc. of 46th IEEE Symposium on Foundations of Computer Science, pp. 184–193, 2005) and Mäkinen and Navarro (Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229–241, 2007). Unfortunately, the literature offers poor solutions: namely, we know either a cubic-time algorithm for computing the optimal partition based on dynamic programming (Buchsbaum et al. in J. ACM 50(6):825–851, 2003; Giancarlo and Sciortino in Proc. of 14th Symposium on Combinatorial Pattern Matching, pp. 129–143, 2003), or few heuristics that do not guarantee any bounds on the efficacy of their computed partition (Buchsbaum et al. in Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175–184, 2000; J. ACM 50(6):825–851, 2003), or algorithms that are efficient but work in some specific scenarios (such as the Burrows-Wheeler Transform, see e.g. Ferragina et al. in J. ACM 52:688–713, 2005; Mäkinen and Navarro in Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229–241, 2007) and achieve compression performance that might be worse than the optimal-partitioning by a Ω(log?n/log?log?n) factor. Therefore, computing efficiently the optimal solution is still open (Buchsbaum and Giancarlo in Encyclopedia of Algorithms, pp. 939–942, 2008). In this paper we provide the first algorithm which computes in O(nlog?_1+ε n) time and O(n) space, a partition of T whose compressed output is guaranteed to be no more than (1+ε)-worse the optimal one, where ε may be any positive constant fixed in advance. This result holds for any base-compressor C whose compression performance can be bounded in terms of the zero-th or the k-th order empirical entropy of the text T. We will also discuss extensions of our results to BWT-based compressors and to the compression booster of Ferragina et al. (J. ACM 52:688–713, 2005).     

Recognition of hand-written rotated digits by neural networks

In this paper, an optical character recognition system for hand-written rotated digits in land registry maps is presented. It is based on a neural network and trained by a constructive learning rule, the Hyperbox Perception Cascade (HPC). The HPC classifier can design complex, possibly nonconvex, disjoint, and bounded decision regions and treat the rejection problems of outliers and unanticipated patterns, which would otherwise tend to be classified positively in an incorrect class. We use shape features and a novel approach to select the most promising features to attain a low generalization error. The numerous experiments show that a subset of 24 of the 46 features obtains a good classifier with a high rate of correct classification and a low rate of rejection.     

A wide-band 280-MHz four-path time-interleaved bandpass sigma-delta modulator

This paper describes a 0.35-/spl mu/m CMOS fourth-order bandpass analog-digital sigma-delta (/spl Sigma//spl Delta/) modulator for wide-band base stations receivers. The modulator, based on a time-interleaved four-path architecture, achieves an equivalent sampling frequency of 280 MHz, although the building blocks operate at only 70 MHz. In measurements, the prototype chip achieves a dynamic range of 72 dB (12 bits of resolution) with a signal bandwidth of 4.375 MHz centered around an intermediate frequency of 70 MHz. The measured spurious-free dynamic range is 69 dB. The /spl Sigma//spl Delta/ modulator dissipates 480 mW from a 3.3-V supply, including voltage reference buffers and output pads with high-driving capabilities, and occupies 20 mm/sup 2/ of silicon area.     

Prediction and repeatability of milk coagulation properties and curd-firming modeling parameters of ovine milk using Fourier-transform infrared spectroscopy and Bayesian models

The aim of this study was to apply Bayesian models to the Fourier-transform infrared spectroscopy spectra of individual sheep milk samples to derive calibration equations to predict traditional and modeled milk coagulation properties (MCP), and to assess the repeatability of MCP measures and their predictions. Data consisted of 1,002 individual milk samples collected from Sarda ewes reared in 22 farms in the region of Sardinia (Italy) for which MCP and modeled curd-firming parameters were available. Two milk samples were taken from 87 ewes and analyzed with the aim of estimating repeatability, whereas a single sample was taken from the other 915 ewes. Therefore, a total of 1,089 analyses were performed. For each sample, 2 spectra in the infrared region 5,011 to 925 cm^?1 were available and averaged before data analysis. BayesB models were used to calibrate equations for each of the traits. Prediction accuracy was estimated for each trait and model using 20 replicates of a training-testing validation procedure. The repeatability of MCP measures and their predictions were also compared. The correlations between measured and predicted traits, in the external validation, were always higher than 0.5 (0.88 for rennet coagulation time). We confirmed that the most important element for finding the prediction accuracy is the repeatability of the gold standard analyses used for building calibration equations. Repeatability measures of the predicted traits were generally high (≥95%), even for those traits with moderate analytical repeatability. Our results show that Bayesian models applied to Fourier-transform infrared spectra are powerful tools for cheap and rapid prediction of important traits in ovine milk and, compared with other methods, could help in the interpretation of results.     

Breed of goat affects the prediction accuracy of milk coagulation properties using Fourier-transform infrared spectroscopy

The prediction of traditional goat milk coagulation properties (MCP) and curd firmness over time (CF_t) parameters via Fourier-transform infrared (FTIR) spectroscopy can be of significant economic interest to the dairy industry and can contribute to the breeding objectives for the genetic improvement of dairy goat breeds. Therefore, the aims of this study were to (1) explore the variability of milk FTIR spectra from 4 goat breeds (Camosciata delle Alpi, Murciano-Granadina, Maltese, and Sarda), and to assess the possible discriminant power of milk FTIR spectra among breeds, (2) assess the viability to predict coagulation traits by using milk FTIR spectra, and (3) quantify the effect of the breed on the prediction accuracy of MCP and CF_t parameters. In total, 611 individual goat milk samples were used. Analysis of variance of measured MCP and CF_t parameters was carried out using a mixed model including the farm and pendulum as random factors, and breed, parity, and days in milk as fixed factors. Milk spectra for each goat were collected over the spectral range from wavenumber 5,011 to 925 × cm^?1. Discriminant analysis of principal components was used to assess the ability of FTIR spectra to identify breed of origin. A Bayesian model was used to calibrate equations for each coagulation trait. The accuracy of the model and the prediction equation was assessed by cross-validation (CRV; 80% training and 20% testing set) and stratified CRV (SCV; 3 breeds in the training set, one breed in the testing set) procedures. Prediction accuracy was assessed by using coefficient of determination of validation (R²_VAL), the root mean square error of validation (RMSE_VAL), and the ratio performance deviation. Moreover, measured and FTIR predicted traits were compared in the SCV procedure by assessing their least squares means for the breed effect, Pearson correlations, and variance heteroscedasticity. Results showed the feasibility of using FTIR spectra and multivariate analyses to correctly assign milk samples to their breeds of origin. The R²_VAL values obtained with the CRV procedure were moderate to high for the majority of coagulation traits, with RMSE_VAL and ratio performance deviation values increasing as the coagulation process progresses from rennet addition. Prediction accuracy obtained with the SCV were strongly influenced by the breed, presenting general low values restricting a practical application. In addition, the low Pearson correlation coefficients of Sarda breed for all the traits analyzed, and the heteroscedastic variances of Camosciata delle Alpi, Murciano-Granadina, and Maltese breeds, further indicated that it is fundamental to consider the differences existing among breeds for the prediction of milk coagulation traits.     

Swat: A system for detecting salient Wikipedia entities in texts

We study the problem of entity salience by proposing the design and implementation of Swat , a system that identifies the salient Wikipedia entities occurring in an input document. Swat consists of several modules that are able to detect and classify on‐the‐fly Wikipedia entities as salient or not, based on a large number of syntactic, semantic, and latent features properly extracted via a supervised process, which has been trained over millions of examples drawn from the New York Times corpus. The validation process is performed through a large experimental assessment, eventually showing that Swat improves known solutions over all publicly available datasets. We release Swat via an API that we describe and comment in the paper to ease its use in other software.