6
$\begingroup$

As part of a course I am teaching on Data Structures, I want students to research and present the use of Data Structures in popular software/services. However, basic googling shows me that this information is not so readily available.

Can someone point me to the right resources that I may share with the students as a starting point for their research?

EDIT

Judging from the received replies, the original question is not sufficiently clear so I am adding more details.

I am looking for resources of the type that state, for example, that service-x uses data-structure-a in order to perform functionality-y because of property-b. This is the ideal case. Other resources that provide similar information are also welcome.

$\endgroup$
  • 1
    $\begingroup$ With so many software got open source and hosted on GitHub, you can try to search for some commonly used data structure on GitHub. You will find incredible number of hits there. $\endgroup$ – Andrew Au Feb 9 '16 at 1:09
  • $\begingroup$ A search like that only yields direct implementations of the data structure, e.g. here. I am looking for cases where the data structure is part of a larger software. Maybe you can suggest a more helpful way to search. $\endgroup$ – wsaleem Feb 9 '16 at 1:26
  • $\begingroup$ Pick your favorite data structures and algorithms book. Every one of the structures described is used rather frequently. And so are more exotic structures (the literature is luxuriant), used in cases were their humdrum brethren's performance falls short. $\endgroup$ – vonbrand Feb 9 '16 at 1:58
  • 1
    $\begingroup$ Pick any open-source library -- there are many. Students can learn a lot by digging through source code and documentation, I guess. $\endgroup$ – Raphael Feb 9 '16 at 8:19
  • 2
    $\begingroup$ @SamM Perhaps not "popular software", but Fibonacci heaps are very often used in genome and transcriptome assembly for second generation sequencing. De novo assemblers such as Velvet and SOAPdenovo use Dijkstra's all shortest paths algorithm to detect potential read errors. $\endgroup$ – Pseudonym Feb 10 '16 at 22:20
10
$\begingroup$

Off the top of my head:

Every modern operating system uses balanced binary search trees to implement the virtual memory map of a process. Windows uses splay trees, Linux and OS X use red-black trees, and Solaris uses AVL trees. They do this because the operating system needs to store the virtual memory map in order (by virtual address), to allow for fast insertion and removal, and to look for unused regions where it could allocate space.

Many modern 3D games (e.g. anything which uses a recent version of Unreal Engine) use octrees to determine what objects are visible to the camera. They do this because it's quite efficient to calculate what nodes overlap with a camera's view frustum.

Many (if not most) routers use radix trees to implement routing tables. They do this because it is often the prefix of a network address (i.e. the most significant bits) which is important, not the whole key. Moreover, lookup takes time which only depends on the size of the address, not the number of routing table entries, which makes predicting timing easier.

Hash tables are, of course, used everywhere. Antivirus software uses it to perform lookups in its database of known malware, word processors use it to perform spelling checks, etc.

Graph data structures are used by spreadsheets to implement evaluation. Think of each occupied cell as a node, and draw an arc between to cells if the value of one directly depends on the value of the other. When an entry changes in a cell, the graph is traversed to determine which cells need updating based on that change.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.