Aplicando algoritmos en grandes datos

8

¿Hay algún libro o tutorial que nos enseñe cómo aplicar eficientemente los algoritmos comunes (clasificación, búsqueda, etc.) en datos grandes (es decir, datos que no se pueden cargar completamente en la memoria principal) y cómo aplicar esos algoritmos de manera eficiente teniendo en cuenta el costo de bloquear la transferencia desde la memoria externa? Por ejemplo, casi todos los libros de texto de algoritmos dicen que los árboles B y B + se pueden usar para almacenar datos en el disco. Sin embargo, en realidad no se explica cómo se puede hacer esto, especialmente el manejo de los punteros donde los datos están presentes en el disco. De manera similar, aunque muchos libros enseñan técnicas de búsqueda, no consideran los datos presentes en la memoria secundaria.

He revisado el libro de Knuth. Aunque discute estas ideas, todavía no entendía cómo aplicarlas en un lenguaje de alto nivel. ¿Hay alguna referencia que discuta estos detalles?

algorithms efficiency memory-management big-data Arani
fuente
1
Consulte "Conjuntos de datos masivos de minería" .
Dave Clarke
Puede echar un vistazo a la bibliografía completa de STXXL: la biblioteca de plantillas estándar para conjuntos de datos XXL .
Vor
En estos días, con grandes bases de datos como Oracle, DB2, SQL Server, normalmente nadie trabaja con grandes conjuntos de datos, si le interesa, puede consultar documentos relacionados con uno de los servidores de bases de datos, pero en la actualidad Martin Fowler y otras personas están tratando de pasar a NO SQL , también puede verificarlo. (pero hay demasiados aspectos en grandes bases de datos, como concurrencia, seguridad, ... no solo algoritmos rápidos).
@Dave, Vor: Gracias por sus referencias. Los revisaré e informaré si son lo que estoy buscando.
Arani
@SaeedAmiri: Entiendo eso, pero por lo que entiendo, almacenar datos en bases de datos solo es útil si los datos están altamente estructurados de alguna manera. Entonces, la secuencia de números y otros datos similares generalmente no se almacenan usando bases de datos. Además, los libros de texto de bases de datos no describen con mucho detalle desde el punto de vista del desarrollador de la base de datos. Si bien la mayoría de ellos mencionan que las bases de datos usan árboles B y B +, la mayoría no describe realmente CÓMO implementan estas estructuras de datos.
Arani

Respuestas:

2

Los libros de bases de datos son un buen ejemplo. Sin embargo, eche un vistazo a las estructuras de datos (y algoritmos) eficientes de E / S de campo. Que yo sepa, hay algunos cursos sobre este tema, pero muy pocos libros.

Consulte este libro: U. Meyer, P. Sanders y J. Sibeyn (eds.), Algorithms for Memory Hierarchies, Lecture Notes in Computer Science 2625, Springer, 2003.

Consulte estos cursos: http://www.win.tue.nl/~hermanh/teaching/2IL35/ http://www.daimi.au.dk/~large/ioS12/

y estas diapositivas: algo2.iti.kit.edu/sanders/courses/algen09-10/rdslides.pdf

AJed
fuente
1

El libro de la base de datos de Ramkrishnan y Gehrke discute estas cosas con cierto detalle.

Arani
fuente
¡Lo peor y más aburrido :)! aunque es una buena introducción a muchos temas interesantes en bases de datos y optimización de db.
AJed
0

Hoy en día, este campo se conoce como big data , y está evolucionando muy rápido y rápidamente en función de la fuerte conexión con la virtualización y la tecnología de bases de datos relacionales solo se ve como un subconjunto. Además, como se observa en los comentarios, las bases de datos de clave / valor y NoSQL son donde se están moviendo muchas nuevas innovaciones e impulso. Pero a partir de sus comentarios, parece estar más interesado en los principios y técnicas de diseño de bases de datos relacionales . Pruebe las siguientes referencias:

vzn
fuente
Realmente no he estudiado sistemas de bases de datos no relacionales, por lo que esa podría ser una respuesta plausible. Pero en realidad no estoy buscando libros de texto de bases de datos que describan el diseño de la base de datos. En cambio, un libro que lo describa desde el punto de vista del desarrollador de la base de datos (que explícitamente nos dice cómo se implementan las estructuras de datos para trabajar en discos) sería muy útil.
Arani
Odio admitir esto, pero falló un poco estas referencias. hay libros sobre algoritmos de bases de datos , pero hay muchos libros sobre diseño de bases de datos que realmente tratan sobre cómo organizar tablas, modelado de datos, normalización, índices, etc., conceptos como estos. Si bien estos están relacionados tangencialmente con su pregunta, no están realmente conectados exactamente. Básicamente, muchas de las estrategias para gestionar b-trees en las bases de datos modernas están al borde de los secretos comerciales. generalmente los árboles b se almacenan en "páginas" que se asignan e indexan dinámicamente. puede buscar mejores referencias en este momento.
vzn
Supongo que lo que realmente quiere es el diseño de almacenamiento de la base de datos física (que podría estar cubierto en algunas de esas referencias, o tal vez no). , Servidor MS SQL
vzn
vea también la optimización del plan de consultas
vzn
1
vea también los índices de árbol B + con algunas referencias a páginas de almacenamiento y apache derby , una implementación de almacenamiento / recuperación de árbol B en Java con detalles de implementación
vzn