특정 서브 세트가있는 세트를 찾습니다

https://stackoverflow.com/questions/494502

20-08-2019
|

문제

저는 물리학 대학원생이며 수백 기가 바이트의 데이터를 정렬하고 요청할 때 해당 데이터의 슬라이스를 반환하는 코드를 작성하고 있습니다. 여기에 트릭이 있습니다. 이런 종류의 데이터를 정렬하고 검색하는 데 좋은 방법이 없습니다.

내 데이터는 본질적으로 많은 수의 숫자 세트로 구성됩니다. 이 세트는 그 안에 1 ~ N 숫자를 포함 할 수 있으며 (세트의 99.9%에서는 N이 15 미만)이 세트의 약 1.5 ~ 20 억이 있습니다 (불행히도이 크기는 무차별 인력 검색을 배제합니다).

K 요소가있는 세트를 지정할 수 있어야하고 지정된 서브 세트가 포함되어있는 K+1 요소 이상의 모든 세트가 나에게 반환됩니다.

Simple Example:
내 데이터에 대한 다음 세트가 있다고 가정합니다.
(1,2,3)
(1,2,3,4,5)
(4,5,6,7)
(1,3,8,9)
(5,8,11)

내가 요청을한다면 (1,3) 나는 세트를 가질 것이다 : (1,2,3), (1,2,3,4,5) 및 (1,3,8,9).
요청 (11)은 세트를 반환합니다 : (5,8,11).
요청 (1,2,3)은 세트를 반환합니다 : (1,2,3) 및 (1,2,3,4,5)
요청 (50)은 세트를 반환하지 않습니다.

지금까지 패턴은 명확해야합니다. 이 예제와 내 데이터의 주요 차이점은 내 데이터와 함께 세트가 더 크고, 세트의 각 요소에 사용 된 숫자는 0에서 16383 (14 비트)이며 더 많은 세트가 많이 있다는 것입니다.

그것이 중요하다면 나는이 프로그램을 C ++로 작성하고 있지만 Java, C, 일부 어셈블리, 일부 Fortran 및 일부 Perl도 알고 있습니다.

누구든지 이것을 끌어내는 방법에 대한 단서가 있습니까?

편집하다:
몇 가지 질문에 답하고 몇 가지 요점을 추가하려면 다음과 같습니다.

1.) 데이터가 변경되지 않습니다. 그것은 모두 한 번의 긴 실행 세트 (각각 2 개의 공연 파일로 나뉘 었음)로 가져갔습니다.

2.) 저장 공간은. 원시 데이터는 약 250 기가 바이트를 차지합니다. 나는 관심이없는 많은 외부 메타 데이터를 처리하고 박탈 한 후에 내가 지수없이 유지하기로 결정한 메타 데이터의 양에 따라 36 ~ 48 기가 바이트로 줄일 수 있다고 추정합니다. 또한 데이터의 초기 처리에서 충분한 세트가 발생하면 단순히 이벤트를 반복해서 반복하는 대신 반복 이벤트에 대한 카운터를 추가하여 데이터를 더 이상 동일하게 할 수 있습니다.

3.) 처리 된 세트 내의 각 숫자에는 실제로 데이터 자체에 대해 최소 2 개의 숫자 14 비트 (감지 된 에너지)와 메타 데이터 (검출기 번호)의 경우 7 비트가 포함됩니다. 따라서 숫자 당 최소 3 바이트가 필요합니다.

4.) 내 "세트의 99.9%에서는 N이 15보다 작지만"댓글이 오도했다. 데이터 덩어리 중 일부를 통해 예비 한 눈에, 나는 22 숫자를 포함하는 세트를 가지고 있지만 중앙값은 세트 당 5 숫자이고 세트 당 평균 숫자는 6 숫자입니다.

5.) 파일에 포인터 색인을 구축한다는 아이디어가 마음에 들지만 둘 이상의 숫자와 관련된 요청에 대해서는 세트를 찾는 반면 느린 작업 (적어도 느리다고 생각합니다)이 남아 있기 때문에 약간 겁쟁이입니다. 목록에 공통적 인 모든 포인터 중에서, 주어진 수의 세트에 대한 가장 큰 공통 서브 세트를 찾습니다.

6.) 나에게 이용할 수있는 자원의 관점에서, 나는 시스템에 원시 데이터를 가지고있다 (해당 시스템에 대한 내 할당량의 나머지 부분) 후 약 300 공간의 공간을 소집 할 수있다. 이 시스템은 2 개의 Quad Core AMD Opteron과 16 기가 바이트의 RAM이있는 듀얼 프로세서 서버입니다.

7) 예 0이 발생할 수 있습니다. 데이터 수집 시스템의 아티팩트이지만 발생할 수 있습니다.

해결책 4

최근 공간 충전 곡선을 사용하여 다차원 데이터를 단일 차원으로 매핑하는 방법을 발견했습니다. 그런 다음 1D 인덱스를 기반으로 데이터를 색인 할 수 있습니다. 곡선을 나타내는 상자를 교차하는 곡선의 세그먼트를 찾은 다음 해당 세그먼트를 검색하여 범위 쿼리를 쉽게 수행 할 수 있습니다.

