Chapter 9 Nearest neighbor
Course Content
0 / 173 completedChapter 1 Describing a data structure
Part 1. Improving over basic data structures
Chapter 1 Packing your knapsack - Data structures meet the real world
Chapter 1 Introducing data structures
Chapter 2 Improving priority queues - d-way heaps
Chapter 1 Algorithms to the rescue
Chapter 2 Concrete data structures
Chapter 2 Solutions at hand - Keeping a sorted list
Chapter 2 How to implement a heap
Chapter 2 Priority, min-heap, and max-heap
Chapter 2 PushDown
Chapter 2 Top
Chapter 2 Use case - Find the k largest elements
Chapter 2 Heapify
Chapter 2 Analysis of branching factor
Chapter 2 More use cases
Chapter 2 Interpreting results
Chapter 2 Performance analysis - Finding the best branching factor
Chapter 3 Treaps - Using randomization to balance binary search trees
Chapter 2 The mystery with heapify
Chapter 3 A few design questions
Chapter 3 Treap
Chapter 3 Delete
Chapter 3 Performance analysis and profiling
Chapter 3 Profiling height
Chapter 3 Profiling memory usage
Chapter 3 Applications - Randomized treaps
Chapter 4 Bloom filters - Reducing the memory for tracking content
Chapter 4 Alternatives to implementing a dictionary
Chapter 4 Concrete data structures
Chapter 4 Binary search tree - Every operation is logarithmic
Chapter 4 Implementation
Chapter 4 Constructor
Chapter 4 Why Bloom filters work
Chapter 4 Performance analysis
Chapter 4 Explanation of the false-positive ratio formula
Chapter 4 Applications
Chapter 4 Improved variants
Chapter 5 Reasoning on solutions
Chapter 5 Disjoint sets - Sub-linear time processing
Chapter 5 Naïve solution
Chapter 5 Using a tree-like structure
Chapter 5 Heuristics to improve the running time
Chapter 5 Applications
Chapter 6 Trie, radix trie - Efficient string search
Chapter 6 Trie
Chapter 6 Search
Chapter 6 Insert
Chapter 6 Keys matching a prefix
Chapter 6 Applications
Chapter 6 String sorting
Chapter 6 Radix tries
Chapter 6 Search
Chapter 7 First attempt - Remembering values
Chapter 7 Use case - LRU cache
Chapter 7 Handling asynchronous calls
Chapter 7 Memory is not enough (literally)
Chapter 7 Temporal ordering
Chapter 7 Getting rid of stale data - LRU cache
Chapter 7 When fresher data is more valuable - LFU
Chapter 7 How to use cache is just as important
Chapter 7 Read locks
Chapter 7 Solving concurrency (in Java)
Part 2. Multidimensional queries
Chapter 8 Nearest neighbors search
Chapter 8 Moving to k-dimensional spaces
Chapter 8 Simplifying things to get a hint
Chapter 9 K-d trees - Multidimensional data indexing
Chapter 9 Constructing the BST
Chapter 9 Balanced tree
Chapter 9 Remove
Chapter 9 Methods
Chapter 9 Nearest neighbor
Chapter 9 Region search
Chapter 10 Inserting points in an R-tree
Chapter 10 R-tree
Chapter 10 Similarity Search Trees - Approximate nearest neighbors search for image retrieval
Chapter 10 Similarity search tree
Chapter 10 SS-tree search
Chapter 10 Insertion - Split nodes
Chapter 10 Delete
Chapter 10 Insert
Chapter 10 Similarity Search
Chapter 10 Approximated similarity search
Chapter 10 SS+-tree
Chapter 10 Reducing overlap
Chapter 11.Centralized application
Chapter 11 Applications of nearest neighbor search
Chapter 11 Other applications
Chapter 11 Multidimensional DB queries optimization
Chapter 11 Moving to a distributed application
Chapter 12 Clustering
Chapter 12 Types of learning
Chapter 12 The curse of dimensionality strikes again
Chapter 12 Boosting k-means with k-d trees
Chapter 12 K-means
Chapter 12 DBSCAN
Chapter 12 And finally, an implementation
Chapter 12 OPTICS
Chapter 12 From definitions to an algorithm
Chapter 12 From reachability distance to clustering
Chapter 12 Hierarchical clustering
Chapter 13 Canopy clustering
Chapter 12. Evaluating clustering results - Evaluation metrics
Chapter 13 Parallel clustering - MapReduce and canopy clustering
Chapter 13 MapReduce
Chapter 13 MapReduce k-means
Chapter 13 Parallelizing canopy clustering
Chapter 13 First map, then reduce
Chapter 13 MapReduce canopy clustering
Chapter 13 MapReduce DBSCAN - Part 1
Chapter 13 MapReduce DBSCAN - Part 2
Part 3. Planar graphs and minimum crossing number
Chapter 14 An introduction to graphs - Finding paths of minimum distance
Chapter 14 Graph properties
Chapter 14 Implementing graphs
Chapter 14 Graph traversal - BFS and DFS
Chapter 14 Reconstructing the path to target
Chapter 14 Beyond Dijkstra’s algorithm - A
Chapter 14 Shortest path in weighted graphs - Dijkstra
Chapter 14 How good is A search
Chapter 14 Heuristics as a way to balance real-time data
Chapter 15 Some basic definitions
Chapter 15 Graph embeddings and planarity - Drawing graphs with minimal edge intersections
Chapter 15 Planar graphs
Chapter 15 Planarity testing
Chapter 15 Non-planar graphs
Chapter 15 Improving performance
Chapter 15 Rectilinear crossing number
Chapter 15 Edge intersections
Chapter 15 Polylines
Chapter 15 Intersections between quadratic Bézier curves
Chapter 16 Gradient descent - Optimization problems (not just) on graphs
Chapter 16 Did you just say heuristics
Chapter 16 How optimization works
Chapter 16 When is gradient descent appliable
Chapter 16 Gradient descent
Chapter 16 Applications of gradient descent
Chapter 16 Gradient descent for graph embedding
Chapter 17 Simulated annealing - Optimization beyond local minima
Chapter 17 Sometimes you need to climb up to get to the bottom
Chapter 17 Why simulated annealing works
Chapter 17 Short-range vs long-range transitions
Chapter 17 Exact vs approximated solutions
Chapter 17 Simulated annealing + traveling salesman
Chapter 17 Simulated annealing and graph embedding
Chapter 17 State transitions
Chapter 18 Genetic algorithms - Biologically inspired, fast-converging optimization
Chapter 17 Force-directed drawing
Chapter 18 Inspired by nature
Chapter 18 Chromosomes
Chapter 18 Natural selection
Chapter 18 Selecting individuals for mating
Chapter 18 The genetic algorithm template
Chapter 18 Crossover
Chapter 18 TSP
Chapter 18 Minimum vertex cover
Chapter 18 Other applications of the genetic algorithm
Chapter 18 Beyond genetic algorithms
Chapter 18 Results and parameters tuning
Appendix B. Big-O notation
Appendix A Blocks and indent
Appendix A Conditional instructions
Appendix A. A quick guide to pseudo-code
Appendix C Tree
Appendix C. Core data structures
Appendix C Hash table
Appendix B Notation
Appendix D. Containers as priority queues
Appendix E. Recursion
Appendix E Tail recursion
Appendix F. Classification problems and randomnized algorithm metrics
Appendix F Classification metrics