Структура данных для запросов минимальных точек продукта

19

Rn,mv1,v2,,vmxRnмин ях , v яminix,viО ( п т )O(nm) п = 2 n=2O ( войти 2 м )O(log2m)

Единственное, что я могу придумать, это следующее. Непосредственным следствием леммы Джонсона-Линденштрауса является то, что для каждого и распределения в существует линейное отображение (который можно вычислить за времени) так, чтобы . Итак, за время O ((n + m) \ log m) мы можем вычислитьε > 0 ε>0D DR nRn f : R nR O ( log m )f:RnRO(logm)O(nlogm)P r x D [яХ , v я- ε ( | | х | | + | | v я) 2 & le ; F ( х ) , F ( v я ) ⟩ & le ; х , v я+ ε ( | | х | | + | | V я | | ) 2 ]1 - ε O ( ( nPrxD[ix,viε(x+vi)2f(x),f(vi)x,vi+ε(x+vi)2]1ε+ м ) лог м )O((n+m)logm)что-то, что в некотором смысле близко к minix,viminix,vi для большинства xx (по крайней мере, если нормы xx и vivi малы).

UPD Упомянутая выше граница может быть несколько увеличена до времени запроса O(n+m)O(n+m) если мы используем локальное хеширование. Точнее, мы выбираем k:=O(1ε2)k:=O(1ε2) независимых гауссовских векторов r1,r2,,rkr1,r2,,rk . Затем мы отображаем RnRn в {0,1}k{0,1}k следующим образом: v(r1,v0,r2,v0,,rk,v0)v(r1,v0,r2,v0,,rk,v0) . Затем мы можем оценить угол между двумя векторами в пределах аддитивной ошибки εε , вычислив 11 расстояние на изображении этого отображения. Таким образом, мы можем оценить точечные произведения в пределах аддитивной ошибкиεxviεxviза O(1ε2)O(1ε2) время.


ilyaraz
источник
Я не уверен, работает ли это или помогает, но ваша проблема (после переключения знака v_i для преобразования в максимизацию) выглядит связанной с диаграммами Вороного. Может быть возможно модифицировать алгоритмы для диаграмм Вороного к этой задаче, но даже если это возможно, это будет полезно, вероятно, только для малых n.
Цуёси Ито
Я не знаю, является ли это тем же наблюдением ... Все xx могут быть нормализованы к единичному вектору и не изменяют результат, мы можем сделать все в единичном n-кубе с центром в начале координат. Найдите, какая область куба минимизирует скалярное произведение с vivi для каждого ii (каждая область должна быть многогранником). У меня нет ограничений на количество многогранников. Если оно меньше экспоненциального в nmnm , вы получите что-то лучше, чем O(nm)O(nm) , выполнив n-мерный запрос местоположения точки.
Чао Сюй
какой параметр вам важнее? обычно, если вы хотите получить сублинейный по m, вы начнете получать экспоненциальный по n.
Суреш Венкат
@Suresh Хорошо, было бы неплохо понять различные возможные компромиссы. Примерная версия тоже интересна.
Ильяраз
Краткое примечание: для случая n = 2 бинарный поиск на выпуклой оболочке дает время запроса . O(logn)O(logn)
Джеффри Ирвинг

Ответы:

16

Рассмотрим специальный случай, когда вы просто хотите определить, является ли ваш вектор запроса ортогональным к какому-либо вектору в вашей предварительно обработанной коллекции. (То есть вы хотите определить, если , где обсуждаемые векторы имеют неотрицательные коэффициенты.) Этот случай уже очень интересен.minix,vi=0minix,vi=0

Предположим, что вы можете ответить на запросы за времени для некоторого , с предварительной обработкой ( степени многочлена не должны зависеть от или или ).nO(1)m1δnO(1)m1δδ>0δ>0mO(1)nO(1)mO(1)nO(1)mmnnδδ

В статье «Новый алгоритм оптимального удовлетворения 2-ограничений и его последствия» я заметил, что такая структура данных фактически позволит вам решить CNF-SAT за времени для некоторого , где - количество переменных. Это опровергнет «гипотезу сильного экспоненциального времени», согласно которой для k-SAT требуется, по существу, времени для неограниченного .2αv2αvα<1α<1vv2n2nkk

Чтобы понять почему, предположим, что время предварительной обработки ограничено . Рассмотрим формулу CNF с переменными и предложениями. Разобьем множество переменных на две части и размером и соответственно. Перечислите все возможные назначения для переменных в частях (получая и соответственно). Свяжите каждое из этих частичных присвоений с битным вектором где если(nm)c(nm)cFFvvnnP1P1P2P2v(11/(2c))v(11/(2c))v/(2c)v/(2c)2v(11/(2c))2v(11/(2c))2v/(2c)2v/(2c)AiAinnwiwiwi[j]=1wi[j]=1jjабзац не удовлетворен . Таким образом, у нас есть два списка экспоненциально многих битовых векторов.FFAiAi

Обратите внимание, что выполнимо, если существует вектор из назначения на и вектор из назначения на такой что .FFw1P1w2P2w1,w2=0

Теперь давай m=2v/(2c) и предварительно обработает предполагаемую структуру данных со всеми векторами из части . По предположению, это занимает времени. Запустите алгоритм запроса для всех векторов из присвоений детали . По предположению, это займет . Пусть .P2n2v/2P12v(11/(2c))nO(1)m1δ=nO(1)2vδv/(2c)α=1δ/(2c)

Возможно, можно получить эффективную предварительную обработку и с помощью существующих методов. Самые известные алгоритмы CNF-SAT не исключают этого. (Они получают что-то вроде .) Но вычислить немного сильнее - в этой настройке это будет похоже на решение MAX CNF-SAT.nO(1)m11/(loglogm)2nn/lognminix,vi

Райан Уильямс
источник
Потрясающие! Но это не исключает приблизительные структуры данных, а также время запроса, например , что также было бы очень интересно. O(mpoly(logn))
Ильяраз
Кстати, нельзя ли сказать что-то вроде «если бы существовала даже приблизительная структура данных с быстрым временем запроса, то MAX-SAT был бы приближенным».
Ильяраз
Почему соблюдается эквивалентность, указанная в первом абзаце? Я думаю, что внутренний продукт может быть отрицательным в целом.
Цуёси Ито
Ильяраз: Да, даже приблизительные структуры данных подразумевают приблизительный MAX-SAT. Tsuyoshi: Спасибо за ваше понимание
Райан Уильямс
6

Вот одна идея для точного ответа, на которую, я подозреваю, намекал Чао Сюй. Во-первых, заметим, что мы могли бы также нормализовать x , как указывает Чао. Теперь рассмотрим гиперплоскость h, перпендикулярную направлению x . Цель состоит в том, чтобы найти точку, ближайшую к этой гиперплоскости. По двойственности это соответствует запросу съемки луча в расположении гиперплоскостей, чтобы найти ближайшую плоскость «выше» точки запроса. Так как это может быть предварительно обработано, основной сложностью является местоположение точки, поэтому ваша задача теперь сводится к сложности определения местоположения точки в расположении гиперплоскостей. Используя черенки, это можно сделать за O ( log n ) за n d Космос.

Суреш Венкат
источник
1
Я должен был упомянуть, что меня также интересует разумное время предварительной обработки, которое здесь не имеет место, если измерение имеет большой размер.
Ильяраз