O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Handbook of Data Structures and Applications, 2nd Edition

Book Description

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.

Table of Contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright Page
  5. Dedication
  6. Contents
  7. Preface to the Second Edition
  8. Preface to the First Edition
  9. Editors
  10. Contributors
  11. PART I: Fundamentals
    1. 1. Analysis of Algorithms
    2. 2. Basic Structures
    3. 3. Trees
    4. 4. Graphs
  12. PART II: Priority Queues
    1. 5. Leftist Trees
    2. 6. Skew Heaps
    3. 7. Binomial, Fibonacci, and Pairing Heaps
    4. 8. Double-Ended Priority Queues
  13. PART III: Dictionary Structures
    1. 9. Hash Tables
    2. 10. Bloom Filter and Its Variants
    3. 11. Balanced Binary Search Trees
    4. 12. Finger Search Trees
    5. 13. Splay trees
    6. 14. Randomized Dictionary Structures
    7. 15. Trees with Min Weighted Path Length
    8. 16. B Trees
  14. PART IV: Multidimensional/Spatial Structures
    1. 17. Multidimensional Spatial Data Structures
    2. 18. Planar Straight Line Graphs
    3. 19. Interval, Segment, Range, Priority Search Trees
    4. 20. Quadtrees and Octtrees
    5. 21. BSP Trees
    6. 22. R-Trees
    7. 23. Managing Spatio-Temporal Data
    8. 24. Kinetic Data Structures
    9. 25. Online Dictionary Structures
    10. 26. Cuttings
    11. 27. Approximate Geom Query Structures
    12. 28. Geometric and Spatial Data Structures in External Memory
  15. PART V: Miscellaneous
    1. 29. Tries
    2. 30. Suffix Trees and Suffix Arrays
    3. 31. String Searching
    4. 32. Binary Decision Diagrams
    5. 33. Persistent Data Structures
    6. 34. Data Structures for Sets
    7. 35. Cache Oblivious Data Structures
    8. 36. Dynamic Trees
    9. 37. Dynamic Graphs
    10. 38. Succinct Representation of Data Structures
    11. 39. Randomized Graph Data Structures
    12. 40. Searching and Priority Queues in o(log n) Time
  16. PART VI: Data Structures in Langs and Libraries
    1. 41. Functional Data Structures
    2. 42. LEDA, a Platform for Combinatorial and Geometric Computing
    3. 43. Data Structures in C++
    4. 44. Data Structures in JDSL
    5. 45. Data Structure Visualization
    6. 46. Drawing Trees
    7. 47. Drawing Graphs
    8. 48. Concurrent Data Structures
  17. PART VII: Applications
    1. 49. IP Router Tables
    2. 50. Multidimensional Packet Classification
    3. 51. Data Structures in Web Information Retrieval
    4. 52. The Web as a Dynamic Graph
    5. 53. Layout Data Structures
    6. 54. Floorplan Rep in VLSI
    7. 55. Computer Graphics
    8. 56. Geographic Information Systems
    9. 57. Collision Detection
    10. 58. Image Data Structures
    11. 59. Computational Biology
    12. 60. Data Structures for Cheminformatics
    13. 61. Elimination Structures in Scientific Computing
    14. 62. Data Structures for Databases
    15. 63. Data Structures for Big Data Stores
    16. 64. Data Mining
    17. 65. Computational Geometry: Fundamental Structures
    18. 66. Computational Geometry: Proximity and Location
    19. 67. Computational Geometry: Generalized (or Colored) Intersection Searching
  18. Index