Note: Page numbers followed by “fn” indicate footnotes.
A
AA-trees, 157
AABB, see Axis-aligned bounding box
ABIT, see Alternative BIT structure
Abstract data types (ADT), 77, 79, 117, 197, 595, 653, 655
Accept nodes, 477
Access structure, 260
Accounting method, 14
subset generation, 19
ACID semantics, see Atomicity, Consistency, Isolation, Durability semantics
Ackermann’s function, 538, 1014
functional inverse of, 95
inverse, 322
Active pair, 225
Active vertex, 190
Actual complexity, 14
Acyclic digraphs, 58
Acyclic graph, 53
Adaptive merging algorithm, 176–177
Adaptive multidimensional histogram (AMH), 367
Adaptive-phi, 986
Adaptive properties of pairing heaps, 94
Adaptive sorting algorithm, 176–177
Additional operations, 69, 343, 389, 395, 540, 599, 668
Additive weights, 1022
Address computation methods, 253
Adjacency
lists representation, 277
Adjacent polygons, 872
ADT, see Abstract data types
Advanced geometric data structures, 656
Advanced operations, 350
nearest neighbor queries, 350–351
Agglomerative clustering, 1007, 1008
Aggregate method, 14
maintenance contract, 15
McWidget company, 17
subset generation, 19
Aggregate query, 367
Aggregation
B+-tree, 246
operators, 245
Air-traffic controls, 370
AlgoComs, 884
Algorithmic Solutions Software GmbH, 654
Algorithm(s), 656, 679, 683–684, 688, 948–949
animation, 697
designers, 7
Dijkstra’s, 689
euler tour tree traversal, 688
iterator-based tree traversals, 688
Prim-Jarník, 689
sequence sorting, 688
topological numbering, 689
visualization, 697
All-pairs approximate shortest paths (APASP), 611
All-pairs shortest path, 64–65
All-pairs shortest paths, 591
updates in O(n2.5Clog n) time, 592
updates in O(n2 log3n) time, 592
AllocatePage function, 234
Almost-linear-time algorithm, 951
α-balanced region, 406
canonical region, 413
Alphabetic tree problem, 224
Alpha channel, 859
Alternative BIT structure (ABIT), 775
Alternative node structures, 447–449
ALU, see Arithmetic and logic unit
Amalgamated node, 950
Ambivalent data structures, 574, 582; see also Cache-oblivious data structures; Randomized graph data-structure
Amethyst system, 704
AMH, see Adaptive multidimensional histogram
Amortized complexity, 14
Amortized cost, 14–19, 79, 94, 98, 121, 160, 161, 164, 185, 427, 532–534
analysis of Insert or DeleteMin operation, 552, 556–557, 559–560
of single splaying, 188
Amortized time, 69, 90, 181–182
Amortized update cost to worst-case, 633–634
Analogous methods for 3D polytopes, 383
Analysis of algorithms, 3
Analytical models of R-trees, 353–356
Analytics workloads, 987
node, 36
Anchor, 923
Angular resolution, 723
Annulus wedge, 719
Anomaly detection, 999
Anti-monotone property of itemset support, 1003
Apache Zookeeper projects, 986
APASP, see All-pairs approximate shortest paths
Applicability criteria, 891
“Apply” algorithm, 506
Apportion, 715
Approximate distance oracle, 611, 616
computing Balli(u) efficiently, 616–618
computing pi(u), ∀u ∈ V, 616
Approximate geometric query structures
general terminology, 406
maximum-spread k-d trees, 416
Approximate nearest neighbor searching, 1037–1038
Approximate pattern matching, 473–474
Approximate range query, 407
Approximates optimal Huffman code, 230
Approximate Voronoi diagram (AVD), 1038; see also Voronoi diagrams
Approximation algorithm, 389
Approximation error factor, 1038
Apriori algorithm, 1003, 1004, 1005
AQT, see Area-based Quadtree
Arbitrarily oriented objects, 1045
Arbitrarily shaped queries, 345
Arbitrary element deletion from Max HBLT, 74
Arbitrary merging order, 175–176
Arbitrary range minimum query, 472
Arbitrary space decomposition, 262
ArcGIS, 883
Archetypical data structure, 595
Architectural design, 817
Arc of dynamic trees, 193
Area-based Quadtree (AQT), 790–791, 792
Area Searches operation, 820
Arithmetic and logic unit (ALU), 7
Arithmetic operation, 7
Arrangement(s), 288, 385, 1014
of curves in plane, 1014
of lines, 288
maximum complexity of single cells and envelopes in arrangements, 1015
substructures and complexity, 1014–1015
access structure, 253
of arrays representation, 26
doubling, 25
dynamic, 607
handling, 518
implementation of queue, 33
index, 24
multiple lists in single array, 25
resizable, 607
sorted, 25
sparse matrices, 27
ArrayHeap, 687
ArrayQuickSort, 688
ArraySequence, 686
Assignment pedigree, 519
Association analysis, 1002
basic K-means algorithm, 1007
enumerating subsets of three items from transaction, 1005
hashing transaction at root node of hash tree, 1004
hash tree structure, 1004–1005
subset operation on left most subtree of root of candidate hash tree, 1006
Association rule, 1003
Associative containers, 667, 669
sets and multisets, 669–670, 671
“Assume, verify, and conquer” strategy (AVC strategy), 392
Asymmetric hashing, 125
Asymmetric matrix, 959
Asymmetric multifrontal algorithm, elimination structures for, 962
Asymptotic complexity
little oh notation (o), 11
omega and theta notations, 11
Asymptotic notation, 10
Atomicity, Consistency, Isolation, Durability semantics (ACID semantics), 983
Attribute, 278
geometric, 378
geometric, 871
primary, 252
Augmented ephemeral data structure, 517
Autocorrelation factor, 919
Automatic Graph Drawing, 707
Automatic translation techniques, 819
Automorphism, 937
group, 937
Auxiliary 3D R-tree, 369
AVC strategy, see “Assume, verify, and conquer” strategy
AVD, see Approximate Voronoi diagram
Average path length, 810
AVL-trees, 155–156, 159, 164, 166, 179, 180, 389, 390, 708
Axes-parallel objects, 1044–1045
Axial case, 729
Axioms of probability, 199
Axis-aligned bounding box (AABB), 256, 893, 896
B
Back-end structure, 774
Back edges, 54
Backoff technique, 743
Backward analysis, 207
Backward finger search, 174
Backward pointers, 456
Bad nodes, 910
Balanced aspect ratio tree (BAR tree), 405, 412–416, 426, 1038; see also Binary space partitioning trees (BSP trees); R-trees*
construction algorithm, 414
Balanced binary search trees (BBST), 78, 151–152, 183, 233, 316, 389, 644; see also Finger search trees
application to multi-dimensional search trees, 161–162
binary trees as dictionaries, 152–153
classic balancing schemes, 155–158
general balanced trees, 160–161
implementation of binary search trees, 153
implicit representation of balance information, 159–160
rebalancing tree to perfect balance, 158
schemes with no balance information, 158
Balanced binary tree, 574
based on multi-way trees, 157–158
Balanced box decomposition tree (BBD tree), 405, 410–411, 412, 426, 1038; see also Binary space partitioning trees (BSP trees); R-trees*
Balanced BST implementation, 393–395
in AVL-trees, 155
rebalancing tree to perfect, 158
Balanced parenthesis representation, 600
Balanced priority search tree, 1046
Balanced search tree, 554
Balanced structures, 390, 391, 393
Balance information, implicit representation of, 159–160
Balance of node, 156
Balancer, 750
Balancing, 153
balance definitions, 154
complexity results, 155
rebalancing algorithms, 154–155
Balli(u) efficiently computiation, 616–618
BANG file, 258
Barriers, 748
Bars”, horizontal line segments, 732
BAR tree, see Balanced aspect ratio tree
Bar visibility algorithm, 734–735
Bar visibility representations
for orthogonal drawings, 736–737
Barycenter algorithm, 726
Base repertoire of actions, 529
Base repertoire plus member, 529
BasicintervalPointer, 774
Basic Library (libL), 654
Basic search algorithms, 783
Basket weaving, 338
Batched dynamic operations, 427
Batched filtering, 422
Batched geometric problems, EM algorithms for, 421–424
Batched incremental construction, 422
Batched techniques, 421
Batcher’s merging technique, 635
Bayes’ rule, 200
BB[α]-trees, see Weight-balanced trees
BBD tree, see Balanced box decomposition tree
BBST, see Balanced binary search trees
BDDs, see Binary decision diagrams
Beam-tracing based algorithm, 334
Beam tracing, 336
Bernoulli distribution, 202, 918, 919
Bernoulli Trial, see Coin flip
Beyond planar graphs, 738
Beyond planarity, 738
BFS, see Breadth-first search
Bibliometrics, 805
Bidirectional iterators, 674
Big data stores, data structures for, 983
data models, 984
replication and consistency, 985–987
Big data technologies, 872
BigTable, 989
Binarizations of multi-way search tree schemes, 154
Binary B-tree, 157
Binary decision diagrams (BDDs), 495
BDD-based techniques, 495
construction from Boolean expressions, 499–502
package, 506
related research activities, 506–507
shared BDD, 498
truth table and, 496
for typical Boolean functions, 498
variable ordering for, 502–503
Winter of BDDs”, 507
Binary dispatching problem, 514
Binary encoding, 800
Binary image, 904
Binary interval tree (BIT), 774
Binary large objects (blobs), 977
Binary logic operation, 500–501
Binary merge sort, 175
Binary merge trees, 548
Binary search recurrence of equation, 13
Binarysearchtree-on-Trie (BoT), 793
Binary search trees (BSTs), 42, 152, 209, 223, 253, 329, 331–332, 421, 447, 642–644, 774–775
algorithm, 470
delete, 43
implementation, 153
search, 42
Binary space partitioning trees (BSP trees), 261, 262, 329–330, 340, 384, 406, 416, 867–868, 1032; see also R-trees*
boundary representations vs. BSP trees, 340
converting B-Reps to trees, 339–340
elementary operation, 331
as hierarchy of regions, 334
of inter-object spatial relations, 330
of intra-object spatial relations, 330
merging BSP trees, 336
multi-dimensional search structure, 331–332
multiresolution representation, 335
plane power, 330
BinaryTree, 686
Binary tree on binary tree (BOB), 777
Binary trees, 35–37, 39, 152, 470, 599, 708
data structure, 427
hashing, 127
Binary tree traversals, 39
inorder traversal, 40
level order traversal, 41
preorder traversal, 40
Binary trie, 448, 449, 531, 533, 603
Binary union tree, 538
Binomial coefficients, 202
Binomial distribution, 135, 137, 140, 202, 206
Binomial heaps, 69, 85–89; see also Skew heaps
Biological sequence data, 917
Biological taxonomies, 332, 1007
Bipartite cores, 805
Bisector list implementation in HVT, 829
Bisector List Quad Trees (BLQT), 264, 884
Bisector List Quad Trees (BLQT), 826
Bisectors, 826
Bit-wise boolean operations, 595
BIT, see Binary interval tree
Bit collision”, 146
Bitmap graphics, see Raster graphics
Bitmap index, 970
Bits, 604
Bit string, 317
Bit table, 975
Black box”, 179
blobs, see Binary large objects
BlobWorld system, 915
Block(s), 234, 833–834, 974, 976, 980
decomposition, 261
size, 988
Blocked bloom filter, 136
bloom-1 vs. bloom with optimal k, 139–140
bloom-1 vs. bloom with small k, 138–139
bloom-g in dynamic environment, 144
bloom-g vs. bloom with optimal k, 142–144
bloom-g vs. bloom with small k, 141–142
discussion, 144
Blocking phenomenon, 743
vs. bloom with optimal k, 142–144
vs. bloom with small k, 141–142
in dynamic environment, 144
black box view, 132
false-positive ratio and optimal k, 133–134
performance metrics, 133
Bloom filter variants, 136, 144
bloom filter for dynamic set, 146–147
improving read/write efficiency, 145–146
improving space efficiency, 145
reducing false-positive ratio, 145
reducing hash complexity, 146
BloomFlash, 146
Bloom with optimal k
Bloom with small k
BLQT, see Bisector List Quad Trees
BOB, see Binary tree on binary tree
Boolean” objects, 868
Boolean AND, 800
Boolean expressions, BDDs construction from, 499
binary logic operation, 500–501
primitive operations for BDD manipulation, 499
systematic methods for, 495
Boolean NOT, 800
Boole’s Inequality, see Sub additivity
Bootstrapping
for three-sided orthogonal 2-D range search, 432–433
Boruvka’s MST algorithm, 62
BoT, see Binarysearchtree-on-Trie
Bottom-up
algorithms, 393
construction, 316
splay trees, 195
traversal, 470
Bottom-vertex triangulations, 1015–1016
Bottom trees, 549
Boundary-based representation, 259
Boundary-labeling problem, 873
Boundary model, 266
Boundary of face, 891
Boundary representation, 339, 340
vs. BSP trees, 340
Boundary vertices, 574
Bounded-sliceline grid (BSG), 833, 844, 847–848
Bounded aspect ratio, 434
Bounded Quad Trees (BQT), 828–829
Bounded slicing grid, 835
Bounding
box, 437
functions, 350
size of
sphere, 383
Bounding volume hierarchies (BVHs), 340, 383, 892, 896
Bounding volumes (BVs), 334, 892
choice of, 893
Bounds from computational geometry, 786
Bowtie2 alignment tool, 927
BQT, see Bounded Quad Trees
Branch-and-bound algorithm, 351
Branch-node pointers, 456
Breadth-first search (BFS), 54, 56, 578–579
simple applications of, 56
Breadth-first traversal strategy, 880
BRep, see winged-edge data structure
Brightness value, 904
Broad phase, 898
Brute force algorithm, 345
BSG, see Bounded-sliceline grid
B-spline curves, 867
BSP trees, see Binary space partitioning trees
BSTs, see Binary search trees
B+-tree, 233, 239, 245, 911, 987, 988
bulk-loading, 245
copy-up and push-up, 240
B-tree based technique, 360
B-trees, 157, 166, 233, 234–235, 389, 425–426, 878, 969, 970; see also Splay trees
disk-based environment, 233–234
efficiency analysis, 245
family, 874
structure, 421
variants, 360
Bubble sort, 25
Bucketing, 163
Bucket(s), 252, 254, 562, 980, 988
directory, 980
Buddy trees, 429
Buffer management, data structures for, 974
direct page addressing, 974, 975
indirect page addressing, 975
shadow paging concept, 976
Buffer Manager, 968
pool, 234
zone, 407
Bugs, 640
Bulk dynamic operations, 430
B+-tree, 245
“Bump” mapping, 862
Burrows–Wheeler transform, 927, 928
Bursty access pattern, 775fn
BVHs, see Bounding volume hierarchies
BVs, see Bounding volumes
BWA-MEM alignment tool, 927
C
C++, data structures in
C++ programming language, 23, 679
Cache-coherent multiprocessor, 743
Cached assertions, 378
Cache hierarchy, utilizing, 864
Cache-oblivious algorithm, 545–546
Cache-oblivious data structures; see also Randomized graph data-structure
cache-oblivious model, 545–546
fundamental primitives, 546
2d orthogonal range searching, 560–563
Cache-oblivious kd-tree, 560
construction, 561
structure, 560
updates, 561
Cache-oblivious model, 545–546
Cache-oblivious range tree, 561
four-sided queries, 563
Cache misses effect on run time, 7–8
Caching mechanisms, 360
CAD, see Computer aided design
CAGD, see Computer-aided geometric design
Calinescu’s algorithm, 541
CAM, see Computer Aided Manufacturing
Candidate itemsets, 1004
Canonical bounding cuts, 412
Canonical cuts, 412
Canonical geometric structures, 386
Canonical label, 936
Canonical labeling methods, 937
Morgan’s algorithm, 937
signature-based canonization, 938
Canonical order, 605
Canonical region, 412
Canonical representations, 936–937
Canonical spatial join algorithm, 352
Canonical triangulation, 399, 400
Capacitance, 818
Capacity of cut, 190
CAP theorem, see Consistency, availability, and partition tolerance theorem
Cardinality degree, 571
CartoDB, 883
Cartographic generalization, 873
Cartography, see Map visualization
CAS, see Chemical abstracts service; Compare-and-swap
CAS-based lock-free linked list, 753–754
Cascade hashing, 127
Catalan numbers, 39
Catenate, 522
Causteljau algorithm, 866
CBAC, see Context-based access control
CBF, see Counting Bloom filter
CBIR systems, see Content-Based Image Retrieval systems
CBL, see Corner block list
complex, 1028
deletion, 317
insertion, 317
probe model, 530
Central projection, 897
Centroid shrink, 410
Certificate, 378
CGAL, see Computational geometry algorithms library
Chain codes, 265
Chaining, hashing with, 122
Characteristic functions, 504
Character large objects!character (clobs), 977
Chemical abstracts service (CAS), 935
Chemical fingerprints, 939
bitbound algorithm, 940
combining hashing and trees, 943
fingerprint compression, 940
hashing approaches for improved searches, 940–941
inverted indices, 942
LINGO, 942
multibit and union tree, 943
triangle inequality and improvements, 941
trie-based approaches for storing fingerprints, 943
Chemical graph, 936
Chemical space, 935
Cheminformatics, 935
bitbound algorithm, 940
chemical fingerprints and similarity search, 939
combining hashing and trees, 943
fingerprint compression, 940
hashing approaches for improved searches, 940–941
inverted indices, 942
LINGO, 942
multibit and union tree, 943
triangle inequality and improvements, 941
trie-based approaches for storing fingerprints, 943
Chernoff bounds, 203
Child cache, 432
Child deque, 523
childNode, 448
Chip multithreading (CMT), 741
Cholesky factorization, 946
Chord, 954
Circular deque, 607
C language, 640
Classical binary merge sort algorithm, 176
Classical O(n log n) time sorting algorithm, 175
Classical union-find problem and variants, 539–540
Classic balancing schemes, 155
balanced binary trees based on multi-way trees, 157–158
weight-balanced trees, 156–157
Classic search trees, 164
Classification, 1000
k-nearest neighbor classification algorithm, 1001
nearest-neighbor classifiers, 1001
1-, 2-and 3-nearest neighbors of instance, 1001
proximity graphs for enhancing nearest neighbor classifiers, 1001–1002
system, 541
techniques, 998
Classifier, 783
Clique, 291
covering column-intersection graph and biclique covers, 958–959
problem of degree updates, 958
algorithm, 955
compact clique trees, 956
design of efficient algorithms with, 955–956
clobs, see Character large objects!character
Closely-related variables, 502
analysis, 999
changes, 384
path, 574
Clustered graph drawing, 737
Clustering, 384, 582, 999, 1007
hierarchical and partitional clustering, 1007–1008
mobile nodes, 384
multi-dimensional access methods, 1008–1010
nearest neighbor search, 1008–1010
CLWS problem, see Concave Least Weight Subsequence problem
c-maximal point, 1050
CMT, see Chip multithreading
CNFs, see Conjunctive normal forms
Co-expressed genes, 918
Coarsest equitable partitions, 938
Coboundary of vertex, 891
Code fragments for sequential and lock-based fetch-and-inc operations, 742
Code Generator, 969
Coding information, 159
Cofactors, 496
Coin collector problem, 221
Coin flip, 202
Col-etree, see Column elimination tree
Collection of prefix trees (CPT), 774
Collision detection, 377, 383–384, 889, 893, 894–895
general polygonal models, 892–896
array, 749
resolution strategy, 122
Color, 859
Colored intersection searching, see Generalized intersection searching
Colored problems, 1044
Color monitors, 859
Column-count of vertex, 951
Column-intersection graph, 958–959
Column-oriented symbolic factorization algorithms, 951
Column elimination tree (Col-etree), 945, 959–960
asymmetric multifrontal algorithm, elimination structures for, 962
Column family stores, 984
Column indices, 950
Column intersection graph, 958, 961
Column major representation, 26
Column nonzero counts prediction, 951–952
Column orderings, 958
Column subgraph, 956
Combinatorial and geometric computing, 653, 654
Combinatorial complexity, 1014, 1028
Combining funnel, 749
Combining hashing and trees, 943
Combining nodes, 389
Combining techniques, 635
Combining tree approach, 743, 749
Command completion system, 451
Common-sense approach, 224
COMMON statements, 538
Communication systems, 359
Compact clique trees, 956
using compact DAWG to finding locations of
edge labels representation, 488
variations and applications, 488–489
Compactness, 380
Compact quadtrees, 907, 908–909
Comparators, 683
Compare-and-swap (CAS), 744
Comparison-based model, 627, 634
Complementary range search problem, 104–105
Complemented edges, 501
Complete binary tree, 599
Complete directed bipartite graph, 277
Complete subset graph, 536
“Compound” objects, 868
Compressed binary trie, 456, 457
Compressed data structure, 435
Compressed path method, 522
Compressed quadtrees
bottom-up construction, 316
construction of, 315
divide-and-conquer construction algorithm, 315–316
Compressed tries, 452
with edge information, 454–456
with skip fields, 454
space required by compressed trie, 456
Compressed tries with digit numbers
removing element from, 453–454
searching, 452
Compressed tries with edge information, 454
inserting into, 455
removing element from, 456
searching, 455
“Compresses” multiple R-trees, 368
Compression process, 756
Computational biology, 917
whole genomes comparison, 923–926
Computational geometry, 377, 1013
bounds from, 786
motion in, 377
Computational geometry algorithms library (CGAL), 679, 872, 884
Computational platforms, 948
Computational tasks, 622
Computer aided design (CAD), 343, 858
Computer-aided geometric design (CAGD), 377
Computer Aided Manufacturing (CAM), 858
Computer graphics, 857
fonts, 859
hardware and pipeline, 857–858
hidden surface removal, 867
meshes, 858
proximity and collision, 867–868
Concave Least Weight Subsequence problem (CLWS problem), 230
Concave matrix multiplication techniques, 230
Concurrent data structures
barriers, 748
complexity measures, 745
designing, 741
hash tables, 754
locks, 747
nonblocking techniques, 744–745
shared counters and fetch-and-φ structures, 749–750
tools of trade, 746
transactional synchronization
mechanisms, 748
verification techniques, 746
Concurrent queue implementation, 748–749
Condensing, 1002
Conditional probability, 200–201
Confidence bounds, 199
Conflict-free ranges, 780
Confluently persistent data structures, 511, 518–522
Conjugated systems, 936
Conjunctive normal forms (CNFs), 501, 506
Connected components, 57
labeling, 322
Connected graph, 53
updates in O(log2n) time, 587–588
Consistency, availability, and partition tolerance theorem (CAP theorem), 983
key assignment, 985
node addition, 986
Consolidation process, 91
Constant, 478
Constant size, 401
alphabet, 463
Constrained MST, 62
relationship between constraint graph based representation, 845
triangulation, 839
Constraint plane, 891
Construction
in RAM model, 561
of topology trees, 572
Constructive Solid Geometry (CSG), 259, 868–869
Constructors, 641
Contact determination, see Collision detection
stack and queue, 672
associative containers, 669–672
classes, 667
Content-Based Image Retrieval systems (CBIR systems), 914, 915
computational framework, 915
Context-based access control (CBAC), 131
Continuous differential equations, 806
Continuously moving items, 436–437
Continuously moving objects, indexing structures for, 370
REXP-tree, 373
STAR-tree, 373
TPR*-tree, 373
Continuous query, 367
Contract cases, 286
Conventional DBMS, 874
Converting B-reps to trees, 339–340
Convex bounding volumes, 336
Convex drawing, 726; see also Symmetric drawing; Visibility drawing
algorithm using canonical ordering, 727–728
Barycenter algorithm, 726
divide and conquer algorithm, 726–727
Convex hulls, 378–379, 385, 402, 894, 1017
convex hull-trees, 893
maximum complexity, 1018
Overmars-van Leeuwen structure, 1019
Convex optimization, 892
Convex-polygon clipping, 337
Convex polytopes, 382, 890, 896–897
linear programming, 890
Minkowski sums and convex optimization, 892
Voronoi-based marching algorithm, 890–892
Coordinate values, 253
Copy pointer, 517
Copy-up node, 240
Corner block list (CBL), 833, 844, 848–849, 851
Corner cut canonical set, 416
Corner(s), 1024
Corner stitching data structure, 819
point finding operation, 820–821
storage requirements of, 822
Corner stitching extensions, 822
curved tiles, 823
trapezoidal tiles, 823
Correctness, 225, 654, 745–746
Correspondence property, 101, 108, 109
Counting Bloom filter (CBF), 135
counter size and counter overflow, 135–136
Counting cache misses, 7
effect of cache misses on run time, 7–8
simple computer model, 7
Counting networks, 750
CPT, see Collection of prefix trees
Crawlers fingerprint, 802
invariant, 556
Crossing minimization methods, 737
Cross tree, 429
CRUST algorithm, 661
Cryptographic hash function, 986
CSE method, 360
CSG, see Constructive Solid Geometry
Cuckoo hashing, 126
Current edge, 192
currentNode, 448
“Curse of dimensionality”, 359, 999, 1037
Curved tiles, 823
Cuttings
applications, 401
convex hulls and Voronoi diagrams, 402
cutting construction, 397
Hopcroft’s problem, 401
point location, 401
range searching, 402
Cyber communities, 805
Cycle detection, 57
Cyclic case, 729
Cyclic ordering of characters, 489
D
DAG, see Directed acyclic graph
DAM, see Disk access model
Dangling edges, 278
Data
definition statements, 967
element, 389
field, 447
flow diagrams, 707
ownership and distribution, 1000
quality, 1000
set, 349
structuring techniques, 583
warehouse, 874
Database management system (DBMS), 233, 245, 874, 881, 967
simplified architecture, 968
Databases, data structures for, 967
for buffer management, 974–976
for disk space management, 976–981
functionality of database management system, 967–968
Data-driven spatial data structures, 428
Dataflow analysis, 589
and role of data structures and algorithms, 1000
Web pages indexed by Google© search engine, 998
Data structure(s), 23, 151, 179, 186, 197, 263, 331, 363, 419, 420, 426, 489, 551, 579, 584, 628, 639, 655, 698, 767, 787, 862, 891
advanced geometric data structures, 656
and algorithms, 1000
for buffer management, 974–976
for disk space management, 976–981
geometry Kernels, 656
graph data structures, 655
hierarchical distance maintaining, 619–621
linear interpolation and Bezier curves, 864–867
linear search, 787
numbers and matrices, 655
Patricia, 456
rendering value, 698
tiled, multidimensional array, 864
vertex, normal, and face lists, 863
vertices, edges, and faces, 862
views, 699
Data structures library in Java (JDSL), 680, 681
architecture of, 684
Class IntegerDijkstraPathfinder, 693–694
Class IntegerDijkstraTemplate, 690–693
comparators, 683
containers and accessors, 681–682
decorations, 683
design concepts in, 681
minimum-time flight itineraries, 689–690
packages, 684
positional containers, 684–687
sample application, 689
Data structure visualization, 697
data structure views, 699
existing research and systems, 700
GELO, 702
incense, 701
interacting with system, 699–700
purpose and environment, 698–699
value of data structure rendering, 698
Data types, 655
advanced data types, 655
basic, 655
geometry Kernels, 656
numbers and matrices, 655
DAWG, see Directed acyclic word graph
db.collection.indexStats() method, 988
d-box, 389
DBMS, see Database management system
DCAS, see Double-compare-and-swap
d-dimensional array, 252
d-dimensional packet classification problem, 765
d-dimensional points, 343
Deadlocks, 744
DeallocatePage function, 234
inserting element, 109
Decision nodes, see Nonterminal nodes
Decision trees, 332
Decomposability property, 291
Decorations, 683
Decremental APASP, randomized data-structure for, 618
bounding size of
hierarchical distance maintaining data-structure, 619–621
improved decremental algorithm for APASP up to distance d, 622–624
notations, 619
Decremental graph problem, 581
defaultAncestor, 714
Default prefix, 766
Deferred splitting, policy for, 347
Deformable objects, 383
Defragmentation, 979
Degree, 49
distribution, 806
node, 36
Degree updates, problem of, 958
Delaunay diagrams, 385
Delaunay graph, 1034
Delaunay triangulation (DT), 277, 289, 1020, 1021–1023, 1033–1034
under point motion, 382
Delayed pivoting, 962
Delete algorithm, 237–238, 242–244
Delete-max operation, 77
Delete-min operation, 77, 80, 304, 554
Delete operation, 14, 85, 182, 197, 554, 987
BSTs, 43
Deletion(s), 152–153, 160, 161
algorithm, 317
of arbitrary element from Max HBLT, 74
of max element from Max HBLT, 72
in O(log2n) time, 589
of object, 362
Delta-encoding technique, 800
Dendrogram, 1007
Dense case, 120
Dense index, 980
Dense interconnection, 805
“Denseness” of interconnection, 805
Density based search tree, 550–552
Density of intervals set, 291
Density thresholds, 551
DEPQs, see Double-ended priority queues
Depth first expression (DF-expression), 362
Depth-first search (DFS), 54, 683, 688, 948, 961
adjacency lists and depth-first traversal, 55
algorithm for depth-first search on undirected graph, 55
on digraph, 57
simple applications of, 56
traversal, 472
Depth-first strategy, 880
Depth first traversal, 55, 926
Depth-first unary degree sequence representation, 600
Depth of node, 152
Deques, see Double ended queues
Descriptive tasks, 998
Designating algorithms, 402
Design Rule Checking (DRC), 263, 818, 829
Destination address, 765
Deterministic algorithms, 198, 630
exponential search trees, 632–633
Deterministic finite automaton, 477
Deterministic sum of n random variables, 203
Dewey decimal notation, 35
DF-expression, see Depth first expression
DFS, see Depth-first search
problem, 529
Dictionary operations, 207
analysis of dictionary operations, 207–209
Diffracting balancers, 750
Diffracting trees, 750
Diffusing computation tree, 748
Diffusion layer, 817
Digital searching, see Radix searching
digitNumber field, 452
Digit numbers, compressed tries with, 452–454
digitValue, 448
digraph, see Directed graph
Digraph, DFS, 57
Dihedral case, 729
Dihedral symmetry, displaying, 732
Dijkstra’s algorithm, 616, 689
Dijkstra’s label-setting algorithm, 63
Dijkstra’s shortest-path algorithm, 63, 659
Dimension reduction approach, 899
Directed acyclic graph (DAG), 511, 938, 948, 956, 959
effective depth of, 512
of five versions, 520
Directed acyclic word graph (DAWG), 477, 479, 920; see also Compact DAWG
constructing DAWG in linear time, 482
simple algorithm for constructing, 481–482
Directed Area Enumeration, 820
Directed graph (digraph), 49, 50, 581, 584, 805
long paths, 585
Direct page addressing, 974, 975
Direct preprocessing, 473
Discrete event simulation, 427
Discrete geometry, 377
Discrete random variable, expected value of, 201
Disjoint set union-find problem, 538
classical union-find problem and variants, 539–540
Disjunctive normal forms (DNFs), 501, 506
Disk access model (DAM), 988
Disk-based environment, 233–234
DiskRead function, 234
Disk space management, data structures for, 976
Disk space manager, 968
DiskWrite function, 234
Dismissals of false alarms, 365
distance-based techniques, 914
joins, 353
predicate, 879
query, 872
Distributed consensus algorithms, 986
Distributed memory multiprocessors, 949
Distributed R-trees, 343
Distribution sweep(ing), 421, 422–423
algorithms, 12, 13, 175, 726–727, 879
construction algorithm, 315–316
problem-solving paradigm, 268
technique, 582
Division, hashing by, 118
DNA sequences, 918
DNFs, see Disjunctive normal forms
Document stores, 984
Dopants, 817
Double-compare-and-swap (DCAS), 752
Double-ended priority queues (DEPQs), 77, 97; see also Meldable priority queues
MDEPQs, 113
Double ended queues (Deques), 31, 512, 607, 752
of elements, 523
Double hashing, 124
Double rotation, 154
Doubly connected edge list (DCEL), see Halfedge data structure
Doubly linked circular lists, 30
Downward pointers, see Branch-node pointers
Downward traversal, 466
Drawing algorithm input, 729
Drawing trees
level layout for binary trees, 709–710
level layout for n-ary trees, 710–718
typical layout of binary tree, 708
DRC, see Design Rule Checking
Drill bit models, 859
Driscoll, Sarnak, Sleator, and Tarjan (DSST), 511, 512, 516
limitations of transformations, 512
Druglike chemical space, 935
DSST, see Driscoll, Sarnak, Sleator, and Tarjan
DS-Viewer system, 704
DT, see Delaunay graph; Delaunay triangulation
Dual plane, 1016
Dual priority queues, 111
Dual structure method, 111
Dual transformed space, 360
Dynamic B-trees, 550
exponential tree based, 552–553
Dynamic bit vector problem, 606
Dynamic computational geometry, 377
Dynamic convex hulls, 1019–1020
Dynamic counting problem, 1047–1048
Dynamic data structures, 421, 435
continuously moving items, 436–437
logarithmic method for decomposable search problems, 435–436
Dynamic environments, 892
bloom-g in, 144
Dynamic finger search trees, 171–172; see also Randomized finger search trees
Dynamic finger theorem, 185
all-pairs shortest paths, 591–592
directed graphs, techniques for, 584–587
minimum spanning tree, 588–589
undirected graphs, techniques for, 582–584
Dynamic hash files, 980
Dynamic hashing, 127
Dynamic interval management, 432
Dynamic map labeling, 873
Dynamic multi-level tree algorithms, 793
“Dynamic Optimality Conjecture”, 185
Dynamic perfect hashing, 120–122
recurrences, 223
Dynamic queries, 890
Dynamic reporting problem, 1046–1047
Dynamic rule, 767
Dynamic set
intersections and subset testing, 537–538
Dynamic setting, 567
Dynamic subset testing problem, 537
Dynamic tree
clustering techniques, 574
linking and cutting trees, 567, 568–571
membership, 567
reachability trees, 567, 578–579
Dynamic variable ordering, 503
Dynamization, 291
static algorithms, 583
DynamoDB, 986
E
Eager learners, 1001
EC, see Extended connectivity
ECFP, see Extended connectivity fingerprint
edags, see Elimination dags
Edge-deletions, bounding size of
maintaining BFS tree, 622
technical details, 622
Edge-flip, 382
Edge information, 454
compressed tries with, 454–456
algebra, 288
bends, 723
crossings, 723
resolution, 723
ring, 287
Editing, 1002
efficient symbolic factorization, 950–951
Elementary operations, 331, 945
Elementary range, 294
Elimination
directed acyclic graph, 945
forest, 947
Elimination dags (edags), 959, 960, 961
column elimination tree, 959–960
elimination structures for asymmetric multifrontal algorithm, 962
Elimination structures, 945
applications of etrees, 950–953
clique covers and quotient graphs, 957–959
column elimination trees and elimination dags, 959–962
skeleton graph, 949
EM, see External memory
Empty-circle condition, 1022
Empty circumcircle property, 1033
Empty pointers, 160
Empty string, 477
EMST, see Euclidean minimum spanning tree
Enclosing interval searching problem, 293, 296
Encode set, 132
Entity-relationship diagrams, 707
Entropy
Huffman codes and, 220
of subdivision, 1032
Entry coordinate, 298
Ephemeral data structures, 511
Epochs, 533
ε-approximation, 398
ε-cutting, 397
ε-net, 398
Equal-length prefixes sets, 768–769
Equidepth histograms, 973
Equivalence classes, 53, 478, 484, 535, 919, 920
EQUIVALENCE statements, 538
Equiwidth histograms, 973
Error rate, 95
Etrees applications, 950
efficient symbolic factorization, 950–951
predicting row and column nonzero counts, 951–952
scheduling out-of-core factorizations, 953
scheduling parallel factorizations, 952–953
three classes of factorization algorithms, 952
ET trees, see Euler tour trees
Euclidean minimum spanning tree (EMST), 1023, 1034
Eulerian trail, 65
Euler’s formula, 1018
Euler tour trees (ET trees), 567, 577, 582
applications, 578
data structure, 583
traversal, 688
updates, 578
KDS, 382
queue, 378
Evolutionary web graph models, 808
Exact-match query, 234, 240, 241
canonical labeling methods, 937–938
canonical representations, 936–937
graph theoretic representations, 936
Exit coordinate, 298
Expected mean of X, see Expectation of X
Expected value of discrete random variable, 201
Expected value of X, see Expectation of X
Explanatory variables, 998
Exponential backoff lock, 747
Exponential growth models, 808
Exponential layout, 552
Exponential level based priority queue, 557
layout, 558
Exponential search, 171
Exponential tree based structure, 552–553
Expression trees, 40, 968, 969, 972–973
Extended binary tree, 70
Extended connectivity (EC), 937
Extended connectivity fingerprint (ECFP), 939
Extendible hashing, 127
Extending LEDA to secondary memory (LEDA-SM), 884
Extensibility, 654
eXtensible and fleXible Library (XXL), 884
Extensible hash files, 980
Extensible hash table, 754
Extent problems, 382
External algorithms, 879
index on both spatial relations, 880
index on none of inputs, 880–881
index on one spatial relation, 880
External boundary vertices, 574
External degree, 571
External fractional cascading, 422
External fragmentation, 598
“Externalizing” plane sweep algorithms, 422
External marriage-before-conquest, 422
External memory (EM), 421
algorithms, 419, 421–424, 1045–1046
design criteria for EM data structures, 420–421
dynamic and kinetic data structures, 435–437
finger search trees, 173
online data structure, 421
spatial data structures and range search, 428–434
External merge sort, 970
External path length, 37
Extractmin, 93
Extra fields, 517
Extremal sets and subset testing, 535
dynamic set intersections and subset testing, 537–538
Extremal sets problem, 536 F
Failure-detection protocols, 986
Fair split, 411
False negative, 132
probability, 133
ratio, 133–134, 137, 139, 142, 145
False sharing phenomenon, 743
Farach’s algorithm, 467
Faster randomized algorithms, 635
Fat Inverted Segment tree (FIS-tree), 791–792
Fat-triangle, 1045
FCFS hashing, see First-come first-served hashing
FD, see Fixed length-depth
Fetch-and-φ structures, 749
combining, 749
counting networks, 750
Fibonacci heaps, 69, 86, 89–92; see also Skew heaps
data structure, 85
Fibonacci number, 155
Fibonacci trees, 708
FID, see Fully indexable dictionary
FIFO, see First in first out
formats, 859
index data structure, 799
path, 947
File organization, 980–981; see also Page organizations; Record organizations
Filtering, 421
Filter-refinement approach, 872, 883
compression, 940
Finger search trees, 155, 171, 179; see also Balanced binary search trees (BBST)
adaptive merging and sorting algorithm, 176–177
applications, 175
arbitrary merging order, 175–176
dynamic finger search trees, 171–172
level linked (2,4)-trees, 172–173
list splitting problem, 176
optimal merging and set operations, 175
randomized finger search trees, 173–175
Fine-grained locking scheme, 743
FinishPointer, 774
Finite element methods, 323
Finite trees, 151
First-come first-served hashing (FCFS hashing), 125
First in first out (FIFO), 31, 192
dynamic tree implementation, 193–194
First matching rule in table, 766, 783
FIS-tree, see Fat Inverted Segment tree
Fixed-length records, 977
Fixed-stride trie optimization (FSTO), 771
Fixed-stride tries (FSTs), 770–772
Fixed length (FL), 361
Fixed length-depth (FD), 361
Fixed size alphabet, 463
Fixed string of diamonds, 730
FKS-(α/2) data structure, 121
FKS hashing scheme, 597
FL, see Fixed length
Flexibility, 680
Flight simulators, 857
Flip bit, 288
Float-kernel, 656
Floating point Cartesian coordinates, 656
Floats data type, 699
Floorplan representation in VLSI, 833, 834, 849
combinations and complexities of representations, 834–835
extra constraints, 854
graph based representations, 837–844
motivation of representation, 834
placement based representations, 844–850
rectilinear shape handling, 851–853
relationships of representations, 851
slicing, mosaic, LB compact, and general floorplans, 835–837, 838
statement of floorplanning problem, 833–834
Flow, 190, 765fn
across cut, 190
Flow-Excess, 190
fast rank and select operations using wavelet trees, 929–931
problem of searching patterns in string, 931
simple scheme supporting Rank queries on binary string, 931
suffix array and Burrows–Wheeler transform, 927
Fonts, 859
Force directed methods, 737
Forced reinsertion, 429
Forest
forest-structured Bloom filter, 146
ordered set of trees, 37
set of trees, 53
Forest of Quadtrees (FQT), 903, 907, 909–910
Fortune’s algorithm, 1021
4-dimensional real-life classifier, 785
Four-dimensional space, 251
Four-sided queries, 563
FP-growth algorithm, 1005, 1007
FQT, see Forest of Quadtrees
Fractional cascading, 1029–1030
Fractional cascading, 990, 991
Fragmentation, 979
Freelist, 752
Free tree, 35
Frequent itemsets, 1003
Frequently-encountered problem, 58
Frontier-based methods, 507
FSTO, see Fixed-stride trie optimization
FSTs, see Fixed-stride tries
Full path method, 519
Fully dynamic algorithms, 582, 589
Fully dynamic connectivity, 574
problem, 587
Fully dynamic graph problem, 581
Fully dynamic minimum spanning tree, 588–589
problem, 574
Fully dynamic tree membership, 573
Fully indexable dictionary (FID), 597, 598
Fully persistent data structures, 511
Functional data structures, 639
data structures in functional languages, 639–640
decreased synchronization, 640
difficulties, 649
fewer bugs, 640
functional data structures in mainstream
languages, 640
increased sharing, 640
in mainstream languages, 640
Functional languages, data structures in, 639–640
Functional programming language, 641
Fundamental primitives, 546
Fundamental supernodes, 950, 960
Funnel heap structure, 554, 555
Furthest-site Voronoi diagram partitions, 1022
Fusion tree, 597, 628, 630–632
G
Gabriel Graph (GG), 1023, 1034
Garbage collection, 640
Garsia-Wachs algorithm, 216, 224, 226, 227, 228
Gaussian elimination, 945, 946, 957, 958
Gauss map, 897
GB(c)-trees, see General balanced trees (GB-tree)
GB-tree, see General balanced trees
GDAL, see Geospatial Data Abstraction Library
GDBX system, 704
GEM alignment tool, 927
Genbank, 923
Genealogical information, 35
General balanced trees (GB-tree), 160–161
constraint graphs for, 838
example, 851
O-tree representation, 844
General graph, 49
Generalization
of map, 873
Generalized-element model, 957
Generalized grounded range reporting problem, 1048
Generalized half-space range searching, 1049–1050; see also Persistence-based approach; Sparsification-based approach
Generalized intersection searching; see also Nearest neighbor searching
adding range restrictions, 1053–1054
approach for reporting problems, 1052–1053
arbitrarily oriented objects, 1045
axes-parallel objects, 1044–1045
exploiting output size, 1054–1055
external memory and word-RAM algorithms, 1045–1046
geometric intersection searching problems, 1043–1044
persistence-based approach, 1050–1052
problems on grid, 1045
reverse transformation, 1055–1056
single-shot problems, 1045
sparsification-based approach, 1048–1050
summary of known results, 1044–1046
transformation-based approach, 1046–1048
Generalized lists, 31
Generalized one-dimensional range searching problem, 1046
Generalized reporting problem, 1043–1044
Generalized search trees (GiSTs), 756
Generalized semidynamic
two-dimensional range searching, 1051
Generalized suffix trees, 466
Generalized three-dimensional range searching, 1050, 1052
Generalized two-dimensional quadrant range searching, 1050
General orthogonal 2-D range search, 433–434
General polygonal models, 892
interference detection using trees of oriented bounding boxes, 893–896
performance of bounding volume hierarchies, 896
Generating function framework, 809–810
Generic algorithms, 667
Geodesic triangulations, see Pseudo-triangulations
Geographic information systems (GISs), 251, 343, 359, 419, 871, 878
applications, 872
cartographic generalization, 873
data mining, 874
geometric data structures, 872
geometric objects, 871
geometric operations, 872
map labeling, 873
map overlay, 873
models, toolboxes, and systems for geographic information, 882
open source systems and research prototypes, 883
spatial database systems, 883
spatiotemporal data, 874
standardized data models, 882
topological vs. metric data, 872
Geography Markup Language (GML), 882
GeoJSON, 882
Geometric
automorphisms, 728
computing, 277
data, 331
data structures, 872
distribution, 202
dynamic multi-level tree algorithms, 793
graphs, 384
intersection searching problems, 1043–1044
operations, 872
primitives, 892
relation, 378
scene, 658
set systems, 399
software libraries, 872
structures, 385
2-dimensional classification scheme, 790, 791
Geometry, 882
Geometry Engine, Open Source (GEOS), 883–884
Geometry Kernels, 656
GEOS, see Geometry Engine, Open Source
Geospatial Data Abstraction Library (GDAL), 882, 883
Geotagging, 269
GeoWin, 358
GG, see Gabriel Graph
Giant components, emergence of, 811
GISs, see Geographic information systems
GiSTs, see Generalized search trees
Global rebuilding
approach, 535
operation, 121
GML, see Geography Markup Language
Golumb code, 800
Good nodes, 910
Google Chubby projects, 986
Gossip-style protocol, 986
Gouraud model, 861
GPA, see Grade point average
GPS
devices, 874
systems, 370
Grade point average (GPA), 969–970
Graham’s scan, 1018
Graph(s), 277, 686–687, 938, 960
based representations, 837
connectivity, distance, and spanning trees, 51–54
corner stitching, 841
databases, 984
data structures, 655
data type, 657
digraph with 6 vertices and 11 edges, 50
Eulerian and Hamiltonian graphs, 65–66
graph-based approach, 833
“graph-like” representations, 533
graph-theoretic approach, 935
graph-theoretic representations, 935
pseudograph of 6 vertices and 10 edges, 50
representations, 603
simple applications of DFS and BFS, 56–58
single tree representations, 842–844
theoretic representations, 936
undirected graph with 5 vertices and 6 edges, 50
weighted graph representation, 51, 52
has-a-joint-paper-with Relation, 724
prerequisite diagram, 725
two drawings of graph, 724
two drawings of social network, 724
Graphical display of data structures, 698
GraphLibrary (libG), 655
Graycode, 315
Gray code curve, 875
“Greedy” algorithms, 62, 216, 217, 955
Greengard’s fast multipole method, 323
Grid
directory, 255
grid-based methods, 323
placement, 845
problems on, 1045
vertex, 347
Grounded 2D-range search problem, 305–306
Grouping process, 256
Group mutual exclusion, 748
Group queries, unified algorithm for, 319
Growth model, 807
Gunther’s algorithm, 352
H
H2GIS, 883
Halfedge data structure, 281; see also Kinetic data structures (KDS); Layout data structures; Online dictionary structures; Spatial data structures
access functions, 282
edge insertion and deletion, 283–284
effects of half_splice, 283
vertex split and edge contraction, 284–287
Halfedge data structure, 872, 1021
Half-space in d-dimensional space, 261fn
Halfspace range searching, 435
Hand, 172
Hand-over-hand locking approach, 753
Haptic rendering, 889
hardware-based algorithms, 795
Hardware depth buffer, 384
Hash-based cache, 501
Hash-based indexes, 969
Hash-based join approach, 353
Hash complexity, reducing, 146
Hashed consing, 532
Hash files, 980
Hash functions, 117, 118, 132fn
approaches for improved searches, 940–941
with chaining, 122
by division, 118
with open addressing, 123
HashtableDictionary, 687
developments, 127
historical notes, 126
operations, 506
Hash tree structure, 1004–1005
Hash value, 117
Haskell
binary search trees in, 643
skew heaps in, 645
stacks in, 641
Hasse diagram, 479
Hbase, 984, 986, 988, 989, 990, 992
HBLTs, see Height-biased leftist trees
HBSTR-tree, 360
Header, 977
Header page, 980
Heap-on-Trie (HoT), 793
files, 980
heap-based priority queues, 756–757
insertion, 45
max-heap, 44
priority queues, 44
Height balanced trees, 180
Height-biased leftist trees (HBLTs), 70
deletion of arbitrary element from max HBLT, 74
deletion of max element from max HBLT, 72
insertion into max HBLT, 71
max trees, 71
Height limited Huffman trees, 220
algorithm for coin collector problem, 221–222
reduction to coin collector problem, 220–221
Height of trie, 447
Heights of subtrees, 154
Heuristic(s), 793
optimization, 346
optimizing algorithms, 834
tuple space search, 795
HiCuts, see Hierarchical intelligent cuttings
Hidden surface removal, 867
Hierarchical clustering, 1007–1008
Hierarchical information, 35
Hierarchical intelligent cuttings (HiCuts), 793–794
Hierarchical motion descriptions, 386
Hierarchical partitioning, 434
Hierarchy generation, 893
High confidence bounds, 198, 199
High-dimensional data, problems with, 1009
Highest-priority matching, 777; see also Most-specific-range matching
search for highest-priority matching range, 779
Highest-priority rule, 766
High-level data, 903
High-level image processing, 903
Highly recurring oligonucleotides, 917
High probability bounds, 198
High-speed on-die cache memory, 132
High-throughput screening, 935
Hilbert curve, 347, 875, 876–877, 878
Hilbert R-tree, 429
Hilbert sort (HS), 349
Hilbert value, 347
Hinted Quad Trees (HQT), 829–830
Historical R-tree (HR-trees), 368
Historical shortest path, 586
Historical synopsis, 367
History DAG, 1031
Homology, 845
Hopcroft’s problem, 401
Horizontal-vertical (hv), 719
hv-layout algorithms, 708
HV Trees, 829
Horizontal combination, 719
Horizontal pointers, 204
HoT, see Heap-on-Trie
HQT, see Hinted Quad Trees
HR-trees, see Historical R-tree
HS, see Hilbert sort
“Hubs”, 805
Huffman algorithm, 215
Huffman algorithm for t-ary trees, 220
Huffman codes, 216
and entropy, 220
Huffman algorithm for t-ary trees, 220
Huffman codes and entropy, 220
linear time algorithm for presorted sequence of items, 218
O(n log n) time algorithm, 217
relation between general uniquely decipherable codes and prefix-free codes, 218–219
Hydrogen-excluded representation, 936
Hydrogen-included representation, 936
Hyperoctrees, 309
Hyperplane, 329, 332, 333, 401
Hyperrectangles, 298
I
IDE, see Integrated development environment
Image acquisition, 903
Image array, 259
Image data structures; see also Kinetic data structures (KDS); Layout data structures; Online dictionary structures; Spatial data structures
Image dilation, 263
Image manipulation/analysis, 903
Image processing, 903
applications, 320
connected component labeling, 322
construction of image quadtrees, 321
rotation and scaling, 321
union and intersection of images, 321
Image quadtrees construction, 321
Immediate subcells, 312, 313, 314, 317
Immediate supercell, 312
Immutability, 639
Immutable data structures, 639
Implicit data structures, 98
Implicit representation of balance information, 159–160
Improved decremental algorithm for APASP up to distance d, 622–624
Incense system, 701
IncidenceListGraph, 687
Incidence preserving, 1016
Inclusion exclusion pruning, 814
Incorporating randomness, 197
Incremental dynamic graph problem, 581
Incremental graph problem, 581
Incremental landscape, 482, 484
Incremental penetration depth computation, 897
implementation and application, 898
initialization and refinement, 897–898
local walk, 897
Independence of two events, 200
Independent set of vertices, 1029
Index
on both spatial relations, 880
compression, 800
generation efficiency, 360
index-nested-loop join algorithm, 970
multi-dimensional indexes, 970
one-dimensional indexes, 969–970
on one spatial relation, 880
Indexability, 434
Indexable bitvector, 597
Indexable circular deques, 607
Indexing
hybrid type of indexing methods, 360
mechanisms, 864
Indirect addressing, 978
Indirect page addressing, 975
Inductance, 818
Induction
hypothesis, 620
Influential variables, 502
Information processors, 679
Information retrieval, 799
Information-theoretic O(log n) barrier, 628
Information visualization, 697
interval heap, 103
Inner convex drawings, 738
Inner radius, 406
In-order invariant, 152
of threaded binary tree, 41–42
Input communication, 419
Input data distribution, 355
Input/output (I/O), 343
algorithms, 419
cost of insertion, deletion and exact-match query, 245
efficient algorithms, 1045
high I/O performance, 987
performance, 427
two-level I/O-model, 545
“Insert 23” operation, 992
Insert algorithm, 236, 241–242
Inserting into trie, 449
algorithm, 317
max-heap, 45
into max HBLT, 71
of object, 362
sort, 25
sort algorithm, 176
of string, 466
Insert operation, 14, 80, 85, 182, 197, 554
InspectableBinaryTree, 686
InspectableGraph, 687
InspectableKeyBasedContainer, 687
InspectableTree, 686
Instance, see Records
IntegerDijkstraPathfinder class, 693–694
IntegerDijkstraTemplate class, 690–693
Integer keys, hash tables for, 118
dynamic perfect hashing, 120–122
hashing by division, 118
hashing by multiplication, 118–119
static perfect hashing, 119–120
universal hashing, 119
Integers data type, 699
Integrated development environment (IDE), 699
Intention content, 700
Interference detection, see Collision detection
Interior-based representation, 259
Internal nodes, 37, 70, 152, 972, 1031
Internal path length, 37
Internet-of-Things (IoT), 983
Internet Protocol (IP), 765
highest-priority matching, 777–779
longest matching-prefix, 767–777
most-specific-range matching, 780–780
prefixes and ranges, 766
router tables, 765
Inter-object spatial relations, BSP tree representation of, 330
Inter-object visibility orderings, 336
Intersection
bound, 941
of images, 321
model, 882
operation, 868
Interval graph, 291
complementary range search problem, 104–105
complexity of interval heap operations, 104
initializing interval heap, 103
inserting element, 101–102, 103
removing min element, 102–103, 104
Interval intersection graph, 291
Interval tree, 263, 291, 292, 901
example and applications, 293–294
Intra-object visibility, 333
Invariants, 588
Inverse Ackermann’s function, 322
index compression, 800
Invocation, 548
IoT, see Internet-of-Things
IP, see Internet Protocol
IPv4
prefix sets, 771
router tables, 770
Irregular arrays, 27
Iso-oriented rectangles, 291
Isolated vertex, 53
Itemset, 1003
Iterated logarithm function, 539
Iterator(s), 668, 674, 682–683
classes, 667
iterator-based tree traversals, 688
reverse iterators, 676
J
Jaccard coefficient of similarity, 802
Java, 26
applications, 883
binary search trees in, 643
language, 640
programming language, 679
skew heaps in, 646
stacks in, 641
Java collections (JC), 679, 681
Java generic libraries (JGL), 679, 681
JC, see Java collections
JDSL, see Data structures library in Java
JGL, see Java generic libraries
Join algorithms, 352
Join operations, 183
Join procedure, 211
JTS Topology Suite (JTS), 883–884
K
Käräkkanen and Sanders’ algorithm, 467–468
k-cells, 1014
k-crossing filter set (k-CFS), 790
k-cut, 413
kd–B-trees, 429
KDD, see Knowledge discovery in databases
k-DOP-tree, 893
KDS, see Kinetic data structures
k-d tree, 254, 256, 261, 311, 331, 343, 360, 412, 426, 560, 826, 892, 1036
nearest neighbor search in, 1037
set of points in plane, 1036
KeyBasedContainer, 687
Keys, 152
with different length, 446–447
key-based containers, 682, 687
key-based partitioning, 991
key-value stores, 984
priority queues, 687
Kinetic data structures (KDS), 378, 435; see also Layout data structures; Online dictionary structures; Spatial data structures
application survey, 381
connectivity and clustering, 384
continuously moving items, 436–437
convex hull, revisited, 380–381
event, 382
extent problems, 382
logarithmic method for decomposable search problems, 435–436
motion in computational geometry, 377
performance measures for, 379–380
querying moving objects, 387
triangulations and tilings, 382–383
Kinetic methods, 383
Kinetic motion-sensitive algorithms, 386
Kirchoff voltage law, 840
Kirkpatrick’s algorithm, 1028–1029
Kleene closures, 584
logarithmic decomposition, 585
recursive decomposition, 585
Kleinberg’s HITS algorithm, 805
binary mergers and merge trees, 548–549
funnelsort, 550
k-nearest neighbors, 320
classification algorithm, 1001
k-nearest neighbor joins, 881
query, 367
k-neighbor trees, 162
Knowledge discovery in databases (KDD), 997
Knowledge processing application, 507
Kraft’s inequality, 219
Kruskal’s MST algorithm, 59, 60
L
Label-correcting method, 63
Labeled buffer, 430
Labeled Hilbert, 431
Labeled naive, 430
Labeled universe, 531
Label of directed path, 477
Laguerre diagram, 1022
Land use, 873
Large binary objects (LOBs), 968
Large environments, 898
algorithms for, 890
multiple-object collision detection, 899–900
two-dimensional intersection tests, 900–901
Large objects (lobs), 977
Largest strongly connected component, 806
Larmore-Hirschberg algorithm, 215, 216
Last-come first-served hashing (LCFS hashing), 125–126
Last in first out (LIFO), 31
Las Vegas type algorithms, 198
Las Vegas type randomized algorithm, 203
Latency, 872
Law of total probability in conditional form, 200
Laws of probability, 199
Layer, 873
editor, 819
process, 819
Layout data structures, 818, 819; see also Halfedge data structure; Multidimensional spatial data structures
corner stitching data structure, 819–822
corner stitching extensions, 822–826
quad trees and variants, 826–830
Lazy skew heaps analysis, 648–649
Lazy strategy, 373
LB compact floorplans, 835–837, 838
LCA, see Least common ancestor
LCFS hashing, see Last-come first-served hashing
LCS data structure, see L-shaped corner stitching data structure
LC-tries, see Level-compressed tries
Leaf
correspondence, 112
entry updating, 363
label, 462
leaf-oriented trees, 165
quads, 828
selection, 345
Least common ancestor (LCA), 174, 951
Least Weight Subsequence problem (LWS problem), 230
LEDA, see Library of efficient data types and algorithms
LEDA extension packages (LEPs), 654
LEDA-SM, see Extending LEDA to secondary memory
Left child-right sibling representation, 37
Left contour, 709
Left-deep tree, 973
Leftist orders, 426
Leftist trees, 77; see also Trees
binary tree and extended binary tree, 70
Left-justified trees property, 230–231
Left-looking algorithm, 952
Leftmost canonical ordering, 728
Left tree, 195
Length of path, 215
Length of string, 477
Lens system, 704
LEPs, see LEDA extension packages
Level, 153
Level-balanced B-trees, 426–427
Level-compressed tries (LC-tries), 449
Level drawings, 709
Level equivalent, 225
Leveling, 204
Level layout
Level linked (2,4)-trees, 171, 172–173, 175
Level links, 172
Level number, 361
Level-order unary degree sequence representation, 600
Level order traversal, 41
Level-pointers, 153
Level-tiered LSM trees, 989
Lexicographic depth, 464
Lexicographic ordering, 464
Library of efficient data types and algorithms (LEDA), 653, 679, 884
algorithms, 656
availability and usage, 654
combinatorial and geometric computing, 653
correctness, 654
data structures and data types, 655–656
discussion, 664
example programs, 659
extensibility, 654
projects enabled by, 665
upper convex hull, 663
word count, 659
LIFO, see Last in first out
Lifting map, 1034
Limited node copying, 1029
Lin-Canny algorithm, 892
Line-based constraint graphs, 840
Linear growth models, 808
Linear hash files, 980
Linear hashing, 127
Linear in d-dimensional space, 261fn
Linearizability, 746
Linearization point, 746
Linear list, 767
Linear ordering, 315
Linear programming problem (LP problem), 890
Linear quadtrees, 903
Linear region quadtree, 361
Linear space, 630
exponential search trees, 632–633
spatial structures, 429
Linear speedup, 742
Linear split algorithm, 345
Linear time
constructing DAWG in, 482
tree traversal method, 471
Linear time algorithm, 467, 482, 709, 728, 732, 1036
for constructing convex drawings of planar graphs, 726
for constructing planar convex grid drawing, 727
for drawing binary trees, 707
for drawing planar graphs, 728
for presorted sequence of items, 218
Linear time construction algorithms, 463
Käräkkanen and Sanders’ algorithm, 467–468
space issues, 468
of suffix arrays, 467
Line data and boundaries of regions, 265–268
Line quadtrees, 906
Line road data sets, 423
Line-swept sphere (LSS), 893
LINGO, 942
LINGOsim computation, 942
Linked lists, 28, 204, 753–754
doubly linked circular lists, 30
generalized lists, 31
Linking and cutting trees, 185, 567, 568, 582, 584
data structure, 186
implementation of primitives for, 189
implementation without, 192–193
implementing operations on vertex-disjoint paths, 569–571
using operations on vertex-disjoint paths, 568–569
splay analysis in virtual tree, 188–189
splay in virtual tree, 188
splicing, 188
Linking operation, 85
two heap-ordered trees and result of linking, 86
LISP functional programming languages, 532
List, 668
ranking, 427
representation, 37
splitting problem, 176
structures, 862
Little oh notation (o), 11
LL/SC, see Load-linked/store-conditional
lmp, see Locally minimal pair
LMPBOB, see Longest matching-prefix BOB
l-multiMEM-problem, 924
Load-linked/store-conditional (LL/SC), 744
Load balancing algorithm, 753
Loading algorithms, 352
LOBs, see Large binary objects
lobs, see Large objects
geometric locality, 892
locality-guided work stealing algorithm, 753
locality-sensitive hashing, 435
principle of, 338
Locally minimal pair (lmp), 225–226
“Locally optimal” solution, 897
Local rebuilding, 155
Local retiling of space, 382
Local spinning, 743
Location, 1027; see also Point location
planar point, 554
Locator, 682
Lock, see Mutual exclusion lock
Logarithmic method, 435–436, 561
Logarithmic on binary search tree, 35
Logical address, 978
Logical operation, 7
Logical pointers, 978
Logical query plans, 968
Logic design, 817
Logic elements, 817
Logic gates, 817
Log structured merge tree (LSM tree), 987, 988–989
Long development time, 679
Longest common prefix, 462
Longest common substrings, 470–471
Longest matching-prefix
linear list, 767
sets of equal-length prefixes, 768–769
Longest matching-prefix BOB (LMPBOB), 777
Longest prefix matching for routing lookups, 784
Longest-side k-d trees, 416
Long paths, 585
Loose quadtree, 264
Loser trees, 48
Lowest common ancestors, 472
Bender and Farach’s lca algorithm, 472–473
suffix links from, 473
Low-level data, 903
Low-level image processing, 903
LP problem, see Linear programming problem
L-shaped corner stitching data structure (LCS data structure), 823–824
comments on corner stitching, 825–826
parallel corner stitching, 825
rectilinear polygons, 825
space requirements of tiles, 825
LSM tree, see Log structured merge tree
LSS, see Line-swept sphere
Lune, 1034
LWS problem, see Least Weight Subsequence problem
M
Mainstream languages, functional data structures in, 640
Maintenance contract, 15
aggregate method, 15
potential method, 16
problem definition, 15
worst-case method, 15
labeling, 873
overlay, 873
visualization, 873
Mapping data to display, 704
Marker partitioning technique, 769
Market basket
analysis, 998
Mark procedure, 207
Markup languages, 882
Master Equation Approach, 808
Matching basic interval, 774, 775
Match path, 926
Mathematical Graph Theory, 725
Matrix-vector multiplications, 899–900
Max-Flow Min-Cut Theorem, 190–191
Max-heap, 44
Max arrays, 101
Max HBLT
arbitrary element deletion from, 74
deletion of max element from, 72
Max heap, 108
Maximal clique in graph, 949
Maximal multiple exact match, 924–926
Maximal palindrome, 474
Maximum Clique Size of set of Intervals, 297
Maximum-spread k-d trees, 416
Maximum clique problem, 291, 296
Maximum elements, 43
Maximum weight spanning tree (MST), 954
maxPQ, 111
Max tree, 71
Max WBLT operations, 75
MB, see Megabytes
MBB, see Minimum bounding boxes
MBRs, see Minimum bounding rectangles
McCreight’s algorithm, 465–466, 470
McWidget company, 16
aggregate method, 17
potential method, 18
problem definition, 16
worst-case method, 17
MDEPQs, see Meldable DEPQs
“Mean field theory” based model, 806
Medial axis, 1033
Megabytes (MB), 859
Meldable DEPQs (MDEPQs), 113
Meldable priority queues, 77, 80; see also Double-ended priority queues (DEPQs)
amortized cost of meld operation, 82–83
left and right children of nodes, 81
left subtrees of nodes in merged path, 81
Melding operation, 77
Meld operation, 77, 80, 85, 113, 153
max HBLT meld operation, 71
skew heaps for, 80
ofWBLT, 75
Membership
bits, 132
problem, 291
word, 137
Memory management techniques, 506
Memory model, 595
Memory transfer, 545
MEMS, see Microelectromechanical systems
based priority queue, 554
layout, 555
scheduling, 991
sort, 970
sort recurrence of equation, 13
Merged constraint graph, 839
Mergesort, 546
Merging
BSP trees, 336
phase, 971
process, 175
Metanode, 908
Metric data, 872
Metric distance, 406
Microelectromechanical systems (MEMS), 823
Middle tree, 195
Min array, 101
minconf thresholds, 1003
Min heap, 108
Minimal edags, 961
Minimalistic approach, 166
Minimal perfect hash function, 127
Minimal pseudo-triangulations, see Minimum pseudo-triangulations
Minimum-degree algorithms, 957, 958
Minimum-degree ordering heuristics, 957
Minimum-time flight itineraries, 689–690
Minimum AABB, 256
Minimum bounding boxes (MBB), 365, 373
leaf-level MBBs, 371
MBB-based index, 365
Minimum bounding rectangles (MBRs), 343, 365, 370, 879, 882
Minimum pseudo-triangulations, 1024, 1025
Minimum separation determination, 377
Minimum spanning forest, 59
Minimum spanning tree (MST), 58, 381, 384, 588, 689; see also n–ary trees; Ordered-tree (O-tree)
Boruvka’s MST algorithm, 62
constrained MST, 62
deletions in O(log2 n) time, 589
of graph, 35
Kruskal’s MST algorithm, 59, 60
updates in O(log4n) time, 589
Minkey queries, 567
Minkowski metric (Lm metric), 1035
minsup thresholds, 1003
Min tree, 71
Model evolutionary graphs, 808
Molecular graph, 936
Molecular sequence databases, 917
MonetDB/GIS, 883
MongoDB, 988
Monoid, 530
Monotone, 1023
monotone-matrix concepts, 228
subdivisions, 427
Monotonicity property, 223
Monte Carlo algorithms, 198
Morgan’s algorithm, 937
Morton encoding, 875
Morton order, 255
Morton ordering, 315
constraint graphs for, 839
example, 851
and representations, 852
Most-specific-range matching, 780; see also Highest-priority matching
conflict-free ranges, 780
nonintersecting ranges, 780
Most-specific-rule matching, 766
Motion, 377
formulation, 890
plan, 378
sensitivity, 386
MPBSM, 423
MSQT, see Multiple Storage Quad Trees
MST, see Minimum spanning tree
Multibit tree, 943
Multi-dimensional access methods, 1008–1010
Multidimensional arrays, 26, 864
array of arrays representation, 26
irregular arrays, 27
row-or column major representation, 26
Multidimensional balanced binary search trees, 393, 395
Multidimensional binary search trees, 311
Multidimensional data, 251
Multi-dimensional indexes, 970, 980
Multi-dimensional packet classification
bounds from computational geometry, 786
classification algorithms, 785
hardware-based algorithms, 795–797
performance metrics for classification algorithms, 785
taxonomy of classification algorithms, 787
Multidimensional range search, 428
Multi-dimensional search
application to multi-dimensional search trees, 161–162
Multidimensional spatial data structures; see also Kinetic data structures (KDS); Layout data structures; Online dictionary structures; Spatial data structures
line data and boundaries of regions, 265–268
transformation approach, 251–252
Multi edges, 49
Multifrontal factorization method, 957
Multigraph, see Multi edges
Multi-level index, 980
Multimedia systems, 359
multiMEM, see Maximal multiple exact match
Multiple-choice hashing method, 125, 126
Multiple-key index, 970
Multiple-object collision detection, 899
implementation and application, 900
one-dimensional sweep and prune, 900
Multiple elimination, 958
Multiple exact match, 924
Multiple lists in single array, 25
Multiple posting problem, 258
Multiple Storage Quad Trees (MSQT), 827
Multiple views, 984
Multiplication, 506, 595, 627, 630
Multiplicative weights, 1022
Multi-resolution representation, 335, 337
Multirooted BDDs, 498
Multistep query processing, 879
Multiversion 3D R-trees (MV3R-trees), 360, 370
Multiversion B-trees (MVBT), 360
Multiversion linear quadtree (MVLQ), 360
deletion of object in, 362
insertion of object in, 362
updating object in, 363
Multiversion linear quadtree (MVLQ), 360, 361
deletion of object, 362
insertion of object, 362
updating object, 363
Multiversion R-tree (MVR-tree), 368, 369, 370
Multi-way merging, 971
Multi-way trees, 166–167, 425, 431
balanced binary trees based on, 157–158
Munro’s equations, 591
Mutex, see Mutual exclusion lock
Mutual exclusion lock, 742, 747
coupling approach, 753
elision, 749
granularity, 742
lock-free counter, 745
lock-free operation, 744
MV3R-trees, see Multiversion 3D R-trees
MVBT, see Multiversion B-trees
MVLQ, see Multiversion linear quadtree
MVR-tree, see Multiversion R-tree
MX-CIF quadtree, see Bisector List Quad Trees (BLQT)
MX quadtree, 266
“Mysterious” behavior, 216
N
n–ary trees, 708–709; see also Minimum spanning tree (MST); Ordered-tree (O-tree)
apportion, 715
combining subtree and left subforest, 713–714
level layout for, 710
level layout of PQ-tree, 712
PrePosition, 713
shifting smaller subtrees, 715–718
spacing out smaller subtrees, 711
Nahar-Sahni algorithm, 825
Naïve approach, 364
Naive scheme, 511
NAND gate, 817
NAP, see Network Access Point
Narrow phase, 898
Nauty, see No AUTomorphism, Yes?
N-component, 552
Near-duplicate detection algorithm, 802
Near-duplicate documents, finding, 801–802
classification scheme, 1001
classifiers, 1001
proximity graphs for enhancing, 1001–1002
query, 310, 350–351, 407, 425, 428, 872
Nearest Neighbor Graph (NNG), 1034
Nearest neighbor searching, 421, 1008–1010, 1035; see also Generalized intersection searching
approximate nearest neighbor searching, 1037–1038
AVD, 1038
other approaches to, 1037
through point location, 1036
Nearest-X (NX), 349
Negative binomial distribution, 202–203
Neighbor(s), 574
Finding operation, 820
list, 323
Nested-loop algorithm, 879
Nested clustering, see Hierarchical clustering
Network Access Point (NAP), 783
Network flows, application to, 190–192
Networks, 50
NewSQL databases, 984
Next-generation sequencing (NGS), 926–927
NGS, see Next-generation sequencing
NNG, see Nearest Neighbor Graph
No AUTomorphism, Yes? (Nauty), 937–938
Node, 49, 151, 152, 344, 425, 496, 688, 826
capacity, 345
deletion rule, 497
reduction rules, 497
sharing rule, 497
NodeBinaryTree, 686
algorithm, 346
NodeTree, 686
Nonblocking
algorithms, 743
linearizable heap-based priority queue algorithms, 756
operator, 882
Non-canonical structures, 386–387
Non-clustered index, 980
Non-convex
models, 898
polyhedral models, 899
Nondestructive updates, 531
Non-indexed data set, 352
Nonintersecting ranges, 780
Nonnegative weights, single-source shortest paths and, 62–63
Nonoverlapping, 258
collinear chain of nonoverlapping anchors, 923, 924
intervals
polytopes, 897
Nonpoint data, 429
Non-robust
algorithms, 953
method, 953
Nonroot nodes, 194
Non-slicing structure, 849
Nonterminal nodes, 496
Non-uniform memory access (NUMA), 743
Nonzero element, 27
NOR gate, 817
NoSQL paradigm, see Not Only SQL paradigm
NOT gate, 817
Not Only SQL paradigm (NoSQL paradigm), 983
database workloads, 987
data stores, 983–984, 987, 993
NP-complete problem, 502
NUMA, see Non-uniform memory access
Number-of-brep-faces, 340
Number-of-tree-nodes, 340
Number processors, 679
Numerical linear algebra, 945
NX, see Nearest-X
O
OAT problem, see Optimal alphabetic tree problem
OBBs, see Oriented bounding boxes
OBDDs, see Ordered BDDs
Object, 332
hierarchy, 256
object-oriented language, 699
total ordering of collection of, 332–333
updating, 363
OBST, see Optimal binary search trees
Obstruction-free operation, 744
OCC, see Optimistic concurrency control
Occupancy of hash table, 117
OCR, see Optical character recognition
Octants, 262
Octrees, 260, 322, 340, 412, 892, 911–912; see also Quadtrees
compressed quadtrees and, 313–314
representation, 913
Odd-even merge sort, 635
Offset, 977
OGC, see Open Geospatial Consortium
O(log n) Time, searching and priority queues in, 627
achieving sub-logarithmic time per element by simple means, 628–630
from amortized update cost to worst-case, 633–634
deterministic algorithms and linear space, 630–633
model of computation, 627
overview, 628
sorting and priority queues, 634–636
OM data structure, see Order Maintenance data structure
Omega notation (Ω), 11
One-at-a-time result, 959
One-cut, 413
One-dimension (1D)
1D-range tree, 299
array, 26
compaction, 819
data structures, 874
packet classification, 765, 783
sweep and prune, 900
1-edge, 496
One-level search tree, 800
1-terminal, 496
Online data structures, 421
Online dictionary structures; see also Kinetic data structures (KDS); Spatial data structures
additional operations, 395
balanced BST implementation, 393–395
binary search tree implementations, 391–393
discussion, 396
O(n2 log n) time, updates in, 590
O(n2 log3 n) time, updates in, 592
O(n log n) planesweep algorithm, 825
O(n log n) time algorithm, 217
O(n2) time, updates in, 591
O(nβ+2)-timedynamic programming algorithm, 227
Open addressing, hashing with, 123
Open Geospatial Consortium (OGC), 882, 883
Open source systems, 883
Open transaction times, handling query with, 367–368
Operating system, 451
Operations, 555–556, 558–559, 601
cache, 501
types, 350
on vertex-disjoint paths, 568–569, 569–571
Operator trees, 968
Optical character recognition (OCR), 541
Optimal algorithm, 881
Optimal alphabetic tree problem (OAT problem), 216, 224–226
construction, 226
for presorted items, 226
Optimal binary search trees (OBST), 216, 222–224
Optimal construction, 402
Optimal hashing, 127
Optimality of splay trees, 184–185
bloom-1 vs. bloom with, 139–140
bloom-g vs. bloom with, 142–144
Optimal lopsided trees, 216, 226–229
Optimal merging, 175
Optimal paging strategy, 560
Optimal policy matrix, 65
Optimal static finger search algorithm, 171
Optimal structure, 432
Optimistic approach, 744
Optimistic concurrency control (OCC), 749
Orbit-stabilizer theorem, 728
Order, 969
preserving, 1016
queries, 427
Ordered BDDs (OBDDs), 496
Ordered partition, 954
Ordered queries, 152
Ordered-tree (O-tree), 429, 833, 842, 844; see also Minimum spanning tree (MST); n–ary trees
building, 842
horizontal O-tree, 842
with linear lists, 843
performance, 843
representations, 844, 851, 853
structures, 835
Ordering, 255
fields, 980
key for file, 980
of polygons, 334
Order–kVoronoi diagram, 1022
Order Maintenance data structure (OM data structure), 516, 518
Order-preserving hash functions, 424, 425
Oriented bounding boxes (OBBs), 893, 896
implementation and application, 896
interference detection, 894–895
interference detection using trees of, 893
OBB-trees, 893
Original heuristics, 345
Original tree, 186
Orthogonal drawings, bar visibility representations for, 736–737
Orthogonal range
lower bounds for orthogonal range search, 434
queries, 561
O-tree, see Ordered-tree
Outer radius, 406
Outliers, 1009
Out-of-core
algorithms, 419
factorization, 953
Output communication, 419
Output-sensitive
query time, 1043
Output size, exploiting, 1054–1055
Overlap(ping)
query, 367
interval searching problem, 293
polytopes, 897
Overlapping linear quadtrees, see Multiversion linear quadtree (MVLQ)
Overmars-van Leeuwen structure, 1019
P
P2P search problem, see Peer to peer search problem
Packed bucketing, 635
Packet, 787
packet-header information, 765
Packing algorithms, 349
Packing function, 409
Packing problem, 852
Page header, 978
pageID, 234
Page organizations, 978; see also File organization; Record organizations
alternative page organizations for fixed-length records, 979
slots, 978
for variable-length records, 979
Page reference list, 977
Page reference pointer, 977
Page-related pointers, 978
Pages, 234
Page table, 975
Painter’s Algorithm, 329, 332, 867
Pairing heaps, 69, 86, 92–94; see also Skew heaps
adaptive properties, 94
data structure, 85
variations, 94
Pairwise independence, 200
Pairwise join method (PJM), 881
Palindrome, 474
Panning, 873
Parallel algorithms, 230
property of left-justified trees, 230–231
Parallel column-oriented factorizations, 953
Parallel disk model (PDM), 419–420, 421
Parallel edges, 49
Parallel factorization algorithm, 952
Parallelism, 799
Parallel R-trees, 343
Parallel Random Access Machines (PRAM), 230, 745
Parallel triangular solution, 956
Parameterization, see Transformation approach
Parasitics, 818
parentElement, 105
parentNode, 106
Partially dynamic graph problem, 581
Partially dynamic problem, 581
Partially persistent data structures, 511
Partial pivoting, 959
Partial rebuilding technique, 155, 160, 161
Partial sums, 606
Particle-based methods, 323
Partitional clustering, 1007–1008
Partition-Based Spatial Merge (QPBSM), 423
Partition Based Spatial-Merge Join (PBSM), 880
Partitioned Bloom filter, 145
Partitioning, 984
edges, 574
process, 445
scheme, 819
tree representation of intra-object spatial relations, 330
Partition maintenance algorithms, 540–542
Partition trees, 387, 402–403, 426
data structure, 535
Path, 152
caching, 433
path-balancing, 157
problems, 584
PA-tree, 368
Patricia, see Practical Algorithm To Retrieve Information Coded In Alphanumeric
pattern matching using suffix arrays, 469–470
pattern matching using suffix trees, 469
p-biased coin, 202
PBSM, see Partition Based Spatial-Merge Join
PD, see Penetration depth
PDM, see Parallel disk model
Peano–Hilbert order, 255
Peano–Hilbert space-filling curve, 429
Peer to peer search problem (P2P search problem), 811
Penetration depth (PD), 897
computation, 896
incremental penetration depth computation, 897–898
non-convex models, 898
Perfect elimination ordering, 954
Perfect hash function, 118, 127
Performance analysis of 3D R-Trees, 367
Performance metrics, 133, 785, 987–988
Performance optimizations, 990
fractional cascading, 990, 991
“Insert 23” operation, 992
Persistence-based approach, 1050; see also Sparsification-based approach; Transformation-based approach
generalized semidynamic quadrant searching, 1050–1051
generalized semidynamic 2D range searching, 1051
generalized 3D range searching, 1052
Persistence, 987
performance optimizations, 990–992
Persistent data structures, 361, 511, 639; see also Kinetic data structures (KDS); Layout data structures; Online dictionary structures; Spatial data structures
algorithmic applications, 513–516
fat node method, 516
general techniques for making, 516
handling arrays, 518
making data structures confluently persistent, 518–522
making specific data structures more efficient, 522
node copying, 517
redundant binary counters, 524
representation of deque of elements, 523
Persistent search tree, 1029
Persistent trees, 1029
Phong model, 861
Physical address, 978
Physically-based modeling, 889
Physical Plan Generator, 969
Physical pointers, 978
Physical query plans, 969
Physical trajectory, 874
ping, see PNG
Pivot, 97
element, 558
two dimensional array of, 320
PJM, see Pairwise join method
Placeholders, 681
Placement based representations, 833, 844
Planar drawings, 723
Planarity, 725
Planarization algorithm, 603
Planar point location, 554
problem, 1027
Planar st-graphs, 427, 733–734
Planar straight line graphs (PSLGs), 277, 1027
edge deletion, 279
edge insertion, 279
halfedge data structure, 281–287
operations on, 279
quadedge data structure, 287–288
vertex split and edge contraction, 279–280
winged-edge data structure, 280–281
Planar subdivision, 1028
Plane-sweep algorithm, 881, 1021
Plowing, 820
pmf, see Probability mass function
PM quadtree family, 267
Point-in-polygon query, 872
Point-swept sphere (PSS), 893
Pointed pseudo-triangulations, see Minimum pseudo-triangulations
Pointed pseudotriangulations, 1024
based data structure, 517
element, 454
machine model, 530
triple, 449
types, 391
Point Finding operation, 820–821, 825
Point location, 401, 421, 429, 786, 1027, 1028
fractional cascading, 1029–1030
Kirkpatrick’s algorithm, 1028–1029
nearest neighbor searching through, 1036
persistent trees, 1029
sequence of triangulations, 1028
slab-based methods, 1029
slab refinement of subdivision, 1029
trapezoidal maps and history graph, 1031–1032
worst-and expected-case optimal, 1032
Point quadtree, 253, 254, 310–311
Point queries, 316–317, 354, 987
Point region quadtree (PR-quadtree), 253, 254, 255–256, 312
Point search tree (PTST), 777
Polycrystalline silicon, 818
Polygon(al), 330, 343, 350, 872, 1023
data sets, 352
line, 871
maps, 267
mesh, 858
polygon-area approaches, 338
soups, 892
subdivision, 1028
Polyhedral, 330
Polyhedral regions, 891
Polyhedron, 891
Polyline, 265
Polynomial time algorithms, 345, 936
Polytopes, 330
data structure, 891
representation, 891
Positional B+-trees, 978
Positional containers, 681, 684
sequences, 685
trees, 686
of aabcabcaa, 479
building position heap, 489–490
construction, 489
improvements to time bounds, 491–494
for string, 478
time bounds, 491
Post-office problem, 1013, 1020
PostGIS, 883
Postprocessing, 997
Postscript
driver software, 859
font, 859
Potential method, 15
maintenance contract, 16
McWidget company, 18
Power distance, 1022
Power law distribution, 806, 808
PQ, see Priority queues
Practical Algorithm To Retrieve Information Coded In Alphanumeric (Patricia), 456
removing element, 458
searching, 457
PRAM, see Parallel Random Access Machines
Predecessor, 49
pointers, 517
search, 152
Predecessor fields (p), 517
Predictive category, 998
Predictive modeling, 998
Preemption-safe locks, 747
Preferential attachment paradigm, 806, 807, 808, 809
Prefix(es), 523
paths, 1007
prefix-free codes, 216
range, 766
and ranges, 766
relation between general uniquely decipherable codes and prefix-free codes, 218–219
search and applications, 451–452
PreFlow, 190
Preflow-push algorithms, 191–192
Preorder traversal, 40, 262, 316, 710
PrePosition method, 713
Preprocessing time, 513
Presorted items, OAT for, 226
Presorted sequence of items, 218
Prim-Jarník algorithm, 689
Primal heap, 491
Primary attribute, 252
Primary organization, 980
Priori, 294
Priorities, 212
Priority_queue template, 672–673
Priority_Search_Tree_root(S), 304
Priority queues (PQ), 44, 69, 77, 98, 304, 407, 554, 634, 687, 756
combining techniques, 635
exponential level based, 557–560
further techniques and faster randomized algorithms, 635–636
heap-based priority queues, 756
merge based, 554
range reduction, 634
tree-based priority pools, 757
Priority R-tree, 431
Priority search trees (PSTs), 263, 291, 304–306, 432, 775–777, 1037, 1046
example and applications, 305–306
PR k-d tree, 254
Probabilistic priority queues, 212
Probability density function, see Probability mass function (pmf)
Probability distribution, 199
Probability mass function (pmf), 201
Probability theory, 199
Procedure Interval_Insertion function, 295–296
Process function, 319
Process visualization and debugging environment system (PROVIDE system), 704
Product-form inverse, 956
Programming languages, 23
Program visualization, 697
Projection point, 857
Projects enabled by LEDA, 665
PROVIDE system, see Process visualization and debugging environment system
Delaunay triangulation, 1033–1034
geometric graphs on point set, 1035
geometric proximity structures, 1034–1035
graphs for enhancing nearest neighbor classifiers, 1001–1002
queries, 343
set, 323
“Proxy TID”, 979
PR-quadtree, see Point region quadtree
Pseudo-algebraic motions, 380
Pseudograph, see General graph
Pseudotriangulation, 383, 385, 1024–1025
of convex hull of point set, 382–383
mixed, 383
pointed pseudotriangulations, 1024
pseudotriangulation-based methods, 384
PSLGs, see Planar straight line graphs
PSS, see Point-swept sphere
PSTs, see Priority search trees
PTST, see Point search tree
Public-domain libraries, 892
Pure Heap Model, 94
Pure silicon, 817
Push-up node, 240
Q
QGIS, 883
QLQT, see Quad List Quad Trees
QMAT, see Quadtree medial axis transform
QoS routers, 765
QPBSM, see Partition-based spatial merge
q tokens, 802
Quad-edge data structure, 287–288, 1021
Quad List Quad Trees (QLQT), 828
Quadrangle inequality, 230
Quadrants, 267–268, 309, 320–321, 361, 790, 791, 905, 907
Quadratic Bezier curve, 866
Quadratic probing, 124
Quadtree-based approach, 259, 264, 360
Quadtree Complexity Theorem, 262, 268
Quadtree medial axis transform (QMAT), 260
Quadtrees, 252, 256, 260, 309, 312, 361, 819, 883, 903, 905, 906, 910–911
basic operations, 316
cell deletion, 317
cell insertion, 317
cell orderings and space-filling curves, 314–315
compressed quadtrees and octrees, 313–314
construction of compressed quadtrees, 315–316
with coordinates, 909
image processing applications, 320–322
insertions and deletions, 317
point and cell queries, 316–317
for point data, 310
practical considerations, 317–318
representation of image, 912
scientific computing applications, 322–325
spatial queries with region quadtrees, 318–320
BLQT, 826
HV Trees, 829
k-d trees, 826
QLQT, 828
Queries, 560–561, 562–563, 593, 967
curve pieces for query range, 877–878
data structures for query processing, 968
operators, 884
optimization, 969
optimizer component, 967
performance, 360
re-writing, 968
sorting large data sets, 970–971
“Query-reply” loop, 698
Querying position heap, 490–491
Query Translation and Rewrite module, 968
Queue(s), 31, 192, 522, 672, 751–752
Queuelocks, 747
Quiescent consistency condition, 746
Quotient graphs, 945, 953, 957–958
clique covers, 957
covering column-intersection graph and biclique covers, 958–959
problem of degree updates, 958
R
Rabin’s fingerprints, 801, 802
Radix priority-search tree (RPST), 775
Radix searching, 253
RAM, see Random Access Machine model of computation
Random-access iterators, 674
Random access, 649
Random Access Machine model of computation (RAM), 172, 530, 536, 545, 546, 561, 627
Random hash functions, 137
maintaining spanning forests, 583
random sampling, 583
Randomized algorithms, 198–199, 531
Randomized binary search tree (RBST), 171, 197, 209–210, 212
Randomized data-structure
for decremental APASP, 618–624
Randomized dictionary structures; see also Online dictionary structures
analysis of dictionary operations, 207–209
Bernoulli distribution, 202
binomial distribution, 202
conditional probability, 200–201
Dictionary ADT, 198
dictionary operations, 207
geometric distribution, 202
negative binomial distribution, 202–203
preliminaries, 198
probability theory, 199
randomized algorithms, 198–199
structural properties of skip lists, 205–206
Randomized finger search trees, 173
Randomized graph data-structures; see also Cache-oblivious data structures
(2k–1)-approximate distance oracle, 613–615
3-approximate distance oracle, 612–613
bounding size of
computing approximate distance oracles, 616–618
hierarchical distance maintaining data-structure, 619–621
improved decremental algorithm, 622–624
notations, 619
preliminaries, 613
randomized data-structure for decremental APASP, 618
randomized data-structure for static APASP, 611
Randomized incremental construction, 1021–1022, 1031
Randomized search tree, 533
Randomized set representations
remarks on unique representations, 533
simple, 530
Random probing, 122
assumption, 122
asymmetric hashing, 125
Brent’s method, 124
Cuckoo hashing, 126
double hashing, 124
hashing with chaining, 122
hashing with open addressing, 123
multiple-choice hashing, 125
quadratic probing, 124
Robin-Hood hashing, 126
Range allocation rule, 777
Range query, 240, 241, 310, 318–319, 367, 425, 434, 547–548, 551, 872
analytical models for, 353
for SFC data structures, 876
Range restrictions, adding, 1053–1054
Range search(ing), 402, 428, 429, 434
bootstrapping for 2-D diagonal corner and stabbing queries, 431–432
bootstrapping for three-sided orthogonal 2-D range search, 432–433
general orthogonal 2-D range search, 433–434
linear-space spatial structures, 429
lower bounds for orthogonal range search, 434
problem, 298
structures, 387
tools, 387
Range search-tree (RST), 778
Range trees, 291, 298, 387, 560
example and applications, 301–304
Rank search, 153
Rank/Select queries, 931
Raster, 904
graphics, 904
Rat-kernel, 656
“Rate equation” approach, 806
Ray shooting, 786
RBPST, see Red-black priority-search tree
RBST, see Randomized binary search tree
RCS data structure, see Rectangular corner stitching data structure
RDBMS, see Relational database management systems
Reachability trees, 567, 578–579, 584
Read/write efficiency, 145–146
Real-life classifier, 785, 795
Rebalancing
binary search tree, 159
operations, 180
technique, 155
tree to perfect balance, 158
Record organizations, 976; see also File organization; Page organizations
alternative organizations of records with fields of variable length, 977
organization of records with fields of fixed length, 976
positional B+-trees, 978
Rectangle-swept sphere (RSS), 893
enclosure, 786
intersection graph, 291fn
Rectangular corner stitching data structure (RCS data structure), 823, 824
Rectilinear polygons, 825
Rectilinear shape handling, 851–853
Recurrence equations, 12
table-lookup method, 13
Recursive algorithm, 40, 42, 222, 1037
Recursive decomposition of space, 309
Recursive flow classification (RFC), 793, 794
Recursive halving process, 253
Recursively defined SFCs, 875
method, 162
Red-black priority-search tree (RBPST), 775
RedBlackTree, 688
Red, green, and blue (RGB), 904
Reduced ordered BDD (ROBDD), 497, 498
Redundant binary counters, 524
Redundant binary representation, 524
Redundant counters, 522
Reference(s), 23
counter, 499
element, 454
Reflectional symmetry, 728
Regional images, 361
Regional quadtrees, 361
Region quadtrees, 260, 266, 311–313, 322, 905–906
k-nearest neighbors, 320
spatial queries with, 318
spherical region queries, 319–320
Region Search operation, 827
Regression techniques, 998, 1000
Regular decomposition, 253, 261, 264, 266
Regulatory elements, 918
Reingold-Tilford algorithm, 710, 711
Relational database management systems (RDBMS), 967, 983
Relative Neighborhood Graph (RNG), 1023, 1034
Relaxed balance, 164
AVL-trees, 166
other results, 167
update operations, 165
Relaxed depth, 167
Relaxed height of node, 166
Relaxed multi-way trees, 167
Relaxed supernode partitions, 950
Reliability, 680
Removing element, 449–451, 458
Removing min element
Repairable certification, 380
Replication consistency, 985
Reporting distance with stretch at-most (2k–1), 614–615
Reporting problems, general approach for, 1052–1053
Representative vertex, 954
Resemblance, 802
Residual capacity, 190
Residual graph, 190
Resistance, 818
Resizable arrays, 607
Restricted Dijkstra’s algorithm, 617, 618
Restricted multilevel partition, 572, 573
Restricted partition, 571
Restructuring primitive, 154
Reverse-nearest-neighbor query, 367
Reverse iterators, 676
Reverse transformation, 1055–1056
REXP-tree, 373
RFC, see Recursive flow classification
RGB, see Red, green, and blue
RGB color value, 904
Right-deep tree, 973
Right-looking algorithm, 952, 953
Rightist orders, 426
Right tree, 195
Rigid circuit graphs, 954
RNG, see Relative Neighborhood Graph
ROBDD, see Reduced ordered BDD
Robust algorithms, 953
Room synchronization, 748
cell, 312
level of min-max heap, 105
Root*table, 362
Rotational symmetry, displaying, 729–730
Rotation(s), 154, 187–188, 204, 321, 389, 395, 426
Routers, 165
Row-counts algorithm, 952
Row-prime order method, 255
Row indices, 950
Row nonzero counts prediction, 951–952
Row order method, 255
RPST, see Radix priority-search tree
RSS, see Rectangle-swept sphere
RST, see Range search-tree
R-tree(s), 233, 252, 256, 266, 343, 360, 429–431, 880, 881, 883, 884, 910–911, 970, 1037
R-trees*, 343, 346; see also Binary space partitioning trees (BSP trees)
bulk loading, 349
improving performance, 346
R* tree, 346
Rule-based decision-making, 914
Run-generation phase, 971
S
Sarnak and Tarjan’s tree, 1029
Saturating push, 191
Save-points, 976
SBB-trees, see Symmetric Binary B-trees
SB-tree, 425
Scalability, 136, 742, 749, 785, 999
Scalable sweeping-based spatial join (SSSJ), 423
Scene, geometric, 658
Scheduling out-of-core factorizations, 953
Scheduling parallel factorizations, 952–953
Schönhardt’s polyhedron, 1024
Scientific computing applications, 322–325
physical system behavior, 322–323
Scuttlebutt gossip-style protocol, 986
SDD, see Sentential Decision Diagram
Searchable partial sums problem, 606
Search(ing), 457, 547, 553, 676, 677
BSTs, 42
graph, 54
for highest-priority matching range, 779
index, 365
problem, 291
procedures, 153
trie, 446
Secondary clustering phenomenon, 124
Secondary organization, 980, 981
Seeded tree creation algorithm, 352, 353
Seed levels, 352
Segments, 974
segment-oriented recovery, 976
Segment tree(s), 263, 291, 294, 422, 791
example and applications, 296–298
Select-from-where (SFW), 972
Select functions, 319
sort, 25
Self-adjusting binary search trees, 172, 571
Self-tunable spatiotemporal B+-tree (SP2 B-tree), 360
“Semi-splaying” tree, 195
Sentential Decision Diagram (SDD), 507
Separability assumption, 540
Separator decomposition tree, 603
Sequence pair (SP), 833, 835, 844, 845–847, 851
sorting algorithms, 688
Sequential bottleneck, 742
Sequential consistency, 746
Sequential greedy algorithm for Huffman coding, 230
Sequential pattern analysis, 999
Serializability, 746
Set abstract data type (Set ADT), 117, 119, 122, 127
SETI, spatial partition method, 360, 368
ADT, 117
data structures for, 529
disjoint set union-find problem, 538–540
extremal sets and subset testing, 535–538
models of computation, 530
operations, 175
of operators, 363
partition maintenance algorithms, 540–542
set-theoretic operations, 259
simple randomized set representations, 530–533
system, 398
SFCs, see Space filling curves
SFW, see Select-from-where
Shading model, 861
Shadow bits, 976
Shadow paging concept, 976
Shannon expansion, 496
Shared-memory multiprocessor machines, 741, 751
Shared counters, 749
combining, 749
counting networks, 750
data structure, 742
Shared mode, 754
Shifting smaller subtrees, 715–718
Shingling technique, 802
Shortcut representation, 604
Shortest elimination trees, 955
Shortest paths, 62, 585, 589, 659–661
all-pairs shortest path, 64–65
single-source shortest paths, arbitrary weights, 63–64
single-source shortest paths, nonnegative weights, 62–63
Shrinking node, 1038
Siblings, 708
Sides, 256, 263, 268, 1024, 1045
Signature, 938
signature-based canonization, 938
sort, 635
Similarity, 208
detection mechanisms, 802
Jaccard coefficient, 802
bitbound algorithm, 940
combining hashing and trees, 943
fingerprint compression, 940
hashing approaches for improved searches, 940–941
inverted indices, 942
LINGO, 942
multibit and union tree, 943
triangle inequality and improvements, 941
trie-based approaches for storing fingerprints, 943
Similar property principle, 935
Simple computer model, 7
Simple graph, 49
Simple path, 65
Simple searching, 152
Simple splay trees, 195
Simple updates, 152
Simplicial partition, 402
Simulators, 817
Singlebit tree, 943
Single-ended priority queues, 69, 98
Single-level index, 980
Single-shot problems, 1045
Single Source LWS problem, 230
Single-source shortest paths
Single tree representations, 842–844
Sizes of subtrees, 154
Size-tiered LSM-tree, 989
Sketch subset, 802
Skewed tree, 39
Skew heaps, 69, 78, 644; see also Binomial heaps; Fibonacci heaps; Pairing heaps
executing pending merge, 648
meldable priority queues and, 80–83
merging two, 645
skew heaps with lazy evaluation in Java, 647
unbalanced, 646
Skew operation, 158
Skip fields, compressed tries with, 454
Skip lists, 173, 174–175, 198, 204–205, 206, 533
space complexity, 206
structural properties, 205
Skip value, 455
Slabs, 349, 422, 431, 433, 1029
slab-based methods, 1029
x-range, 562
Slicing
structure, 849
Slot index spatial join, 353
“Small motions”, 385
SMAWK algorithm, 228
SMMH, see Symmetric min-max heap
Smoothed particle hydrodynamics, 323
Soap2 alignment tool, 927
Social security number, 445, 447
Software environment, 698
Software transactional memory, 749
Software visualization, 697, 698
Solid state drives (SSDs), 987
Solid tiles, 819
Sort-tile-recursive (STR), 349
Sorted array merge tree, see Size-tiered LSM-tree
Sorted files, 980
Sorted String Table (SSTable), 988
“Sort heap”, 94
algorithms, 634
arrangement of buffer pages and disk blocks, 971
combining techniques, 635
further techniques and faster randomized algorithms, 635–636
large data sets, 970
by mindist, 351
by minmaxdist, 351
networks 634
policy, 351
range reduction, 634
Sort–merge paradigm, 884
SP, see Sequence pair
SP2 B-tree, see Self-tunable spatiotemporal B+-tree
Space bounds, 435, 512, 556, 602, 603, 1048
Space decomposition process, 256, 259
Space-driven
methods, 428
partitioning of methods, 429
Space efficiency, 145, 234, 909
Space efficient computation of MEMs for two genomes, 926
Space filling curves (SFCs), 314–315, 347, 429, 874, 884
corner cell traversals, 879
curve pieces for query range, 877–878
orderings, 315
range queries for SFC data structures, 876
recursively defined, 875
Space issues, 468
Space-ordering methods, 255
Space partitioning, binary tree representation of, 334
Space required by compressed trie, 456
Space required structures, 447–449
Spanned organization, 977
Spanning
forest, 54, 578, 583, 584, 588
Sparse
case, 120
direct solvers, 952
environments, 899
matrices, 27
matrix factorizations, 948
multislab lists, 432
segment, 598
symmetric factorization, 959
Sparsification-based approach, 1048; see also Persistence-based approach; Transformation-based approach
generalized half-space range searching, 1049–1050
Spatial 2D R-tree, 365
mining, 263
models, 882
operations, 343
sets, 351
Spatial database systems, 883
Spatial data structures, 309, 425, 428; see also Kinetic data structures (KDS)
bootstrapping for 2-D diagonal corner and stabbing queries, 431–432
bootstrapping for three-sided orthogonal 2-D range search, 432–433
general orthogonal 2-D range search, 433–434
linear-space spatial structures, 429
lower bounds for orthogonal range search, 434
Spatial join(s), 343, 351–353, 365, 872, 879, 882
Spatial libraries, 883
JTS, GeoTools, and GEOS, 883–884
LEDA and CGAL, 884
XXL, 884
Spatial partitioning hierarchies, 892
Spatial partition methods, 360
Spatial queries
with region quadtrees, 318–320
Spatial searching, 872
Spatial search structures, 331
Spatial sorting, 329
Spatial–temporal queries, 364
Spatio-temporal data, 343, 359, 874
HR-trees, 368
indexing structures for continuously moving objects, 370–373
overlapping linear quadtree, 360–363
spatiotemporal indexing techniques, 360
3D R-tree, 363
2+3 R-tree, 368
Spatiotemporal databases (STB), 359
Spatiotemporal data structures (STDS), 359
Spatiotemporal indexing techniques, 360
Spatiotemporal joins, 370
Spatiotemporal operators, 363
Spatiotemporal query types, 367
Spatio-temporal self-adjusting R-tree (STAR-tree), 373
Specialized data structures, 359
Speedup of application, 742
Sphere-trees, 893
Spherical region query, 309, 310, 319–320
Spherical shell-trees, 893
Spinlocks technique, 747
Spiral storage, 127
Splay
analysis in virtual tree, 188–189
sequence of rotations, 180
Splay trees, 78, 155, 158, 172, 179, 180–181; see also B-tree
access and update operations, 182–183
analysis, 181
application to network flows, 190–192
FIFO dynamic tree implementation, 193–194
implementation without linking and cutting trees, 192–193
linking and cutting trees, 185–189
variants and top-down splaying, 195
Splice effects, 289
Split
cases, 285
operation, 153, 158, 183, 395, 410, 576
policy, 346
split-find problem, 540
Splitting, 389
nodes, 1038
rule, 1036
threshold, 267
SQLite, 883
SSDs, see Solid state drives
SSSJ, see Scalable sweeping-based spatial join
SSTable, see Sorted String Table
SSV, see Swept sphere volume
SSV-trees, 893
Stabbing queries, 421, 426, 431–432
Stability, 583
Stacks, 31–32, 522, 640–642, 672, 751
Standardized data models, 882
Standard range, 294, 295, 301, 1055
Standard template library (STL), 667, 679
additional components, 676
sorting, searching, and selection, 676–677
Star-shaped drawings, 738
STAR-tree, see Spatio-temporal self-adjusting R-tree
Star-triangulation, 729
Static APASP
(2k–1)-approximate distance oracle, 613–615
3-approximate distance oracle, 612–613
computing approximate distance oracles, 616–618
preliminaries, 613
randomized data-structure for, 611
Static array, 24
Static counting problem, 1047
Static data structure, 291, 633
Static finger theorem, 184
Static hash file, 980
Static optimality, 184
Static perfect hashing, 119–120
Static pivoting, 960
Static point interval query, 373
Static R-tree, 884
Static search tree, 546
Static structure, 433
Static type-2 problem, 1048
Statistical analysis of words, 918–919
Status function, 319
STB, see Spatiotemporal databases
STDS, see Spatiotemporal data structures
Steiner points, 382, 383, 1024
analysis, 10
method, 5
Stepped merge method, see Size-tiered LSM-tree
Steps per execution (s/e), 6
STL, see Standard template library
Storage, 348
subsystem, 968
systems, 419
utilization, 360
Stout-Warren algorithm, 158
STR-tree, 360
STR, see Sort-tile-recursive
Stride of node, 770
containment, 471
data type, 699
“String art” algorithm, 866
String searching, 477
preliminaries, 479
Strip-emptiness queries, 1016–1017
Strip tree data structure, 266
Structural operations, 279
Structural theorem, 225
Sub additivity, 199
Subcell, 312, 314, 317, 320, 1016, 1036
Sub-circuits, 833
Subgraph of graph, 53
Sub-hyperplanes, 337
Sub-logarithmic time per element by simple means, 628
combining, 630
Sub-quadratic space, 612
Subset enumerator, 18
Subset generation, 18
accounting method, 19
aggregate method, 19
worst-case method, 19
Subset testing
dynamic set intersections and, 537–538
extremal sets and, 535
Subtrees, 35, 72, 90, 93, 151, 154, 156, 163, 223, 301, 319, 344–345, 501, 547, 561, 571, 605, 688, 708, 711, 713, 715, 777, 926, 1055
Successor
search, 152
vertex, 49
Succinct dictionaries, 597
FID, 598
Succinct representation of data structures
arrays, 607
graph representations, 603
partial sums, 606
permutations and functions, 604–606
succinct dictionaries, 597–599
succinct structures for indexing, 603–604
Succinct structures for indexing, 603–604
Suffix array(s), 461, 462, 463, 467, 603
advanced applications, 473
applications, 468
approximate pattern matching, 473–474
construction algorithms, 463
Käräkkanen and Sanders’ algorithm, 467–468
linear time construction algorithms, 463–468
longest common substrings, 470–471
lowest common ancestors, 472
maximal palindromes, 474
string containment, 471
suffix-prefix overlaps, 471–472
suffix links from lowest common ancestors, 473
text compression, 471
Suffix tree(s), 461, 462, 463, 467, 603, 924
advanced applications, 473
applications, 468
approximate pattern matching, 473–474
construction algorithms, 463, 464
generalized, 466
linear time construction algorithms, 463–468
longest common substrings, 470–471
lowest common ancestors, 472
maximal palindromes, 474
McCreight’s algorithm, 465–466, 470
string containment, 471
suffix-prefix overlaps, 471–472
suffix arraysvs., 464
suffix links from lowest common ancestors, 473
text compression, 471
Super-element model, 957
Support count of itemset, 1003
SWAN system, 704
Swapping pointers, 160
distribution, 422
phases, 748
plane sweeping algorithm, 516
Sweep-line algorithm, 352, 423, 879, 880, 1021
Swept sphere volume (SSV), 893
SWIM, failure-detection protocols, 986
Symbolic Cholesky factor, 950
Symbolic elimination, see Symbolic factorization
Symbolic factorization, 950–951, 957
Symbolic perturbation, 654
Symmetric Binary B-trees (SBB-trees), 157
Symmetric drawing, 728; see also Convex drawing; Visibility drawing
displaying axial symmetry, 730–732
displaying dihedral symmetry, 732
displaying rotational symmetry, 729–730
Symmetric matrix, 893, 946, 950
Symmetric min-max heap (SMMH), 98–100
Symmetric pruning, 961
Synchronous traversal method, 353
“Syntactic” duplicates, 801, 802
T
Table-lookup method, 13
Tag value, 166
“Tailor” layout system, 823
Tall cache assumption, 546, 556
Tanimoto distance, 941
Tanimoto similarity, 939–940, 943
Target function, 1000
t-ary trees, Huffman algorithm for, 220
TB-tree, 360
TBT, see Twin binary tree
TCAMs, see Ternary content-addressable memories
TCG, see Transitive closure graph
Template method pattern, 683, 684, 689, 692
Template sets, 907
Temporal 1D R-tree, 365
Temporal index, 365
Terminal nodes, 496
Ternary content-addressable memories (TCAMs), 767, 795–796
Tetrahedralizations, 1023
“Texels”, 862
Text, 477
compression, 471
index, 603
Theoretical growth models, 806–809
Theta notation (Θ), 11
Threaded binary trees
threads, 41
3-approximate distance oracle, 612–613
3D Geometry Library (libP), 655
cache-oblivious kd-tree, 560–561
cache-oblivious range tree, 561–563
Three-dimensional lines, 368
3-D polygonal meshes, 861
layout, 562
structure, 562
Three-sided range search(ing), 433
Three dimensional graph drawing, 737
3D R-tree, 363
handling queries with open transaction times, 367–368
performance analysis, 367
spatiotemporal queries using unified schema, 365–367
TID, see Translation invariant data structure
TID concept, see Tuple identifier concept
Tiered vector, 607
curved, 823
deletion, 820
trapezoidal, 823
Time bounds, 94, 491, 568, 582, 606, 1056
of finger search trees, 176
logarithmic, 523
run–time bounds, 468
for updates and queries, 515
Time complexity, 3, 9, 54, 204, 224, 391, 541, 776, 836, 847, 949
Time-forward processing, 427
Time-Parameterized R*-tree (TPR*-tree), 371–373
Timeslice query, 371
Timestamp query, 368
TMS, see Truth Maintenance System
Tombstones, 988
Top-down
hierarchical methodology, 834
methods, 893
splaying, 195
traversal of suffix tree, 470
Topological
approach, 935
data, 872
Topological number(ing), 689, 734, 735, 736
construction, 572
update, 573
Toponym recognition, 269
Toponym resolution, 269
representation and applications, 576–577
Tournament trees, 46
loser trees, 48
winner trees, 47
TPIE system, see Transparent parallel I/O environment system
TPR*-tree, see Time-Parameterized R*-tree
Traditional indexing
schemas, 371
techniques, 360
Traditional metrics, 987
Traditional spatial data structures, 359
Traditional spatial indexes, 360
Trajectory indexing techniques, 359
Transaction-oriented recovery, 976
Transactional memory mechanism, 749
Transactional synchronization mechanisms, 748
Transaction management subsystem, 968
Transaction time, 359, 360, 367–368
Transformation-based approach, 1046
dynamic counting problem, 1047–1048
dynamic reporting problem, 1046–1047
static counting problem, 1047
static type-2 problem, 1048
Transformed data structure, 1054
Transition function, 745
Transitive closure, 589
updates in O(n2) time, 591
updates in O(n2 log n) time, 590
Transitive closure graph (TCG), 841
Transitively closed subgraphs, 956
Transitive reduction, 479, 961
Translational C-space obstacle (TCSO), see Minkowski sum
Translation invariant data structure (TID), 903, 912–914
Translation table, 978
Transparent parallel I/O environment system (TPIE system), 423
Trapezoidal decomposition, see Trapezoidal map; Vertical decompositions
Trapezoidal tiles, 823
Trashing, 391
Tree-depth, 462
TreeLayout algorithm, 711
TreeNode class, 39
Trees, 35, 49, 53, 151–152, 686; see also Leftist trees
color problem, 514
compaction, 988
height limited Huffman trees, 220–222
left child-right sibling representation, 37
membership, 579
with minimum weighted path length, 215
nodes, 601
optimal lopsided trees, 226–229
rebalancing algorithm, 163
references primitives, 869
tree-based data structures, 425
tree-based priority pools, 757
tree-push procedure, 193
type data structure, 825
Treewise merging process, 175
Triangle mesh, 858
Triangulations, 277, 288, 382–383, 839, 1022
of point set, simple polygon, and polyhedron, 1024
polygons, 1023
pseudo-triangulations, 1024–1025
Trickle-down process, 107, 108
Triconnected planar graph, 728
Tridiagonal matrix, 27
height of trie, 447
inserting into, 449
keys with different length, 446–447
prefix search and applications, 451–452
representation, 449
searching, 446
space required and alternative node structures, 447–449
trie-array implementation, 391
trie-based approaches for storing fingerprints, 943
trie-bst approach, 396
Trivial labeling, 190
Trivial rebalancing scheme, 153
True color, 859
Truth Maintenance System (TMS), 507
Tuple identifier concept (TID concept), 979
Tuple space search, 795
TV-tree, 1037
Twin binary tree (TBT), 833, 834, 841–842, 849, 851
Twin heap, 111
Twin slot method, 975
2-3-4 tree, 234
Two-cuttable theorem, 415
Two-dimension (2D), 8
approaches, 935
bootstrapping for 2-D diagonal corner,, 431–432
classification scheme, 790, 791
classifier, 786
compaction, 819
data set, 353
data types, 884
homothetic range search, 435
orthogonal range queries, 428
points, 368
2D-range search problem, 302–304
2D Geometry Library (libP), 655
2D orthogonal range searching, 560
2-edge connectivity, 574
Two-handed emulation technique, 754
Two-level hash function, 597
Two-pass pairing, 93
Two-step approach, 628
Two dimensional array of pixels, 320
(2k–1)-approximate distance oracle, 613
reporting distance with stretch at-most (2k–1), 614–615
size of (2k–1)-approximate distance oracle, 615
Type-2 counting problem, 1044
(t, ε) -AVD decomposition, 1038, 1039
U
UML, see Unified modelling language
Unary encoding, 800
Uncertain points, 1050
Uncompressed region quadtrees, 317
Undirected graph(s), 50, 51, 53, 581
clustering, 582
techniques for, 582
Unified algorithm for group queries, 319
Unified modelling language (UML), 707
Unified schema, spatiotemporal query using, 365–366
Uniform distribution, 199, 338, 973, 1034
Uniform grid, 252, 253, 259, 260
Uniform hashing assumption, 122fn
Union
of images, 321
UnionBit Tree, 943
Union-copy problem, 540
Union tree, 943
Unique representation
property, 531
remarks on, 533
UnitWeightedTopologicalNumbering, 689
Universal hashing, 119
Unmatched clusters, 572
Unordered BDD, 496
Unordered dictionaries, 151
Unreliability, 679
Unrooted tree, 35
Unspanned organization, 977
Unusual words, 917
statistical analysis of words, 918–919
subtrees rooted at solid gray nodes, 921
on graph, 581
in O(log4n) time, 589
in O(n2.5 √Clog n) time, 592
tradeoffs, 593
Upper bound theorem, 1014
Upper convex hull, 663
Upper envelope, 380, 381, 1014, 1049
Upper triangular matrix, 27, 945
Upstream sequence, 918
Upward star-shaped polytopes, 738
User-defined displays, 704
V
Vacant tiles, 819, 822, 823, 824
Valence of atom, 936
Valid labeling, 190
Valid time, 359
Value of flow, 190
van derWaal forces, 323
Van Emde Boaz layout, 546, 547, 560, 561
search, 547
Vapnik and Chervonenkis dimension (VC-dimension), 398, 399
Variable-Increment Counting Bloom Filter (VI-CBF), 146
Variable-length record, 968, 977
Variable-stride trie (VST), 772–774
Variable length (VL), 361, 977
encoding scheme, 800
records, 979
strings, 118
Variable length signatures (VBF), 146
Variable ordering for BDDs, 502–503
line quadtrees, 906
of quadtrees, 905
of splay trees, 195
template quadtrees, 907
Variety, 983
VBF, see Variable length signatures
VC-dimension, see Vapnik and Chervonenkis dimension
Verification techniques, 746
elimination process, 957
hub pair, 897
resolution, 723
Vertex, normal, and face lists, 863
Vertical combination, 719
Vertical decompositions, 1016
Vertical inversions of polygon, 825
Vertical ray shooting, 1028
Vertical slabs, 422, 432, 513, 1029
Vertices, 862
Very Large Scale Integration (VLSI), 817–819
combinations and complexities of representations, 834–835
design process, 507
design stages, 818
example of extra constraints, 854
floorplan representation in, 833
graph based representations, 837–844
logic design, 495
motivation of representation, 834
placement based representations, 844–850
rectilinear shape handling, 851–853
relationships of representations, 851
slicing, mosaic, LB compact, and general floorplans, 835–837, 838
statement of floorplanning problem, 833–834
VI-CBF, see Variable-Increment Counting Bloom Filter
Violations of CV property, 822
Virtual environments, 889
Virtual hashing, 127
Virtual trees, 186
splay in, 188
representation, 732
Visibility drawing, 732; see also Convex drawing; Symmetric drawing
bar visibility algorithm, 734–735
bar visibility representations and layered drawings, 735–736
bar visibility representations for orthogonal drawings, 736–737
Visibility orderings, 332
binary tree representation of space partitioning, 334
intra-object visibility, 333
ordering of polygons, 334
total ordering of collection of objects, 332–333
as tree traversal, 333
visibility ordering as tree traversal, 333
Visualization, 657
GeoWin, 358
systems, 700
VL, see Variable length
VLSI, see Very Large Scale Integration
Voronoi-based marching algorithm, 890
implementation and application, 892
polytope representation, 891
Voronoi cell, 891, 1020, 1032, 1033
Voronoi diagrams, 277, 288, 385, 402, 1002, 1013, 1020, 1021, 1032–1033
complexity, 1021
variations, 1022
Voronoi edges, 1021
Voronoi regions, 890, 891, 1002
VST, see Variable-stride trie
W
Wait-freedom, 744
Wait-free operation, 744
Walkthroughs, 889
Warm-up filter, 146
Warshall-Floyd algorithm, 64
Wavelet trees, fast rank and select operations using, 929–931
WBA, see Worst-case bounding-box area ratio
WBLTs, see Weight-biased leftist trees
WBP, see Worst-case bounding-box squared perimeter ratio
Weak version condition, 369
Web algorithmics, properties of, 809
average path length, 810
crawling and trawling, 813–814
emergence of giant components, 811
generating function framework, 809–810
Web as dynamic graph
experimental observations, 806
properties of web graphs and web algorithmics, 809–814
theoretical growth models, 806–809
web model building techniques, 805–806
Web graph(s), 806
average path length, 810
crawling and trawling, 813–814
emergence of giant components, 811
generating function framework, 809–810
Web information retrieval
data structures in, 799
finding near-duplicate documents, 801–802
fingerprints, 801
Web model building techniques, 805
Web search engines, 799
Wedge cut canonical set, 416
Weight
function, 230
matrix, 51
Weight-balanced B-trees, 426, 429, 431, 435
Weight-balanced trees, 156–157, 389, 390
Weight-balanced trees, 426
Weight-biased leftist trees (WBLTs), 74
maxWBLT operations, 75
connected weighted graph for MST algorithm, 60
undirected, 611
Weighted path length, 215
Well-separatedness criteria, 323–324
“Where-am-I” queries, 970
Whole genomes comparison, 923
collinear chain of nonoverlapping anchors, 923, 924
computation of multiMEMs, 925–926
space efficient computation of MEMs for two genomes, 926
three genomes represented as horizontal lines, 923
Window data type, 657
Window Library (libW), 655
Window query, see Range query
Winged-edge
Winged-edge data structure, 266
Winner trees, 47
Witness points, 892
WKT, 882
Word count, 659
Word processor, 452
Word RAM
model, 530
“Working-set” theorem, 94, 185
distribution algorithm, 753
NoSQL database, 987
Work sharing, classes of algorithm, 753
Work stealing, classes of algorithm, 753
Worst-and expected-case optimal point location, 1032
Worst-case bounding-box area ratio (WBA), 877
Worst-case bounding-box squared perimeter ratio (WBP), 877
Worst-case efficient exponential search trees, 634
Worst-case method
maintenance contract, 15
McWidget company, 17
subset generation, 19
Worst-case search time, 122
Write amplification, 987, 988, 989, 992
X
x-monotone, 1023
polygon triangulation, 1024
x-nodes, 1031
X-tree, 1037
XXL, see eXtensible and fleXible Library
Y
y-nodes, 1031
Z
ZBDD, see Zero-suppressed BDD (ZDD)
z-buffers, 340
z-curve, 875
ZDD, see Zero-suppressed BDD
0-edge, 496
Zero-suppressed BDD (ZDD), 495, 504–506
0-terminal, 496
Zig step, 180
Ziv-Lempel compression, 471
Zooming, 873
Z-space filling curve, see Morton ordering