대규모 데이터 세트를 위한 알고리즘과 데이터 구조

Dzejla Medjedovic 지음 | 김정선 옮김

다이피아 2023년 08월 30일 출간

작품소개

책소개

확률 및 디스크 기반 데이터 구조 및 알고리즘에 대한 액세스 가능하고 아름답게 설명된 소개입니다.

Marcus Young, Prosper Marketplace

최신 데이터 세트가 방대해지면서 기존의 데이터 구조와 알고리즘은 한계에 도달했습니다. 이 재미있고 실용적인 가이드에서는 대규모 분산 데이터 집합도 안정적으로 처리할 수 있는 최신 기술을 소개합니다.

대규모 데이터 세트를 위한 알고리즘 및 데이터 구조에서는 다음에 대해 안내합니다.

실제 문제에 대한 확률론적 스케치 데이터 구조
애플리케이션에 적합한 데이터베이스 엔진 선택
효율적인 온디스크 데이터 구조 및 알고리즘 평가 및 설계
대규모 시스템과 관련된 알고리즘 트레이드 오프 이해하기
스트리밍 데이터에서 기본 통계 도출
스트리밍 데이터를 올바르게 샘플링
제한된 공간 리소스로 백분위수 계산

대규모 데이터 세트를 위한 알고리즘 및 데이터 구조는 최신 빅 데이터 애플리케이션을 처리하는 데 완벽한 새로운 방법의 도구 상자를 보여줍니다. Google, Facebook 및 진정으로 방대한 양의 데이터로 작동하는 기타 엔터프라이즈 애플리케이션을 뒷받침하는 새로운 데이터 구조 및 알고리즘을 탐색합니다. 이러한 효과적인 기술은 금융에서 텍스트 분석에 이르기까지 모든 분야에 적용할 수 있습니다. 그래픽, 일러스트레이션 및 실습 업계 사례를 통해 복잡한 아이디어를 프로젝트에 실용적으로 구현할 수 있으며 수수께끼로 풀 수 있는 수학적 증명이 없습니다. 이 독특한 가이드를 따라 작업하면 데이터의 정확성을 유지하면서 공간을 절약할 수 있는 최적의 지점을 찾을 수 있습니다.

기술에 대해

표준 알고리즘 및 데이터 구조는 대규모 분산 데이터 세트에 적용될 때 느려지거나 완전히 실패할 수 있습니다. 빅 데이터용으로 설계된 알고리즘을 선택하면 시간을 절약하고 정확도를 높이며 처리 비용을 줄일 수 있습니다. 이 독특한 책은 최첨단 연구 논문을 디스크와 클라우드에서 스케치, 스트리밍 및 대규모 데이터 세트 구성을 위한 실용적인 기술로 추출합니다.

책에 대해

대규모 데이터 세트를 위한 알고리즘 및 데이터 구조에서는 대규모 분산 데이터에 대한 처리 및 분석 기술을 소개합니다. 업계 이야기와 재미있는 삽화로 가득한 이 친근한 가이드는 복잡한 개념도 쉽게 이해할 수 있도록 합니다. Bloom 필터, Count-min 스케치, HyperLogLog 및 LSM-트리와 같은 강력한 알고리즘을 자신의 사용 사례에 매핑하는 방법을 배우면서 실제 사례를 탐색하게 됩니다.

목차

머리말
감사의 말
이 책에 대하여
저자 소개
역자 서문

1장. 소개
1.1 예제
1.2 이 책의 구성
1.3 다른 책과의 차이점과 그 대상
1.4 대규모 데이터가 오늘날의 시스템에서 어려운 문제인 이유
1.5 하드웨어를 염두에 둔 알고리즘 설계

Part 1. 해시 기반 스케치

2장. 해시 테이블 및 최신 해싱 검토
2.1 유비쿼터스 해싱
2.2 데이터 구조 집중 강좌
2.3 최신 시스템의 사용 시나리오
2.4 O(1) - 무엇이 중요한 문제인가?
2.5 충돌 해결: 이론 대 실제
2.6 사용 시나리오: Python의 dict의 작동 방식
2.7 MurmurHash
2.8 분산 시스템용 해시 테이블: 일관된 해싱

3장. 근사 멤버십: Bloom 및 Quotient Filter
3.1 작동 방식
3.2 사용 사례
3.3 간단한 구현
3.4 Bloom Filter 구성
3.5 약간의 이론
3.6 Bloom Filter 적용 및 대안
3.7 Quotient filter
3.8 Bloom filter와 Quotient filter의 비교

4장. 빈도 추정 및 Count-Min Sketch
4.1 다수(과반수) 요소(Majority element)
4.2 Count-Min Sketch: 작동 방식
4.3 사용 사례
4.4 Count-Min Sketch의 오차 vs. 공간
4.5 Count-Min Sketch의 간단한 구현
4.6 Count-Min Sketch를 사용한 Range queries

5장. 카디널리티 추정 및 HyperLogLog
5.1 데이터베이스의 개별 항목 계산
5.2 HyperLogLog 증분 설계
5.3 사용 사례: HLL로 worm 잡기
5.4 하지만 어떻게 작동할까요? - 작은 실험
5.5 사용 사례: HyperLogLog를 사용한 집계

Part 2. 실시간 분석
6장. 스트리밍 데이터: 모든 것을 하나로 모으기
6.1 스트리밍 데이터 시스템: 메타 예시
6.2 데이터 스트림의 실제 제약 및 개념
6.3 수학 비트: 샘플링 및 추정

7장. 데이터 스트림에서 샘플링
7.1 랜드마크 스트림의 샘플링
7.2 슬라이딩 윈도우에서의 샘플링
7.3 샘플링 알고리즘 비교

8장. 데이터 스트림의 근사 분위수
8.1 정확한 분위수
8.2 근사 분위수
8.3 t-digest 작동 방식
8.4 Q-digest
8.5 시뮬레이션 코드 및 결과

Part 3. 데이터베이스 및 외부 메모리 알고리즘의 데이터 구조
9장. 외부 메모리 모델 소개
9.1 외부 메모리 모델: 서두
9.2 예제 1: 최소값 찾기
9.3 예제 2: 이진 검색
9.4 최적의 검색
9.5 예제 3: K 정렬 목록 병합
9.6 다음 단계

10장. 데이터베이스용 데이터 구조: B-트리, Bε-트리, LSM-트리
10.1 인덱싱 작동 방식
10.2 이 장에서 다루는 데이터 구조
10.3 B-트리
10.4 수학 비트: B-트리 조회가 외부 메모리에서 최적인 이유는 ?
10.5 Bε-트리
10.6 로그 구조 병합 트리 (LSM-trees)

11장. 외부 메모리 정렬
11.1 정렬의 사용 사례
11.2 외부 메모리에서 정렬할 때의 문제: 예시
11.3 외부 메모리 병합 정렬(M/B-way 병합 정렬)
11.4 외부 퀵-정렬은 어떨까요?
11.5 수학 비트: 외부 메모리 병합 정렬이 최적인 이유
11.6 마무리

참고 문헌

작가정보

저자(글) Dzejla Medjedovic

Dzejla Medjedovic 박사는 2014년에 뉴욕 Stony Brook University의 컴퓨터 과학과 응용 알고리즘 연구실에서 박사 학위를 받았습니다. 또한 Microsoft에서 시간을 보냈습니다. Dzejla는 교육, 컴퓨터 과학 교육 촉진 및 기술 이전에 열정적입니다. 현재 그녀는 Social Explorer, Inc.에서 데이터 부사장으로 일하고 있습니다.

번역 김정선