Also, the algorithms around using Reduced Order Binary Decision Diagrams (ROBDD) to represent sets efficiently. They are used in verification algorithms with very large state spaces, such as "Symbolic Model Checking: 10^20 states and beyond" by Burch, Clarke, and McMillan <http://www.cse.chalmers.se/edu/year/2012/course/TDA956/Paper...>
I was on the relational side (I worked for MySQL) when MongoDB first sprung up, and IMHO it was to some extent a knee-jerk reaction.
MongoDB claimed far superior performance for web-applications simply by not persisting data to disk. MongoDB offered one thing that was very useful to web-developers: a good API for storing JSON data directly into the database. Not having transactional semantics was of course a terrible idea once critical data was stored into the databases and the systems started to have crashes, but it worked for small applications and while developing the applications nothing looked amiss.
Since web-developers are not database experts and many did not have experience with deploying large-scale applications, it was of course very appealing to have both performance and simplicity. But as the downsides of not persisting data started to become a real problem, many applications moved away from MongoDB and into other systems that offered transactional capabilities and durability of data. At the same time, MongoDB started to implement transactional support, which of course affected performance, but allowed applications to remain on MongoDB.
All in all, I think the takeaway is that database APIs matter to developers (not really very surprising) and it is important to have a good API to the database, but transactional behavior is important for real applications and it is essential to have that as well.
With JSON being added to PostgreSQL and MySQL, I think that some of that simplicity that MongoDB offered is available in PostgreSQL and MySQL as well. (The API is still an SQL API, but at least you can easily store and retrieve JSON documents directly from the database.)
I think the main problem during that time is that the issues of performance and API was conflated and a general assumption grew that NoSQL also meant high performance, which is not necessarily the case.
