ㅁ 지능형 캐싱

ㅇ 정의:

ㅇ 특징:

ㅇ 적합한 경우:

ㅇ 시험 함정:

ㅇ 시험 대비 “패턴 보기” 예시:

================================

1. Approximate Nearest Neighbor

ㅇ 정의:
대규모 데이터셋에서 특정 쿼리 벡터와 가장 가까운 벡터를 완전 탐색 대신 근사적으로 빠르게 찾아주는 검색 기법. 고차원 벡터 공간에서 거리 계산 비용을 줄이기 위해 해시, 트리, 그래프 기반 인덱스를 활용.

ㅇ 특징:
– 정확도(Recall)를 일부 희생하고 검색 속도를 획기적으로 향상
– LSH(Locality Sensitive Hashing), HNSW(Hierarchical Navigable Small World) 등의 기법 사용
– 메모리 사용량과 인덱스 구축 시간이 알고리즘별로 상이
– 온라인 추천, 이미지 검색, 문서 유사도 계산 등에 활용

ㅇ 적합한 경우:
– 데이터셋 규모가 수백만~수억 건 이상인 경우
– 실시간 응답이 필요한 검색/추천 시스템
– 완전 일치보다 빠른 응답이 중요한 상황

ㅇ 시험 함정:
– ANN은 항상 정확한 최근접 이웃을 반환하지 않음 → ‘정확한’이라는 표현이 나오면 X
– 고차원 데이터에서 차원의 저주를 완전히 해결하는 기법이 아님
– LSH는 해시 버킷에 따라 검색 누락 가능성이 있음

ㅇ 시험 대비 “패턴 보기” 예시:
O: “대규모 벡터 검색에서 응답 속도를 위해 근사치를 반환한다”
X: “항상 정확한 최근접 이웃을 반환한다”

ㅁ 추가 학습 내용

ANN 주요 알고리즘별 특징
– LSH(Locality Sensitive Hashing): 해시 기반, 인덱스 구축 속도가 빠름. 그러나 차원이 높아질수록 성능 저하 발생.
– HNSW(Hierarchical Navigable Small World): 그래프 기반, 높은 검색 정확도와 빠른 검색 속도 제공. 하지만 인덱스 메모리 사용량이 많음.

벡터 거리 계산 방식
– Euclidean 거리: 두 점 사이의 직선 거리 계산.
– Cosine similarity: 벡터 방향의 유사도 측정, 크기보다 방향 중요할 때 사용.
– Inner Product: 내적을 통한 유사도 계산, 크기와 방향 모두 고려 가능.

인덱스 튜닝 파라미터
– efSearch: 검색 시 탐색 범위를 조절, 값이 크면 정확도 증가하지만 속도 저하.
– efConstruction: 인덱스 구축 시 연결 정도를 조절, 값이 크면 검색 품질 향상 가능.
– nprobe: 검색 시 탐색할 클러스터 개수, 값이 크면 정확도 증가하지만 속도 저하.

실제 적용 사례
– 이미지·영상 검색: 예) Google 이미지 검색
– 전자상거래 추천 시스템
– 자연어 임베딩 검색: 문서 검색, 챗봇 응답 생성 등

시험 출제 포인트
– ‘근사’의 의미: 정확한 최근접이 아닌, 일정 허용 오차 내에서 빠르게 근접한 결과를 찾는 것.
– ANN과 KNN의 차이: KNN은 정확한 최근접 탐색, ANN은 근사 최근접 탐색으로 속도와 효율성 중시.
– ANN의 산업 적용 영역과 알고리즘 특성을 연결하는 응용 문제 가능성 높음.