Поиск диапазона в d-пространстве с дискретными координатами
Я хотел бы разработать алгоритм поиска диапазона, который сообщает все точки на заданном расстоянии от точки запроса.
Точки задаются d целочисленными координатами в крошечном диапазоне, скажем, до 6 бит на измерение (диапазон 0,63), для общего количества битов, не превышающего 60 бит.
Метрика расстояния - Манхэттен или Евклид (зависит от вас), т.е. сумма абсолютных или квадратов разностей координат. В особом случае одного бита на измерение это составляет расстояние Хемминга.
Там может быть до миллиона очков.
Знаете ли вы о практической структуре данных, которая поддерживает быстрые запросы, скажем O(Log²(n)+k)
или похожий (с пробелом O(n)
) в таких условиях? Разумное время предварительной обработки (subquadratic) также требуется.
k-D
деревья - это первый вариант, но они не используют конечность координат и, я боюсь, могут плохо работать в больших измерениях.
Случай одного бита на координату особенно интересен. Даже частичные решения приветствуются.
2 ответа
После некоторых размышлений (и подталкивания @YvesDaoust) использование дерева VP (дерева точек обзора 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;
}
РЕДАКТИРОВАТЬ Вот JSFiddle, показывающий 2d (x, y) (8 бит, 8 бит) http://jsfiddle.net/fgq1rfLk/1/
Если точки имеют явные координаты и если d не слишком велико, что, как кажется, имеет место здесь, я думаю (но я могу ошибаться, нуждается в проверке), что Kd-дерево будет более эффективным, чем VP-дерево, поскольку он может извлечь выгоду из большей структуры данных (координат), тогда как дерево VP только "видит" расстояния от точки к точке.
В ANN [1] имеется эффективная реализация Kd-деревьев со всеми необходимыми функциями поиска по диапазону (метрика L2 и метрика Манатана) (однако она явно хранит все координаты, и вы, вероятно, захотите извлечь выгоду из своего представления "сжатых координат".
Альтернативой является моя собственная реализация KdTree в Geogram [2], она довольно проста (хотя и вдохновлена ANN) и, вероятно, может быть довольно легко адаптирована для использования вашего сжатого представления координат (но он имеет только k поиск ближайших соседей с метрикой L2)
Referencecs:
[1] https://www.cs.umd.edu/~mount/ANN/
[2] http://alice.loria.fr/software/geogram/doc/html/classGEO_1_1KdTree.html