The Handbook of Data Structures and Applications was first published over a decade ago. This second edition aims to update the first by focusing on areas of research in data structures that have seen significant progress. While the discipline of data structures has not matured as rapidly as other areas of computer science, the book aims to update those areas that have seen advances.

Retaining the seven-part structure of the first edition, the handbook begins with a review of introductory material, followed by a discussion of well-known classes of data structures, Priority Queues, Dictionary Structures, and Multidimensional structures. The editors next analyze miscellaneous data structures, which are well-known structures that elude easy classification. The book then addresses mechanisms and tools that were developed to facilitate the use of data structures in real programs. It concludes with an examination of the applications of data structures.

Four new chapters have been added on Bloom Filters, Binary Decision Diagrams, Data Structures for Cheminformatics, and Data Structures for Big Data Stores, and updates have been made to other chapters that appeared in the first edition.

The Handbook is invaluable for suggesting new ideas for research in data structures, and for revealing application contexts in which they can be deployed. Practitioners devising algorithms will gain insight into organizing data, allowing them to solve algorithmic problems more efficiently.

part I|66 pages


chapter 1|19 pages

Analysis of Algorithms *

BySartaj Sahni

chapter 2|12 pages

Basic Structures *

ByDinesh P. Mehta

chapter 3|14 pages

Trees *

ByDinesh P. Mehta

chapter 4|18 pages

Graphs *

ByNarsingh Deo

part II|48 pages

Priority Queues

chapter 5|7 pages

Leftist Trees *

BySartaj Sahni

chapter 6|7 pages

Skew Heaps *

ByC. Pandu Rangan

chapter 7|11 pages

Binomial, Fibonacci, and Pairing Heaps

ByMichael L. Fredman

chapter 8|18 pages

Double-Ended Priority Queues *

BySartaj Sahni

part III|133 pages

Dictionary Structures

chapter 9|13 pages

Hash Tables *

ByPat Morin

chapter 10|19 pages

Bloom Filter and Its Variants

ByShigang Chen

chapter 11|20 pages

Balanced Binary Search Trees *

ByArne Andersson, Rolf Fagerberg, Kim S. Larsen

chapter 12|8 pages

Finger Search Trees *

ByGerth Stølting Brodal

chapter 13|18 pages

Splay Trees

BySanjeev Saxena

chapter 14|17 pages

Randomized Dictionary Structures *

ByC. Pandu Rangan

chapter 15|18 pages

Trees with Minimum Weighted Path Length

ByWojciech Rytter

chapter 16|15 pages

B Trees *

ByDonghui Zhang

part IV|194 pages

Multidimensional/Spatial Structures

chapter 17|25 pages

Multidimensional Spatial Data Structures

ByHanan Samet

chapter 18|14 pages

Planar Straight Line Graphs *

BySiu-Wing Cheng

chapter 19|17 pages

Interval, Segment, Range, and Priority Search Trees

ByD. T. Lee, Hung-I Yu

chapter 20|18 pages

Quadtrees and Octrees *

BySrinivas Aluru

chapter 21|14 pages

Binary Space Partitioning Trees *

ByBruce F. Naylor

chapter 22|16 pages

R-Trees *

ByScott Leutenegger, Mario A. Lopez

chapter 23|17 pages

Managing Spatiotemporal Data

BySumeet Dua, S. S. Iyengar

chapter 24|12 pages

Kinetic Data Structures *

ByLeonidas Guibas

chapter 25|8 pages

Online Dictionary Structures

ByTeofilo F. Gonzalez

chapter 26|8 pages

Cuttings *

ByBernard Chazelle

chapter 27|13 pages

Approximate Geometric Query Structures *

ByChristian A. Duncan, Michael T. Goodrich

chapter 28|24 pages

Geometric and Spatial Data Structures in External Memory

ByJeffrey Scott Vitter

part V|194 pages


chapter 29|16 pages

Tries *

BySartaj Sahni

chapter 30|15 pages

Suffix Trees and Suffix Arrays *

BySrinivas Aluru

chapter 31|18 pages

String Searching

ByAndrzej Ehrenfeucht, Ross M. McConnell

