Brute-force KNN Search (완전 탐색 최근접 이웃 검색)

개요

Brute-force KNN Search(완전 탐색 최근접 이웃 검색)는 쿼리 벡터와 데이터셋의 모든 벡터 간 거리를 정확히 계산하여 가장 가까운 k개의 이웃을 찾는 검색 방법이다. 완전 탐색(Exhaustive Search) 또는 선형 검색(Linear Search)이라고도 불린다.

100% 정확한 결과를 보장하지만, 데이터셋 크기에 비례하여 계산 비용이 증가하므로 소규모 데이터셋이나 정확도가 필수적인 경우에 주로 사용된다. 대규모 벡터 검색에서는 HNSW 같은 근사 최근접 이웃(ANN) 알고리즘을 사용하는 것이 일반적이다.

KNN 알고리즘과의 차이

혼동하기 쉬운 두 개념을 명확히 구분해야 한다:

구분	KNN 알고리즘	Brute-force KNN Search
분야	머신러닝 (지도 학습)	벡터 검색
목적	분류/회귀 예측	유사 벡터 찾기
입력	특징 벡터 + 레이블	쿼리 벡터 + 벡터 DB
출력	클래스 또는 예측값	k개의 최근접 벡터
최적화	KD-Tree, Ball Tree (저차원)	최적화 불가 (항상 O(N))
사용 예	손글씨 인식, 추천 시스템	시맨틱 검색, 유사 이미지 검색

핵심 차이:

KNN 알고리즘: 레이블이 있는 학습 데이터로 새로운 데이터를 분류하거나 예측
Brute-force KNN Search: 벡터 데이터베이스에서 유사한 벡터를 검색

KNN 알고리즘 내부에서 brute-force search를 사용할 수 있지만, 두 개념은 서로 다른 목적과 맥락에서 사용된다.

작동 원리

알고리즘

거리 계산: 쿼리 벡터 $q$ 와 데이터셋의 모든 벡터 $v_{1}, v_{2}, ..., v_{N}$ 간의 거리 계산
정렬: 거리를 기준으로 오름차순 정렬
선택: 가장 가까운 k개의 벡터 반환

의사 코드

def brute_force_knn(query, dataset, k, distance_metric):
    distances = []
 
    # 모든 벡터와의 거리 계산
    for vector in dataset:
        dist = distance_metric(query, vector)
        distances.append((dist, vector))
 
    # 거리 기준 정렬
    distances.sort(key=lambda x: x[0])
 
    # 상위 k개 반환
    return distances[:k]

거리 메트릭

일반적으로 사용되는 거리 함수:

유클리드 거리 (L2 Distance) $d (p, q) = \sum_{i = 1}^{D} (p_{i} - q_{i})^{2}$

코사인 유사도 (Cosine Similarity) $similarity (p, q) = \frac{p \cdot q}{∣∣ p ∣∣ \cdot ∣∣ q ∣∣}$

내적 (Inner Product) $score (p, q) = p \cdot q$

복잡도 분석

시간 복잡도

$O (N \cdot D)$

$N$ : 데이터셋 크기 (벡터 개수)
$D$ : 벡터 차원

예시:

100만 개 벡터, 768차원 → 약 7억 6800만 번 연산
1억 개 벡터, 1536차원 → 약 1조 5360억 번 연산

공간 복잡도

$O (N \cdot D)$

원본 벡터 데이터만 저장하면 되므로 공간 효율적이다. 별도의 인덱스 구조가 필요 없다.

확장성 문제

데이터셋 크기와 차원이 증가하면 검색 시간이 선형적으로 증가한다:

데이터셋 크기	차원	단일 쿼리 시간 (예상)
1만 개	128	~1ms
10만 개	384	~50ms
100만 개	768	~500ms
1000만 개	1536	~10초

장점과 단점

장점

100% 정확도: 항상 정확한 최근접 이웃 반환
단순성: 구현이 매우 간단하고 이해하기 쉬움
전처리 불필요: 인덱스 구축 시간이 없음 ( $O (1)$ )
메모리 효율: 원본 데이터만 저장하면 됨
동적 데이터: 삽입/삭제가 즉시 반영됨
고차원 안정성: 차원의 저주가 있지만 정확도는 유지

단점

