가장 적합한 검색 알고리즘은 무엇입니까?

Question

나는 지금 문제에 직면하고 있으며 올바른 해결책이 무엇인지 잘 모르겠습니다. 나는 그것을 설명하려고 노력할 것이고 누군가 나를 위해 좋은 해결책을 가지기를 바란다 :

나는 두 개의 큰 데이터 배열을 가지고있다. 50^3 ~ 150^3 데이터 샘플 (대개 50과 100 사이의 희귀 최악의 경우 시나리오 150)을 사용하여 탐색하는 대상입니다. 모든 샘플에 대해 같은 크기의 다른 구조체에 대한 쿼리를 만들고 싶습니다 (전체 조합 수가 너무 많아서 모두 탐색 할 수는 없습니다).

쿼리가 정확히 예측할 수는 없지만 대개 다음과 같습니다. 구조체 필드가 ​​있습니다. (편집 : 총 10 ~ 20 개의 int 필드와 비슷합니다). 쿼리는 다음과 같습니다. < 20 및 B> 100, D> 200 예, SQL과 매우 비슷합니다.

데이터베이스에 넣으려고했지만 실제로는 독립형 데이터베이스가 될 것이므로 RAM을 사용하여 작업 속도를 더욱 빠르게 할 수 있습니다 (속도는 필수 기준 임).

GPGPU를 사용하여 무언가를 시도해 보았지만 검색이 병렬 일 수는 있지만 끔찍한 생각 인 것 같습니다. 예측할 수없는 결과를 검색하는 것이 좋은 아이디어는 아닙니다. (if if 누군가 내 이해가 옳다면 내가이 해결책을 용서해야한다는 것을 확인하는 데 도움이 될 것이라고 말할 수있다.) 편집 : 결과의 nubmer는 쿼리 특성으로 인해 예측할 수 없지만 적합성이 낮은 조합을 찾기 위해 목적이 적절하기 때문에 상당히 낮습니다.

그런 다음 DB를 사용할 수 있으므로 RAM B- 트리? 그것은 해결책에 가까운 것처럼 보이지만 그것은 무엇입니까? 그렇다면 색인을 어떻게 작성해야합니까? 다차원 검색이 항상 존재하기 때문에 실제로 다차원 인덱스를 수행 할 수 있습니까? 아마도 UB-Tree 나 R-tree가 그 일을 할 수있을 것입니다.하지만 두 번째 데이터 샘플에서는 중복이있을 수 있으므로 R-TREE를 적용 할 수 없습니까?). 문제는, 지금 당장은 모든 사람들을 제대로 이해하고 있는지 확신 할 수 없기 때문에, 나무 중 하나 (그리고 gpgpu, 심지어 생각하지도 않았던 솔루션)를 알고 있다면, 어느 솔루션을 사용해야하는지 알 수 있습니다. 탐구하고 배우고 실행한다.

Answer 1

• GPGPU 때문에 당신이 그들의 능력에 의해 당신이 우리에게 나는 티탄 X 계층 카드가 충분하지 않을 것이라는 가정하고 이러한 샘플의 데이터 크기를 말하는되지 않기 때문에 제한되어 있다는 사실에 적절한 선택이 아니다. TESLA 나 FirePro와 같이 정말 거칠 수 있다면 속도가 중요하다는 사실을 언급 한 이래로 실제로 가치가 있습니다. 그러나 나는 이러한 것들이 당신의 예산에서 벗어났다는 것을 추측 할 것이며, CUDA 나 OpenCL을 배워서 여기저기서 일반적으로 통하는 고통을 만들어야한다는 것을 고려할 때, 필자의 생각은 "아니오"입니다.

• 예기치 않은 결과가 있으며 이는 나쁜 것입니다. 당신은 "다소"필요한 공간의 양을 계산하는 수식을 개발해야합니다. 그렇지 않으면 용량 오류/충돌을 얻기 위해 꽤 오랫동안 프로그램을 작업하게되어 실망하게 될 것입니다. 반면에 RAM 용량이 충분하지 않으면 필요한 경우 저장소에서 "데이터베이스 스타일"데이터를 가져와 작업 할 수 있습니다 (구현을 예약하기 때문에 구현하기가 상당히 어렵습니다).

• 주문품을 준비 할 시간이 있다면 여기에 유용한 링크가 있습니다.기억하세요, 당신이 많은 우연히 발견하려고하지만, 당신이 그것을 할 때 물건의 톤 배운 것 : 내 생각에

  https://www.quora.com/What-are-some-fast-similarity-search-algorithms-and-data-structures-for-high-dimensional-vectors 
  

• 를 메모리 데이터베이스에서 가장 쉬운이며 동시에 가장 신뢰할 수있는 속도에 타협하지 않고 할 일. 어떤 것을 구현할 것인가? 나는 MemSQL이 좋은 것이라고 생각한다.