Core algorithms deployed
To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of examples where core algorithms have been deployed in commercial, governmental, or widely-used software/hardware.
I am looking for such examples that satisfy the following criteria:
The software/hardware using the algorithm should be in wide use right now.
The example should be specific. Please give a reference to a specific system and a specific algorithm.
E.g., in "algorithm X is useful for image processing" the term "image processing" is not specific enough; in "Google search uses graph algorithms" the term "graph algorithms" is not specific enough.
The algorithm should be taught in typical undergraduate or Ph.D. classes in algorithms or data structures. Ideally, the algorithm is covered in typical algorithms textbooks. E.g., "well-known system X uses little-known algorithm Y" is not good.
Thanks again for the great answers and links! Some people comment that it is hard to satisfy the criteria because core algorithms are so pervasive that it's hard to point to a specific use. I see the difficulty. But I think it is worthwhile to come up with specific examples because in my experience telling people: "Look, algorithms are important because they are just about everywhere!" does not work.
Algorithms that are the main driver behind a system are, in my opinion, easier to find in non-algorithms courses for the same reason theorems with immediate applications are easier to find in applied mathematics rather than pure mathematics courses. It is rare for a practical problem to have the exact structure of the abstract problem in a lecture. To be argumentative, I see no reason why fashionable algorithms course material such as Strassen's multiplication, the AKS primality test, or the Moser-Tardos algorithm is relevant for low-level practical problems of implementing a video database, an optimizing compiler, an operating system, a network congestion control system or any other system. The value of these courses is learning that there are intricate ways to exploit the structure of a problem to find efficient solutions. Advanced algorithms is also where one meets simple algorithms whose analysis is non-trivial. For this reason, I would not dismiss simple randomized algorithms or PageRank.
I think you can choose any large piece of software and find basic and advanced algorithms implemented in it. As a case study, I've done this for the Linux kernel, and shown a few examples from Chromium.
Basic Data Structures and Algorithms in the Linux kernel
Links are to the source code on github.
- Linked list, doubly linked list, lock-free linked list.
B+ Trees with comments telling you what you can't find in the textbooks.
A relatively simple B+Tree implementation. I have written it as a learning exercise to understand how B+Trees work. Turned out to be useful as well.
A tricks was used that is not commonly found in textbooks. The lowest values are to the right, not to the left. All used slots within a node are on the left, all unused slots contain NUL values. Most operations simply loop once over all slots and terminate on the first NUL.
- Red-Black trees are used for scheduling, virtual memory management, to track file descriptors and directory entries,etc.
- Interval trees
A common use of the radix tree is to store pointers to struct pages;
Simple insertion-only static-sized priority heap containing pointers, based on CLR, chapter 7
Hash functions, with a reference to Knuth and to a paper.
Knuth recommends primes in approximately golden ratio to the maximum integer representable by a machine word for multiplicative hashing. Chuck Lever verified the effectiveness of this technique:
These primes are chosen to be bit-sparse, that is operations on them can use shifts and additions instead of multiplications for machines where multiplications are slow.
Some parts of the code, such as this driver, implement their own hash function.
hash function using a Rotating Hash algorithm
Knuth, D. The Art of Computer Programming, Volume 3: Sorting and Searching, Chapter 6.4. Addison Wesley, 1973
- Hash tables used to implement inodes, file system integrity checks etc.
Bit arrays, which are used for dealing with flags, interrupts, etc. and are featured in Knuth Vol. 4.
Performs a modified depth-first walk of the namespace tree, starting (and ending) at the node specified by start_handle. The callback function is called whenever a node that matches the type parameter is found. If the callback function returns a non-zero value, the search is terminated immediately and this value is returned to the caller.
Breadth first search is used to check correctness of locking at runtime.
Bubble sort is amazingly implemented too, in a driver library.
Implements a linear-time string-matching algorithm due to Knuth, Morris, and Pratt . Their algorithm avoids the explicit computation of the transition function DELTA altogether. Its matching time is O(n), for n being length(text), using just an auxiliary function PI[1..m], for m being length(pattern), precomputed from the pattern in time O(m). The array PI allows the transition function DELTA to be computed efficiently "on the fly" as needed. Roughly speaking, for any state "q" = 0,1,...,m and any character "a" in SIGMA, the value PI["q"] contains the information that is independent of "a" and is needed to compute DELTA("q", "a") 2. Since the array PI has only m entries, whereas DELTA has O(m|SIGMA|) entries, we save a factor of |SIGMA| in the preprocessing time by computing PI rather than DELTA.
 Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press
 See finite automation theory