chapter 32|15 pages

Binary Decision Diagrams

ByShin-ichi Minato

chapter 33|17 pages

Persistent Data Structures *

ByHaim Kaplan

chapter 34|16 pages

Data Structures for Sets *

ByRajeev Raman

chapter 35|21 pages

Cache-Oblivious Data Structures *

ByLars Arge, Gerth Stølting Brodal, Rolf Fagerberg

chapter 36|14 pages

Dynamic Trees *

ByCamil Demetrescu, Irene Finocchi, Giuseppe F. Italiano

chapter 37|14 pages

Dynamic Graphs *

ByCamil Demetrescu, Irene Finocchi, Giuseppe F. Italiano

chapter 38|16 pages

Succinct Representation of Data Structures *

ByJ. Ian Munro, S. Srinivasa Rao

chapter 39|15 pages

Randomized Graph Data-Structures for Approximate Shortest Paths *

BySurender Baswana, Sandeep Sen

chapter 40|10 pages

Searching and Priority Queues in o(log n) Time *

ByArne Andersson

part VI|126 pages

Data Structures in Langs and Libraries

chapter 41|13 pages

Functional Data Structures *

ByChris Okasaki

chapter 42|14 pages

LEDA, a Platform for Combinatorial and Geometric Computing *

ByStefan Naeher

chapter 43|11 pages

Data Structures in C++

ByMark Allen Weiss

chapter 44|17 pages

Data Structures in JDSL *

ByMichael T. Goodrich, Roberto Tamassia, Luca Vismara

chapter 45|9 pages

Data Structure Visualization *

ByJohn Stasko

chapter 46|15 pages

Drawing Trees *

BySebastian Leipert

chapter 47|18 pages

Drawing Graphs *

ByPeter Eades, Seok-Hee Hong

chapter 48|22 pages

Concurrent Data Structures *

ByMark Moir, Nir Shavit

part VII|296 pages


chapter 49|17 pages

IP Router Tables *

BySartaj Sahni, Kun Suk Kim, Haibin Lu

chapter 50|16 pages

Multi-Dimensional Packet Classification *

ByPankaj Gupta

chapter 51|5 pages

Data Structures in Web Information Retrieval *

ByMonika Henzinger

chapter 52|11 pages

The Web as a Dynamic Graph *

ByS. N. Maheshwari

chapter 53|15 pages

Layout Data Structures *

ByDinesh P. Mehta

chapter 54|23 pages

Floorplan Representation in VLSI *

ByZhou Feng, Bo Yao, Chung-Kuan Cheng

chapter 55|13 pages

Computer Graphics *

ByDale McMullin, Alyn Rockwood

chapter 56|18 pages

Geographic Information Systems

ByBernhard Seeger, Peter Widmayer

chapter 57|14 pages

Collision Detection *

ByMing C. Lin, Dinesh Manocha

chapter 58|14 pages

Image Data Structures *

ByS. S. Iyengar, V. K. Vaishnavi, S. Gunasekaran

chapter 59|18 pages

Computational Biology

ByPaolo Ferragina, Stefan Kurtz, Stefano Lonardi, Giovanni Manzini

chapter 60|10 pages

Data Structures for Cheminformatics

ByDinesh P. Mehta, John D. Crabtree

chapter 61|21 pages

Elimination Structures in Scientific Computing *

ByAlex Pothen, Sivan Toledo

chapter 62|15 pages

Data Structures for Databases *

ByJoachim Hammer, Markus Schneider

chapter 63|13 pages

Data Structures for Big Data Stores

ByArun A. Ravindran, Dinesh P. Mehta

chapter 64|16 pages

Data Mining *

ByVipin Kumar, Pang-Ning Tan, Michael Steinbach

chapter 65|14 pages

Computational Geometry: Fundamental Structures *

ByMark de Berg, Bettina Speckmann

chapter 66|16 pages

Computational Geometry: Proximity and Location *

BySunil Arya, David M. Mount

chapter 67|16 pages

Computational Geometry: Generalized (or Colored) Intersection Searching

ByProsenjit Gupta, Ravi Janardan, Saladi Rahul, Michiel Smid