Tính toán giá trị Hilbert của một điểm để sử dụng trong R-Tree Hilbert?

Question

Tôi có một ứng dụng mà một Hilbert R-Tree (wikipedia)(citeseer) dường như là một cấu trúc dữ liệu thích hợp. Cụ thể, nó yêu cầu các truy vấn không gian hợp lý nhanh chóng trên một tập dữ liệu sẽ trải qua rất nhiều cập nhật.

Tuy nhiên, như xa như tôi có thể thấy, không ai trong số các mô tả của các thuật toán cho cấu trúc dữ liệu này thậm chí đề cập làm thế nào để thực sự tính toán cần thiết Hilbert Value; đó là khoảng cách dọc theo Hilbert Curve đến điểm.

Vì vậy, bất kỳ đề xuất nào về cách tính toán điều này?

Answer 1

Câu hỏi thú vị!

Tôi đã làm một chút googling, và tin tốt là, tôi đã tìm thấy một thực hiện giá trị Hilbert.

Các tin tức có khả năng xấu là, đó là trong Haskell ...

http://www.serpentine.com/blog/2007/01/11/two-dimensional-spatial-hashing-with-space-filling-curves/

Nó cũng đưa ra một khoảng cách Lebesgue số liệu bạn có thể có thể tính toán dễ dàng hơn.

Answer 2

Xem uzaygezen.

Answer 3

Gợi ý: Cấu trúc dữ liệu hiệu quả đơn giản tốt cho các truy vấn không gian là một cây nhị phân nhiều chiều.

Trong cây nhị phân truyền thống, có một "phân biệt đối xử"; giá trị được sử dụng để xác định xem bạn có rẽ nhánh trái hay nhánh phải không. Điều này có thể được coi là trường hợp một chiều.

Trong cây nhị phân nhiều chiều, bạn có nhiều phân biệt đối xử; các cấp độ liên tiếp sử dụng các phân biệt đối xử khác nhau. Ví dụ, đối với dữ liệu không gian hai chiều, bạn có thể sử dụng tọa độ X và Y làm phân biệt đối xử. Các cấp liên tiếp sẽ sử dụng X, Y, X, Y ...

Đối với các truy vấn không gian (ví dụ tìm tất cả các nút trong một hình chữ nhật) bạn thực hiện tìm kiếm theo chiều sâu của cây bắt đầu từ gốc và bạn sử dụng phân biệt đối xử ở mỗi cấp để tránh tìm kiếm các nhánh không chứa các nút trong hình chữ nhật đã cho.

Điều này cho phép bạn có khả năng cắt giảm không gian tìm kiếm ở một nửa ở mỗi cấp, làm cho nó rất hiệu quả để tìm các vùng nhỏ trong một tập dữ liệu khổng lồ. (BTW, cấu trúc dữ liệu này cũng hữu ích cho các truy vấn đối sánh từng phần, tức là các truy vấn bỏ qua một hoặc nhiều phân biệt đối xử. Bạn chỉ cần tìm kiếm cả hai nhánh ở cấp độ với một phân biệt bỏ qua.)

Một bài báo tốt về cấu trúc dữ liệu này: http://portal.acm.org/citation.cfm?id=361007 bài viết này có sơ đồ tốt và mô tả thuật toán: http://en.wikipedia.org/wiki/Kd-tree

Answer 4

Dưới đây là mã java của tôi chuyển từ mã C trong giấy "Encoding và giải mã trình tự Hilbert" bởi Xian Lu và Gunther Schrack, được công bố trong phần mềm: Thực hành và kinh nghiệm Vol. 26 trang 1335-46 (1996).

Hy vọng điều này sẽ hữu ích. Cải tiến chào đón!

Michael

/** 
* Find the Hilbert order (=vertex index) for the given grid cell 
* coordinates. 
* @param x cell column (from 0) 
* @param y cell row (from 0) 
* @param r resolution of Hilbert curve (grid will have Math.pow(2,r) 
* rows and cols) 
* @return Hilbert order 
*/ 
public static int encode(int x, int y, int r) { 

    int mask = (1 << r) - 1; 
    int hodd = 0; 
    int heven = x^y; 
    int notx = ~x & mask; 
    int noty = ~y & mask; 
    int temp = notx^y; 

    int v0 = 0, v1 = 0; 
    for (int k = 1; k < r; k++) { 
     v1 = ((v1 & heven) | ((v0^noty) & temp)) >> 1; 
     v0 = ((v0 & (v1^notx)) | (~v0 & (v1^noty))) >> 1; 
    } 
    hodd = (~v0 & (v1^x)) | (v0 & (v1^noty)); 

    return interleaveBits(hodd, heven); 
} 

