다차원 데이터를 보유한 B + 트리를 효율적으로 질의

Question

나는 내 데이터 집합을 구성하는 64 비트 정수의 튜플 집합 (x,y)을 가지고있다. 나는 말하자면, 수조 개의 튜플을 가지고있다. 그것은 지구상의 모든 기계에있는 메모리에 데이터 세트를 유지하는 것이 가능하지 않습니다. 그러나 디스크에 저장하는 것이 좋습니다.

나는 하나의 차원에서 데이터를 빠르고 동시에 질의 할 수있는 디스크상의 저장소 (B + -tree)를 가지고있다. 그러나 일부 쿼리는 두 차원 모두에 의존합니다.

쿼리 예제 :

• x 일부가 주어진 값
• x 튜플을 찾아보다 이상인 튜플 찾기 s.t. 가능한 한 작은 그것은 y이 주어진 값보다 크거나 같음
• x이 가능한 작은 s.t. 인 튜플을 찾습니다. y는

내가 찾은 최선의 방법은 Z 순서 곡선하지만 내가 알아낼 수 없습니다 (일부 튜플을 일부 튜플을 삽입, 제거)

유지 보수 작업을 수행 어떤 주어진 값보다 작거나 같은 것 내 2 차원 데이터 세트를 사용하여 쿼리를 수행하는 방법.

허용되지 않는 솔루션에는 데이터의 순차적 스캔이 포함되며 이는 너무 느릴 수 있습니다.

Answer 1

z 차수 곡선을 쿼리하는 방법을 모르는 것이 있습니까? Wikipedia page은 범위 검색을 수행하는 방법을 설명합니다.

z- 곡선은 공간을 중첩 된 사각형으로 나눕니다. 중첩 된 사각형으로 키의 각 추가 비트가 공간을 절반으로 나눕니다. 포인트를 검색하려면 :

Start with the largest rectangle that might contain your point. 

    Recursively: 

     Create a result set of rectangles  

    For each rectangle in your set   
     If the rectangle is a single point, you are done, it is what you are looking for. 
     Otherwise, divide the rectangle in two (specify one additional bit of the z-curve) 
      If both halves contain a point 
       If one half is better 
        Add that rectangle to your result set of rectangles 
       Otherwise 
        Add both rectangles to your result set of rectangles 
      Otherwise, only one half contains a point 
        Add that rectangle to your result set of rectangles 

    Search your result set of rectangles 

최악의 경우 성능이 좋지 않습니다. Z- 순서 인덱스를 구성하는 방법을 변경하여 조정할 수 있습니다.

Answer 2

귀하의 요구 사항에 가장 적합한 데이터 구조는 R-tree 및 그 변형 (R * -tree, R + -tree, Hilbert R-tree)입니다. R-tree는 B + -tree와 유사하지만 다차원 쿼리도 허용합니다.

기타 관련 데이터 구조는 우선 순위 검색 트리입니다. 예제 1 .. 3과 같은 쿼리는 좋지만 잦은 업데이트 나 디스크 저장소가 필요한 경우 매우 효율적이지는 않습니다. 자세한 내용은 this paper 또는이 설명서 : "Handbook of Data Structures and Applications" (18.5 장)을 참조하십시오. I은 본질적 '스택'의 B + 트리 (또는 D는 차원 수이다 D + 트리) 다차원 데이터 인 데이터 구조를 설계하고 있어요

Answer 3

. 나는 이것이 당신의 데이터에 완벽하게 맞을 것이며 당신의 유스 케이스를 위해 특별히 설계되고 있다고 믿는다.

기본적인 아이디어는 이것이다 :

각 차원은 B + 트리이며, 다음 차원의 B + 트리에 연결되어 있습니다. 첫 번째 차원을 정상적으로 검색하면 잎에 도달하면 다음 차원에 속한 다음 B + 트리의 루트에 대한 포인터가 포함됩니다. 두 번째 B + 트리의 모든 내용은 동일한 x 값에 속합니다.

독창적 인 계획은 각 측정 기준과 함께 고유 값을 개수와 함께 저장하는 것이 었습니다. 이것은 매우 간단한 압축 알고리즘을 사용하며 (심지어 호출 할 수 있다면) 전체 데이터 세트를 표현할 수 있습니다. 이 '링크 된'차원 구성표를 사용하면 나중에 B + 트리 스택에 추가되는 추가 차원을 나중에 추가 할 수 있습니다. B 각각 B + 트리와 카드의 기본 (x)는는 기수 것

log b(card(x)) + log b(card(y)) 

입니다 :

총 삽입/검색 /이 비슷한 것 2 차원의 시간을 삭제 x 치수의

나는 그것이 의미가 있기를 바랍니다. 나는 여전히 구현을 위해 노력하고 있지만 자유롭게 아이디어를 사용하거나 늘릴 수 있습니다.

Answer 4

http://fallabs.com/tokyocabinet/

도쿄 내각은 데이터베이스를 관리하기위한 루틴의 라이브러리입니다. 데이터베이스는 레코드를 포함하는 단순한 데이터 파일이며 각각은 키와 값의 쌍입니다. 모든 키와 값은 가변 길이의 직렬 바이트입니다. 이진 데이터와 문자열은 모두 키와 값으로 사용할 수 있습니다. 데이터 표나 데이터 유형의 개념은 없습니다. 레코드는 해시 테이블, B + 트리 또는 고정 길이 배열로 구성됩니다.

도쿄 캐비닛은 C 언어로 작성되었으며 C, Perl, Ruby, Java 및 Lua의 API로 제공됩니다. Tokyo Cabinet은 C99 및 POSIX를 준수하는 API가있는 플랫폼에서 사용할 수 있습니다. Tokyo Cabinet은 GNU Lesser General Public License에 따라 사용 허가 된 무료 소프트웨어입니다.

쉽게 포함시킬 수 있습니까?