Handbook of data structures and applications

Handbook of DATA STRUCTURES and APPLICATIONS......Page 3
Dedication......Page 5
Preface......Page 6
About the Editors......Page 8
Contributors......Page 9
Contents......Page 12
Part I: Fundamentals......Page 15
1.1 Introduction......Page 16
1.2 Operation Counts......Page 17
1.3 Step Counts......Page 19
1.4.2 Effect of Cache Misses on Run Time......Page 21
1.4.3 Matrix Multiplication......Page 22
1.5.1 Big Oh Notation (O)......Page 24
1.5.2 Omega (omega) and Theta (theta) Notations......Page 26
1.6 Recurrence Equations......Page 27
1.6.2 Table-Lookup Method......Page 28
1.7.1 What is Amortized Complexity?......Page 29
Aggregate Method......Page 31
Potential Method......Page 32
Worst-Case Method......Page 33
Accounting Method......Page 34
Potential Method......Page 35
Accounting Method......Page 36
Potential Method......Page 37
1.8 Practical Complexities......Page 38
Acknowledgment......Page 39
References......Page 40
2.2 Arrays......Page 41
2.2.1 Operations on an Array......Page 42
2.2.2 Sorted Arrays......Page 43
2.2.4 Multiple Lists in a Single Array......Page 44
Array of Arrays Representation......Page 45
2.2.7 Sparse Matrices......Page 46
2.3 Linked Lists......Page 47
2.3.1 Chains......Page 48
2.3.3 Doubly Linked Circular Lists......Page 50
2.3.4 Generalized Lists......Page 51
2.4.1 Stack Implementation......Page 52
2.4.2 Queue Implementation......Page 54
References......Page 56
3.1 Introduction......Page 57
3.2.3 Binary Tree Representation......Page 59
3.3.1 Properties......Page 60
3.3.2 Binary Tree Representation......Page 62
3.4.1 Inorder Traversal......Page 63
3.4.4 Level Order Traversal......Page 64
3.5.2 Inorder Traversal of a Threaded Binary Tree......Page 65
3.6.2 Search......Page 66
3.6.4 Delete......Page 67
3.6.5 Miscellaneous......Page 68
3.7.2 Definition of a Max-Heap......Page 69
3.7.3 Insertion......Page 70
3.7.4 Deletion......Page 71
3.8.2 Loser Trees......Page 72
References......Page 74
4.1 Introduction......Page 75
4.2 Graph Representations......Page 77
4.2.1 Weighted Graph Representation......Page 79
4.3 Connectivity, Distance, and Spanning Trees......Page 80
4.3.1 Spanning Trees......Page 81
4.4.1 Depth-First Search......Page 82
4.4.2 Breadth-First Search......Page 84
4.5.1 Depth-First Search on a Digraph......Page 86
4.5.2 Topological Sorting......Page 87
4.6.1 Kruskal’s MST Algorithm......Page 88
4.6.2 Prim’s MST Algorithm......Page 90
4.7 Shortest Paths......Page 93
4.7.1 Single-Source Shortest Paths, Nonnegative Weights......Page 94
4.7.2 Single-Source Shortest Paths, Arbitrary Weights......Page 95
4.7.3 All-Pairs Shortest Paths......Page 96
References......Page 98
Part II: Priority Queues......Page 100
5.1 Introduction......Page 101
5.2.1 Definition......Page 102
5.2.4 Melding Two Max HBLTs......Page 104
5.2.5 Initialization......Page 105
5.2.6 Deletion of Arbitrary Element from a Max HBLT......Page 107
5.3.2 Max WBLT Operations......Page 108
References......Page 109
6.1 Introduction......Page 110
6.2 Basics of Amortized Analysis......Page 111
6.3.1 Meldable Priority Queue Operations......Page 114
6.3.2 Amortized Cost of Meld Operation......Page 116
References......Page 118
7.1 Introduction......Page 119
7.2 Binomial Heaps......Page 120
7.3 Fibonacci Heaps......Page 124
7.4 Pairing Heaps......Page 130
7.5.1 Link and Insertion Algorithms......Page 132
7.5.3 Fibonacci Heap-Specific Algorithms......Page 133
7.5.4 Pairing Heap-Specific Algorithms......Page 134
Skew-Pairing Heaps......Page 135
Adaptive Properties of Pairing Heaps......Page 136
Soft Heaps......Page 137
References......Page 138
8.1 Definition and an Application......Page 139
8.2 Symmetric Min-Max Heaps......Page 140
8.3 Interval Heaps......Page 143
8.3.1 Inserting an Element......Page 145
8.3.2 Removing the Min Element......Page 146
8.3.5 The Complementary Range Search Problem......Page 148
8.4 Min-Max Heaps......Page 149
8.4.1 Inserting an Element......Page 150
8.4.2 Removing the Min Element......Page 151
8.5.1 Inserting an Element......Page 154
8.5.2 Removing the Min Element......Page 156
8.6.2 Total Correspondence......Page 157
8.6.3 Leaf Correspondence......Page 158
8.7 Meldable DEPQs......Page 159
References......Page 160
Part III: Dictionary Structures......Page 162
9.1 Introduction......Page 163
9.2 Hash Tables for Integer Keys......Page 164
9.2.2 Hashing by Multiplication......Page 165
9.2.3 Universal Hashing......Page 166
9.2.4 Static Perfect Hashing......Page 167
9.2.5 Dynamic Perfect Hashing......Page 168
9.3 Random Probing......Page 170
9.3.2 Hashing with Open Addressing......Page 171
9.3.5 Double Hashing......Page 173
9.3.7 Multiple-Choice Hashing......Page 174
9.3.9 LCFS Hashing......Page 175
9.3.11 Cuckoo Hashing......Page 176
9.5 Other Developments......Page 177
Acknowledgment......Page 178
References......Page 179
10.1 Introduction......Page 182
10.2.2 Binary Trees as Dictionaries......Page 183
Simple Updates......Page 184
10.3 Generic Discussion of Balancing......Page 185
10.3.2 Rebalancing Algorithms......Page 186
10.3.3 Complexity Results......Page 187
10.4.1 AVL-Trees......Page 188
10.4.2 Weight-Balanced Trees......Page 189
10.4.3 Balanced Binary Trees Based on Multi-Way Trees......Page 190
10.5 Rebalancing a Tree to Perfect Balance......Page 192
Using Empty Pointers......Page 193
10.6.2 General Balanced Trees......Page 195
10.6.3 Application to Multi-Dimensional Search Trees......Page 197
10.7 Low Height Schemes......Page 198
10.8 Relaxed Balance......Page 201
10.8.1 Red-Black Trees......Page 202
10.8.3 Multi-Way Trees......Page 204
References......Page 205
11.1 Finger Searching......Page 210
11.2 Dynamic Finger Search Trees......Page 211
11.3 Level Linked (2,4)-Trees......Page 212
11.4.1 Treaps......Page 213
11.4.2 Skip Lists......Page 214
11.5.1 Optimal Merging and Set Operations......Page 215
11.5.2 Arbitrary Merging Order......Page 216
11.5.4 Adaptive Merging and Sorting......Page 217
References......Page 218
12.1 Introduction......Page 221
12.2 Splay Trees......Page 222
12.3 Analysis......Page 224
12.3.1 Access and Update Operations......Page 226
12.4 Optimality of Splay Trees......Page 227
12.4.2 Static Finger Theorem......Page 228
12.4.4 Other Properties and Conjectures......Page 229
12.5.1 Data Structure......Page 230
12.5.2 Solid Trees......Page 231
12.5.3 Rotation......Page 232
12.5.6 Analysis of Splay in Virtual Tree......Page 234
12.5.7 Implementation of Primitives for Linking and Cutting Trees......Page 235
12.6 Case Study: Application to Network Flows......Page 236
Preflow-Push Algorithms......Page 238
Push/Relabel(v)......Page 239
12.8 FIFO: Dynamic Tree Implementation......Page 240
Analysis......Page 241
Acknowledgment......Page 243
References......Page 244
13.1 Introduction......Page 245
13.2.1 Randomized Algorithms......Page 247
13.2.2 Basics of Probability Theory......Page 248
13.2.3 Conditional Probability......Page 249
Binomial Distribution......Page 251
Negative Binomial distribution......Page 252
13.2.5 Tail Estimates......Page 253
13.3 Skip Lists......Page 254
13.4.1 Number of Levels in Skip List......Page 256
13.5 Dictionary Operations......Page 257
13.6 Analysis of Dictionary Operations......Page 258
13.7 Randomized Binary Search Trees......Page 261
13.7.1 Insertion in RBST......Page 262
13.7.2 Deletion in RBST......Page 263
References......Page 265
14.1 Introduction......Page 267
14.2 Huffman Trees......Page 268
14.2.2 Linear Time Algorithm for Presorted Sequence of Items......Page 270
14.2.3 Relation between General Uniquely Decipherable Codes and Prefix-free Codes......Page 271
14.2.5 Huffman Algorithm for t-ary Trees......Page 273
14.3.1 Reduction to the Coin Collector Problem......Page 274
14.3.2 The Algorithm for the Coin Collector Problem......Page 275
14.4 Optimal Binary Search Trees......Page 276
14.4.1 Approximately Optimal Binary Search Trees......Page 278
14.5.1 Computing the Cost of Optimal Alphabetic Tree......Page 279
14.5.3 Optimal Alphabetic Trees for Presorted Items......Page 281
14.7 Parallel Algorithms......Page 285
References......Page 287
15.1 Introduction......Page 290
15.2 The Disk-Based Environment......Page 291
15.3.1 B-tree Definition......Page 292
15.3.2 B-tree Query......Page 293
15.3.3 B-tree Insertion......Page 294
15.3.4 B-tree Deletion......Page 296
15.4.1 Copy-up and Push-up......Page 299
15.4.2 B+-tree Query......Page 300
15.4.3 B+-tree Insertion......Page 301
15.4.4 B+-tree Deletion......Page 302
15.5.1 Eficiency Analysis......Page 306
15.5.4 Aggregation Query in a B+-tree......Page 307
References......Page 309
Part IV: Multidimensional and Spatial Structures......Page 311
16.1 Introduction......Page 313
16.2 Point Data......Page 315
16.3 Bucketing Methods......Page 320
16.4 Region Data......Page 324
16.5 Rectangle Data......Page 329
16.6 Line Data and Boundaries of Regions......Page 332
16.7 Research Issues and Summary......Page 335
References......Page 336
17.1 Introduction......Page 342
17.2 Features of PSLGs......Page 343
Edge insertion and deletion......Page 344
Vertex split and edge contraction......Page 345
17.4 Winged-Edge......Page 346
17.5 Halfedge......Page 348
Edge insertion and deletion......Page 350
Vertex split and edge contraction......Page 351
17.6 Quadedge......Page 354
17.7 Further Remarks......Page 356
References......Page 357
18.1 Introduction......Page 359
18.2.1 Construction of Interval Trees......Page 360
18.2.2 Example and Its Applications......Page 361
18.3.1 Construction of Segment Trees......Page 363
18.3.2 Examples and Its Applications......Page 365
18.4.1 Construction of Range Trees......Page 368
18.4.2 Examples and Its Applications......Page 370
18.5.1 Construction of Priority Search Trees......Page 375
18.5.2 Examples and Its Applications......Page 376
References......Page 378
19.1 Introduction......Page 380
19.2 Quadtrees for Point Data......Page 381
19.2.1 Point Quadtrees......Page 382
19.2.2 Region Quadtrees......Page 384
19.2.3 Compressed Quadtrees and Octrees......Page 386
19.2.4 Cell Orderings and Space-Filling Curves......Page 388
A Divide-and-Conquer Construction Algorithm......Page 389
19.2.6 Basic Operations......Page 390
19.2.7 Practical Considerations......Page 391
19.3.1 Range Query......Page 393
19.4 Image Processing Applications......Page 395
19.4.1 Construction of Image Quadtrees......Page 396
19.4.3 Rotation and Scaling......Page 397
19.4.4 Connected Component Labeling......Page 398
19.5 Scientific Computing Applications......Page 399
19.5.1 The N-body Problem......Page 400
References......Page 403
20.1 Introduction......Page 406
20.2 BSP Trees as a Multi-Dimensional Search Structure......Page 408
20.3 Visibility Orderings......Page 410
20.3.1 Total Ordering of a Collection of Objects......Page 411
20.3.3 Intra-Object Visibility......Page 412
20.4 BSP Tree as a Hierarchy of Regions......Page 413
20.4.1 Tree Merging......Page 414
20.4.2 Good BSP Trees......Page 417
20.4.3 Converting B-reps to Trees......Page 419
20.4.4 Boundary Representations vs. BSP Trees......Page 420
Bibliography......Page 421
21.1 Introduction......Page 425
Intersection queries......Page 426
Updating the tree......Page 427
21.3.1 R* Tree......Page 429
21.3.2 Hilbert Tree......Page 430
Hilbert Sort (HS)......Page 433
21.4 Advanced Operations......Page 434
21.4.1 Nearest Neighbor Queries......Page 435
21.4.2 Spatial Joins......Page 437
21.5 Analytical Models......Page 439
References......Page 443
22.1 Introduction and Background......Page 448
22.2 Overlapping Linear Quadtree......Page 449
22.2.3 Updating an Object in MVLQ......Page 452
22.3 3D R-tree......Page 453
22.3.1 Answering Spatio-Temporal Queries Using the Unified Schema......Page 456
22.4 2+3 R-tree......Page 458
22.5 HR-tree......Page 459
22.6 MV3R-tree......Page 460
22.7 Indexing Structures for Continuously Moving Objects......Page 462
22.7.1 TPR-tree......Page 463
22.7.3 STAR-tree......Page 465
References......Page 466
23.1 Introduction......Page 468
23.4 Kinetic Data Structures......Page 469
23.4.1 Convex Hull Example......Page 470
23.4.3 The Convex Hull, Revisited......Page 472
23.5 A KDS Application Survey......Page 474
23.5.2 Proximity Problems......Page 475
23.5.4 Collision Detection......Page 476
23.5.5 Connectivity and Clustering......Page 478
23.5.7 Result Summary......Page 479
Recovery after multiple certificate failures......Page 480
Motion sensitivity......Page 481
23.7 Sources and Related Materials......Page 482
References......Page 483
24.1 Introduction......Page 486
24.2 Trie Implementations......Page 487
24.3 Binary Search Tree Implementations......Page 490
24.4 Balanced BST Implementation......Page 492
24.6 Discussion......Page 495
References......Page 496
25.1 Introduction......Page 497
25.2.1 Geometric Sampling......Page 498
25.2.2 Optimal Cuttings......Page 500
25.3 Applications......Page 502
25.3.3 Convex Hulls and Voronoi Diagrams......Page 503
25.3.4 Range Searching......Page 504
References......Page 505
26.1 Introduction......Page 507
26.2 General Terminology......Page 508
26.3 Approximate Queries......Page 509
26.4 Quasi-BAR Bounds......Page 511
26.5 BBD Trees......Page 514
26.6 BAR Trees......Page 516
26.7 Maximum-Spread k-d Trees......Page 521
References......Page 522
27.1 Introduction......Page 524
27.1.1 Disk Model......Page 525
27.1.2 Design Criteria for External Memory Data Structures......Page 526
27.2 EM Algorithms for Batched Geometric Problems......Page 527
27.3.1 B-trees and Variants......Page 532
27.3.2 Weight-Balanced B-trees......Page 533
27.3.3 Parent Pointers and Level-Balanced B-trees......Page 534
27.3.4 Buffer Trees......Page 535
27.4 Spatial Data Structures and Range Search......Page 536
27.4.1 Linear-Space Spatial Structures......Page 537
27.4.2 R-trees......Page 538
27.4.3 Bootstrapping for 2-D Diagonal Corner and Stabbing Queries......Page 541
27.4.4 Bootstrapping for Three-Sided Orthogonal 2-D Range Search......Page 543
27.4.5 General Orthogonal 2-D Range Search......Page 544
27.4.6 Lower Bounds for Orthogonal Range Search......Page 545
27.6 Dynamic and Kinetic Data Structures......Page 546
27.6.1 Logarithmic Method for Decomposable Search Problems......Page 547
27.6.2 Continuously Moving Items......Page 548
References......Page 549
Part V: Miscellaneous Data Structures......Page 557
28.1 What Is a Trie?......Page 559
28.2 Searching a Trie......Page 560
28.4 Height of a Trie......Page 561
28.5 Space Required and Alternative Node Structures......Page 562
28.6 Inserting into a Trie......Page 565
28.7 Removing an Element......Page 566
Automatic Command Completion......Page 567
Searching a Compressed Trie with Digit Numbers......Page 568
Inserting into a Compressed Trie with Digit Numbers......Page 569
Removing an Element from a Compressed Trie with Digit Numbers......Page 570
28.9.3 Compressed Tries with Edge Information......Page 571
Inserting into a Compressed Trie with Edge Information......Page 572
28.10 Patricia......Page 573
28.10.2 Inserting an Element......Page 574
28.10.3 Removing an Element......Page 577
References......Page 578
29.1 Basic Definitions and Properties......Page 579
29.2.1 Suffix Trees vs. Suffix Arrays......Page 582
McCreight’s Algorithm......Page 584
Generalized Suffix Trees......Page 586
Käräkkanen and Sanders’ Algorithm......Page 587
29.2.4 Space Issues......Page 588
29.3 Applications......Page 589
Pattern Matching using Suffix Arrays......Page 590
29.3.2 Longest Common Substrings......Page 592
29.3.3 Text Compression......Page 593
29.3.5 Suffix-Prefix Overlaps......Page 594
Bender and Farach’s lca algorithm......Page 595
29.5.1 Suffix Links from Lowest Common Ancestors......Page 596
29.5.2 Approximate Pattern Matching......Page 597
References......Page 598
30.1 Introduction......Page 600
30.3 The DAWG......Page 603
30.3.1 A Simple Algorithm for Constructing the DAWG......Page 605
30.3.2 Constructing the DAWG in Linear Time......Page 607
30.4 The Compact DAWG......Page 612
30.4.2 Variations and Applications......Page 615
30.5.2 Querying the Position Heap......Page 616
30.5.4 Improvements to the Time Bounds......Page 619
References......Page 623
31.1 Introduction......Page 624
31.2 Algorithmic Applications of Persistent Data Structures......Page 627
31.3.1 The Fat Node Method......Page 632
31.3.2 Node Copying and Node Splitting......Page 633
31.3.3 Handling Arrays......Page 635
31.3.4 Making Data Structures Confluently Persistent......Page 636
31.4 Making Specific Data Structures More Efficient......Page 641
31.4.1 Redundant Binary Counters......Page 643
31.4.2 Persistent Deques......Page 644
References......Page 647
32.1 Introduction......Page 650
32.2 The Consecutive-Ones Problem......Page 655
32.2.1 A Data Structure for Representing the PC Tree......Page 659
32.2.2 Finding the Terminal Path Efficiently......Page 660
32.2.3 Performing the Update Step on the Terminal Path Efficiently......Page 661
32.2.4 The Linear Time Bound......Page 662
32.3.1 Preliminaries......Page 663
32.3.2 The Strategy......Page 664
The Terminal Path......Page 666
The Linear Time Bound......Page 668
32.3.5 Returning a Kuratowski Subgraph when G is Non-Planar......Page 670
References......Page 675
33.1 Introduction......Page 677
33.1.1 Models of Computation......Page 678
33.2.1 The Hash Trie......Page 679
33.3 Equality Testing......Page 682
33.4 Extremal Sets and Subset Testing......Page 686
33.4.2 Dynamic Set Intersections and Subset Testing......Page 687
33.5 The Disjoint Set Union-Find Problem......Page 690
33.5.1 The Classical Union-Find Problem and Variants......Page 691
33.6 Partition Maintenance Algorithms......Page 693
33.7 Conclusions......Page 695
References......Page 696
34.1 The Cache-Oblivious Model......Page 699
Search......Page 701
Range query......Page 702
Binary mergers and merge trees......Page 703
k-merger......Page 704
Funnelsort......Page 705
Structure......Page 706
Range queries......Page 707
Structure......Page 708
Updates......Page 709
34.4 Priority Queues......Page 710
Structure......Page 711
Operations......Page 712
Analysis......Page 713
Structure......Page 715
Operations......Page 716
Query......Page 719
Updates......Page 720
Structure......Page 721
Query......Page 722
Four-sided queries......Page 723
References......Page 724
35.1 Introduction......Page 726
35.2.1 Using Operations on Vertex-Disjoint Paths......Page 727
35.2.2 Implementing Operations on Vertex-Disjoint Paths......Page 729
35.3 Topology Trees......Page 731
35.3.1 Construction......Page 733
35.3.3 Applications......Page 734
35.4 Top Trees......Page 735
35.4.1 Updates......Page 737
35.4.2 Representation and Applications......Page 738
35.5.1 Updates......Page 739
35.5.2 Applications......Page 740
35.6 Reachability Trees......Page 741
References......Page 742
36.1 Introduction......Page 744
36.2.1 Clustering......Page 745
36.2.2 Sparsification......Page 746
Graph Decomposition......Page 747
36.3.1 Kleene Closures......Page 748
36.3.2 Long Paths......Page 749
36.3.3 Locality......Page 750
36.3.4 Matrices......Page 751
36.4 Connectivity......Page 752
36.4.1 Updates in O(log2 n) Time......Page 753
36.5 Minimum Spanning Tree......Page 754
36.5.2 Updates in O(log4 n) Time......Page 755
36.6 Transitive Closure......Page 756
36.6.2 Updates in O(n2) Time......Page 757
36.7 All-Pairs Shortest Paths......Page 758
36.7.1 Updates in O(n2.5...) Time......Page 759
36.8 Conclusions......Page 760
References......Page 761
37.1 Introduction......Page 764
37.2 Bitvector......Page 765
37.3 Succinct Dictionaries......Page 767
37.3.2 Fully Indexable Dictionary......Page 768
37.3.3 Dynamic Dictionary......Page 769
37.4.2 Ordinal Trees......Page 770
37.4.4 Dynamic Binary Trees......Page 773
37.6 Succinct Structures for Indexing......Page 775
37.7.1 Permutations......Page 777
37.7.2 Functions......Page 778
37.8 Partial Sums......Page 779
37.9.1 Resizable Arrays......Page 780
37.9.2 Dynamic Arrays......Page 781
References......Page 782
38.1 Introduction......Page 786
 38.2.1 3-Approximate Distance Oracle......Page 787
38.2.2 Preliminaries......Page 789
38.2.3 (2k – 1)-Approximate Distance Oracle......Page 790
Reporting distance with stretch at-most (2k – 1)......Page 791
38.2.4 Computing Approximate Distance Oracles......Page 792
Computing Balli(u) efficiently......Page 793
38.3.1 Main Idea......Page 795
38.3.3 Hierarchical Distance Maintaining Data-Structure......Page 797
38.3.4 Bounding the Size of … under Edge-Deletions......Page 799
Some technical details......Page 800
38.3.5 Improved Decremental Algorithm for APASP up to Distance d......Page 801
38.4 Further Reading and Bibliography......Page 802
References......Page 803
39.2 Model of Computation......Page 805
39.3 Overview......Page 806
39.4.1 Range Reduction......Page 807
39.4.2 Packing Keys......Page 808
39.4.3 Combining......Page 809
39.5.1 Fusion Trees......Page 810
39.5.2 Exponential Search Trees......Page 812
39.7 Sorting and Priority Queues......Page 814
39.7.2 Packed Sorting......Page 815
39.7.4 Further Techniques and Faster Randomized Algorithms......Page 816
References......Page 817
Part VI: Data Structures in Languages and Libraries......Page 819
40.1 Introduction......Page 820
Fewer Bugs......Page 821
40.2 Stacks: A Simple Example......Page 822
40.3 Binary Search Trees: Path Copying......Page 825
40.4 Skew Heaps: Amortization and Lazy Evaluation......Page 826
40.4.1 Analysis of Lazy Skew Heaps......Page 830
40.5 Difficulties......Page 833
References......Page 834
41.1 Introduction......Page 837
41.1.3 Correctness......Page 838
41.2 The Structure of LEDA......Page 839
41.3.3 Advanced Data Types......Page 840
41.4 Algorithms......Page 841
41.5.1 GraphWin......Page 842
41.5.2 GeoWin......Page 844
41.6.1 Word Count......Page 845
41.6.2 Shortest Paths......Page 846
41.6.3 Curve Reconstruction......Page 848
41.6.4 Upper Convex Hull......Page 850
41.6.5 Delaunay Flipping......Page 851
41.6.6 Discussion......Page 852
References......Page 853
42.2 Basic Containers......Page 855
42.2.1 Sequence Containers......Page 856
42.2.2 Sorted Associative Containers......Page 857
Sets and Multisets......Page 858
Maps and Multimaps......Page 859
42.2.3 Container Adapters......Page 861
42.3.1 Basics......Page 862
Sorting......Page 864
Searching......Page 866
42.5 Sample Code......Page 867
References......Page 870
43.1 Introduction......Page 872
43.2.1 Containers and Accessors......Page 875
43.2.3 Decorations......Page 877
43.3 The Architecture of JDSL......Page 878
43.3.2 Positional Containers......Page 879
Graphs......Page 881
43.3.3 Key-Based Containers......Page 882
Dictionaries......Page 883
Euler tour tree traversal......Page 884
The Prim-Jarník algorithm......Page 885
43.4.2 Class IntegerDijkstraTemplate......Page 886
43.4.4 Class FlightDijkstra......Page 890
Acknowledgments......Page 892
References......Page 893
44.1 Introduction......Page 894
44.2 Value of Data Structure Rendering......Page 895
44.3.1 Purpose and Environment......Page 896
44.3.2 Data Structure Views......Page 897
44.3.3 Interacting with a System......Page 898
44.4 Existing Research and Systems......Page 899
44.4.1 Incense......Page 900
44.4.2 VIPS......Page 901
44.4.3 GELO......Page 902
44.4.4 DDD......Page 903
44.5 Summary and Open Problems......Page 904
References......Page 905
45.1 Introduction......Page 907
45.2 Preliminaries......Page 909
45.3 Level Layout for Binary Trees......Page 910
45.4 Level Layout for n-ary Trees......Page 912
45.4.1 PrePosition......Page 913
45.4.2 Combining a Subtree and Its Left Subforest......Page 915
45.4.3 Ancestor......Page 916
45.4.5 Shifting the Smaller Subtrees......Page 918
45.6 HV-Layout......Page 922
References......Page 924
46.1 Introduction......Page 926
46.2 Preliminaries......Page 929
46.3.1 Barycenter Algorithm......Page 930
46.3.3 Algorithm Using Canonical Ordering......Page 931
46.4 Symmetric Drawing......Page 932
46.4.1 Displaying Rotational Symmetry......Page 935
46.4.2 Displaying Axial Symmetry......Page 936
46.5 Visibility Drawing......Page 938
46.5.1 Planar st-Graphs......Page 940
46.5.2 The Bar Visibility Algorithm......Page 941
46.5.3 Bar Visibility Representations and Layered Drawings......Page 943
46.6 Conclusion......Page 944
References......Page 945
47.1 Designing Concurrent Data Structures......Page 948
47.1.1 Performance......Page 950
47.1.2 Blocking Techniques......Page 951
47.1.3 Nonblocking Techniques......Page 952
47.1.5 Correctness......Page 954
47.1.6 Verification Techniques......Page 955
Locks......Page 956
Transactional Synchronization Mechanisms......Page 958
Combining......Page 959
Counting Networks......Page 960
Stacks......Page 961
Deques......Page 963
47.4 Pools......Page 964
47.5 Linked Lists......Page 965
47.6 Hash Tables......Page 966
47.7 Search Trees......Page 967
Heap-Based Priority Queues......Page 969
References......Page 970
Part VII: Applications......Page 978
48.1 Introduction......Page 980
48.2.1 Linear List......Page 983
48.2.2 End-Point Array......Page 984
48.2.3 Sets of Equal-Length Prefixes......Page 985
1-Bit Tries......Page 987
Fixed-Stride Tries......Page 988
Variable-Stride Tries......Page 990
48.2.5 Binary Search Trees......Page 993
48.2.6 Priority Search Trees......Page 995
48.3.1 The Data Structure BOB......Page 997
48.3.2 Search for the Highest-Priority Matching Range......Page 999
48.4 Most-Specific-Range Matching......Page 1000
48.4.2 Conflict-Free Ranges......Page 1001
References......Page 1002
49.1 Introduction......Page 1004
49.1.1 Problem Statement......Page 1006
49.3.1 Background......Page 1007
Bounds from Computational Geometry......Page 1008
Hierarchical tries......Page 1009
Grid-of-tries......Page 1011
Cross-producting......Page 1012
Area-based quadtree......Page 1014
Fat Inverted Segment tree (FIS-tree)......Page 1015
Dynamic multi-level tree algorithms......Page 1016
Recursive Flow Classification (RFC)......Page 1017
Hierarchical Intelligent Cuttings (HiCuts)......Page 1018
Tuple Space Search......Page 1019
Ternary CAMs......Page 1020
Bitmap-intersection......Page 1021
References......Page 1022
50.2 Inverted Indices......Page 1024
50.2.1 Index Compression......Page 1025
50.3 Fingerprints......Page 1026
50.4 Finding Near-Duplicate Documents......Page 1027
References......Page 1029
51.1 Introduction......Page 1031
51.2 Experimental Observations......Page 1032
51.3 Theoretical Growth Models......Page 1033
51.4.1 Generating Function Framework......Page 1037
51.4.2 Average Path Length......Page 1038
51.4.3 Emergence of Giant Components......Page 1039
51.4.4 Search on Web Graphs......Page 1040
51.4.5 Crawling and Trawling......Page 1042
51.5 Conclusions......Page 1043
References......Page 1044
52.2 VLSI Technology......Page 1046
52.4 Corner Stitching......Page 1049
52.4.1 Point Finding......Page 1050
52.4.2 Tile Insertion......Page 1051
52.5.2 Trapezoidal Tiles......Page 1053
52.5.4 L-shaped Tiles......Page 1054
Comments about Corner Stitching......Page 1056
52.6 Quad Trees and Variants......Page 1057
52.6.3 Multiple Storage Quad Trees......Page 1059
52.6.5 Bounded Quad Trees......Page 1060
52.6.6 HV Trees......Page 1061
52.6.7 Hinted Quad Trees......Page 1062
References......Page 1063
53.1 Introduction......Page 1066
53.1.1 Statement of Floorplanning Problem......Page 1067
53.1.3 Combinations and Complexities of the Various Representations......Page 1068
53.1.4 Slicing, Mosaic, LB Compact, and General Floorplans......Page 1070
The generation of constraint graphs......Page 1073
Tutte’s duality......Page 1074
53.2.3 Twin Binary Tree......Page 1076
53.2.4 Single Tree Representations......Page 1078
53.3.1 Sequence-Pair......Page 1081
53.3.3 Corner Block List......Page 0
53.3.4 Slicing Tree......Page 1086
53.4.1 Summary of the Relationships......Page 1089
53.4.3 A General Floorplan Example......Page 1090
53.5 Rectilinear Shape Handling......Page 1092
References......Page 1093
54.1 Introduction......Page 1095
54.2.1 Meshes......Page 1096
54.2.3 Fonts......Page 1097
54.2.4 Bitmaps......Page 1098
54.2.5 Texture Mapping......Page 1099
54.3.1 Vertices, Edges, and Faces......Page 1101
54.3.3 Winged Edge......Page 1103
54.3.4 Tiled, Multidimensional Array......Page 1104
54.3.5 Linear Interpolation and Bezier Curves......Page 1106
54.4.1 Hidden Surface Removal: An Application of the BSP Tree......Page 1109
54.4.3 More With Trees: CSG Modeling......Page 1111
References......Page 1112
55.1 Geographic Information Systems: What They Are All About......Page 1113
55.1.3 Geometric Operations......Page 1114
Map Overlay......Page 1115
Road Maps......Page 1116
55.2 Space Filling Curves: Order in Many Dimensions......Page 1117
55.2.1 Recursively Defined Space Filling Curves......Page 1118
55.2.2 Range Queries for Space Filling Curve Data Structures......Page 1119
55.2.3 Are All Space Filling Curves Created Equal?......Page 1120
55.2.4 Many Curve Pieces for a Query Range......Page 1121
55.2.5 One Curve Piece for a Query Range......Page 1122
55.3 Spatial Join......Page 1123
Index on both spatial relations......Page 1124
Index on none of the inputs......Page 1125
55.3.2 Advanced Issues......Page 1126
55.4 Models, Toolboxes and Systems for Geographic Information......Page 1127
55.4.2 Commercial Systems......Page 1128
LEDA and CGAL......Page 1129
Dedale......Page 1130
References......Page 1131
56.1 Introduction......Page 1135
Polytope Representation......Page 1137
Local Walk......Page 1138
56.2.3 Minkowski Sums and Convex Optimization......Page 1139
56.3 General Polygonal Models......Page 1140
OBBTree Construction......Page 1141
OBB Representation and Overlap Test......Page 1143
Implementation and Application......Page 1144
56.4 Penetration Depth Computation......Page 1145
Local Walk......Page 1146
Initialization and Refinement......Page 1147
56.5 Large Environments......Page 1148
56.5.1 Multiple-Object Collision Detection......Page 1149
One-Dimensional Sweep and Prune......Page 1150
References......Page 1151
57.1 Introduction......Page 1155
57.2 What is Image Data?......Page 1156
57.3 Quadtrees......Page 1157
Region quadtrees......Page 1158
Line quadtrees......Page 1159
57.4 Virtual Quadtrees......Page 1160
57.4.1 Compact Quadtrees......Page 1161
57.4.2 Forest of Quadtrees (FQT)......Page 1162
57.5 Quadtrees and R-trees......Page 1165
57.6 Octrees......Page 1166
57.7 Translation Invariant Data Structure (TID)......Page 1167
General structure of CBIR systems......Page 1169
57.9 Summary......Page 1170
References......Page 1171
58.2 Discovering Unusual Words......Page 1173
Statistical analysis of words......Page 1175
Detecting unusual words......Page 1176
58.3 Comparing Whole Genomes......Page 1181
Basic Definitions......Page 1182
Computation of multiMEMs......Page 1183
Space efficient computation of MEMs for two genomes......Page 1185
References......Page 1186
Chapter 59: Elimination Structures in Scientific Computing......Page 1190
59.1.1 The Elimination Game......Page 1191
59.1.2 The Elimination Tree Data Structure......Page 1192
59.1.3 An Algorithm......Page 1194
59.1.4 A Skeleton Graph......Page 1195
59.1.5 Supernodes......Page 1196
59.2.1 Efficient Symbolic Factorization......Page 1197
59.2.2 Predicting Row and Column Nonzero Counts......Page 1198
59.2.4 Scheduling Parallel Factorizations......Page 1199
59.2.5 Scheduling Out-of-Core Factorizations......Page 1200
59.3.1 Chordal Graphs and Clique Trees......Page 1201
59.3.2 Design of Efficient Algorithms with Clique Trees......Page 1203
59.3.3 Compact Clique Trees......Page 1205
59.4.1 Clique Covers......Page 1206
59.4.3 The Problem of Degree Updates......Page 1207
59.4.4 Covering the Column-Intersection Graph and Biclique Covers......Page 1208
59.5.1 The Column Elimination Tree......Page 1209
59.5.2 Elimination DAGS......Page 1211
59.5.3 Elimination Structures for the Asymmetric Multifrontal Algorithm......Page 1213
References......Page 1214
60.1 Overview of the Functionality of a Database Management System......Page 1219
60.2 Data Structures for Query Processing......Page 1221
60.2.1 Index Structures......Page 1222
Multi-dimensional Indexes......Page 1223
60.2.2 Sorting Large Data Sets......Page 1224
60.2.3 The Parse Tree......Page 1226
60.2.4 Expression Trees......Page 1227
60.2.5 Histograms......Page 1228
60.3 Data Structures for Buffer Management......Page 1229
60.4.1 Record Organizations......Page 1233
60.4.2 Page Organizations......Page 1234
60.4.3 File Organization......Page 1237
References......Page 1239
61.1 Introduction......Page 1241
61.1.1 Data Mining Tasks and Techniques......Page 1242
61.1.2 Challenges of Data Mining......Page 1244
61.1.3 Data Mining and the Role of Data Structures and Algorithms......Page 1245
61.2.1 Nearest-Neighbor Classifiers......Page 1246
61.2.2 Proximity Graphs for Enhancing Nearest Neighbor Classifiers......Page 1247
61.3 Association Analysis......Page 1248
61.3.1 Hash Tree Structure......Page 1250
61.3.2 FP-Tree Structure......Page 1253
61.4.1 Hierarchical and Partitional Clustering......Page 1255
61.4.2 Nearest Neighbor Search and Multi-Dimensional Access Methods......Page 1256
References......Page 1259
62.1 Introduction......Page 1263
62.2 Arrangements......Page 1264
62.2.1 Substructures and Complexity......Page 1265
62.2.2 Decomposition......Page 1266
62.2.3 Duality......Page 1268
62.3 Convex Hulls......Page 1269
62.3.2 Construction......Page 1270
62.3.3 Dynamic Convex Hulls......Page 1272
62.4 Voronoi Diagrams......Page 1273
62.4.2 Construction......Page 1274
62.4.3 Variations......Page 1275
62.5.1 Delaunay Triangulation......Page 1276
62.5.2 Polygons......Page 1277
62.5.3 Polyhedra......Page 1278
62.5.4 Pseudo-Triangulations......Page 1279
References......Page 1280
63.1 Introduction......Page 1283
63.2 Point Location......Page 1284
63.2.1 Kirkpatrick’s Algorithm......Page 1285
63.2.2 Slab-Based Methods and Persistent Trees......Page 1286
63.2.3 Separating Chains and Fractional Cascading......Page 1287
63.2.4 Trapezoidal Maps and the History Graph......Page 1288
63.2.5 Worst- and Expected-Case Optimal Point Location......Page 1290
63.3.1 Voronoi Diagrams......Page 1291
63.3.2 Delaunay Triangulations......Page 1292
63.3.3 Other Geometric Proximity Structures......Page 1293
63.4 Nearest Neighbor Searching......Page 1294
63.4.2 K-d trees......Page 1296
63.4.4 Approximate Nearest Neighbor Searching......Page 1298
63.4.5 Approximate Voronoi Diagrams......Page 1299
Acknowledgments......Page 1300
References......Page 1301
64.1 Geometric Intersection Searching Problems......Page 1305
64.1.1 Generalized Intersection Searching......Page 1306
64.2.3 Problems on the Grid......Page 1307
64.3.1 A Transformation-Based Approach......Page 1308
The Dynamic Reporting Problem......Page 1309
The dynamic counting problem......Page 1310
The static type-2 problem......Page 1311
Generalized halfspace range searching in R2 and R3......Page 1312
Generalized semi-dynamic quadrant searching......Page 1314
Generalized semidynamic 2-dimensional range searching......Page 1315
Generalized 3-dimensional range searching......Page 1316
64.3.4 A General Approach for Reporting Problems......Page 1317
64.3.5 Adding Range Restrictions......Page 1318
64.4 Conclusion and Future Directions......Page 1319
References......Page 1320