나는이 방법이 제안 된대로 미친 인덱스를 만드는 것보다 훨씬 우수하다고 생각합니다. 왜냐하면 그것을 살펴본 후에, 인덱스는 내가 저장하고자하는 데이터만큼 클수록 좋지 않기 때문입니다. 이것에 대한 다소 자세한 설명은 다음에서 찾을 수 있습니다.

http://www.ddj.com/184410998
그리고
http://www.dcs.bbk.ac.uk/~jkl/publications.html

다른 팁

귀하의 문제는 검색 엔진이 직면 한 것과 동일합니다. "Bajillion 문서가 있습니다.이 단어 세트가 포함 된 문서가 필요합니다." 당신은 단지 (매우 편리하게), 단어 대신 정수 및 작은 문서를 가지고 있습니다. 해결책은 an입니다 역 색인. 정보 검색 소개 Manning et al은 (해당 링크에서) 온라인에서 무료로 제공되며, 매우 읽기 쉬우 며,이를 수행하는 방법에 대한 자세한 내용을 다룰 것입니다.

디스크 공간에서 가격을 지불해야하지만 병렬화 될 수 있으며 인덱스가 구성되면 타이밍 요구 사항을 충족하기에 충분히 빠르야합니다.

세트 당 15 개의 요소와 20 억 세트의 0-16383의 무작위 분포를 가정하면 각 요소는 약 1.8m 세트로 나타납니다. 16384x ~ 1.8m (각 30b 항목, 4 바이트) 조회 테이블을 구축 할 수있는 용량이 있습니까? 그러한 테이블이 주어지면 (1) 및 (17) 및 (5555)를 포함하는 쿼리를 한 다음 해당 세 ~ 1.8m 요소 목록의 교차로를 찾을 수 있습니다.

내 추측은 다음과 같습니다.

각 세트에 이름 또는 ID 또는 주소가 있다고 가정합니다 (4 바이트 번호는 20 억 개에 불과한 경우).

이제 모든 세트를 한 번 안내하고 다음 출력 파일을 만듭니다.

'1'을 포함하는 모든 세트의 ID가 포함 된 파일
'2'를 포함하는 모든 세트의 ID가 포함 된 파일
'3'을 포함하는 모든 세트의 ID가 포함 된 파일
... 등 ...

세트 당 16 개의 항목이있는 경우 평균적 으로이 2^16 파일 각각에는 2^20 세트의 ID가 포함됩니다. 각 ID는 4 바이트 인 경우 2^38 바이트 (256GB)의 저장소가 필요합니다.

요청을 처리하기 전에 위의 한 번을 수행합니다.

요청을 받으면이 파일을 다음과 같이 사용하십시오.

요청에서 몇 숫자를보십시오
해당 인덱스 파일 몇 개를 엽니 다
이 두 파일에 존재하는 모든 세트의 목록을 가져옵니다 (각 파일에 백만 ID 만 있으므로 어려워서는 안됩니다).
이 소수의 세트 중 어느 것이 나머지 요청을 만족시키는 지 확인하십시오.

내 생각에 위의 작업을 수행하면 인덱스를 만드는 것이 매우 느리고 처리 요청이 매우 빠릅니다.

가능한 각 검색 값마다 16383 인덱스 파일을 하나씩 만듭니다. 입력 세트의 각 값에 대해 세트 시작의 파일 위치를 해당 색인 파일에 씁니다. 각 인덱스 파일에는 동일한 세트에 대해 동일한 숫자를 포함하는 것이 중요합니다. 이제 각 인덱스 파일은 마스터 파일로의 오름차순 인덱스로 구성됩니다.

검색하려면 각 검색 값에 해당하는 인덱스 파일을 읽으십시오. 다른 파일에서 읽은 색인보다 낮은 색인을 읽으면 버리고 다른 파일을 읽으십시오. 모든 파일에서 동일한 색인을 얻으면 일치합니다. 마스터 파일에서 세트를 얻고 각 인덱스 파일에서 새 인덱스를 읽으십시오. 인덱스 파일의 끝에 도달하면 완료됩니다.

값이 균등하게 분산되면 각 인덱스 파일에는 입력 세트의 1/16383이 포함됩니다. 평균 검색 세트가 6 값으로 구성되면 원래 입력의 6/16383 이상의 선형 패스를 수행하게됩니다. 여전히 O (N) 솔루션이지만 N은 이제 약간 작습니다.

추신은 불가능한 결과 값이 0이거나 실제로 1638을 가지고 있습니까?4 가능성?

Brute Force + Index Lookup을 포함한 접근 방식에 대한 Devil 's Advocate를 연주합니다.

최소, 최대 및 세트 요소가없는 인덱스를 만듭니다.
그런 다음 Max <Max (검색중인 세트) 및 Min> Min (검색 설정)을 제외한 Brute Force를 제외하십시오.
Brute Force에서는 세트를 제외합니다. 전체 요소 수는 검색중인 세트의 요소 수보다 작습니다.

검색의 95%는 실제로 매우 작은 하위 집합을 강요합니다. 그냥 생각.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow