4

我想开发一个范围搜索算法，报告查询点给定距离内的所有点。

这些点由 d 个整数坐标在一个很小的范围内指定，例如每个维度最多 6 位（范围 0..63），总位数不超过 60 位。

距离度量是曼哈顿或欧几里得（由您决定），即绝对或平方坐标差的总和。在每个维度一个比特的特殊情况下，它相当于汉明距离。

最多可以有一百万个点。

您是否知道在这种情况下支持快速查询O(Log²(n)+k)或类似（带有空格O(n)）的实用数据结构？还需要合理的预处理时间（二次）。

k-D树是第一选择，但恐怕它们没有利用坐标的有限性，并且可能在高维度上表现不佳。

每个坐标只有一位的情况特别有趣。即使是部分解决方案也是受欢迎的。

4

2 回答 2

0

经过一番思考（并由@YvesDaoust 推动）后，使用 VP 树（Vantage Point Tree https://en.wikipedia.org/wiki/Vantage-point_tree）可能是最好的解决方案。

VP Tree 是一个 BSP，其中左节点在距离之内，右节点在距离之外。这适用于每个维度的单个位和每个维度的多个位（只有距离公式会改变。距离是每个树节点的阈值/半径。查询涉及通过树递归获取当前节点值与查询值的距离并比较该结果与查询距离。

JSFiddle http://jsfiddle.net/fgq1rfLk/

var DIMS = 16;
var BITS = 1;
var MASK = (Math.pow(2, BITS) - 1)|0;
var SIZE = DIMS * BITS;
var list = [];
var tree = null;
//
// set bit count (population count)
function popCnt(x) {
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}
//
// manhattan distance
function dist(a, b) {
    if(BITS == 1) {
        return popCnt(a ^ b);
    }
    var result = 0;
    for(var i=0; i<DIMS; i++) {
        var shr = i * BITS;
        result += Math.abs(((a >> shr) & MASK) - ((b >> shr) & MASK));
    }
    return result;
}
//
// Vantage point tree
// max size of tree leaf nodes
VP_LEAF_SIZE = 32;
// need to choose a reasonable maximum distance
VP_DISTANCE = (BITS === 1) ? SIZE : 32;
function VPTree(data) {
    this.radius = null;
    this.center = null;
    this.values = null;
    this.inside = null;
    this.outside = null;
    // 
    var n = data.length;
    var r = data[0];
    // leaf node?
    if(n <= VP_LEAF_SIZE || n <= 1) {
        this.values = [].concat(data);
        return this;
    }
    this.center = r;
    // process data for counts at all possible distances
    var buckets = Array(VP_DISTANCE + 1);
    for(var i=0; i<=VP_DISTANCE; i++) { 
        buckets[i] = 0; 
    }
    // distance counts
    for(var i=0; i<n; i++) {
        var v = data[i];
        var d = dist(r, v);
        if(d < VP_DISTANCE) {
            buckets[d]++;
        } else {
            buckets[VP_DISTANCE]++;
        }
    }
    // distance offsets
    var sum = 0;
    for(var i=0; i<=VP_DISTANCE; i++) { 
        buckets[i] = (sum += buckets[i]); 
    }
    // pivot index
    var median = n >> 1;
    var pivot = 1;
    for(var i=1; i<=VP_DISTANCE; i++) {
        if(buckets[i] > median) {
            pivot = (i > 1 && median - buckets[i - 1] <= buckets[i] - median) ? i - 1 : i;
            break; 
        }
    }
    this.radius = pivot;
    // parition data into inside and outside
    var iCount = buckets[pivot] - buckets[0];
    var oCount = (n - buckets[pivot]) - buckets[0];
    var iData = Array(iCount);
    var oData = Array(oCount);
    iCount = oCount = 0;
    for(var i=0; i<n; i++) {
        var v = data[i];
        if(v === r) { continue; };
        if(dist(r, v) <= pivot) {
            iData[iCount++] = v;
        } else {
            oData[oCount++] = v;
        }
    }
    // recursively create the rest of the tree
    if(iCount > 0) {
        this.inside = new VPTree(iData);
    }
    if(oCount > 0) {
        this.outside = new VPTree(oData);
    }
    return this;
}
VPTree.prototype.query = function(value, distance, result) {
    if(result === undefined) {
        return this.query(value, distance, []);
    }
    // leaf node, test all values
    if(this.values !== null) {
        for(var i=0; i<this.values.length; i++) {
            var v = this.values[i];
            if(dist(value, v) <= distance) {
                result.push(v);
            }
        }
        return result;
    }
    // recursively test the rest of the tree
    var tmpDistance = dist(value, this.center);
    // inside
    if(tmpDistance <= distance + this.radius) {
        if(tmpDistance <= distance) {
            result.push(this.center);
        }
        if(this.inside !== null) {
            this.inside.query(value, distance, result);
        }
    }
    // outside
    if(tmpDistance + distance > this.radius && this.outside !== null) {
        this.outside.query(value, distance, result);
    }
    return result;
}

编辑这是显示 2d (x, y) (8bits, 8bits) http://jsfiddle.net/fgq1rfLk/1/的 JSFiddle

于 2015-09-25T16:45:51.000 回答
0

如果这些点具有明确的坐标并且如果 d 不是太大，这似乎是这里的情况，我认为（但我可能错了，需要测试）Kd-tree 将比 VP-tree 更有效，因为它可以从数据（坐标）的更多结构中受益，而 VP-tree 只“看到”点到点的距离。

在 ANN [1] 中有一个具有所有需要的范围搜索函数（L2 和 Manathan 度量）的 Kd 树的有效实现（但是，它显式存储所有坐标，您可能希望从“压缩坐标”表示中受益。

另一种选择是我自己在 Geogram [2] 中实现的 KdTree，它非常简单（尽管受到 ANN 的高度启发）并且可能很容易适应使用压缩坐标表示（但它只有 k 最近邻搜索与 L2 度量)

参考文献：

[1] https://www.cs.umd.edu/~mount/ANN/

[2] http://alice.loria.fr/software/geogram/doc/html/classGEO_1_1KdTree.html

于 2015-10-29T17:26:44.927 回答