New linear-time algorithm for suffix array construction

Juha Kärkkäinen, Peter Sanders , and Stefan Burkhardt: Linear Work Suffix Array Construction, Journal of the ACM (JACM), Volume 53 Issue 6, November 2006.
As the authors have said, this algorithm narrows the gap between suffix tree and suffix array, which are widely used and largely interchangeable index structures on strings and sequences. Usually theoreticians prefer the former due to linear-time construction algorithms and more explicit structure while practitioners prefer the latter due to its simplicity and space efficiency. Now there is one more reason for practitioners to stick with suffix array.

Research Impact for REF

The British government's emphasis on the practical impact of research in REF reminds me of Feynman's following words.

Physics [research] is like sex: sure, it may give some practical results, but that's not why we do it.

DiveRS'11

Pablo Castells, Jun Wang, Ruben Lara, and Dell Zhang are organising an ACM RecSys-2011 workshop on Novelty and Diversity in Recommender Systems (DiveRS). A special issue of ACM TIST in the scope of the workshop will be announced after the conference. Authors of accepted papers will be invited to submit an extended version.

A couple of metrics

It is often desirable to measure the dissimilarity or distance between items using a proper metric.

• Jaccard coefficient can be converted to a metric by by subtracting the Jaccard coefficient from 1.
• Kullback–Leibler divergence can be converted to a metric by taking the square root of its symmetric version Jensen–Shannon divergence.

A Poor Man's Parallel Processing

A very crude, but often good enough, method to achieve parallel processing (e.g., on multi-core computers) is to partition the large input data file into small chunks, run the program to process each of them in parallel, and then merge the output results file back. Fortunately, this process can be done easily with the wise iterative usage of two Unix utilities: split and cat.