Handbook of Data Structures and Applications

In the late sixties, Donald Knuth, winner of the 1974Turing Award, published his landmark

book The Art of Computer Programming: Fundamental Algorithms. This book brought to-

gether a body of knowledge that defined the data structures area. The term data structure,

itself, was defined in this book to be A table of data including structural relationships.

Niklaus Wirth, the inventor of the Pascal language and winner of the 1984 Turing award,

stated that “Algorithms + Data Structures = Programs”. The importance of algorithms

and data structures has been recognized by the community and consequently, every under-

graduate Computer Science curriculum has classes on data structures and algorithms. Both

of these related areas have seen tremendous advances in the decades since the appearance

of the books by Knuth and Wirth. Although there are several advanced and specialized

texts and handbooks on algorithms (and related data structures), there is, to the best of

our knowledge, no text or handbook that focuses exclusively on the wide variety of data

structures that have been reported in the literature. The goalof this handbook is to provide

a comprehensive survey of data structures of di?erent types that are in existence today.

To this end, we have subdivided this handbook into seven parts, each of which addresses

a di?erent facet of data structures. Part I is a review of introductory material. Although

this material is covered in all standard data structures texts, it was included to make the

handbook self-containedand in recognitionofthe factthatthere aremany practitionersand

programmers who may not have had a formal education in Computer Science. Parts II, III,

and IV discuss Priority Queues, Dictionary Structures, and Multidimensional structures,

respectively. These are all well-known classes of data structures. Part V is a catch-all used

for well-known data structures that eluded easy classification. Parts I through V are largely

theoretical in nature: they discuss the data structures, their operations and their complex-

ities. Part VI addresses mechanisms and tools that have been developed to facilitate the

use of data structures in real programs. Many of the data structures discussed in previous

parts are very intricate and take some e?ort to program. The developmentof data structure

libraries and visualization tools by skilled programmers are of critical importance in reduc-

ing the gap between theory and practice. Finally, Part VII examines applications of data

structures. The deployment of many data structures from Parts I through V in a variety

of applications is discussed. Some of the data structures discussed here have been invented

solely in the context of these applications and are not well-known to the broader commu-

nity. Some of the applications discussed include Internet Routing, Web Search Engines,

Databases, Data Mining, Scientific Computing, Geographical Information Systems, Com-

putational Geometry, Computational Biology, VLSI Floorplanning and Layout, Computer

Graphics and Image Processing.

Bookmarks

Handbook of DATA STRUCTURES and APPLICATIONS

Dedication

Preface

About the Editors

Contributors

Contents

Part I: Fundamentals

Chapter 1: Analysis of Algorithms

1.1 Introduction

1.2 Operation Counts

1.3 Step Counts

1.4 Counting Cache Misses

1.4.1 A Simple Computer Model

1.4.2 Effect of Cache Misses on Run Time

1.4.3 Matrix Multiplication

1.5 Asymptotic Complexity

1.5.1 Big Oh Notation (O)

1.5.2 Omega (omega) and Theta (theta) Notations

1.5.3 Little Oh Notation (o)

1.6 Recurrence Equations

1.6.1 Substitution Method

1.6.2 Table-Lookup Method

1.7 Amortized Complexity

1.7.1 What is Amortized Complexity?

1.7.2 Maintenance Contract

Problem Definition

Worst-Case Method

Aggregate Method

Accounting Method

Potential Method

1.7.3 The McWidget Company

Problem Definition

Worst-Case Method

Aggregate Method

Accounting Method

Potential Method

1.7.4 Subset Generation

Problem Definition

Worst-Case Method

Aggregate Method

Accounting Method

Potential Method

1.8 Practical Complexities

Acknowledgment

References

Chapter 2: Basic Structures

2.1 Introduction

2.2 Arrays

2.2.1 Operations on an Array

2.2.2 Sorted Arrays

2.2.3 Array Doubling

2.2.4 Multiple Lists in a Single Array

2.2.5 Heterogeneous Arrays

2.2.6 Multidimensional Arrays

Row- or Column Major Representation

Array of Arrays Representation

Irregular Arrays

2.2.7 Sparse Matrices

2.3 Linked Lists

2.3.1 Chains

2.3.2 Circular Lists

2.3.3 Doubly Linked Circular Lists

2.3.4 Generalized Lists

2.4 Stacks and Queues

2.4.1 Stack Implementation

2.4.2 Queue Implementation

Acknowledgments

References

Chapter 3: Trees

3.1 Introduction

3.2 Tree Representation

3.2.1 List Representation

3.2.2 Left Child-Right Sibling Representation

3.2.3 Binary Tree Representation

3.3 Binary Trees and Properties

3.3.1 Properties

3.3.2 Binary Tree Representation

3.4 Binary Tree Traversals

3.4.1 Inorder Traversal

3.4.2 Preorder Traversal

3.4.3 Postorder Traversal

3.4.4 Level Order Traversal

3.5 Threaded Binary Trees

3.5.1 Threads

3.5.2 Inorder Traversal of a Threaded Binary Tree

3.6 Binary Search Trees

3.6.1 Definition

3.6.2 Search

3.6.3 Insert

3.6.4 Delete

3.6.5 Miscellaneous

3.7 Heaps

3.7.1 Priority Queues

3.7.2 Definition of a Max-Heap

3.7.3 Insertion

3.7.4 Deletion

3.8 Tournament Trees

3.8.1 Winner Trees

3.8.2 Loser Trees

Acknowledgments

References

Chapter 4: Graphs

4.1 Introduction

4.2 Graph Representations

4.2.1 Weighted Graph Representation

4.3 Connectivity, Distance, and Spanning Trees

4.3.1 Spanning Trees

4.4 Searching a Graph

4.4.1 Depth-First Search

4.4.2 Breadth-First Search

4.5 Simple Applications of DFS and BFS

4.5.1 Depth-First Search on a Digraph

4.5.2 Topological Sorting

4.6 Minimum Spanning Tree

4.6.1 Kruskal’s MST Algorithm

4.6.2 Prim’s MST Algorithm

4.6.3 Boruvka’s MST Algorithm

4.6.4 Constrained MST

4.7 Shortest Paths

4.7.1 Single-Source Shortest Paths, Nonnegative Weights

4.7.2 Single-Source Shortest Paths, Arbitrary Weights

4.7.3 All-Pairs Shortest Paths

4.8 Eulerian and Hamiltonian Graphs

Acknowledgment

References

Part II: Priority Queues

Chapter 5: Leftist Trees

5.1 Introduction

5.2 Height-Biased Leftist Trees

5.2.1 Definition

5.2.2 Insertion into a Max HBLT

5.2.3 Deletion of Max Element from a Max HBLT

5.2.4 Melding Two Max HBLTs

5.2.5 Initialization

5.2.6 Deletion of Arbitrary Element from a Max HBLT

5.3 Weight-Biased Leftist Trees

5.3.1 Definition

5.3.2 Max WBLT Operations

Acknowledgment

References

Chapter 6: Skew Heaps

6.1 Introduction

6.2 Basics of Amortized Analysis

6.3 Meldable Priority Queues and Skew Heaps

6.3.1 Meldable Priority Queue Operations

6.3.2 Amortized Cost of Meld Operation

6.4 Bibliographic Remarks

References

Chapter 7: Binomial, Fibonacci, and Pairing Heaps

7.1 Introduction

7.2 Binomial Heaps

7.3 Fibonacci Heaps

7.4 Pairing Heaps

7.5 Pseudocode Summaries of the Algorithms

7.5.1 Link and Insertion Algorithms

7.5.2 Binomial Heap-Specific Algorithms

7.5.3 Fibonacci Heap-Specific Algorithms

7.5.4 Pairing Heap-Specific Algorithms

7.6 Related Developments

Skew-Pairing Heaps

Adaptive Properties of Pairing Heaps

Soft Heaps

References

Chapter 8: Double-Ended Priority Queues

8.1 Definition and an Application

8.2 Symmetric Min-Max Heaps

8.3 Interval Heaps

8.3.1 Inserting an Element

8.3.2 Removing the Min Element

8.3.3 Initializing an Interval Heap

8.3.4 Complexity of Interval Heap Operations

8.3.5 The Complementary Range Search Problem

8.4 Min-Max Heaps

8.4.1 Inserting an Element

8.4.2 Removing the Min Element

8.5 Deaps

8.5.1 Inserting an Element

8.5.2 Removing the Min Element

8.6 Generic Methods for DEPQs

8.6.1 Dual Priority Queues

8.6.2 Total Correspondence

8.6.3 Leaf Correspondence

8.7 Meldable DEPQs

Acknowledgment

References

Part III: Dictionary Structures

Chapter 9: Hash Tables

9.1 Introduction

9.2 Hash Tables for Integer Keys

9.2.1 Hashing by Division

9.2.2 Hashing by Multiplication

9.2.3 Universal Hashing

9.2.4 Static Perfect Hashing

9.2.5 Dynamic Perfect Hashing

9.3 Random Probing

9.3.1 Hashing with Chaining

9.3.2 Hashing with Open Addressing

9.3.3 Linear Probing

9.3.4 Quadratic Probing

9.3.5 Double Hashing

9.3.6 Brent’s Method

9.3.7 Multiple-Choice Hashing

9.3.8 Asymmetric Hashing

9.3.9 LCFS Hashing

9.3.10 Robin-Hood Hashing

9.3.11 Cuckoo Hashing

9.4 Historical Notes

9.5 Other Developments

Acknowledgment

References

Chapter 10: Balanced Binary Search Trees

10.1 Introduction

10.2 Basic Definitions

10.2.1 Trees

10.2.2 Binary Trees as Dictionaries

Simple Searching

Simple Updates

More Searching Procedures

Operations Involving More Trees

10.2.3 Implementation of Binary Search Trees

10.3 Generic Discussion of Balancing

10.3.1 Balance Definitions

10.3.2 Rebalancing Algorithms

10.3.3 Complexity Results

10.4 Classic Balancing Schemes

10.4.1 AVL-Trees

10.4.2 Weight-Balanced Trees

10.4.3 Balanced Binary Trees Based on Multi-Way Trees

10.5 Rebalancing a Tree to Perfect Balance

10.6 Schemes with no Balance Information

10.6.1 Implicit Representation of Balance Information

Using Empty Pointers

Swapping Pointers

10.6.2 General Balanced Trees

10.6.3 Application to Multi-Dimensional Search Trees

10.7 Low Height Schemes

10.8 Relaxed Balance

10.8.1 Red-Black Trees

10.8.2 AVL-Trees

10.8.3 Multi-Way Trees

10.8.4 Other Results

References

Chapter 11: Finger Search Trees

11.1 Finger Searching

11.2 Dynamic Finger Search Trees

11.3 Level Linked (2,4)-Trees

11.4 Randomized Finger Search Trees

11.4.1 Treaps

11.4.2 Skip Lists

11.5 Applications

11.5.1 Optimal Merging and Set Operations

11.5.2 Arbitrary Merging Order

11.5.3 List Splitting

11.5.4 Adaptive Merging and Sorting

Acknowledgment

References

Chapter 12: Splay Trees

12.1 Introduction

12.2 Splay Trees

12.3 Analysis

12.3.1 Access and Update Operations

12.4 Optimality of Splay Trees

12.4.1 Static Optimality

12.4.2 Static Finger Theorem

12.4.3 Working Set Theorem

12.4.4 Other Properties and Conjectures

12.5 Linking and Cutting Trees

12.5.1 Data Structure

12.5.2 Solid Trees

12.5.3 Rotation

12.5.4 Splicing

12.5.5 Splay in Virtual Tree

12.5.6 Analysis of Splay in Virtual Tree

12.5.7 Implementation of Primitives for Linking and Cutting Trees

12.6 Case Study: Application to Network Flows

Push(v,w)

Relabel(v)

Preflow-Push Algorithms

12.7 Implementation Without Linking and Cutting Trees

Push/Relabel(v)

Discharge(v)

FIFO/Queue

12.8 FIFO: Dynamic Tree Implementation

Tree-Push(v)

Analysis

12.9 Variants of Splay Trees and Top-Down Splaying

Acknowledgment

References

Chapter 13: Randomized Dictionary Structures

13.1 Introduction

13.2 Preliminaries

13.2.1 Randomized Algorithms

13.2.2 Basics of Probability Theory

13.2.3 Conditional Probability

13.2.4 Some Basic Distributions

Bernoulli Distribution

Binomial Distribution

Geometric Distribution

Negative Binomial distribution

13.2.5 Tail Estimates

13.3 Skip Lists

13.4 Structural Properties of Skip Lists

13.4.1 Number of Levels in Skip List

13.4.2 Space Complexity

13.5 Dictionary Operations

13.6 Analysis of Dictionary Operations

13.7 Randomized Binary Search Trees

13.7.1 Insertion in RBST

13.7.2 Deletion in RBST

13.8 Bibliographic Remarks

References

Chapter 14: Trees with Minimum Weighted Path Length

14.1 Introduction

14.2 Huffman Trees

14.2.1 O(n log n) Time Algorithm

14.2.2 Linear Time Algorithm for Presorted Sequence of Items

14.2.3 Relation between General Uniquely Decipherable Codes and Prefix-free Codes

14.2.4 Huffman Codes and Entropy

14.2.5 Huffman Algorithm for t-ary Trees

14.3 Height Limited Huffman Trees

14.3.1 Reduction to the Coin Collector Problem

14.3.2 The Algorithm for the Coin Collector Problem

14.4 Optimal Binary Search Trees

14.4.1 Approximately Optimal Binary Search Trees

14.5 Optimal Alphabetic Tree Problem

14.5.1 Computing the Cost of Optimal Alphabetic Tree

14.5.2 Construction of Optimal Alphabetic Tree

14.5.3 Optimal Alphabetic Trees for Presorted Items

14.6 Optimal Lopsided Trees

14.7 Parallel Algorithms

References

Chapter 15: B Trees

15.1 Introduction

15.2 The Disk-Based Environment

15.3 The B-tree

15.3.1 B-tree Definition

15.3.2 B-tree Query

15.3.3 B-tree Insertion

15.3.4 B-tree Deletion

15.4 The B+-tree

15.4.1 Copy-up and Push-up

15.4.2 B+-tree Query

15.4.3 B+-tree Insertion

15.4.4 B+-tree Deletion

15.5 Further Discussions

15.5.1 Eficiency Analysis

15.5.2 Why is the B+-tree Widely Accepted?

15.5.3 Bulk-Loading a B+-tree

15.5.4 Aggregation Query in a B+-tree

References

Part IV: Multidimensional and Spatial Structures

Chapter 16: Multidimensional Spatial Data Structures

16.1 Introduction

16.2 Point Data

16.3 Bucketing Methods

16.4 Region Data

16.5 Rectangle Data

16.6 Line Data and Boundaries of Regions

16.7 Research Issues and Summary

Acknowledgment

References

Chapter 17: Planar Straight Line Graphs

17.1 Introduction

17.2 Features of PSLGs

17.3 Operations on PSLGs

Edge insertion and deletion

Vertex split and edge contraction

17.4 Winged-Edge

17.5 Halfedge

Access functions

Edge insertion and deletion

Vertex split and edge contraction

17.6 Quadedge

17.7 Further Remarks

17.8 Glossary

Acknowledgment

References

Chapter 18: Interval, Segment, Range, and Priority Search Trees

18.1 Introduction

18.2 Interval Trees

18.2.1 Construction of Interval Trees

18.2.2 Example and Its Applications

18.3 Segment Trees

18.3.1 Construction of Segment Trees

18.3.2 Examples and Its Applications

18.4 Range Trees

18.4.1 Construction of Range Trees

18.4.2 Examples and Its Applications

18.5 Priority Search Trees

18.5.1 Construction of Priority Search Trees

18.5.2 Examples and Its Applications

Acknowledgment

References

Chapter 19: Quadtrees and Octrees

19.1 Introduction

19.2 Quadtrees for Point Data

19.2.1 Point Quadtrees

19.2.2 Region Quadtrees

19.2.3 Compressed Quadtrees and Octrees

19.2.4 Cell Orderings and Space-Filling Curves

19.2.5 Construction of Compressed Quadtrees

A Divide-and-Conquer Construction Algorithm

Bottom-up Construction

19.2.6 Basic Operations

Point and Cell Queries

Insertions and Deletions

Cell Insertion

Cell Deletion

19.2.7 Practical Considerations

19.3 Spatial Queries with Region Quadtrees

19.3.1 Range Query

19.3.2 Spherical Region Queries

19.3.3 k-Nearest Neighbors

19.4 Image Processing Applications

19.4.1 Construction of Image Quadtrees

19.4.2 Union and Intersection of Images

19.4.3 Rotation and Scaling

19.4.4 Connected Component Labeling

19.5 Scientific Computing Applications

19.5.1 The N-body Problem

Acknowledgment

References

Chapter 20: Binary Space Partitioning Trees

20.1 Introduction

20.2 BSP Trees as a Multi-Dimensional Search Structure

20.3 Visibility Orderings

20.3.1 Total Ordering of a Collection of Objects

20.3.2 Visibility Ordering as Tree Traversal

20.3.3 Intra-Object Visibility

20.4 BSP Tree as a Hierarchy of Regions

20.4.1 Tree Merging

20.4.2 Good BSP Trees

20.4.3 Converting B-reps to Trees

20.4.4 Boundary Representations vs. BSP Trees

Bibliography

Chapter 21: R-trees

21.1 Introduction

21.2 Basic Concepts

Intersection queries

Updating the tree

21.3 Improving Performance

21.3.1 R* Tree

21.3.2 Hilbert Tree

21.3.3 Bulk Loading

General Algorithm

Nearest-X (NX)

Hilbert Sort (HS)

Sort-Tile-Recursive (STR)

21.4 Advanced Operations

21.4.1 Nearest Neighbor Queries

21.4.2 Spatial Joins

21.5 Analytical Models

Acknowledgment

References

Chapter 22: Managing Spatio-Temporal Data

22.1 Introduction and Background

22.2 Overlapping Linear Quadtree

22.2.1 Insertion of an Object in MVLQ

22.2.2 Deletion of an Object in MVLQ

22.2.3 Updating an Object in MVLQ

22.3 3D R-tree

22.3.1 Answering Spatio-Temporal Queries Using the Unified Schema

22.3.2 Performance Analysis of 3D R-trees

22.3.3 Handling Queries with Open Transaction-Times

22.4 2+3 R-tree

22.5 HR-tree

22.6 MV3R-tree

22.7 Indexing Structures for Continuously Moving Objects

22.7.1 TPR-tree

22.7.2 REXP -tree

22.7.3 STAR-tree

22.7.4 TPR*-tree

References

Chapter 23: Kinetic Data Structures

23.1 Introduction

23.2 Motion in Computational Geometry

23.3 Motion Models

23.4 Kinetic Data Structures

23.4.1 Convex Hull Example

23.4.2 Performance Measures for KDS

23.4.3 The Convex Hull, Revisited

23.5 A KDS Application Survey

23.5.1 Extent Problems

23.5.2 Proximity Problems

23.5.3 Triangulations and Tilings

23.5.4 Collision Detection

23.5.5 Connectivity and Clustering

23.5.6 Visibility

23.5.7 Result Summary

23.5.8 Open Problems

Recovery after multiple certificate failures

Hierarchical motion descriptions

Motion sensitivity

Non-canonical structures

23.6 Querying Moving Objects

23.7 Sources and Related Materials

References

Chapter 24: Online Dictionary Structures

24.1 Introduction

24.2 Trie Implementations

24.3 Binary Search Tree Implementations

24.4 Balanced BST Implementation

24.5 Additional Operations

24.6 Discussion

References

Chapter 25: Cuttings

25.1 Introduction

25.2 The Cutting Construction

25.2.1 Geometric Sampling

25.2.2 Optimal Cuttings

25.3 Applications

25.3.1 Point Location

25.3.2 Hopcroft’s problem

25.3.3 Convex Hulls and Voronoi Diagrams

25.3.4 Range Searching

Acknowledgments

References

Chapter 26: Approximate Geometric Query Structures

26.1 Introduction

26.2 General Terminology

26.3 Approximate Queries

26.4 Quasi-BAR Bounds

26.5 BBD Trees

26.6 BAR Trees

26.7 Maximum-Spread k-d Trees

Acknowledgment

References

Chapter 27: Geometric and Spatial Data Structures in External Memory

27.1 Introduction

27.1.1 Disk Model

27.1.2 Design Criteria for External Memory Data Structures

27.1.3 Overview of Chapter

27.2 EM Algorithms for Batched Geometric Problems

27.3 External Memory Tree Data Structures

27.3.1 B-trees and Variants

27.3.2 Weight-Balanced B-trees

27.3.3 Parent Pointers and Level-Balanced B-trees

27.3.4 Buffer Trees

27.4 Spatial Data Structures and Range Search

27.4.1 Linear-Space Spatial Structures

27.4.2 R-trees

27.4.3 Bootstrapping for 2-D Diagonal Corner and Stabbing Queries

27.4.4 Bootstrapping for Three-Sided Orthogonal 2-D Range Search

27.4.5 General Orthogonal 2-D Range Search

27.4.6 Lower Bounds for Orthogonal Range Search

27.5 Related Problems

27.6 Dynamic and Kinetic Data Structures

27.6.1 Logarithmic Method for Decomposable Search Problems

27.6.2 Continuously Moving Items

27.7 Conclusions

Acknowledgment

References

Part V: Miscellaneous Data Structures

Chapter 28: Tries

28.1 What Is a Trie?

28.2 Searching a Trie

28.3 Keys with Different Length

28.4 Height of a Trie

28.5 Space Required and Alternative Node Structures

28.6 Inserting into a Trie

28.7 Removing an Element

28.8 Prefix Search and Applications

Criminology

Automatic Command Completion

28.9 Compressed Tries

28.9.1 Compressed Tries with Digit Numbers

Searching a Compressed Trie with Digit Numbers

Inserting into a Compressed Trie with Digit Numbers

Removing an Element from a Compressed Trie with Digit Numbers

28.9.2 Compressed Tries with Skip Fields

28.9.3 Compressed Tries with Edge Information

Searching a Compressed Trie with Edge Information

Inserting into a Compressed Trie with Edge Information

Removing an Element from a Compressed Trie with Edge Information

28.9.4 Space Required by a Compressed Trie

28.10 Patricia

28.10.1 Searching

28.10.2 Inserting an Element

28.10.3 Removing an Element

Acknowledgment

References

Chapter 29: Suffix Trees and Suffix Arrays

29.1 Basic Definitions and Properties

29.2 Linear Time Construction Algorithms

29.2.1 Suffix Trees vs. Suffix Arrays

29.2.2 Linear Time Construction of Suffix Trees

McCreight’s Algorithm

Generalized Suffix Trees

29.2.3 Linear Time Construction of Suffix Arrays

K?r?kkanen and Sanders’ Algorithm

29.2.4 Space Issues

29.3 Applications

29.3.1 Pattern Matching

Pattern Matching using Suffix Trees

Pattern Matching using Suffix Arrays

29.3.2 Longest Common Substrings

29.3.3 Text Compression

29.3.4 String Containment

29.3.5 Suffix-Prefix Overlaps

29.4 Lowest Common Ancestors

Bender and Farach’s lca algorithm

29.5 Advanced Applications

29.5.1 Suffix Links from Lowest Common Ancestors

29.5.2 Approximate Pattern Matching

29.5.3 Maximal Palindromes

Acknowledgment

References

Chapter 30: String Searching

30.1 Introduction

30.2 Preliminaries

30.3 The DAWG

30.3.1 A Simple Algorithm for Constructing the DAWG

30.3.2 Constructing the DAWG in Linear Time

30.4 The Compact DAWG

30.4.1 Using the Compact DAWG to Find the Locations of a String in the Text

30.4.2 Variations and Applications

30.5 The Position Heap

30.5.1 Building the Position Heap

30.5.2 Querying the Position Heap

30.5.3 Time Bounds

30.5.4 Improvements to the Time Bounds

References

Chapter 31: Persistent Data Structures

31.1 Introduction

31.2 Algorithmic Applications of Persistent Data Structures

31.3 General Techniques for Making Data Structures Persistent

31.3.1 The Fat Node Method

31.3.2 Node Copying and Node Splitting

31.3.3 Handling Arrays

31.3.4 Making Data Structures Confluently Persistent

31.4 Making Specific Data Structures More Efficient

31.4.1 Redundant Binary Counters

31.4.2 Persistent Deques

31.5 Concluding Remarks and Open Questions

Acknowledgment

References

Chapter 32: PQ Trees, PC Trees, and Planar Graphs

32.1 Introduction

32.2 The Consecutive-Ones Problem

32.2.1 A Data Structure for Representing the PC Tree

32.2.2 Finding the Terminal Path Efficiently

32.2.3 Performing the Update Step on the Terminal Path Efficiently

32.2.4 The Linear Time Bound

32.3 Planar Graphs

32.3.1 Preliminaries

32.3.2 The Strategy

32.3.3 Implementing the Recursive Step

The Terminal Path

Finding the Terminal Path

The Linear Time Bound

32.3.4 Difierences between the Original PQ-Tree and the New PC-Tree Approaches

32.3.5 Returning a Kuratowski Subgraph when G is Non-Planar

32.4 Acknowledgment

References

Chapter 33: Data Structures for Sets

33.1 Introduction

33.1.1 Models of Computation

33.2 Simple Randomized Set Representations

33.2.1 The Hash Trie

33.2.2 Some Remarks on Unique Representations

33.3 Equality Testing

33.4 Extremal Sets and Subset Testing

33.4.1 Static Extremal Sets

33.4.2 Dynamic Set Intersections and Subset Testing

33.5 The Disjoint Set Union-Find Problem

33.5.1 The Classical Union-Find Problem and Variants

33.6 Partition Maintenance Algorithms

33.7 Conclusions

References

Chapter 34: Cache-Oblivious Data Structures

34.1 The Cache-Oblivious Model

34.2 Fundamental Primitives

34.2.1 Van Emde Boas Layout

Layout

Search

Range query

34.2.2 k-Merger

Binary mergers and merge trees

k-merger

Funnelsort

34.3 Dynamic B-Trees

34.3.1 Density Based

Structure

Updates

Range queries

34.3.2 Exponential Tree Based

Structure

Search

Updates

Reducing space usage

34.4 Priority Queues

34.4.1 Merge Based Priority Queue: Funnel Heap

Structure

Layout

Operations

Analysis

34.4.2 Exponential Level Based Priority Queue

Structure

Layout

Operations

34.5 2d Orthogonal Range Searching

34.5.1 Cache-Oblivious kd-Tree

Structure

Query

Construction

Updates

34.5.2 Cache-Oblivious Range Tree

Three-Sided Queries

Structure

Layout

Query

Four-sided queries

Acknowledgments

References

Chapter 35: Dynamic Trees

35.1 Introduction

35.2 Linking and Cutting Trees

35.2.1 Using Operations on Vertex-Disjoint Paths

35.2.2 Implementing Operations on Vertex-Disjoint Paths

35.3 Topology Trees

35.3.1 Construction

35.3.2 Updates

35.3.3 Applications

35.4 Top Trees

35.4.1 Updates

35.4.2 Representation and Applications

35.5 ET Trees

35.5.1 Updates

35.5.2 Applications

35.6 Reachability Trees

35.7 Conclusions

Acknowledgments

References

Chapter 36: Dynamic Graphs

36.1 Introduction

36.2 Techniques for Undirected Graphs

36.2.1 Clustering

36.2.2 Sparsification

36.2.3 Randomization

Maintaining Spanning Forests

Random Sampling

Graph Decomposition

36.3 Techniques for Directed Graphs

36.3.1 Kleene Closures

Logarithmic Decomposition

Recursive Decomposition

36.3.2 Long Paths

36.3.3 Locality

36.3.4 Matrices

36.4 Connectivity

36.4.1 Updates in O(log2 n) Time

36.5 Minimum Spanning Tree

36.5.1 Deletions in O(log2 n) Time

36.5.2 Updates in O(log4 n) Time

36.6 Transitive Closure

36.6.1 Updates in O( n2 log n) Time

36.6.2 Updates in O(n2) Time

36.7 All-Pairs Shortest Paths

36.7.1 Updates in O(n2.5...) Time

36.7.2 Updates in O(n2 log3 n) Time

36.8 Conclusions

Acknowledgment

References

Chapter 37: Succinct Representation of Data Structures

37.1 Introduction

37.2 Bitvector

37.3 Succinct Dictionaries

37.3.1 Indexable Dictionary

37.3.2 Fully Indexable Dictionary

37.3.3 Dynamic Dictionary

37.4 Tree Representations

37.4.1 Binary Trees

37.4.2 Ordinal Trees

37.4.3 Cardinal Trees

37.4.4 Dynamic Binary Trees

37.5 Graph Representations

37.6 Succinct Structures for Indexing

37.7 Permutations and Functions

37.7.1 Permutations

37.7.2 Functions

37.8 Partial Sums

37.9 Arrays

37.9.1 Resizable Arrays

37.9.2 Dynamic Arrays

37.10 Conclusions

References

Chapter 38: Randomized Graph Data-Structures for Approximate Shortest Paths

38.1 Introduction

38.2 A Randomized Data-Structure for Static APASP : Approximate Distance Oracles

38.2.1 3-Approximate Distance Oracle

38.2.2 Preliminaries

38.2.3 (2k – 1)-Approximate Distance Oracle

Reporting distance with stretch at-most (2k – 1)

Size of the (2k – 1)-approximate distance oracle

38.2.4 Computing Approximate Distance Oracles

Computing Balli(u) efficiently

38.3 A Randomized Data-Structure for Decremental APASP

38.3.1 Main Idea

38.3.2 Notations

38.3.3 Hierarchical Distance Maintaining Data-Structure

38.3.4 Bounding the Size of … under Edge-Deletions

Maintaining the BFS tree … under edge deletions

Some technical details

38.3.5 Improved Decremental Algorithm for APASP up to Distance d

38.4 Further Reading and Bibliography

Acknowledgment

References

Chapter 39: Searching and Priority Queues in o(log n) Time

39.1 Introduction

39.2 Model of Computation

39.3 Overview

39.4 Achieving Sub-Logarithmic Time per Element by Simple Means

39.4.1 Range Reduction

39.4.2 Packing Keys

39.4.3 Combining

39.5 Deterministic Algorithms and Linear Space

39.5.1 Fusion Trees

39.5.2 Exponential Search Trees

39.6 From Amortized Update Cost to Worst-Case

39.7 Sorting and Priority Queues

39.7.1 Range Reduction

39.7.2 Packed Sorting

39.7.3 Combining the Techniques

39.7.4 Further Techniques and Faster Randomized Algorithms

References

Part VI: Data Structures in Languages and Libraries

Chapter 40: Functional Data Structures

40.1 Introduction

40.1.1 Data Structures in Functional Languages

Immutability

Recursion

Garbage Collection

Pattern Matching

40.1.2 Functional Data Structures in Mainstream Languages

Fewer Bugs

Increased Sharing

Decreased Synchronization

40.2 Stacks: A Simple Example

40.3 Binary Search Trees: Path Copying

40.4 Skew Heaps: Amortization and Lazy Evaluation

40.4.1 Analysis of Lazy Skew Heaps

40.5 Difficulties

40.6 Further Reading

Acknowledgments

References

Chapter 41: LEDA, a Platform for Combinatorial and Geometric Computing

41.1 Introduction

41.1.1 Ease of Use

41.1.2 Extensibility

41.1.3 Correctness

41.1.4 Availability and Usage

41.2 The Structure of LEDA

41.3 Data Structures and Data Types

41.3.1 Basic Data Types

41.3.2 Numbers and Matrices

41.3.3 Advanced Data Types

41.3.4 Graph Data Structures

41.3.5 Geometry Kernels

41.3.6 Advanced Geometric Data Structures

41.4 Algorithms

41.5 Visualization

41.5.1 GraphWin

41.5.2 GeoWin

41.6 Example Programs

41.6.1 Word Count

41.6.2 Shortest Paths

41.6.3 Curve Reconstruction

41.6.4 Upper Convex Hull

41.6.5 Delaunay Flipping

41.6.6 Discussion

41.7 Projects Enabled by LEDA

References

Chapter 42: Data Structures in C++

42.1 Introduction

42.2 Basic Containers

42.2.1 Sequence Containers

42.2.2 Sorted Associative Containers

Sets and Multisets

Maps and Multimaps

42.2.3 Container Adapters

42.3 Iterators

42.3.1 Basics

42.3.2 Reverse Iterators

42.4 Additional Components of the STL

42.4.1 Sorting, Searching, and Selection

Sorting

Selection

Searching

42.4.2 Non-Standard Extensions

42.5 Sample Code

Acknowledgment

References

Chapter 43: Data Structures in JDSL

43.1 Introduction

43.2 Design Concepts in JDSL

43.2.1 Containers and Accessors

43.2.2 Iterators

43.2.3 Decorations

43.2.4 Comparators

43.2.5 Algorithms

43.3 The Architecture of JDSL

43.3.1 Packages

43.3.2 Positional Containers

Sequences

Trees

Graphs

43.3.3 Key-Based Containers

Priority queues

Dictionaries

43.3.4 Algorithms

Sequence sorting

Iterator-based tree traversals

Euler tour tree traversal

Graph traversals

Topological numbering

Dijkstra’s algorithm

The Prim-Jarník algorithm

43.4 A Sample Application

43.4.1 Minimum-Time Flight Itineraries

43.4.2 Class IntegerDijkstraTemplate

43.4.3 Class IntegerDijkstraPathfinder

43.4.4 Class FlightDijkstra

Acknowledgments

References

Chapter 44: Data Structure Visualization

44.1 Introduction

44.2 Value of Data Structure Rendering

44.3 Issues in Data Structure Visualization Systems

44.3.1 Purpose and Environment

44.3.2 Data Structure Views

44.3.3 Interacting with a System

44.4 Existing Research and Systems

44.4.1 Incense

44.4.2 VIPS

44.4.3 GELO

44.4.4 DDD

44.4.5 Other Systems

44.5 Summary and Open Problems

References

Chapter 45: Drawing Trees

45.1 Introduction

45.2 Preliminaries

45.3 Level Layout for Binary Trees

45.4 Level Layout for n-ary Trees

45.4.1 PrePosition

45.4.2 Combining a Subtree and Its Left Subforest

45.4.3 Ancestor

45.4.4 Apportion

45.4.5 Shifting the Smaller Subtrees

45.5 Radial Layout

45.6 HV-Layout

Acknowledgment

References

Chapter 46: Drawing Graphs

46.1 Introduction

46.2 Preliminaries

46.3 Convex Drawing

46.3.1 Barycenter Algorithm

46.3.2 Divide and Conquer Algorithm

46.3.3 Algorithm Using Canonical Ordering

46.4 Symmetric Drawing

46.4.1 Displaying Rotational Symmetry

46.4.2 Displaying Axial Symmetry

46.4.3 Displaying Dihedral Symmetry

46.5 Visibility Drawing

46.5.1 Planar st-Graphs

46.5.2 The Bar Visibility Algorithm

46.5.3 Bar Visibility Representations and Layered Drawings

46.5.4 Bar Visibility Representations for Orthogonal Drawings

46.6 Conclusion

References

Chapter 47: Concurrent Data Structures

47.1 Designing Concurrent Data Structures

47.1.1 Performance

47.1.2 Blocking Techniques

47.1.3 Nonblocking Techniques

47.1.4 Complexity Measures

47.1.5 Correctness

47.1.6 Verification Techniques

47.1.7 Tools of the Trade

Locks

Barriers

Transactional Synchronization Mechanisms

47.2 Shared Counters and Fetch-and-phi Structures

Combining

Counting Networks

47.3 Stacks and Queues

Stacks

Queues

Deques

47.4 Pools

47.5 Linked Lists

47.6 Hash Tables

47.7 Search Trees

47.8 Priority Queues

Heap-Based Priority Queues

Tree-Based Priority Pools

47.9 Summary

References

Part VII: Applications

Chapter 48: IP Router Tables

48.1 Introduction

48.2 Longest Matching-Prefix

48.2.1 Linear List

48.2.2 End-Point Array

48.2.3 Sets of Equal-Length Prefixes

48.2.4 Tries

1-Bit Tries

Fixed-Stride Tries

Variable-Stride Tries

48.2.5 Binary Search Trees

48.2.6 Priority Search Trees

48.3 Highest-Priority Matching

48.3.1 The Data Structure BOB

48.3.2 Search for the Highest-Priority Matching Range

48.4 Most-Specific-Range Matching

48.4.1 Nonintersecting Ranges

48.4.2 Conflict-Free Ranges

Acknowledgment

References

Chapter 49: Multi-Dimensional Packet Classification

49.1 Introduction

49.1.1 Problem Statement

49.2 Performance Metrics for Classification Algorithms

49.3 Classification Algorithms

49.3.1 Background

Bounds from Computational Geometry

Range lookups

49.3.2 Taxonomy of Classification Algorithms

49.3.3 Basic Data Structures

Linear search

Hierarchical tries

Set-pruning tries

49.3.4 Geometric Algorithms

Grid-of-tries

Cross-producting

A 2-dimensional classification scheme

Area-based quadtree

Fat Inverted Segment tree (FIS-tree)

Dynamic multi-level tree algorithms

49.3.5 Heuristics

Recursive Flow Classification (RFC)

Hierarchical Intelligent Cuttings (HiCuts)

Tuple Space Search

49.3.6 Hardware-Based Algorithms

Ternary CAMs

Bitmap-intersection

49.4 Summary

References

Chapter 50: Data Structures in Web Information Retrieval

50.1 Introduction

50.2 Inverted Indices

50.2.1 Index Compression

50.2.2 Index Granularity

50.3 Fingerprints

50.4 Finding Near-Duplicate Documents

50.5 Conclusions

References

Chapter 51: The Web as a Dynamic Graph

51.1 Introduction

51.2 Experimental Observations

51.3 Theoretical Growth Models

51.4 Properties of Web Graphs and Web Algorithmics

51.4.1 Generating Function Framework

51.4.2 Average Path Length

51.4.3 Emergence of Giant Components

51.4.4 Search on Web Graphs

51.4.5 Crawling and Trawling

51.5 Conclusions

References

Chapter 52: Layout Data Structures

52.1 Introduction

52.2 VLSI Technology

52.3 Layout Data Structures: an Overview

52.4 Corner Stitching

52.4.1 Point Finding

52.4.2 Tile Insertion

52.4.3 Storage Requirements of the Corner Stitching Data Structure

52.5 Corner Stitching Extensions

52.5.1 Expanded Rectangles

52.5.2 Trapezoidal Tiles

52.5.3 Curved Tiles

52.5.4 L-shaped Tiles

Rectilinear Polygons

Parallel Corner Stitching

Comments about Corner Stitching

52.6 Quad Trees and Variants

52.6.1 Bisector List Quad Trees

52.6.2 k-d Trees

52.6.3 Multiple Storage Quad Trees

52.6.4 Quad List Quad Trees

52.6.5 Bounded Quad Trees

52.6.6 HV Trees

52.6.7 Hinted Quad Trees

52.7 Concluding Remarks

Acknowledgment

References

Chapter 53: Floorplan Representation in VLSI

53.1 Introduction

53.1.1 Statement of Floorplanning Problem

53.1.2 Motivation of the Representation

53.1.3 Combinations and Complexities of the Various Representations

53.1.4 Slicing, Mosaic, LB Compact, and General Floorplans

53.2 Graph Based Representations

53.2.1 Constraint Graphs

The generation of constraint graphs

Triangulation

Tutte’s duality

53.2.2 Corner Stitching

53.2.3 Twin Binary Tree

53.2.4 Single Tree Representations

53.3 Placement Based Representations

53.3.1 Sequence-Pair

53.3.2 Bounded-Sliceline Grid

53.3.3 Corner Block List

53.3.4 Slicing Tree

53.4 Relationships of the Representations

53.4.1 Summary of the Relationships

53.4.2 A Mosaic Floorplan Example

53.4.3 A General Floorplan Example

53.5 Rectilinear Shape Handling

53.6 Conclusions

53.7 Acknowledgment

References

Chapter 54: Computer Graphics

54.1 Introduction

54.1.1 Hardware and Pipeline

54.2 Basic Applications

54.2.1 Meshes

54.2.2 CAD/CAM Drawings

54.2.3 Fonts

54.2.4 Bitmaps

54.2.5 Texture Mapping

54.3 Data Structures

54.3.1 Vertices, Edges, and Faces

54.3.2 Vertex, Normal, and Face Lists

54.3.3 Winged Edge

54.3.4 Tiled, Multidimensional Array

54.3.5 Linear Interpolation and Bezier Curves

54.4 Applications of Previously Discussed Structures

54.4.1 Hidden Surface Removal: An Application of the BSP Tree

54.4.2 Proximity and Collision: Other Applications of the BSP Tree

54.4.3 More With Trees: CSG Modeling

References

Chapter 55: Geographic Information Systems

55.1 Geographic Information Systems: What They Are All About

55.1.1 Geometric Objects

55.1.2 Topological versus Metric Data

55.1.3 Geometric Operations

55.1.4 Geometric Data Structures

55.1.5 Applications of Geographic Information

Map Overlay

Map Labeling

Cartographic Generalization

Road Maps

Spatiotemporal Data

Data Mining

55.2 Space Filling Curves: Order in Many Dimensions

55.2.1 Recursively Defined Space Filling Curves

55.2.2 Range Queries for Space Filling Curve Data Structures

55.2.3 Are All Space Filling Curves Created Equal?

55.2.4 Many Curve Pieces for a Query Range

55.2.5 One Curve Piece for a Query Range

55.3 Spatial Join

55.3.1 External Algorithms

Index on both spatial relations

Index on one spatial relation

Index on none of the inputs

55.3.2 Advanced Issues

55.4 Models, Toolboxes and Systems for Geographic Information

55.4.1 Standardized Data Models

55.4.2 Commercial Systems

Oracle

SpatialWare

LEDA and CGAL

JTS Topology Suite

55.4.3 Research Prototypes

SAND

XXL

Dedale

Acknowledgment

References

Chapter 56: Collision Detection

56.1 Introduction

56.2 Convex Polytopes

56.2.1 Linear Programming

56.2.2 Voronoi-Based Marching Algorithm

Polytope Representation

Local Walk

Implementation and Application

56.2.3 Minkowski Sums and Convex Optimization

56.3 General Polygonal Models

56.3.1 Interference Detection using Trees of Oriented Bounding Boxes

OBBTree Construction

Interference Detection

OBB Representation and Overlap Test

Implementation and Application

56.3.2 Performance of Bounding Volume Hierarchies

56.4 Penetration Depth Computation

56.4.1 Convex Polytopes

56.4.2 Incremental Penetration Depth Computation

Local Walk

Initialization and Refinement

Implementation and Application

56.4.3 Non-Convex Models

56.5 Large Environments

56.5.1 Multiple-Object Collision Detection

One-Dimensional Sweep and Prune

Implementation and Application

56.5.2 Two-Dimensional Intersection Tests

References

Chapter 57: Image Data Structures

57.1 Introduction

57.2 What is Image Data?

57.3 Quadtrees

57.3.1 What is a Quadtree?

57.3.2 Variants of Quadtrees

Region quadtrees

Line quadtrees

Edge quadtrees

Template quadtrees

57.4 Virtual Quadtrees

57.4.1 Compact Quadtrees

57.4.2 Forest of Quadtrees (FQT)

57.5 Quadtrees and R-trees

57.6 Octrees

57.7 Translation Invariant Data Structure (TID)

57.8 Content-Based Image Retrieval System

57.8.1 What is CBIR?

General structure of CBIR systems

57.8.2 An Example of CBIR System

57.9 Summary

57.10 Acknowledgments

References

Chapter 58: Computational Biology

58.1 Introduction

58.2 Discovering Unusual Words

Statistical analysis of words

Detecting unusual words

58.3 Comparing Whole Genomes

Basic Definitions

Computation of multiMEMs

Space efficient computation of MEMs for two genomes

Acknowledgment

References

Chapter 59: Elimination Structures in Scientific Computing

59.1 The Elimination Tree

59.1.1 The Elimination Game

59.1.2 The Elimination Tree Data Structure

59.1.3 An Algorithm

59.1.4 A Skeleton Graph

59.1.5 Supernodes

59.2 Applications of Etrees

59.2.1 Efficient Symbolic Factorization

59.2.2 Predicting Row and Column Nonzero Counts

59.2.3 Three Classes of Factorization Algorithms

59.2.4 Scheduling Parallel Factorizations

59.2.5 Scheduling Out-of-Core Factorizations

59.3 The Clique Tree

59.3.1 Chordal Graphs and Clique Trees

59.3.2 Design of Efficient Algorithms with Clique Trees

59.3.3 Compact Clique Trees

59.4 Clique Covers and Quotient Graphs

59.4.1 Clique Covers

59.4.2 Quotient Graphs

59.4.3 The Problem of Degree Updates

59.4.4 Covering the Column-Intersection Graph and Biclique Covers

59.5 Column Elimination Trees and Elimination DAGS

59.5.1 The Column Elimination Tree

59.5.2 Elimination DAGS

59.5.3 Elimination Structures for the Asymmetric Multifrontal Algorithm

Acknowledgment

References

Chapter 60: Data Structures for Databases

60.1 Overview of the Functionality of a Database Management System

60.2 Data Structures for Query Processing

60.2.1 Index Structures

One-dimensional Indexes

Multi-dimensional Indexes

60.2.2 Sorting Large Data Sets

60.2.3 The Parse Tree

60.2.4 Expression Trees

60.2.5 Histograms

60.3 Data Structures for Buffer Management

60.4 Data Structures for Disk Space Management

60.4.1 Record Organizations

60.4.2 Page Organizations

60.4.3 File Organization

60.5 Conclusion

References

Chapter 61: Data Mining

61.1 Introduction

61.1.1 Data Mining Tasks and Techniques

61.1.2 Challenges of Data Mining

61.1.3 Data Mining and the Role of Data Structures and Algorithms

61.2 Classification

61.2.1 Nearest-Neighbor Classifiers

61.2.2 Proximity Graphs for Enhancing Nearest Neighbor Classifiers

61.3 Association Analysis

61.3.1 Hash Tree Structure

61.3.2 FP-Tree Structure

61.4 Clustering

61.4.1 Hierarchical and Partitional Clustering

61.4.2 Nearest Neighbor Search and Multi-Dimensional Access Methods

61.5 Conclusion

Acknowledgment

References

Chapter 62: Computational Geometry: Fundamental Structures

62.1 Introduction

62.2 Arrangements

62.2.1 Substructures and Complexity

62.2.2 Decomposition

62.2.3 Duality

62.3 Convex Hulls

62.3.1 Complexity

62.3.2 Construction

62.3.3 Dynamic Convex Hulls

62.4 Voronoi Diagrams

62.4.1 Complexity

62.4.2 Construction

62.4.3 Variations

62.5 Triangulations

62.5.1 Delaunay Triangulation

62.5.2 Polygons

62.5.3 Polyhedra

62.5.4 Pseudo-Triangulations

References

Chapter 63: Computational Geometry: Proximity and Location

63.1 Introduction

63.2 Point Location

63.2.1 Kirkpatrick’s Algorithm

63.2.2 Slab-Based Methods and Persistent Trees

63.2.3 Separating Chains and Fractional Cascading

63.2.4 Trapezoidal Maps and the History Graph

63.2.5 Worst- and Expected-Case Optimal Point Location

63.3 Proximity Structures

63.3.1 Voronoi Diagrams

63.3.2 Delaunay Triangulations

63.3.3 Other Geometric Proximity Structures

63.4 Nearest Neighbor Searching

63.4.1 Nearest Neighbor Searching through Point Location

63.4.2 K-d trees

63.4.3 Other Approaches to Nearest Neighbor Searching

63.4.4 Approximate Nearest Neighbor Searching

63.4.5 Approximate Voronoi Diagrams

63.5 Sources and Related Material

Acknowledgments

References

Chapter 64: Computational Geometry: Generalized Intersection Searching

64.1 Geometric Intersection Searching Problems

64.1.1 Generalized Intersection Searching

64.2 Summary of Known Results

64.2.1 Axes-Parallel Objects

64.2.2 Arbitrarily-Oriented Objects

64.2.3 Problems on the Grid

64.2.4 Single-Shot Problems

64.3 Techniques

64.3.1 A Transformation-Based Approach

The Dynamic Reporting Problem

The static counting problem

The dynamic counting problem

The static type-2 problem

64.3.2 A Sparsification-Based Approach

Generalized halfspace range searching in R2 and R3

64.3.3 A Persistence-Based Approach

Generalized semi-dynamic quadrant searching

Generalized semidynamic 2-dimensional range searching

Generalized 3-dimensional range searching

64.3.4 A General Approach for Reporting Problems

64.3.5 Adding Range Restrictions

64.4 Conclusion and Future Directions

64.5 Acknowledgment

References