[CE] Linear Search, Naive Search, Brute Force Search

Linear Search (Naive Search)

The simplest solution to the Nearest Neighbor Search problem is
to compute the distance from the query point to every other point in the database,
keeping track of the "best so far".

---

이 방식에서는 모든 가능한 데이터를 하나하나 비교하여, 원하는 결과를 찾는 방식.

• 따라서, 탐색 데이터 구조를 활용하지 않고,
• 단순히 데이터베이스의 모든 항목을 순차적으로 검사

Linear Search는 Naive Search 또는 Brute Force Search라고도 불리며,

$O(dN)$의 시간 복잡도를 가짐

• $N$ : the Cardinarlity of set (집합원소의 갯수, 데이터의 instance 갯수)
• $d$ : 각 instance의 feature수 (vector의 차원수)

장점.

• 탐색을 위한 추가적인 데이터 구조를 유지할 필요가 없음
• Linear Search은 데이터 저장을 제외하고는 추가적인 공간 복잡도를 요구하지 않음.

재밌게도 이 간단한 Naive search 가
고차원의 공간에서는 k-d Tree, R-tree 등의 space partitioning approaches 보다
평균적으로 더 나은 성능을 보이는 경우가 많음.

mlist = []

# query point의 수만큼의 feature vectors
for i in img_model:
    shortest = float('inf')
    # target 영상의 feature vector 수만큼 반복
    for j in img_target:
        d = dist(i,j)
        if d < shortest:
            match = j
            shortest = d
    if shortest < Th:
        mlist.append((i,match))

---

참고자료

• Weber, Schek, Blott. “A quantitative analysis and performance study for similarity search methods in high dimensional spaces”