book

Advanced Algorithms and Data Structures

Name: Advanced Algorithms and Data Structures
Author: Marcello La Rocca
ISBN: 9781617295485

by Marcello La Rocca

July 2021

Intermediate to advanced

768 pages

25h 23m

English

Manning Publications

Read now

Unlock full access

inside front cover
Advanced Algorithms and Data Structures
Copyright
dedication
contents
front matter
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 Introducing data structures
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
Part 1. Improving over basic data structures
2 Improving priority queues: d-way heaps
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 Treaps: Using randomization to balance binary search trees
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 Bloom filters: Reducing the memory for tracking content
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 Disjoint sets: Sub-linear time processing
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 Trie, radix trie: Efficient string search
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 Use case: LRU cache
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
Part 2. Multidimensional queries
8 Nearest neighbors search
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 K-d trees: Multidimensional data indexing
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 Similarity Search Trees: Approximate nearest neighbors search for image retrieval
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 Applications of nearest neighbor search
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 Clustering
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 Parallel clustering: MapReduce and canopy clustering
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
Part 3. Planar graphs and minimum crossing number
14 An introduction to graphs: Finding paths of minimum distance
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 Graph embeddings and planarity: Drawing graphs with minimal edge intersections
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 Gradient descent: Optimization problems (not just) on graphs
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 Simulated annealing: Optimization beyond local minima
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 Genetic algorithms: Biologically inspired, fast-converging optimization
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
appendix A. A quick guide to pseudo-code
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
appendix B. Big-O notation
B.1 Algorithms and performanceB.2 The RAM modelB.3 Order of magnitudeB.4 NotationB.5 Examples
appendix C. Core data structures
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
appendix D. Containers as priority queues
D.1 BagD.2 StackD.3 QueueD.4 A comparative analysis of containers
appendix E. Recursion
E.1 Simple recursionE.1.1 PitfallsE.1.2 Good recursionE.2 Tail recursionE.3 Mutual recursion
appendix F. Classification problems and randomnized algorithm metrics
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
index
inside back cover

Content preview from Advanced Algorithms and Data Structures

12 Clustering

This chapter covers

Classifying different types of clustering
Partitioning clustering
Understanding and implementing k-means
Density-based clustering
Understanding and implementing DBSCAN
OPTICS: Refining DBSCAN as hierarchical clustering
Evaluating clustering results

In the previous chapters we have described, implemented, and applied three data structures designed to efficiently solve nearest neighbor search. When we moved to their applications, we mentioned that clustering was one of the main areas where an efficient nearest neighbor search could make a difference. We had to delay this discussion, but now it’s finally time to put the icing on the cake and get the most out of our hard work. In this chapter, we will first briefly ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Algorithms and Data Structures for Massive Datasets

Publisher Resources

ISBN: 9781617295485Publisher Support Publisher Website Errata Page

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Advanced Algorithms and Data Structures

by Marcello La Rocca

12 Clustering

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.