느린 검색: $O (N)$ 시간 복잡도로 대규모 데이터에 부적합
확장성 부족: 데이터가 증가하면 선형적으로 느려짐
실시간 부적합: 밀리초 단위 응답이 필요한 경우 사용 불가
배치 쿼리 비효율: 여러 쿼리를 동시에 처리해도 $O (Q \cdot N \cdot D)$
병렬화 한계: 분산 처리해도 근본적인 복잡도는 동일

Brute-force vs ANN

정확도-속도 트레이드오프

측면	Brute-force Search	ANN (예: HNSW)
정확도	100%	95~99%
시간 복잡도	$O (N \cdot D)$	$O (lo g N \cdot D)$
공간 복잡도	$O (N \cdot D)$	$O (M \cdot N \cdot D)$
전처리 시간	없음	$O (N lo g N)$
단일 쿼리 (100만 벡터)	~500ms	~1ms
확장성	낮음	높음
사용 사례	소규모, 정확도 필수	대규모, 실시간 검색

언제 무엇을 사용할까?

Brute-force Search가 적합한 경우:

데이터셋 크기 < 10,000개
100% 정확도가 필수적인 경우
실시간 응답이 필요 없는 경우
인덱스 구축 비용을 피하고 싶은 경우
데이터가 자주 변경되는 경우
벤치마크나 정확도 검증 목적

ANN이 적합한 경우:

데이터셋 크기 > 100,000개
실시간 검색이 필요한 경우 (< 100ms)
95~99% 정확도로 충분한 경우
대규모 프로덕션 환경
높은 QPS(Queries Per Second) 요구

최적화 기법

brute-force 방식 자체는 최적화가 어려우나, 구현 수준의 개선은 가능하다.

1. 벡터화 연산 (Vectorization)

NumPy, BLAS 등을 활용한 행렬 연산으로 속도 향상:

import numpy as np
 
def brute_force_knn_vectorized(query, dataset, k):
    # 모든 거리를 한 번에 계산 (벡터화)
    distances = np.linalg.norm(dataset - query, axis=1)
 
    # 상위 k개 인덱스 찾기
    top_k_indices = np.argpartition(distances, k)[:k]
 
    return top_k_indices

2. GPU 가속

CUDA, cuML 등을 사용하여 대량의 거리 계산을 병렬화:

CPU: 순차 계산
GPU: 수천 개 코어로 병렬 계산
수십~수백 배 속도 향상 가능

3. 사전 필터링

쿼리에 메타데이터 조건을 추가하여 검색 대상 축소:

# 예: 카테고리가 "electronics"인 것만 검색
filtered_dataset = dataset[dataset['category'] == 'electronics']
results = brute_force_knn(query, filtered_dataset, k)

4. 조기 종료 (Early Termination)

정렬 대신 부분 정렬(partial sort) 사용:

import heapq
 
def brute_force_knn_heap(query, dataset, k):
    # 최소 k개만 유지하는 힙 사용
    heap = []
 
    for vector in dataset:
        dist = distance(query, vector)
 
        if len(heap) < k:
            heapq.heappush(heap, (-dist, vector))
        elif dist < -heap[0][0]:
            heapq.heapreplace(heap, (-dist, vector))
 
    return [v for _, v in heap]

5. 근사 거리 계산

정확한 거리 대신 근사값 사용:

제곱근 생략: L2 거리에서 제곱근 계산 생략
양자화: 벡터를 저정밀도로 변환 (int8, float16)

구현 예시

NumPy 기본 구현

import numpy as np
 
class BruteForceKNN:
    def __init__(self, metric='euclidean'):
        self.metric = metric
        self.data = None
 
    def fit(self, X):
        """데이터 저장"""
        self.data = np.array(X)
 
    def search(self, query, k=10):
        """k개의 최근접 이웃 검색"""
        query = np.array(query)
 
        if self.metric == 'euclidean':
            # L2 거리 계산
            distances = np.linalg.norm(self.data - query, axis=1)
        elif self.metric == 'cosine':
            # 코사인 유사도 계산 (1 - similarity로 거리화)
            norm_data = self.data / np.linalg.norm(self.data, axis=1, keepdims=True)
            norm_query = query / np.linalg.norm(query)
            similarities = np.dot(norm_data, norm_query)
            distances = 1 - similarities
 
        # 상위 k개 인덱스
        top_k_indices = np.argpartition(distances, k)[:k]
        top_k_indices = top_k_indices[np.argsort(distances[top_k_indices])]
 
        return top_k_indices, distances[top_k_indices]
 
