« July 2012 | Main | October 2012 »
Computing Reviews is currently conducting server maintenance. We apologize for any inconvenience you've experienced. We will post an update when the regular site is available.
While we work on bringing you an improved CR experience, please check below to read recent reviews and additional content.
Unsupervised learning of morphology. By H. Hammarström & L. Borin
Computational Linguistics 37 (2): 309-350, 2011.
CR Review No. 139780
Work on the induction of morphological information from texts is surveyed in this paper. This overview considers only systems that accept as input raw text--that is, unannotated natural language text--and produce as output a description of the morphological structure of the language using as little supervision as possible.
For the purposes of the paper, the authors define a hierarchy of morphological analysis that has as its base a “justification”--a linguistically informed motivation for the morphological description of the language and, at the top, a list of the affixes of the language. The actual segmentation of words into stem and affixes sits in the middle of this hierarchy.
Following a general introduction to the subject, the paper proceeds to a historical survey and motivation for unsupervised learning of morphology (ULM), starting with the work of Zellig Harris. This is followed by a section titled “Trends and Techniques in ULM,” which contains a table that forms a road map (described as brief, even though it covers more than two dense pages) to many of the early studies of ULM. This is followed by surveys of four principle approaches based on the following: border and frequency--where segmentation borders are deduced on the basis of substrings that occur with a variety of adjacent substrings; group and abstract--where words are first grouped according to some metric such as edit distance; features and classes--where a word is viewed as a set of features, for example, n-grams; and phonological categories and separation--where the phonemes of a word may be classed into categories such as vowels and consonants. The authors point out that, regrettably, there has been little cross-fertilization between these approaches.
The penultimate section discusses, among other topics, the language dependence of ULM and ULM’s relation to semantics, and addresses this question: Is ULM of any use? A brief subsection on future directions suggests areas where high-accuracy systems might emerge.
The authors conclude that ULM has made progress, but that there is a long way to go. The paper contains an extensive bibliography with over 250 entries. For anyone interested in finding out more about ULM, this paper is an excellent starting place.
Reviewer: J. P. E. Hodgson
[This is a previously published Editor's Pick.]
Kurt Gödel and the foundations of mathematics: horizons of truth. By M. Baaz, C. Papadimitriou, D. Scott, H. Putnam, C. Harper
Cambridge University Press, New York, NY, 2011, ISBN 9780521761444
CR Review No. 140105
This is a collection of 21 expanded contributions to Gödel’s centenary celebration at the University of Vienna, in 2006. Takeuti, former president of the Kurt Gödel Society, writes in the foreword: “For everyone who gathered in his honor, Gödel’s extraordinary contributions to and tremendous influence in mathematics would be something of which we were already deeply aware.” Gödel has been thought by many to be the greatest logician since Aristotle; the impact of his work can be seen not only in mathematics and logic, but also in philosophy, physics, and, more generally, systems thinking. To quote Manin, a great mathematician:
Some profound thinkers [...] express[ed] the hope that there should exist several universal laws from which all other truths could be deduced by pure reason. After Gödel’s work, however, we can be sure that all of these hopes are unfounded. By pure deductive reasoning, one cannot even deduce from a finite number of basic principles all true statements about integers that can be formulated in the language of high school algebra. [1]Anyone looking for an accessible introduction to the conceptual aspects of Gödel’s theorem and its proof should read Manin’s essay.
[This is a previously published Editor's Pick.]
Programming Perl (4th ed.). By Tom Christiansen, Brian D. Foy, Larry Wall & Jon Orwant
O’Reilly Media, Inc. Cambridge, MA, 2012, 1184 pp., ISBN 0596004923.
CR Review No. 140272
The preface to this book begins with a section titled "The Pursuit of Happiness" that promises readers that the book will help them develop the three great virtues of a programmer: laziness, impatience, and hubris. To assist them on this journey, it offers a comprehensive guide to Perl v5.14.
There are five parts in this book. The first provides an overview of the language. The concepts of arrays and hashes are introduced, and a useful short example program is given, which opens a file, and then reads student grades from it into a hash.
Part 2, "The Gory Details," contains 13 chapters that progressively introduce concepts like operators, loops, pattern matching, and subroutines. I have always been intrigued by the way Perl programmers compete to enhance simple programs to become more concise, more generic, or in some sense "cuter." The examples in Part 2 are no exception. We are told, for instance, that we don't really need to declare a filehandle name when we open a file. We can use in its place a variable whose content will be allocated when we open the file. You might perhaps think: Why wasn't I taught that in class?
There are some sections in Part 2 that you won't find in older books. The Unicode chapter provides some quite complex examples, showing how accented and non-ASCII characters can be included in strings, and how they can be appropriately treated when read from files. And the chapter on data structures notes that arrays of arrays can be used to represent matrices, and then discusses things like hashes of complex records.
Part 3, "Perl as Technology," begins with a chapter about interprocess communication, which contains some useful examples that show how to use signals for timing out stalled operations, how file locks can be established, and how named pipes can be used. There's also a section about using sockets for networking clients and servers. The remaining chapters in Part 3 discuss compiling, command line options, debugging operations, and the Comprehensive Perl Archive Network (CPAN) repository. The last of these is especially important, and the range of resources it provides undoubtedly accounts for the popularity of Perl today.
The title of Part 4, "Perl as a Culture," is somewhat misleading. It actually contains some useful chapters dealing with security, coding practices, portability considerations, and documentation. The suggestions offered in relation to time efficiency, space efficiency, and programming style are particularly interesting.
The final part, "Reference Material," contains an alphabetical list of summaries of Perl special variables and functions. There is also a set of pragmatic module summaries, a glossary, and two sets of index pages.
This is not a book for beginners. It's far too detailed, and too thick to carry around. But if you need to do some serious Perl programming, then it's well worth the purchase price. My only real problem with this book is that it introduces some useful features, such as the given statement, that aren't implemented in the versions of Perl used on my company's servers.
Reviewer: G. K. Jenkins (Merlynston, Australia)
[This review is a previously published Editor's Pick.]
Smart cooperative relay schemes in LTE-advanced system. By Saransh Malik, Dahee No, Dae Jin Kim, Sangmi Moon, Se Young Kim, Intae Hwang, Bora Kim & Jin Lee
In ICUIMC 2012. Proceedings of the 6th International Conference on Ubiquitous Information Management and Communication (Kuala Lumpur, Malaysia, February 20, 2012), ACM, New York, NY, 2012, 1 -7.
CR Rev. No. 140276
A core problem of wireless data communication is how to maximize coverage while minimizing the bit error rate. To address this, the 4G technology known as long-term evolution-advanced (LTE-A) features a cooperative relaying scheme in which relay stations forward signals from neighboring mobile stations to the base station. When the base station receives the original signal together with the duplicated signal, it can restore bits more reliably than with the original signal alone.
This paper analyzes various cooperating relaying schemes, notably amplify-and-forward (AF), where the relay station forwards an amplified copy of the analog signal, and decode-and-forward (DF), where the base station decodes the signal, re-encodes the data, and sends a new signal. While DF does not amplify the noise (unlike AF), it does halve the bandwidth, so it should offer a better error rate. The protocol variants were analyzed under two linear equalization techniques, and under a diversity scheme where stations have multiple simultaneously operating antennas.
The majority of the paper is dedicated to an explanation of the various schemes. The new information contributed by the authors comes in the final section, where a simulation shows that, under the same constraints on transmission power, both relay schemes indeed represent an improvement in terms of error rate; DF clearly outperforms AF in all scenarios; and in the diversity scheme, AF with two antennas is better than DF with one antenna. While not groundbreaking news, these are solid results that confirm that the application of DF in LTE-A is well justified.
Reviewer: Wolfgang Schreiner (Linz, Austria)
[This review is a previously published Editor's Pick.]
Current challenges in patent information retrieval. Edited by Mihai Lupu, Katja Mayer, John Tait & Anthony J. Trippe
Springer Publishing Company, Incorporated New York, NY, 2011, 431 pp., ISBN 3642192300.
CR Rev. No 140048
In the last few decades, the number of patents registered has increased very rapidly. This book discusses some of the challenges in searching for patent information and some of the most advanced searching mechanisms available today. The methods of patent searching, the classifications of patents, the automatic tools associated with patent searching, current research in patent searching, and subject-specific patent searching are discussed.
The book, a collection of papers, is divided into five parts. The first part is an introduction. Chapter 1 introduces patent searching with respect to types of patent searches, such as searching for evidence of use, novelty, infringement, and validity. It also introduces classification-based, full-text, and citation searches. The chapter ends by discussing special patent searches, including those for chemical structures, biotechnology, and engineering drawings. Chapter 2 discusses various aspects of information retrieval (IR) systems, such as choice based on user evaluation, system characteristics (indexing, query, and result presentation), and models.
The second part addresses evaluation. Chapter 3 describes system-based evaluations for general IR systems and evaluation measures based on precision and recall ratios, which are calculated from the number of relevant documents retrieved from test data. It also describes evaluation models for user efforts. Chapter 4 is fully devoted to the CLEF-IP track, which investigates IR techniques in the patents domain. The detailed description includes the summary and evaluation of submissions for the track. Chapter 5 describes chemistry-related patent retrieval. The Text Retrieval Conference--Chemistry (TREC-CHEM) track results are described in detail. Chapter 6 discusses the evaluation of real patent retrievals and potentially misleading evaluations from laboratory tests.
The third part discusses high-recall problems and solutions. Chapter 7 develops a measure called "retrievability." A document with low retrievability is likely to be very difficult to find. The chapter presents details of the experiments done on retrievability. Chapter 8 discusses the effectiveness of the result sets of retrievals. The effectiveness measure depends on recalls and precision in the sample documents. The sampling approaches--and the limitations--are discussed in detail.
Chapter 9 presents logical modeling of a patent search. It describes the representation of patent documents using probabilistic object relational content modeling (PORCM) and a method of searching for such documents. Chapter 10 addresses a method for improving patent claim searches by decomposition, describing ways of decomposing independent claims and dependent claims; it ends by evaluating the method. Chapter 11 presents a graphical user interface prototype implementation for patent searching and discusses various features of the interface, including support from multiple retrieval facilities.
The fourth part of the book is on classifications. Chapter 12 describes various aspects of automated patent classification, including objective, classification-induced issues (distribution and language based), technologies, evaluation, accuracy, and scalability. Chapter 13 proposes a natural language technique to categorize the patent documents. The technique centers on the concept of "aboutness" dependency, in which "aboutness" is what the document is about. The experimental results are also discussed. Chapter 14 presents results of some experiments on classifications; the experiments consist of the examination of classification hierarchies, the weighting of class, and primary classification codes.
The fifth part focuses on the semantic search for patents. Chapter 15 describes a tool called GATE Mimir, which implements annotations in the documents such as section annotations, reference annotations, and measurement annotations. Chapter 16 describes a new search tool for searching scientific documents; the tool utilizes natural language processing techniques. Chapter 17 discusses chemical structure searching. The discussion features representation, specific chemical molecule searching, similarity searching, and so on. Chapter 18 examines a patent taxonomy integration and interaction framework that uses the Wikipedia science ontology and enriches it. Chapter 19 proposes automatic translation of scholarly terms into patent terms and discusses experimental results for the method. The last chapter discusses possible future directions in patent searching.
Each paper in this collection can be read independently. The book smoothly flows from the introduction of patent searching through problems of patent searching and proposals for solving these problems. A normal understanding of intellectual property and searching is enough to understand most parts of the book. The book serves as an introduction and a reference for anybody interested in patents; it can be used as a textbook for patent information retrieval. Researchers in information retrieval will find the papers and bibliographies useful.
Reviewer: Maulik A. Dave (Dunwoody, GA)
Software abstractions. : logic, language, and analysis (rev. ed.). By Daniel Jackson
The MIT Press Cambridge, MA, 2012, 376 pp., ISBN 0262017156.
CR Rev. No. 140359
In a Scientific American article [1] from around the time of this seminal book’s original edition [2], the author stated:
Managers involved in high-profile software blowouts could claim in their defense that they followed standard industry practices, and unfortunately they would be right. Developers rarely articulate their designs precisely and analyze them to check that they embody the desired properties.
The present, revised edition of this latter-day classic is as outstanding and definitive in its approach to the design problem as was the original, only more so (to use a Rick Blaine formula from the timeless film Casablanca). The book and its central subject, the Alloy 4 language, are the foundation and virtually unique occupants of a formal methods niche that I had originally thought impossible: lightweight formal methods that compete on equal terms in many contexts with the elaborate, heavy variety. There now exist a plethora, if not a virtual Tower of Babel, of effective heavyweight formal methods of both the theorem proving [3] and model checking [4] variety. In light of this, Alloy’s promise extends, unlike that of the heavy machinery, to greater pervasiveness of formal modeling and verification among designers and developers.
The book consists of six chapters—“Introduction,” “A Whirlwind Tour,” “Logic,” “Language,” “Analysis” (that is, what the Alloy analyzer does given an Alloy text or model), and “Examples”—and five appendices—“Exercises,” “Alloy Language Reference,” “[Alloy 4] Kernel Semantics,” “Diagrammatic Notation,” and “Alternative Approaches” (that is, heavyweight methods such as B, object constraint language (OCL), Vienna development method (VDM), and Z).
The author identifies his intended audience as “software designers, whether they call themselves requirements analysts, specifiers, designers, architects, or programmers.” This characterization displays the author’s great clarity of expression, in this instance born of avoiding verbal clutter by nonessentials. (Compare this with conventional job descriptions in these purportedly separate callings.) It is quite instructive for the author to state (or admit) that “model,” that most overused word of our profession, was chosen for its vagueness. Theorem proving (syntactic) and model checking (semantic)—what may be termed the two antipodes of formal methods—assign different meanings to the term. However, model checking was the “original inspiration” of the Alloy analyzer, which later was complemented by Boolean constraint satisfaction (SAT) solvers.
Alloy’s logic is that of relations—a relation being the conventional mathematical set of tuples. As one learns and confronts the syntax of Alloy models, it is useful to remember the author’s explanation that Alloy comprises one logic that is expressible in three styles: predicate calculus style, navigation style, and relational calculus style. One model can contain instances of all three. This gives the correct impression that Alloy is very rich, though everything is constructed from atoms and (their) relations. In getting the hang of Alloy, users must master notations and notions such as {(a)} standing for any of a, {a}, (a), and itself.
I hasten to add that it is, to say the least, worth it. The book, though relatively short, imparts some deep insights: “Predicate calculus lacks transitive closure, so reachability properties can’t be expressed [in it].” “Is equality structural equality or reference equality?” The book has the answer: “A relation has no identity distinct from its value[.] ... If two relations have the same set of tuples ... they’re just one and the same relation.” The author points out that equality cannot be represented as a first-order relation. Also, the keyword “in,” which contextually stands for either “is an element of” or “is a subset of” was “carefully chosen for its ambiguity.” This last comment is very helpful regarding motivation. The exposition is honest; there is no salesmanship. The Alloy road to writing what one means to express using, for example, quantifiers versus multiplicities is not a royal one: one x : Line | cache’ = cache - x versus some x : Line | cache’ = cache - x.
Sections 4.5, on Alloy facts, predicates, functions, and assertions, and 5.1.3, on Alloy’s fundamental small-scope hypothesis (which justifies exhaustive search for (counter) examples within a finite scope), effectively summarize the essentials. They can be peeked at with profit before one gets to them through a sequential reading of the whole book. The examples are up to par with the rest of the book. The Alloy model of leader election in a ring topology communication network can, as it happens, be compared with that of Event-B [3], an excellent heavyweight theorem-proving tool.
Ensuring that “what you write down means what you think it means” is the abiding challenge to designers. The book and its associated Web site of tutorials, examples, models, and downloads (including Alloy 4 itself, of course) will furnish designers with a rigorous and expressive but agile way of effecting that most important of features: correctness. It has my highest recommendation.
Reviewer: George Hacken (Wayne, NJ)
REFERENCES
[1] Jackson, D. Dependable software by design. Scientific American 294 (June 2006), 68-75. http://dx.doi.org/10.1038/scientificamerican0606-68.
[2] Jackson, D. Software abstractions: logic, language and analysis. MIT Press, Cambridge, MA, 2006.
[3] Abrial, J.-R. Modeling in Event-B: system and software engineering. Cambridge University Press, Cambridge, MA, 2010.
[4] Ben-Ari, M. Principles of the Spin model checker. Springer, London, UK, 2008.
Speeding up CRC32C computations with Intel CRC32 instruction. By Shay Gueron
Information Processing Letters. 112, 5 (Feb. 2012), 179 -185.
CR Review No. 140251
Gueron introduces an algorithm to speed up the CRC32C implementation using the corresponding central processing unit (CPU) CRC32 instruction from Intel to compute cyclic redundancy checks of an arbitrary length buffer with inputs ranging from eight to 64 bits (powers of two).
The paper is a perfect illustration of classical pipelining techniques and throughput-oriented speedup, which are still pertinent today. Figure 3 is a classic. These techniques are taught to undergraduate students in computer science, software, and computer engineering during their system hardware, system software, and assembly programming courses. Thus, the paper has a lot of educational value where classical techniques are used in actual industrial practice. I strongly believe the content of this paper should become a part of a textbook on assembly and computer organization.
The paper discusses how to speed up CRC32C computations by a factor of at least three with the Intel instruction, a significant improvement over sequential and previous results. A speed increase like this can be applied to remote direct memory access (RDMA) and the Internet small computer system interface (iSCSI) protocol stack, where CRC32C computation can be a bottleneck when doing integrity checks on communicated data transfers.
The author further improves speed using the hardware CRC32 instruction (capable of processing up to eight bytes with a latency of three CPU cycles) instead of a serial instruction, by logically splitting the input data buffer into three disjoint chunks, processing them with CRC32 in a pipelined manner, and then recombining the results. This fully utilizes the CPU’s pipelined hardware, which Gueron makes throughput oriented rather than latency bound.
The author provides very good, easy-to-read background information, bit arithmetic, and theoretical foundations, and a detailed illustration of the instruction and algorithms. The paper concludes with performance results.
Reviewer: Serguei A. Mokhov (Montreal, Canada)
[This review is a previously published Editor's Pick.]
Mailing address:
Computing Reviews
17 W. 17th Street, 7th Floor
New York, NY 10013
General Inquires:
[email protected]
Editorial Department:
[email protected]
Reviewer Help:
[email protected]
Sales:
[email protected]