8
$\begingroup$

Is there any book or tutorial that teaches us how to efficiently apply the common algorithms (sorting, searching, etc.) on large data (i.e. data that cannot be fully loaded into main memory) and how to efficiently apply those algorithms considering the cost of block transfer from external memory ? For example, almost all algorithm textbooks say that B and B+-trees can be used to store data on disk. However, actually how this can be done, especially handling the pointers where the data is present on disk is not explained. Similarly, though many books teach searching techniques, they do not consider data present in secondary memory.

I have checked Knuth's book. Although it discusses these ideas, I still did not understand how to actually apply them in a high-level language. Is there any reference that discusses these details?

$\endgroup$
  • 1
    $\begingroup$ Check out "Mining Massive Data Sets". $\endgroup$ – Dave Clarke Aug 22 '12 at 11:58
  • $\begingroup$ You can give a look to the comprehensive bibliography of the STXXL: the standard template library for XXL datasets. $\endgroup$ – Vor Aug 22 '12 at 18:59
  • $\begingroup$ This days with having great DBs like Oracle, DB2, SQL Server, normally no one works big datasets himself, if you interested you could look at related documents to one of a DB Servers, but this days Martin Fowler and some other people are trying to move to NO SQL, you could also check it. (but there are too many aspects in big databases, like concurrency, security, ... not just fast algorithms). $\endgroup$ – user742 Aug 22 '12 at 22:11
  • $\begingroup$ @Dave, Vor: Thank you for your references. I will check them and inform you if they are what I am looking for. $\endgroup$ – Arani Aug 23 '12 at 14:41
  • $\begingroup$ @SaeedAmiri: I understand that, but from what I understand, storing data in databases is only useful if the data is highly structured in some way. So, sequence of numbers and other similar data are generally not stored using databases. Moreover, database textbooks do not describe in much detail from the database developer's point of view. While most of them mention that databases use B and B+-trees, most do not describe actually HOW they implement these data structures. $\endgroup$ – Arani Aug 23 '12 at 14:45
2
$\begingroup$

Database books are good example. However, have a look at the field I/O efficient data structures (and algorithms). To my knowledge, there are some courses about this topic, but very few books.

Check this book: U. Meyer, P. Sanders, and J. Sibeyn (eds.), Algorithms for Memory Hierarchies, Lecture Notes in Computer Science 2625, Springer, 2003.

Check these courses: http://www.win.tue.nl/~hermanh/teaching/2IL35/ http://www.daimi.au.dk/~large/ioS12/

and these slides: algo2.iti.kit.edu/sanders/courses/algen09-10/rdslides.pdf

$\endgroup$
1
$\begingroup$

Ramkrishnan and Gehrke's database book discusses these things in some detail.

$\endgroup$
  • $\begingroup$ The worst and most boring ever :) ! although it is a good introduction to many interesting topics in databases and db optimization. $\endgroup$ – AJed Sep 12 '15 at 18:36
1
$\begingroup$

Probably what you are looking for in one neat book:Algorithms and Data Structures for External Memory by Jeffrey Scott Vitter.

$\endgroup$
0
$\begingroup$

Nowadays this field is known as big data, and it is evolving very rapidly and quickly based on the strong connection with virtualization and relational database technology is only seen as a subset. Also as comments note, key/value databases and NoSQL are where much new innovation and momentum is moving. But from your comments, you seem to be more interested in relational database design principles and techniques. Try the following refs:

$\endgroup$
  • $\begingroup$ I have not really studied non-relational database systems, and so that might be one plausible answer. But I am not actually looking for database textbooks that describe database design. Instead, a book that describes it from the point of view of database developer (which explicitly tells us how data structures for working on disks are implemented) would be very helpful. $\endgroup$ – Arani Sep 5 '12 at 21:06
  • $\begingroup$ hate to admit this but botched these refs a bit. there are books on database algorithms but there are many books on database design that are really about how to organize tables, datamodelling, normalization, indexes, etc, concepts like these. while these are tangentially related to your question, they arent really exactly connected. basically many of the strategies for managing b-trees in modern databases are somewhat verging on trade secrets. generally the b-trees are stored in "pages" that are dynamically allocated & indexed. may look for better refs on this sometime. $\endgroup$ – vzn Sep 5 '12 at 21:18
  • $\begingroup$ guess what you really want is physical database storage design (which might be covered loosely in some of those refs, or maybe not).. eg heres a whitepaper for a case study with some related content ie "Internals of SQL Server physical design storage", MS SQL server $\endgroup$ – vzn Sep 5 '12 at 21:30
  • $\begingroup$ see also the closely related query plan optimization $\endgroup$ – vzn Sep 6 '12 at 16:11
  • 1
    $\begingroup$ see also B+ tree indexes with some ref to storage pages & apache derby, a B tree fetch/storage implementation in java with implementation details $\endgroup$ – vzn Sep 6 '12 at 17:38

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.