# 사용 예시
knn = BruteForceKNN(metric='euclidean')
knn.fit(vectors)  # N x D 행렬
indices, distances = knn.search(query_vector, k=10)

Scikit-learn 사용

from sklearn.neighbors import NearestNeighbors
 
# Brute-force 알고리즘 명시
knn = NearestNeighbors(n_neighbors=10, algorithm='brute', metric='euclidean')
knn.fit(vectors)
 
# 검색
distances, indices = knn.kneighbors([query_vector])

FAISS 사용

import faiss
import numpy as np
 
# 차원
d = 768
 
# Brute-force 인덱스 (Flat)
index = faiss.IndexFlatL2(d)  # L2 거리
# 또는
# index = faiss.IndexFlatIP(d)  # 내적
 
# 데이터 추가
index.add(vectors)  # N x d numpy array
 
# 검색
k = 10
distances, indices = index.search(query_vectors, k)

벡터 데이터베이스에서의 구현

Elasticsearch

POST /my-index/_search
{
  "query": {
    "script_score": {
      "query": {"match_all": {}},
      "script": {
        "source": "cosineSimilarity(params.query_vector, 'vector_field') + 1.0",
        "params": {"query_vector": [0.1, 0.2, ...]}
      }
    }
  }
}

특징:

script_score는 brute-force 방식
소규모 데이터셋이나 필터링 후 사용 권장
대규모에서는 knn 검색 사용

OpenSearch

GET /my-index/_search
{
  "query": {
    "script_score": {
      "query": {"match_all": {}},
      "script": {
        "source": "1 / (1 + l2Squared(params.query_vector, doc['vector_field']))",
        "params": {"query_vector": [0.1, 0.2, ...]}
      }
    }
  }
}

Pinecone

Pinecone은 항상 인덱스 기반 검색을 사용하며, 순수 brute-force 옵션은 제공하지 않는다.

실무 활용 패턴

1. 하이브리드 검색

1차로 메타데이터 필터링 → 2차로 brute-force 벡터 검색:

# 1차: 필터링 (카테고리, 날짜 등)
filtered_data = data[data['price'] < 100]
 
# 2차: Brute-force 검색
results = brute_force_knn(query, filtered_data, k=10)

2. 재순위화 (Re-ranking)

1차로 ANN 검색 → 2차로 brute-force 정밀 검색:

# 1차: ANN으로 후보 100개 추출
candidates = ann_index.search(query, k=100)
 
# 2차: Brute-force로 정확한 상위 10개 선택
top_10 = brute_force_knn(query, candidates, k=10)

3. 정확도 벤치마킹

ANN 알고리즘의 recall을 측정할 때 ground truth로 사용:

# Ground truth (정답)
true_neighbors = brute_force_knn(query, dataset, k=100)
 
# ANN 결과
ann_neighbors = hnsw_index.search(query, k=100)
 
# Recall 계산
recall = len(set(true_neighbors) & set(ann_neighbors)) / len(true_neighbors)

4. 소규모 임베딩 캐시

자주 사용되는 소량의 벡터를 메모리에 캐시:

class VectorCache:
    def __init__(self, max_size=10000):
        self.cache = {}  # 최대 1만 개
        self.knn = BruteForceKNN()
 
    def search(self, query, k=10):
        # 캐시된 벡터에서만 brute-force 검색
        return self.knn.search(query, k)

참고 자료

학술 자료

Cover, T., & Hart, P. (1967). “Nearest neighbor pattern classification” - 최근접 이웃 개념의 이론적 기초

기술 문서

Elasticsearch: kNN Search - Exact vs Approximate kNN 비교
OpenSearch: k-NN Search - Script score를 이용한 exact 검색
scikit-learn: Nearest Neighbors - Brute-force 알고리즘 구현
FAISS: IndexFlat - Meta의 brute-force 인덱스

비교 및 분석

Microsoft Learn: kNN and ANN algorithm comparison - kNN과 ANN 상세 비교
Elastic Blog: aNN vs kNN - 정확도와 속도 트레이드오프
Wikipedia: Nearest neighbor search - 다양한 검색 방법 비교

📚개자봉의 공책

분류

최근 글

MacOS에서 Docker를 이용해서 OpenSearch 3.2, Nori 플러그인, Dashboards 설치하기

Contextual Retrieval

Attention is All You Need (어텐션이 전부다)