Reducing Lookups for Invariant Checking

Source

• Evernote/Papers/Reducing Lookups for Invariant Checking.md

Summary

이 문서는 불변식(Invariant) 검증 시 조회(Lookup) 횟수를 줄이는 기법을 다룬 Google 연구 논문의 요약이다. 실제 쿼리 언어의 핵심을 포괄하는 간단한 쿼리 언어 기반의 형식 모델을 제시하고, 불변식 표현을 단순화하는 알고리즘과 그 정확성에 대한 기계적 검증 가능한 증명을 제공한다. 일반적인 불변식 검증 문제가 co-NP hard 임을 보이며, 실용적인 해결책은 근사해(Approximation)여야 함을 지적한다. 사례 연구에서 이러한 기법을 적용해 성능이 10배 이상 향상되었음을 확인했다.

Key Points

• 불변식 검증 시 조회(Lookup) 비용 절감을 위한 알고리즘 제안
• 단순화된 불변식 표현 및 기계적 검증 가능한 정확성 증명 제공
• 일반적인 불변식 검증 문제는 co-NP hard 임을 증명 (근사해 필요)
• 사례 연구에서 10배 이상의 성능 개선 효과 확인

Related

• Effective and Robust Query-Based Stemming

• XML 데이터에 대한 키워드 쿼리의 컨텍스트 기반 다양화

• 웹사이트 구조 개선을 통한 사용자 탐색 효율화

• 대규모 저장소에서의 효율적인 비디오 스트림 모니터링 및 유사 중복 탐지

• Patent Query Formulation by Synthesizing Multiple Sources of Relevance Evidence

• Enriching Documents with Examples: A Corpus Mining Approach

• 웹 검색의 내재적 다양성(Intrinsic Diversity)과 전체 세션 관련성

• 리팩토링 개요 및 기법 요약

• Efficient Index-Based Snippet Generation

• k-parity 테스트의 비적응적 쿼리 복잡도

• Trustworthy Proxies: Virtualizing Objects with Invariants

• 비디오 검색 결과의 의미론적 계층 구조화

• Small-Document Approaches to Resource Selection 분석

• 규칙 기반 엔티티 해결 (Rule-Based Entity Resolution)

• Approximate Recall Confidence Intervals

• 구글 비교 도구 (Google Comparison Tool)

• X-Class: XML 문서 구조 기반 연관 분류

• XXS: 압축된 XML 문서에서의 효율적인 XPath 평가

• Deep Web 소스의 관련성 및 신뢰도 평가 (Inter-source Agreement 기반)

• Spaces, Trees, and Colors: 시퀀스 기반 문서 검색의 알고리즘 풍경

• 위키피디아 문서 품질 평가 알고리즘

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

• 웹 애플리케이션 모델 저장소의 텍스트 및 내용 기반 검색

• 정보 기하학을 통한 순수 고차 단어 연관성 마이닝

• 피드백 세션을 통한 사용자 검색 목표 추론 알고리즘

• 대용량 텍스트 컬렉션에서의 효율적 퍼지 검색

• TSum: Fast, Principled Table Summarization

• Scalable Database-Driven Reverse Dictionary

• Query Reformulation Modeling using Query Distributions

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

• Source-Side Classifier Preordering for Machine Translation

• HEADY: 이벤트 패턴 클러스터링을 통한 뉴스 헤드라인 추상화

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

• Semantic Queries by Example

• Efficient Estimation of Word Representations in Vector Space

• 온라인 건강 검색의 콘텐츠 편향성

• 통계적 기계 번역 표현을 활용한 교차 언어 정보 검색

• 수치 추상 도메인을 이용한 프로세스 발견 알고리즘

• Supporting Flexible, Efficient, and User-Interpretable Retrieval of Similar Time Series

• 웹상 어린이의 검색 및 브라우징 행동 분석

• 온라인 리뷰 요약: Starlet 접근법

• 영어 책 코퍼스 기반 시계열 구문 N-그램 데이터셋

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

• URL 기반 웹 페이지 언어 분류 기술 종합 연구