book

Advanced Algorithms and Data Structures

by Marcello La Rocca

July 2021

Intermediate to advanced

768 pages

25h 23m

English

Manning Publications

Read now

Unlock full access

forewordprefaceWelcome to Advanced Algorithms and Data Structuresacknowledgmentsabout this bookWho should read this book?How this book is organized: a roadmapAbout the codeliveBook discussion forumabout the authorabout the cover illustration
1.1 Data structures1.1.1 Defining a data structure1.1.2 Describing a data structure1.1.3 Algorithms and data structures: Is there a difference?1.2 Setting goals: Your expectations after reading this book1.3 Packing your knapsack: Data structures meet the real world1.3.1 Abstracting the problem away1.3.2 Looking for solutions1.3.3 Algorithms to the rescue1.3.4 Thinking (literally) outside of the box1.3.5 Happy endingSummary
2.1 Structure of this chapter2.2 The problem: Handling priority2.2.1 Priority in practice: Bug tracking2.3 Solutions at hand: Keeping a sorted list2.3.1 From sorted lists to priority queues2.4 Describing the data structure API: Priority queues2.4.1 Priority queue at work2.4.2 Priority matters: Generalize FIFO2.5 Concrete data structures2.5.1 Comparing performance2.5.2 What’s the right concrete data structure?2.5.3 Heap2.5.4 Priority, min-heap, and max-heap2.5.5 Advanced variant: d-ary heap2.6 How to implement a heap2.6.1 BubbleUp2.6.2 PushDown2.6.3 Insert2.6.4 Top2.6.5 Update2.6.6 Dealing with duplicates2.6.7 Heapify2.6.8 Beyond API methods: Contains2.6.9 Performance recap2.6.10 From pseudo-code to implementation2.7 Use case: Find the k largest elements2.7.1 The right data structure . . .2.7.2 . . . and the right use2.7.3 Coding it up2.8 More use cases2.8.1 Minimum distance in graphs: Dijkstra2.8.2 More graphs: Prim's algorithm2.8.3 Data compression: Huffman codes2.9 Analysis of branching factor252.9.1 Do we need d-ary heaps?2.9.2 Running time2.9.3 Finding the optimal branching factor2.9.4 Branching factor vs memory2.10 Performance analysis: Finding the best branching factor2.10.1 Please welcome profiling2.10.2 Interpreting results2.10.3 The mystery with heapify2.10.4 Choosing the best branching factorSummary
3.1 Problem: Multi-indexing3.1.1 The gist of the solution3.2 Solution: Description and API3.3 Treap3.3.1 Rotations3.3.2 A few design questions3.3.3 Implementing search3.3.4 Insert3.3.5 Delete3.3.6 Top, peek, and update3.3.7 Min, max3.3.8 Performance recap3.4 Applications: Randomized treaps3.4.1 Balanced trees3.4.2 Introducing randomization3.4.3 Applications of Randomized Treaps3.5 Performance analysis and profiling3.5.1 Theory: Expected height3.5.2 Profiling height3.5.3 Profiling running time3.5.4 Profiling memory usage3.5.5 ConclusionsSummary

