Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Handbook of data structures and applications (2nd ed.)
Mehta D., Sahni S., CRC Press, Inc., Boca Raton, FL, 2018. 1120 pp. Type: Book (978-1-498701-85-3)
Date Reviewed: Apr 15 2019

Data structures and algorithms are key elements of a computing system’s operation, determining its effectiveness and efficiency. Choosing the right ones is becoming increasingly important for two reasons. First, worldwide Internet applications and the Internet of Things (IoT) produce, at relentlessly growing rates, data that requires evermore sophisticated processing and analysis. Second, over the past decade, physical constraints have stalled the rise in central processing unit (CPU) clock speeds, preventing software developers from hiding higher processing demands under the carpet of a faster CPU. Handbook of data structures and applications is a weighty compendium, covering hundreds of ideas that can be used for making modern programs operate more efficiently.

Early in their studies, computing students are taught the most common data structures, such as arrays, linked lists, stacks, and queues, as well as the associated traversal, manipulation, searching, and sorting algorithms. Then, in a more advanced course, they are likely to encounter data structures and algorithms associated with trees, hash tables, and graphs. These elements cover considerable ground, and by judiciously employing them, a developer will avoid many common performance pitfalls. It is therefore not surprising that they are covered in four of the book’s 67 chapters. However, in practice, many problems require more specialized algorithms.

Here are some examples taken from the book. With a Bloom filter, one can quickly and with considerable space savings find elements that are definitely not part of a given set. Operations on planar straight-line graphs (PLSGs) ensure the correct and efficient manipulation of triangulations and Voronoi diagrams. Binary space partitioning (BSP) trees speed up computations on 3D geometric models by orders of magnitude, while kinetic data structures can solve proximity, deformation, collision detection, and clustering problems. Then there are data structures that have specific properties. Two examples are persistent data structures, where each update generates a new version, and cache oblivious data structures, whose performance can model any memory hierarchy.

This book details many mainstream and specialized data structures and algorithms. Its seven parts cover “Fundamentals,” “Priority Queues,” “Dictionary Structures,” “Multidimensional/Spatial Structures,” “Miscellaneous” (for example, tries, sets, dynamic graphs, and succinct representations), data structures associated with particular languages and libraries, and vertical application domains. Most parts contain five to ten chapters, written in an authoritative manner by researchers who are obviously experts in the corresponding field. The part dealing with applications is much longer than the rest; its 18 chapters cover areas such as network routing, the web, VLSI design, imaging, computational biology, databases, big data stores, data mining, and computational geometry.

The chapters are typically structured with their own table of contents, a concise introduction, a detailed exposition aided by well-drawn diagrams and tables, as well as scores of references. Some chapters contain mathematical proofs while others include pseudocode, but there does not seem to be a consistent pattern for this throughout the book. In general, though, most chapters cater to both practitioners looking for a solution to a particular problem and academics who need a concise introduction to a given topic.

The book is a second edition. Compared to the 2004 edition, three new chapters have been added that deal with Bloom filters and data structures for cheminformatics and big data stores. Many of the remaining chapters come with a note indicating that they were not updated for the second edition. This is not a huge problem--once a novel data structure or algorithm is invented, further improvements typically come at the margin. More troublesome is the book’s coverage, which seems opaque and uneven. A map indicating areas that are covered and those that are missing might help here. For example, I was unable to find in the book’s index references to regular expressions, file differencing, and clone detection. Nevertheless, the book is a useful complement to Knuth’s magnum opus [1] and deserves a place on the bookshelves of both computer scientists and software developers.

Reviewer:  D. Spinellis Review #: CR146531 (1906-0212)
1) Knuth, D. E. The art of computer programming (3rd ed.). Addison-Wesley, Reading, MA, 1997.
Bookmark and Share
  Featured Reviewer  
 
Data Structures (E.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Data Structures": Date
Handbook of algorithms and data structures
Gonnet G. (ed), Baeza-Yates R., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991. Type: Book (9780201416077)
Feb 1 1992
Data structures and algorithm analysis
Weiss M., Benjamin-Cummings Publ. Co., Inc., Redwood City, CA, 1992. Type: Book (9780805390544)
Aug 1 1992
Data structures and program design in C
Kruse R., Leung B., Tondo C., Prentice-Hall, Inc., Upper Saddle River, NJ, 1992. Type: Book (9780137256495)
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy