Handbook of Data Structures and Applications
出版信息
Dinesh P. Mehta / Chapman and Hall/CRC / 2004-10-28 / USD 135.95
内容简介
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
