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

Source

• Evernote/Inbox/Efficient fuzzy search in large text collections.md

Summary

본 논문은 대규모 텍스트 컬렉션(100GB 이상)에서 실시간(interactive) 퍼지 풀텍스트 검색을 가능하게 하는 새로운 전처리 기법을 제시합니다. 기존 역색인(inverted-index) 방식은 10GB 이상의 데이터에서 100ms 미만의 응답 시간을 달성하지 못하는 한계가 있었으나, 제안된 방법은 단일 머신에서도 대용량 데이터에 대해 실시간 검색 성능을 확보합니다. 유사도 측정 기준으로는 오타 허용(예: algorithm-algoritm) 및 접두사 유사성(예: alori-algorithm) 두 가지를 다룹니다.

Key Points

• 기존 역색인 방식은 대용량(>10GB) 퍼지 검색에서 실시간 응답(100ms 미만) 달성에 실패함
• 새로운 전처리 기법을 통해 단일 머신에서 100GB 텍스트 컬렉션에 대해 실시간 검색 가능
• 오타 허용 매칭 및 접두사 유사성 매칭 두 가지 유사도 측정 기준 적용

Related

• Efficient Estimation of Word Representations in Vector Space

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

• 온라인 정확한 문자열 매칭 문제: 최근 결과 리뷰

• Sparse Hashing (SH) for Fast Multimedia Search

• Incremental Text Indexing for Fast Disk-Based Search

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

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

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

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

• Route-Saver: 위치 기반 서비스의 효율적 쿼리 처리

• Efficient Inference and Structured Learning for Semantic Role Labeling

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

• E-Tree: 데이터 스트림용 앙상블 모델 효율적 인덱싱 구조

• 실시간 트윗 검색을 위한 블룸 필터 체인(Bloom Filter Chains) 기반 후보 생성

• SACA-K: 상수 알파벳에 대한 실용적 선형 시간 접미사 정렬

• Second Chance: 검색 엔진의 하이브리드 결과 캐싱 및 프리페칭 접근법

• 대규모 다중 라벨 전파를 위한 효율적인 희소 그래프 구성

• Fast Near-Duplicate Image Detection Using Uniform Randomized Trees

• Rolling Up Random Variables in Data Cubes

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

• Regularized Latent Semantic Indexing (RLSI): 대규모 토픽 모델링을 위한 새로운 접근법

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

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

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

• Patent Query Formulation by Synthesizing Multiple Sources of Relevance Evidence

• Effective and Robust Query-Based Stemming

• Reducing Lookups for Invariant Checking

• Scalable Database-Driven Reverse Dictionary

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

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

• Efficient Index-Based Snippet Generation

• Small-Document Approaches to Resource Selection 분석

• TSum: Fast, Principled Table Summarization

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

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

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

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

• Query Reformulation Modeling using Query Distributions

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

• Similarity-based Clustering by Left-Stochastic Matrix Factorization

• Reversible Data Hiding With Optimal Value Transfer

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

• Approximate Recall Confidence Intervals

• 대규모 소셜 네트워크에서의 비용 효율적 바이럴 마케팅 (VirAds)

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

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

• 트위터의 구조적 차이와 시간성이 검색 효과성에 미치는 영향

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

• Enriching Documents with Examples: A Corpus Mining Approach

• Data Enriched Linear Regression

• Source-Side Classifier Preordering for Machine Translation

• Efficient Time-Stamped Event Sequence Anonymization

• 웹 검색 쿼리의 감정 분석 및 활용

• Query-Adaptive Image Search With Hash Codes

• PhishStorm: 스트리밍 분석을 통한 피싱 탐지

• 대규모 그래프 및 라벨 세트에서의 효율적이고 정확한 라벨 전파

• Point Representation for Local Optimization: Towards Multi-Dimensional Gray Codes

• 실시간 스토리 식별을 위한 스트리밍 환경에서의 밀집 부분 그래프 유지

• 이미지 주석 및 검색을 위한 Feature-Word-Topic 모델

• Semantic Queries by Example

• FSR: 안전한 인터도메인 라우팅을 위한 형식 분석 및 구현 툴킷

• 웹 검색 행동의 시간적 동역학: 학습, 모델링 및 예측

• 일관된 멀티스트림 스토리지의 대역폭 효율성 개선 (Wasteless Journaling)

• Circle & Search: 속성 기반 신발 검색 시스템

• 검색 엔진 순위 개선: 신화와 현실 (Myths and Reality)

• 고속 저장 장치를 활용한 고성능 SAN 구축 방향

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

• 딥웹과 다크웹 탐색 및 검색 엔진 개요

• 위키백과 링크 의미소거를 위한 토픽 모델링

• Iustitia: 정보 이론적 접근을 통한 고속 플로우 성격 식별

• Task Trail: 사용자 검색 행동의 효과적인 세분화

• 훈련 레이블 정제를 통한 텍스트 분류 정확도 향상

• Efficient Closed-Form Solution to Generalized Boundary Detection

• 고성능 저장 매체에서의 버퍼 캐싱 유효성

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

• 검색 엔진 쿼리 로그를 통한 사용자 작업(Task) 발견

• Supervised Robust Discrete Multimodal Hashing (SRDMH)

• 다중 사용자 생성 영상 기반 미적 가이드 요약 (Aesthetics-Guided Summarization)

• A Top-Down Approach for Video Summarization

• Topsy: 트위터 전량 데이터 검색 서비스

• Biperpedia: 검색 애플리케이션을 위한 온톨로지

• Smooth Nonnegative Matrix Factorization for Unsupervised Audiovisual Document Structuring

• 3D 객체 검색을 위한 시맨틱 시그니처 학습

• 계층 구조(Taxonomy) 존재 하의 시간적 변화 패턴 발견 (HiGen)

• Browse-to-Search: 시각적 엔티티를 활용한 탐색적 검색

• 인터넷 TV를 위한 콘텐츠 및 사회적 관련성 기반 개인화 광고 추천

• A Hamming Embedding Kernel with Informative Bag-of-Visual Words for Video Semantic Indexing

• 검색 결과 페이지의 해적들 (Pirates of the search results page)

• GeoVisNews: 뉴스 조직 및 검색 시스템

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

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

• 구글의 대화형 검색 (2013)

• Discriminative Segment Annotation in Weakly Labeled Video

• Attribute-Augmented Semantic Hierarchy (A2SH) for CBIR

• Neighborhood Preserving Codes for Assigning Point Labels: Applications to Stochastic Search

• Near-duplicate video retrieval: Current research and future trends

• Fast Data Processing with Spark (도서 소개)

• 음식점명 군집화를 위한 문자열 유사도 계산 (Cosine Similarity)

• Fast, Accurate Detection of 100,000 Object Classes on a Single Machine (Technical Supplement)

• Cross-Media Tag Transfer (CMTT): 이미지에서 비디오로 태그 지식 이전

• 다중 모드 특징 표현 및 시간 피라미드 매칭을 통한 콘텐츠 기반 복제 탐지

• CSS를 이용한 클라이언트 측 전체 텍스트 검색

• 진단 검색에서의 캡션과 편향