Boyer-Moore pattern matching with references and recommendations for when to prefer the alternative.
Implements Boyer-Moore string matching algorithm:
 A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977, pp. 762-772. http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
 Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
Note: Since Boyer-Moore (BM) performs searches for matchings from right to left, it's still possible that a matching could be spread over multiple blocks, in that case this algorithm won't find any coincidence.
If you're willing to ensure that such thing won't ever happen, use the Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose the proper string search algorithm depending on your setting.
Say you're using the textsearch infrastructure for filtering, NIDS or
any similar security focused purpose, then go KMP. Otherwise, if you really care about performance, say you're classifying packets to apply Quality of Service (QoS) policies, and you don't mind about possible matchings spread over multiple fragments, then go BM.
Data Structures and Algorithms in the Chromium Web Browser
Links are to the source code on Google code. I'm only going to list a few. I would suggest using the search feature to look up your favourite algorithm or data structure.
- Splay trees.
The tree is also parameterized by an allocation policy (Allocator). The policy is used for allocating lists in the C free store or the zone; see zone.h.
- Voronoi diagrams are used in a demo.
- Tabbing based on Bresenham's algorithm.
- Binary trees
- Red-Black trees
Conclusion of Julian Walker
Red black trees are interesting beasts. They're believed to be simpler than AVL trees (their direct competitor), and at first glance this seems to be the case because insertion is a breeze. However, when one begins to play with the deletion algorithm, red black trees become very tricky. However, the counterweight to this added complexity is that both insertion and deletion can be implemented using a single pass, top-down algorithm. Such is not the case with AVL trees, where only the insertion algorithm can be written top-down. Deletion from an AVL tree requires a bottom-up algorithm.
Red black trees are popular, as most data structures with a whimsical name. For example, in Java and C++, the library map structures are typically implemented with a red black tree. Red black trees are also comparable in speed to AVL trees. While the balance is not quite as good, the work it takes to maintain balance is usually better in a red black tree. There are a few misconceptions floating around, but for the most part the hype about red black trees is accurate.
- AVL trees
- Rabin-Karp string matching is used for compression.
- Compute the suffixes of an automaton.
- Bloom filter implemented by Apple Inc.
- Bresenham's algorithm.
Programming Language Libraries
I think they are worth considering. The programming languages designers thought it was worth the time and effort of some engineers to implement these data structures and algorithms so others would not have to. The existence of libraries is part of the reason we can find basic data structures reimplemented in software that is written in C but less so for Java applications.
- The C++ STL includes lists, stacks, queues, maps, vectors, and algorithms for sorting, searching and heap manipulation.
- The Java API is very extensive and covers much more.
- The Boost C++ library includes algorithms like Boyer-Moore and Knuth-Morris-Pratt string matching algorithms.
Allocation and Scheduling Algorithms
I find these interesting because even though they are called heuristics, the policy you use dictates the type of algorithm and data structure that are required, so one need to know about stacks and queues.
- Least Recently Used can be implemented in multiple ways. A list-based implementation in the Linux kernel.
- Other possibilities are First In First Out, Least Frequently Used, and Round Robin.
- A variant of FIFO was used by the VAX/VMS system.
- The Clock algorithm by Richard Carr is used for page frame replacement in Linux.
- The Intel i860 processor used a random replacement policy.
- Adaptive Replacement Cache is used in some IBM storage controllers, and was used in PostgreSQL though only briefly due to patent concerns.
- The Buddy memory allocation algorithm, which is discussed by Knuth in TAOCP Vol. 1 is used in the Linux kernel, and the jemalloc concurrent allocator used by FreeBSD and in facebook.
Core utils in *nix systems
- grep and awk both implement the Thompson-McNaughton-Yamada construction of NFAs from regular expressions, which apparently even beats the Perl implementation.
- tsort implements topological sort.
- fgrep implements the Aho-Corasick string matching algorithm.
- GNU grep, implements the Boyer-Moore algorithm according to the author Mike Haertel.
- crypt(1) on Unix implemented a variant of the encryption algorithm in the Enigma machine.
- Unix diff implemented by Doug McIllroy, based on a prototype co-written with James Hunt, performs better than the standard dynamic programming algorithm used to compute Levenshtein distances. The Linux version computes the shortest edit distance.
This could be a very long list. Cryptographic algorithms are implemented in all software that can perform secure communications or transactions.
- Merkle trees, specifically the Tiger Tree Hash variant, were used in peer-to-peer applications such as GTK Gnutella and LimeWire.
- MD5 is used to provide a checksum for software packages and is used for integrity checks on *nix systems (Linux implementation) and is also supported on Windows and OS X.
- OpenSSL implements many cryptographic algorithms including AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES, etc.
- LALR parsing is implemented by yacc and bison.
- Dominator algorithms are used in most optimizing compilers based on SSA form.
- lex and flex compile regular expressions into NFAs.
Compression and Image Processing
- The Lempel-Ziv algorithms for the GIF image format are implemented in image manipulation programs, starting from the *nix utility convert to complex programs.
- Run length encoding is used to generate PCX files (used by the original Paintbrush program), compressed BMP files and TIFF files.
- Wavelet compression is the basis for JPEG 2000 so all digital cameras that produce JPEG 2000 files will be implementing this algorithm.
- Reed-Solomon error correction is implemented in the Linux kernel, CD drives, barcode readers and was combined with convolution for image transmission from Voyager.
Conflict Driven Clause Learning
Since the year 2000, the running time of SAT solvers on industrial benchmarks (usually from the hardware industry, though though other sources are used too) has decreased nearly exponentially every year. A very important part of this development is the Conflict Driven Clause Learning algorithm that combines the Boolean Constraint Propagation algorithm in the original paper of Davis Logemann and Loveland with the technique of clause learning that originated in constraint programming and artificial intelligence research. For specific, industrial modelling, SAT is considered an easy problem (see this discussion). To me, this is one of the greatest success stories in recent times because it combines algorithmic advances spread over several years, clever engineering ideas, experimental evaluation, and a concerted communal effort to solve the problem. The CACM article by Malik and Zhang is a good read. This algorithm is taught in many universities (I have attended four where it was the case) but typically in a logic or formal methods class.
Applications of SAT solvers are numerous. IBM, Intel and many other companies have their own SAT solver implementations. The package manager in OpenSUSE also uses a SAT solver.
Nice list, but I'm not sure about including the OS scheduling algorithms and CDCL since they are heuristic and in the worst-case can be quite bad.
@HuckBennett, CDCL is an algorithm parameterized by heuristics but is not itself a heuristic. It has worst case exponential behaviour but it is non-trivial to show that. Moreover, we cannot do provably better and it is the best we can do in practice, so I feel all computer scientists should know about it! As for LRU,FIFO, etc. they are heuristics, but, as with ARC, may require clever algorithms or data structures to implement.
I'm not saying that CDCL isn't cool or important (it is) but I don't think it's really an algorithm as is usually meant in theory since we can't really prove anything about it. "Here's an algorithm that seems to work well in practice" is more the domain of AI and formal methods. AFAIK it has $O(2^n)$ worst-case running time and no other guarantees using other formal analyses. We actually can do better for various NP-complete variants of SAT such as Schoning's $O^*(1.334)$-time algorithm for 3-SAT.
Wouldn't such a comment have applied to Simplex: initially not well understood and later shown to be exponential but works in practice and much later shown to have polynomial smoothed complexity? CDCL is interesting for algorithm analysis because you need to go via proof complexity to derive families of formulae exhibiting worst case behaviour, and also to show it can be exponentially more succinct than some variants of resolution. There are various extensions, such as symmetry breaking and autarky techniques for which such an analysis is still open.
@VijayD Thanks for the interesting list. I find the use of Red-Black trees in the Linux kernel compelling.
Nice update! I like the list of basic data structures that show up in the Linux kernel. Ideally, it would be great if one could find more examples like that but that are not strictly confined to data structures.
@EmanueleViola, please elaborate. By more examples, do you mean more systems, or do you mean, more algorithms in the same system? What would you like to see beyond data structures? (maybe add it to the original question)
@VijayD: I mean more algorithms in some system. E.g. notable members of sorting, dynamic programming, greedy, flow, LP, graph algorithms, approx algorithms, string matching, number-theoretic, and whatever else you think is core material.
@EmanueleViola, I've added a few more examples. The post is long now, so I don't want to extend it. Maybe you should ask a new question specifically about implementations of Dijkstra, Simplex, Bloom filters as part of a real system like Linux, Chrome, a web server etc. I think you are more likely to get good answers if you are specific.
Wow, is this the most upvoted answer on cstheory now :)? Did someone post this question on reddit?
PageRank is one of the best-known such algorithms. Developed by Google co-founder Larry Page and co-authors, it formed the basis of Google's original search engine and is widely credited with helping them to achieve better search results than their competitors at the time.
We imagine a "random surfer" starting at some webpage, and repeatedly clicking a random link to take him to a new page. The question is, "What fraction of the time will the surfer spend at each page?" The more time the surfer spends at a page, the more important the page is considered.
More formally, we view the internet as a graph where pages are nodes and links are directed edges. We can then model the surfer's action as a random walk on a graph or equivalently as a Markov Chain with transition matrix $M$. After dealing with some issues to ensure that the Markov Chain is ergodic (where does the surfer go if a page has no outgoing links?), we compute the amount of time the surfer spends at each page as the steady state distribution of the Markov Chain.
The algorithm itself is in some sense trivial - we just compute $M^k \pi_0$ for large $k$ and arbitrary initial distribution $\pi_0$. This just amounts to repeated matrix-matrix or matrix-vector multiplication. The algorithms content is mainly in the set-up (ensuring ergodicity, proving that an ergodic Markov Chain has a unique steady state distribution) and convergence analysis (dependence on the spectral gap of $M$).
Incidentally I first learned about PageRank in an algorithms class. In fact, I think the professor chose it because it was a nice example of "algorithms used in practice." If you limit examples to "first half of CLRS" type material, the list of examples will either be too long or too trivial -- quicksort, B-trees, and Dijkstra's algorithm are ubiquitous.
@EmanueleViola I am currently an information science student at a university. I have not taken algorithms but I have had Markov chains and PageRank in other classes
I teach it to undergraduates also (both in the required algorithms class and in a more specialized graph algorithms elective).
Alright, PageRank should qualify even though it's not in standard textbooks (I think). Though the algorithm is a bit atypical (when compared to other core algorithms), because as Huck says it's pretty much all in the analysis.
Isn't pagerank supposed to be based on the number of backlinks from other pages? You say it is based on the time that a user spends on a page; which is data a search engine cannot have.
Here "time" means the fraction of steps in the Markov Chain that the user spends at the page.
I would mention the widely-used software CPLEX (or similar) implementation of the Simplex method/algorithm for solving linear programming problems. It is the (?) most used algorithm in economy and operations research.
"If one would take statistics about which mathematical problem is using up most of the computer time in the world, then (not counting database handling problems like sorting and searching) the answer would probably be linear programming." (L. Lovász, A new linear programming algorithm-better or worse than the simplex method? Math. Intelligencer 2 (3) (1979/80) 141-146.)
The Simplex algorithm has also great influence in theory; see, for instance, the (Polynomial) Hirsch Conjecture.
I guess a typical undergraduate or Ph.D. class in algorithms deals with the Simplex algorithm (including basic algorithms from linear algebra like Gauss Elimination Method).
(Other successful algorithms, including Quicksort for sorting, are listed in Algorithms from the Book.)
"economy and operations research" isn't specific enough. CPLEX isn't the type of example I was looking for either, as it is just an implementation of the algorithm; it would be different if, say, the gcc compiler used the simplex method.
I think "linear programming problems" is specific enough when we speak about economy and OR. Also, by CPLEX I meant the algorithm behind the implementation.
"Today, most large firms use linear programming to price products and manage supply chains. Transportation firms use it to choose the cheapest way to consolidate, coordinate and route shipments of many products from globally distributed suppliers to distant markets subject to capacity constraints. The petroleum industry uses it for exploration, blending, production scheduling and distribution. The iron and steel industry uses it to evaluate iron ores, explore the addition of coke ovens and select products..." http://news.stanford.edu/news/2005/may25/dantzigobit-052505.html
Thanks. But I find the quote terribly vague. I think if I say that in front of a class of students, half of it would fall asleep ;-) It would be different if we say something like: UPS uses LP to ship packages as follows... I am not saying such examples are trivial to find, but given that "most large firms use LP" I'd hope we can at least point to *one*.
Off the top of my head, since 2007 LAX (the airport) has used software for solving Stackelberg games to schedule the security personnel. Solving large LPs is part of the whole thing, see e.g. http://teamcore.usc.edu/ARMOR-LAX/. Besides that, I would ask someone from your Operations Research department: they would usually have plenty of war stories about using LP in real life
As I understand it, the National Resident Matching Program was for a long time just a straight application of the Gale-Shapley algorithm for the stable marriage problem. It has since been slightly updated to handle some extra details like spousal assignments (aka the "two-body problem"), etc...
It's in the Tardos and Kleinberg Algorithms Design book, and also in Motwani's Randomized Algorithms, and both books are widely used. Stable marriage may not be universally taught in algorithms courses, but it certainly is taught in a lot of them.
Interestingly, when you add in spousal assignments, the problem becomes NP-complete: http://arxiv.org/abs/1308.4534. However, in practice this seems not to cause too much of a problem: http://en.wikipedia.org/wiki/National_Resident_Matching_Program#Couples
@EmanueleViola while it might not be covered traditionally, its inclusion in the Kleinberg/Tardos book has made it more popular, (and if not it should be !)
If you're also including PhD-level stuff, many (most?) graduate CS programs include some course in coding theory. If you have a course in coding theory, you will definitely cover the Reed-Solomon code which is integral to how compact discs work and Huffman encoding which is used in JPEG, MP3, and ZIP file formats. Depending on the orientation of the course, you may also cover Lempel-Ziv which is used in the GIF format. Personally, I got Lempel-Ziv in an undergraduate algorithms course, but I think that might be atypical.
And I got a lecture on Huffman encoding as an undergrad, which was required for a project.
GNU grep is a command line tool for searching one or more input files for lines containing a match to a specified pattern. It is well-known that grep is very fast! Here's a quote from its author Mike Haertel (taken from here):
GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the final letter of the target string, and uses a lookup table to tell it how far ahead it can skip in the input whenever it finds a non-matching character.
More generally, the Kanellakis prize is awarded by the ACM for precisely such theoretical discoveries that have had a major impact in practice.
the 2012 award is for locality-sensitive hashing, which has become a go-to method for dimensionality reduction in data mining for near neighbor problems (and is relatively easy to teach - at least the algorithm itself)
Unfortunate, but true. However, variants of LSH (like the Count-min sketch and relatives) are beginning to appear in "large-data" or "data mining" courses. I teach bloom filters in my algorithms class, for example.
As a personal experience, LSH did not scale for us on an instance of a "big data" (100mln items).
The CountMin Sketch and Count Sketch, from data streaming algorithms, are used in industrial systems for network traffic analysis and analysis of very large unstructured data. These are data structure that summarize the frequency of a huge number of items in a tiny amount of space. Of course they do that approximately, and the guarantee is that, with high probability, the frequency of any item is approximated to within an an $\varepsilon$-fraction of the total "mass" of all items (the mass is the first or second moment of the frequency vector). This is good enough to find "trending" items, which is what you need in a lot of applications.
Some examples of industrial uses of these data structures are:
- Google's Sawzall system for unstructured data analysis uses the Count Sketch to implement a 'most popular items' function
- AT&T's Gigascope "stream database" system for network traffic monitoring implements the CountMin sketch.
- Sprint's Continous Monitoring (CMON) system implements CountMin.
Here is also a site that collects information about applications of CountMin.
As far as teaching, I know that basic sketching techniques are taught at Princeton in undergraduate discrete math courses. I was taught the CountMin sketch in my first algorithms course. In any case, the analysis of CountMin is simpler than the analysis for almost any other randomized algorithm: it's a straightforward application of pairwise independence and Markov's inequality. If this is not standard material in most algorithms courses, I think it's for historical reasons.
In the last decade algorithms have been used to increase the number (and quality, I think?) of kidney transplants through various kidney donor matching programs. I've been having trouble finding the latest news on this, but here are at least a few pointers:
As recently as 2007 the Alliance for Paired Donation was using an algorithm of Abraham, Blum, and Sandholm. They may still be using it, but I couldn't find out by searching online. Although this algorithm is almost surely not covered in "standard" courses, it combines several fundamental ideas that surely are taught in such courses to provide a good enough algorithm for a problem that is, in general, NP-complete (a variant of Cycle Cover).
The National Kidney Registry also uses some standard algorithms, including (at one point) CPLEX. This led to an actually performed chain of transplants linking 60 people.
This is one of my favorite examples not just of the success of algorithms, but of the importance of studying algorithms for NP-complete problems. They can literally save lives, and have already done so!
Also, a simpler version of these algorithms is used to trade board games: http://okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html
Viterbi's algorithm, which is still widely used in speech recognition and multiple other applications: http://en.wikipedia.org/wiki/Viterbi_algorithm The algorithm itself is basic dynamic programming.
From Wikipedia: "The Viterbi algorithm was proposed by Andrew Viterbi in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links. The algorithm has found universal application in decoding the convolutional codes used in both CDMA and GSM digital cellular, dial-up modems, satellite, deep-space communications, and 802.11 wireless LANs. It is now also commonly used in speech recognition, speech synthesis, keyword spotting, computational linguistics, and bioinformatics. For example, in speech-to-text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the "hidden cause" of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal."