Нахождение ближайшей пары между двумя наборами точек на гиперкубе

Для двух подмножеств мерного гиперкуба (т. ) я ищу алгоритм, который извлекает точки на расстоянии Хэмминга (или - расстояние по гиперкубу) минимально. Наивный алгоритм, который проверяет только каждую пару $d$ $M, N \subseteq \{0,1\}^d$ $m\in M, n\in N$ $L_1$ $d_H(m,n)$ $|M|\cdot |N| \cdot d$ время, есть ли лучший результат известен?

Для простоты можно предположить, что . $|M|=|N|=d$

cg.comp-geom HDM
источник

хммм. есть ли еще мотивация / приложение? Подозреваю, что существует многомерный аналог этого евклидова / планарного алгоритма, но википедия ничего не цитирует и не слышала об этом где-либо еще ... это может помочь найти алгоритм для n-dim векторов. начало статьи, кажется, утверждает, что она может быть решена в

для более высоких измерений

но не дает цитирования. может где то в ссылках?

O (n \log n)

$O(n \log n)$

d > 2

$d>2$

ВЗН

Аргумент «разделяй и властвуй» опирается на границу упаковки. В более высоких измерениях, это вводит

фактора в рецидиве, но зависимость от

остается тем же самым . Так что, если вы не возражаете против экспоненциальных терминов в

, вы можете использовать этот подход. Если вы хотите что-то точное, вы вряд ли сможете добиться большего.

2^{d}

$2^d$

n

$n$

d

$d$

Суреш Венкат

см. также поиск ближайшего соседа

vzn

Это кажется маловероятным. Подумайте о n + m случайных строк в гиперкубе. Так или иначе, расстояние Хэмминга каждой пары примерно равно d / 2, и вам нужно проверить все пары, чтобы найти ближайшую пару.

Сариэль Хар-Пелед

@Sariel Har-Peled: Как писал Суреш, эту проблему можно решить за время O (n log n) (где n = max {| M |, | N |}) для любой константы d. Поэтому «вы должны проверить все пары, чтобы найти ближайшую пару», мне не кажется правильным.

Tsuyoshi Ito

Ответы:

$|M|=|N|=d$ $M$ $X$ $N$ $Y$ $Y$ $Z=XY$ $z_{i,j}$ $i$ $M$ $j$ $N$ $O(d^{2.3727})$ $O(d^{2.3726999999})$

Вы можете получить аналогичный эффект, если матрицы не квадратные. Я думаю, что у Ури Цвика есть статья о быстром умножении матриц в этом случае.

$O(|M| * |N|)$ $d$

Сариэль Хар-Пелед
источник

Отличная находка. С другой стороны, мой коллега нашел этот документ: toc.cse.iitk.ac.in/articles/v008a014/v008a014.pdf, и только теперь я понимаю, что он (также) был написан вами. Страница 17+ особенно интересна ..

HdM

Да. Выглядит знакомо - но обратите внимание, что это приблизительное значение, - Суреш спросил точный результат ...

Сариэль Хар-Пелед

-3

$L_\infty$ $L_m$ $L_1$ $O(dn \log n)$ $d$

[1] Оптимальный алгоритм поиска приближенных соседей в фиксированных измерениях Arya et al, 30pp

[2] Эффективный поиск ближайших соседей по гиперкубу с приложениями к молекулярной кластеризации Cazals

ВЗН
источник

Ω (d^{d})

$\Omega(d^d)$