HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm

Source

• Evernote/Papers/HyperLogLog in Practice Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm.md

Summary

이 논문은 데이터베이스 시스템에서 중요한 카디널리티 추정 알고리즘인 HyperLogLog(HLL)의 실용적 개선을 다룹니다. 기존 HLL 알고리즘을 수정하여 메모리 요구량을 줄이고, 특정 카디널리티 범위에서 정확도를 크게 향상시켰습니다. 이 개선된 알고리즘은 Google 시스템에 구현되어 평가되었으며, 원본 HLL과 동일하게 완벽한 병렬 처리와 단일 패스(single-pass) 추정이 가능합니다.

Key Points

• 기존 HyperLogLog 알고리즘의 메모리 효율성 및 정확도 개선
• 중요한 카디널리티 범위에서 성능 향상
• Google 시스템에서의 실제 구현 및 실증 평가
• 원본 알고리즘과 동일한 완벽한 병렬화 및 단일 패스 처리 유지

Related

• PASS Approximation: 휴리스틱 분석 및 설계 프레임워크

• ClangMR: 대규모 C++ 코드베이스 자동 리팩토링 시스템

• Reducing Lookups for Invariant Checking

• XMHF: 확장 가능 및 모듈식 하이퍼바이저 프레임워크

• Robust and Energy Efficient Multimedia Systems via Likelihood Processing

• Whare-Map: 대규모 컴퓨팅 환경의 이질성(Heterogeneity) 활용

• MillWheel: 인터넷 규모 내결함성 스트림 처리

• vlHMM 기반 컨텍스트 인식 검색

• FAST CLOUD: 클라우드 스토리지 지연 성능 개선을 위한 코딩 기법

• Efficient Estimation of Word Representations in Vector Space

• The Intervalgram: 대규모 커버송 인식을 위한 오디오 특징

• Collaborative Filtering beyond the User-Item Matrix: A Survey of the State of the Art and Future Challenges

• Image Annotation in Presence of Noisy Labels

• Omega: 대규모 컴퓨팅 클러스터를 위한 유연하고 확장 가능한 스케줄러

• Read-Performance Optimization for Deduplication-Based Storage Systems in the Cloud

• CPI2: 공유 컴퓨터 클러스터용 CPU 성능 격리

• Neighbor Selection and Weighting in User-Based Collaborative Filtering: A Performance Prediction Approach

• 대규모 데이터 스트림의 불확실성 추정

• Knowledge-Based Approaches to Information Management in Coalition Environments

• Science in the Cloud

• Enriching Documents with Examples: A Corpus Mining Approach

• Optimizing Google’s Warehouse Scale Computers: The NUMA Experience

• Knowledge-Based Approaches to Information Management in Coalition Environments

• 협업 필터링을 도입한 컨텍스트 광고 개선

• Nonlinear Latent Factorization by Embedding Multiple User Interests

• Obfuscatory Obscanturism: 상업적 민감성 시스템의 워크로드 트레이스 안전하게 공개하기

• Instant Foodie: Grassroots 평가로부터 전문가 평점 예측

• Beyond Text QA: Multimedia Answer Generation by Harvesting Web Information

• k-Order Statistic Loss 를 활용한 추천 시스템의 Learning to Rank

• Stock Selection Model Based on Machine Learning with Wisdom of Experts and Crowds

• 도대체 소비자에게 상품은 어떻게 추천하지

• Web Service Compositions with Fuzzy Preferences: A Graded Dominance Relationship-Based Approach

• A Multimedia Recommender System

• 강화학습 기반 음악 추천 시스템의 탐색-활용 균형

• 사용자 생성 콘텐츠의 순위 기반 메커니즘에 대한 게임 이론적 분석

• Optimizing Google’s Warehouse Scale Computers: The NUMA Experience

• 넷플릭스의 취향 예측 알고리즘: 인구통계학적 데이터의 한계

• 불신 정보를 활용한 사회적 추천 시스템 (Matrix Factorization)

• Spotify 의 협업 필터링 (Collaborative Filtering) 구현

• 개발자의 데이터 레이스 탐지 도구 사용 현황 (Google 사례)

• Jalopnik 신차 구매 결정 플로우차트

• LCARS: 공간 기반 아이템 추천 시스템

• 검색 광고의 예산 제약 최적화 (Optimizing Budget Constrained Spend in Search Advertising)

• 명시적 불신(Explicit Distrust)을 활용한 신뢰 기반 추천 시스템 강화

• 추천 시스템 분석: 아마존과 넷플릭스의 취향 예측 원리

• R 기반 맥주 추천 엔진 구현 (Beer Advocate 데이터)

• 음악 컨텍스트 데이터 기반 음악 유사도 및 추천 방법론 조사

• Latent Mixture of Discriminative Experts (LMDE)

• 게임 아이템 구매 이력에 word2vec 적용 사례

• Fluent 2016 - 그래프 이론을 활용한 추천 엔진 구축

• ReFr: 오픈소스 리랭커 프레임워크

• Patent Query Formulation by Synthesizing Multiple Sources of Relevance Evidence

• Weakly Supervised Learning of Object Segmentations from Web-Scale Video

• Query Reformulation Modeling using Query Distributions

• 자동화에 대한 신뢰 (Trust in Automation)

• P2P 소셜 태깅 네트워크에서의 온라인 Top-k 처리 개인화

• Netflix 개인화 및 추천 시스템 아키텍처 개요

• Discriminative Segment Annotation in Weakly Labeled Video

• A survey of trust in social networks

• Rolling Up Random Variables in Data Cubes

• Friendbook: 의미 기반 소셜 네트워크 친구 추천 시스템

• 그래프 전파를 통한 개인화 비디오 추천

• Effective and Robust Query-Based Stemming

• A term-based inverted index partitioning model for efficient distributed query processing

• Survey of local algorithms

• Continuous Birdsong Recognition Using Gaussian Mixture Modeling of Image Shape Features

• Transfer Learning In MIR: Sharing Learned Latent Representations For Music Audio Classification And Similarity

• Algebraic Optimization for Processing Graph Pattern Queries in the Cloud

• A Model for Context in the Design of Open Production Communities

• Joint consideration of energy-efficiency and coverage-preservation in microsensor networks

• Online Estimation of Evolving Human Visual Interest

• Generalized Optimal Response Time Retrieval of Replicated Data from Storage Arrays

• Approximate Recall Confidence Intervals

• Twitter 기반 YouTube 동영상 추천: 시간 인식 및 개인화

• Small-Document Approaches to Resource Selection 분석

• TSum: Fast, Principled Table Summarization

• Eureka: Edge-Based Discovery of Training Data for Machine Learning