4.1 The dictionary problem: Keeping track of things4.2 Alternatives to implementing a dictionary4.3 Describing the data structure API: Associative array4.4 Concrete data structures4.4.1 Unsorted array: Fast insertion, slow search4.4.2 Sorted arrays and binary search: Slow insertion, fast(-ish) search4.4.3 Hash table: Constant-time on average, unless you need ordering4.4.4 Binary search tree: Every operation is logarithmic4.4.5 Bloom filter: As fast as hash tables, but saves memory (with a catch)4.5 Under the hood: How do Bloom filters work?4.6 Implementation4.6.1 Using a Bloom filter4.6.2 Reading and writing bits4.6.3 Find where a key is stored4.6.4 Generating hash functions4.6.5 Constructor4.6.6 Checking a key4.6.7 Storing a key4.6.8 Estimating accuracy4.7 Applications4.7.1 Cache4.7.2 Routers4.7.3 Crawler4.7.4 IO fetcher4.7.5 Spell checker4.7.6 Distributed databases and file systems4.8 Why Bloom filters work214.8.1 Why there are no false negatives . . .4.8.2 . . . But there are false positives4.8.3 Bloom filters as randomized algorithms4.9 Performance analysis4.9.1 Running time4.9.2 Constructor4.9.3 Storing an element4.9.4 Looking up an element4.10 Estimating Bloom filter precision254.10.1 Explanation of the false-positive ratio formula4.11 Improved variants4.11.1 Bloomier filter4.11.2 Combining Bloom filters4.11.3 Layered Bloom filter4.11.4 Compressed Bloom filter4.11.5 Scalable Bloom filterSummary
5.1 The distinct subsets problem5.2 Reasoning on solutions5.3 Describing the data structure API: Disjoint set5.4 Naïve solution5.4.1 Implementing naïve solution5.5 Using a tree-like structure5.5.1 From list to trees5.5.2 Implementing the tree version5.6 Heuristics to improve the running time5.6.1 Path compression5.6.2 Implementing balancing and path compression5.7 Applications5.7.1 Graphs: Connected components5.7.2 Graphs:15 Kruskal’s algorithm for minimum spanning tree5.7.3 Clustering5.7.4 UnificationSummary
6.1 Spell-check6.1.1 A prncess, a Damon, and an elf walkz into a bar6.1.2 Compression is the key6.1.3 Description and API6.2 Trie6.2.1 Why is it better again?6.2.2 Search6.2.3 Insert6.2.4 Remove6.2.5 Longest prefix6.2.6 Keys matching a prefix6.2.7 When should we use tries?6.3 Radix tries6.3.1 Nodes and edges6.3.2 Search6.3.3 Insert6.3.4 Remove6.3.5 Longest common prefix6.3.6 Keys starting with a prefix6.4 Applications6.4.1 Spell-checker6.4.2 String similarity6.4.3 String sorting6.4.4 T96.4.5 AutocompleteSummary
7.1 Don’t compute things twice7.2 First attempt: Remembering values7.2.1 Description and API7.2.2 Fresh data, please7.2.3 Handling asynchronous calls7.2.4 Marking cache values as “Loading”7.3 Memory is not enough (literally)7.4 Getting rid of stale data: LRU cache7.4.1 Sometimes you have to double down on problems7.4.2 Temporal ordering7.4.3 Performance7.5 When fresher data is more valuable: LFU7.5.1 So how do we choose?7.5.2 What makes LFU different7.5.3 Performance7.5.4 Problems with LFU7.6 How to use cache is just as important7.7 Introducing synchronization7.7.1 Solving concurrency (in Java)7.7.2 Introducing locks7.7.3 Acquiring a lock7.7.4 Reentrant locks7.7.5 Read locks7.7.6 Other approaches to concurrency7.8 Cache applicationsSummary
8.1 The nearest neighbors search problem8.2 Solutions8.2.1 First attempts8.2.2 Sometimes caching is not the answer8.2.3 Simplifying things to get a hint8.2.4 Carefully choose a data structure8.3 Description and API8.4 Moving to k-dimensional spaces8.4.1 Unidimensional binary search8.4.2 Moving to higher dimensions8.4.3 Modeling 2-D partitions with a data structureSummary
9.1 Right where we left off9.2 Moving to k-D spaces: Cycle through dimensions9.2.1 Constructing the BST9.2.2 Invariants9.2.2 The importance of being balanced9.3 Methods9.3.1 Search9.3.2 Insert9.3.3 Balanced tree9.3.4 Remove9.3.5 Nearest neighbor9.3.6 Region search9.3.7 A recap of all methods9.4 Limits and possible improvementsSummary
10.1 Right where we left off10.1.1 A new (more complex) example10.1.2 Overcoming k-d trees’ flaws10.2 R-tree10.2.1 A step back: Introducing B-trees10.2.2 From B-Tree to R-tree10.2.3 Inserting points in an R-tree10.2.4 Search10.3 Similarity search tree10.3.1 SS-tree search10.3.2 Insert10.3.3 Insertion: Variance, means, and projections10.3.4 Insertion: Split nodes10.3.5 Delete10.4 Similarity Search10.4.1 Nearest neighbor search10.4.2 Region search10.4.3 Approximated similarity search10.5 SS+-tree1810.5.1 Are SS-trees better?10.5.2 Mitigating hyper-sphere limitations10.5.3 Improved split heuristic10.5.4 Reducing overlapSummary
11.1 An application: Find nearest hub11.1.1 Sketching a solution11.1.2 Trouble in paradise11.2 Centralized application11.2.1 Filtering points11.2.2 Complex decisions11.3 Moving to a distributed application11.3.1 Issues handling HTTP communication11.3.2 Keeping the inventory in sync11.3.3 Lessons learned11.4 Other applications11.4.1 Color reduction11.4.2 Particle interaction11.4.3 Multidimensional DB queries optimization11.4.4 ClusteringSummary
12.1 Intro to clustering12.1.1 Types of learning12.1.2 Types of clustering12.2 K-means12.2.1 Issues with k-means12.2.2 The curse of dimensionality strikes again12.2.3 K-means performance analysis12.2.4 Boosting k-means with k-d trees12.2.5 Final remarks on k-means12.3 DBSCAN12.3.1 Directly vs density-reachable12.3.2 From definitions to an algorithm12.3.3 And finally, an implementation12.3.4 Pros and cons of DBSCAN12.4 OPTICS12.4.1 Definitions12.4.2 OPTICS algorithm12.4.3 From reachability distance to clustering12.4.4 Hierarchical clustering12.4.5 Performance analysis and final considerations12.5 Evaluating clustering results: Evaluation metrics12.5.1 Interpreting the resultsSummary
13.1 Parallelization13.1.1 Parallel vs distributed13.1.2 Parallelizing k-means13.1.3 Canopy clustering13.1.4 Applying canopy clustering13.2 MapReduce13.2.1 Imagine you are Donald Duck . . .13.2.2 First map, then reduce13.2.3 There is more under the hood13.3 MapReduce k-means13.3.1 Parallelizing canopy clustering13.3.2 Centroid initialization with canopy clustering13.3.3 MapReduce canopy clustering13.4 MapReduce DBSCANSummary
14.1 Definitions14.1.1 Implementing graphs14.1.2 Graphs as algebraic types14.1.3 Pseudo-code14.2 Graph properties14.2.1 Undirected14.2.2 Connected14.2.3 Acyclic14.3 Graph traversal: BFS and DFS14.3.1 Optimizing delivery routes14.3.2 Breadth first search14.3.3 Reconstructing the path to target14.3.4 Depth first search14.3.5 It’s queue vs stack again14.3.6 Best route to deliver a parcel14.4 Shortest path in weighted graphs: Dijkstra14.4.1 Differences with BFS14.4.2 Implementation14.4.3 Analysis14.4.4 Shortest route for deliveries14.5 Beyond Dijkstra’s algorithm: A*14.5.1 How good is A* search?14.5.2 Heuristics as a way to balance real-time dataSummary
15.1 Graph embeddings15.1.1 Some basic definitions15.1.2 Complete and bipartite graphs15.2 Planar graphs15.2.1 Using Kuratowski’s theorem in practice15.2.2 Planarity testing15.2.3 A naïve algorithm for planarity testing15.2.4 Improving performance15.2.5 Efficient algorithms15.3 Non-planar graphs15.3.1 Finding the crossing number15.3.2 Rectilinear crossing number15.4 Edge intersections15.4.1 Straight-line segments15.4.2 Polylines15.4.3 Bézier curves15.4.4 Intersections between quadratic Bézier curves15.4.5 Vertex-vertex and edge-vertex intersectionsSummary
16.1 Heuristics for the crossing number16.1.1 Did you just say heuristics?16.1.2 Extending to curve-line edges16.2 How optimization works16.2.1 Cost functions16.2.2 Step functions and local minima16.2.3 Optimizing random sampling16.3 Gradient descent16.3.1 The math of gradient descent16.3.2 Geometrical interpretation16.3.3 When is gradient descent appliable?16.3.4 Problems with gradient descent16.4 Applications of gradient descent16.4.1 An example: Linear regression16.5 Gradient descent for graph embedding16.5.1 A different criterion16.5.2 ImplementationSummary
17.1 Simulated annealing17.1.1 Sometimes you need to climb up to get to the bottom17.1.2 Implementation17.1.3 Why simulated annealing works17.1.4 Short-range vs long-range transitions17.1.5 Variants17.1.6 Simulated annealing vs gradient descent: Which one should I use?17.2 Simulated annealing + traveling salesman17.2.1 Exact vs approximated solutions17.2.2 Visualizing cost17.2.3 Pruning the domain17.2.4 State transitions17.2.5 Adjacent vs random swaps17.2.6 Applications of TSP17.3 Simulated annealing and graph embedding17.3.1 Minimum edge crossing17.3.2 Force-directed drawingSummary
18.1 Genetic algorithms18.1.1 Inspired by nature18.1.2 Chromosomes18.1.3 Population18.1.4 Fitness18.1.5 Natural selection18.1.6 Selecting individuals for mating18.1.7 Crossover18.1.8 Mutations18.1.9 The genetic algorithm template18.1.10 When does the genetic algorithm work best?18.2 TSP18.2.1 Fitness, chromosomes, and initialization18.2.2 Mutations18.2.3 Crossover18.2.4 Results and parameters tuning18.2.5 Beyond TSP: Optimizing the routes of the whole fleet18.3 Minimum vertex cover18.3.1 Applications of vertex cover18.3.2 Implementing a genetic algorithm18.4 Other applications of the genetic algorithm18.4.1 Maximum flow18.4.2 Protein folding18.4.3 Beyond genetic algorithms18.4.4 Algorithms, beyond this bookSummary
A.1 Variables and basicsA.2 ArraysA.3 Conditional instructionsA.3.1 Else-ifA.3.2 SwitchA.4 LoopsA.4.1 For loopA.4.2 While loopA.4.3 Break and continueA.5 Blocks and indentA.6 FunctionsA.6.1 Overloading and default argumentsA.6.2 TuplesA.6.3 Tuples and destructuring objects
B.1 Algorithms and performanceB.2 The RAM modelB.3 Order of magnitudeB.4 NotationB.5 Examples
C.1 Core data structuresC.2 ArrayC.3 Linked ListC.4 TreeC.4.1 Binary search treesC.5 Hash tableC.5.1 Storing key-value pairsC.5.2 HashingC.5.3 Conflicts resolution in hashingC.5.4 PerformanceC.6 Comparative analysis of core data structures
D.1 BagD.2 StackD.3 QueueD.4 A comparative analysis of containers
E.1 Simple recursionE.1.1 PitfallsE.1.2 Good recursionE.2 Tail recursionE.3 Mutual recursion
F.1 Decision problemsF.2 Las Vegas algorithmsF.3 Monte Carlo algorithmsF.4 Classification metricsF.4.1 AccuracyF.4.2 Precision and recallF.4.3 Other metrics and recap

Content preview from Advanced Algorithms and Data Structures

9 K-d trees: Multidimensional data indexing

This chapter covers

Indexing a 2-D (and in general k-D) dataset efficiently
Implementing nearest neighbor search with k-d trees
Discussing k-d trees’ strengths and flaws

This chapter will be structured slightly differently from our book’s standard, simply because we will continue here a discussion started in chapter 8. We introduced a problem: searching multidimensional data for the nearest neighbor(s) of a generic point (possibly not in the dataset itself).

In this chapter, we follow up on those topics, so we won’t introduce a new problem, but pick up the “closest hub” example from chapter 8 and show a different option to solve it, using k-d trees.