대략적인 쿼리로 데이터를 저장하려면 어떻게합니까?

Question

빠른 액세스 (O (n)보다 낫다)로 데이터를 저장하는 방법을 찾으려고합니다.

내 데이터베이스는 일부 항목에 대한 정보를 나타내는 데이터 (4096 바이트 문자열)로 구성됩니다.
문제는 쿼리가 절대 정확하지 않습니다. 하나의 Item을 얻은 다음 F(a,b) 함수를 사용하여 가장 가까운 항목을 찾아야합니다.

단지 예 :

1234 
3456 
6466 
F(a,b) = return % of similar digits 

GetClosest(1233,F) = 1234 

문제가 있음을 F (a가, b) 복잡한 알고리즘 (안 적절한 측정)이다.

지금은 전체 데이터베이스를 검색하여 가장 적합한 항목을 검색합니다.
복잡성을 빨리 발견 할 수있는 종류의 트리 또는 다른 클러스터 데이터베이스 유형이 있습니까?

추가 정보 :

F는 % 비율의 유사도 값을 돌려 준다. 여기서 100 %는 완벽한 일치입니다.

Answer 1

죄송합니다. 설명하지 않은 문제에 대한 구조가 더 이상 없으면 "아마도 그렇지 않습니다"라고 대답합니다. 4096 바이트 문자열을 사용하면 the curse of dimensionality이 발생합니다.

문자열이 짧고 문자열의 큰 부분에 대해 가장 가까운 일치 항목이 동일 할만큼 충분한 데이터가있는 경우에는 여러 트리 구조의 데이터를 서로 다른 청크에 인덱싱하여 저장할 수 있습니다. 끈. 가능성이 높으면 가장 가까운 것이 가까운 나무에 가까운 요소를 기반으로 가장 가까운 것으로 증명할 수 있습니다. 그러나 문자열의 크기와 컴퓨터에 저장할 수있는 제한된 데이터가 있으면이 방법이 효과가 없을 수 있습니다.

그렇다면 정확한 근접성 또는 다소 근접한 것이 필요합니까? 가능성이있는 것만 닫으면, 여러 비트의 임의의 희소 샘플로 인덱스 할 수 있습니다. 검색시 요소 중 하나와 정확히 일치하는 요소 만 검사 할 수 있습니다. 이렇게하면 검색 공간이 크게 줄어들고 가까운 이웃을 더 적게 거부 할 수 있으며 합리적 (종종 잘못 되었더라도)의 답을 얻을 수 있습니다.

Answer 2

각 데이터에 '점수'를 지정할 수있는 방법이 있습니까?

점수에 따라 데이터를 색인/순서 지정할 수 있습니다.

검색 할 때 검색 기준에 점수를 지정하고 가장 가까운 점수를 가진 항목을 찾으십시오.

"차이"에 대한 정의와 데이터에 크게 의존합니다.