/** 
* Interleave the bits from two input integer values 
* @param odd integer holding bit values for odd bit positions 
* @param even integer holding bit values for even bit positions 
* @return the integer that results from interleaving the input bits 
* 
* @todo: I'm sure there's a more elegant way of doing this ! 
*/ 
private static int interleaveBits(int odd, int even) { 
    int val = 0; 
    // Replaced this line with the improved code provided by Tuska 
    // int n = Math.max(Integer.highestOneBit(odd), Integer.highestOneBit(even)); 
    int max = Math.max(odd, even); 
    int n = 0; 
    while (max > 0) { 
     n++; 
     max >>= 1; 
    } 

    for (int i = 0; i < n; i++) { 
     int bitMask = 1 << i; 
     int a = (even & bitMask) > 0 ? (1 << (2*i)) : 0; 
     int b = (odd & bitMask) > 0 ? (1 << (2*i+1)) : 0; 
     val += a + b; 
    } 

    return val; 
} 

Answer 5

Michael,

nhờ cho mã Java của bạn! Tôi đã thử nghiệm nó và nó có vẻ hoạt động tốt, nhưng tôi nhận thấy rằng hàm tràn xen kẽ ở mức đệ quy 7 (ít nhất là trong các thử nghiệm của tôi, nhưng tôi đã sử dụng các giá trị dài), bởi vì giá trị "n" được tính bằng cách sử dụng hàm highOneBit () - chức năng, trả về giá trị chứ không phải vị trí của bit cao nhất; vì vậy vòng lặp không cần thiết nhiều interleavings.

Tôi vừa thay đổi nó thành đoạn mã sau và sau đó nó hoạt động tốt.

 
    int max = Math.max(odd, even); 
    int n = 0; 
    while (max > 0) { 
    n++; 
    max >>= 1; 
    } 

Answer 6

Tôi đã tìm ra một cách hiệu quả hơn để xen kẽ các bit. Nó có thể được tìm thấy tại Stanford Graphics Website. Tôi bao gồm một phiên bản mà tôi tạo ra có thể xen kẽ hai số nguyên 32 bit thành một bit dài 64 bit.

public static long spreadBits32(int y) { 
    long[] B = new long[] { 
     0x5555555555555555L, 
     0x3333333333333333L, 
     0x0f0f0f0f0f0f0f0fL, 
     0x00ff00ff00ff00ffL, 
     0x0000ffff0000ffffL, 
     0x00000000ffffffffL 
    }; 

    int[] S = new int[] { 1, 2, 4, 8, 16, 32 }; 
    long x = y; 

    x = (x | (x << S[5])) & B[5]; 
    x = (x | (x << S[4])) & B[4]; 
    x = (x | (x << S[3])) & B[3]; 
    x = (x | (x << S[2])) & B[2]; 
    x = (x | (x << S[1])) & B[1]; 
    x = (x | (x << S[0])) & B[0]; 
    return x; 
} 

public static long interleave64(int x, int y) { 
    return spreadBits32(x) | (spreadBits32(y) << 1); 
} 

Rõ ràng, B và S biến địa phương nên hằng lớp nhưng nó đã để lại theo cách này cho đơn giản.

Answer 7

Mã và mã java ở trên là tốt cho các điểm dữ liệu 2D. Nhưng đối với kích thước cao hơn, bạn có thể cần xem giấy Jonathan Lawder: J.K.Lawder. Calculation of Mappings Between One and n-dimensional Values Using the Hilbert Space-filling Curve.

Answer 8

Nếu bạn cần chỉ mục không gian có khả năng xóa/chèn nhanh, hãy xem cây PH. Nó một phần dựa trên quadtrees nhưng nhanh hơn và nhiều không gian hiệu quả hơn. Bên trong nó sử dụng một đường cong Z có đặc tính không gian kém hơn một chút so với đường cong H nhưng là nhiều hơn dễ tính toán hơn.

Giấy: http://www.globis.ethz.ch/script/publication/download?docid=699

Java thực hiện: http://globis.ethz.ch/files/2014/11/ph-tree-2014-11-10.zip

Một lựa chọn khác là X-cây, mà cũng có sẵn ở đây: https://code.google.com/p/xxl/