Struktura danych dla zapytań o minimalną liczbę kropek

19

Rn,mv1,v2,,vmxRnminix,viO(nm)n=2O(log2m)

Jedyne, co mogę wymyślić, to: Bezpośrednią konsekwencją lematu Johnsona-Lindenstraussa jest to, że dla każdego i rozkładu na występuje liniowe mapowanie (które można ocenić w czasie ) tak, że . Tak więc w czasie O ((n + m) \ log m) możemy obliczyćε>0DRnf:RnRO(logm)O(nlogm)PrxD[ix,viε(x+vi)2f(x),f(vi)x,vi+ε(x+vi)2]1εO((n+m)logm)coś , co jest w pewnym sensie zbliżone do minix,vi dla większości x (przynajmniej jeśli normy x i vi są małe).

UPD Wyżej wymienione ograniczenie może być nieco zaostrzone do czasu zapytania O(n+m) jeśli użyjemy haszowania wrażliwego na lokalizację. Dokładniej, wybieramy k:=O(1ε2) niezależne wektory gaussowskie r1,r2,,rk . Następnie mapujemy Rn do {0,1}k w następujący sposób: v(r1,v0,r2,v0,,rk,v0) . Następnie możemy oszacować kąt między dwoma wektorami w ramach błędu addytywnego ε , obliczając 1 -odległość na obrazie tego odwzorowania. W ten sposób możemy oszacować produkty kropkowe w ramach błędu addytywnegoεxviw czasie O(1ε2) .


ilyaraz
źródło
Nie jestem pewien, czy to działa, czy też pomaga, ale twój problem (po zmianie znaku v_i w celu konwersji na maksymalizację) wygląda na diagramy Voronoi. Możliwe jest zmodyfikowanie algorytmów dla diagramów Voronoi dla tego problemu, ale nawet jeśli jest to możliwe, prawdopodobnie przyda się tylko dla małych n.
Tsuyoshi Ito,
Nie wiem, czy to jest ta sama obserwacja ... Wszystkie x można znormalizować do wektora jednostkowego i nie zmienia wyniku, możemy zrobić wszystko w jednostce n-sześcian wyśrodkowanej na początku. Znajdź, który region sześcianu minimalizuje iloczyn iloczynu z vi dla każdego i (każdy region musi być polytopem). Nie mam ograniczenia liczby polytopów. Jeśli jest mniejsza niż wykładnicza w nm , masz coś lepszego niż O(nm) , wykonując n-wymiarowe zapytanie o lokalizację punktu.
Chao Xu,
jaki parametr bardziej Ci zależy? zazwyczaj, jeśli chcesz uzyskać sublinearne wm, zaczniesz być wykładniczy in.
Suresh Venkat
@Suresh Dobrze byłoby zrozumieć różne możliwe kompromisy. Ciekawa jest także wersja przybliżona.
ilyaraz,
Szybka uwaga: w przypadku n = 2 wyszukiwanie binarne na wypukłym kadłubie daje czas zapytania . O(logn)
Geoffrey Irving

Odpowiedzi:

16

Rozważ szczególny przypadek, w którym chcesz po prostu ustalić, czy wektor zapytania jest ortogonalny względem jakiegoś wektora w zbiorze wstępnie przetworzonym. (Oznacza to, że chcesz ustalić, czy , gdzie omawiane wektory mają współczynniki nieujemne.) Ten przypadek jest już bardzo interesujący.minix,vi=0

Załóżmy, że możesz odpowiadać na zapytania w czasie dla niektórych , przy użyciu wstępnego przetwarzania ( wielomianu stopnia nie powinna zależeć od i i ). δ > 0 m O ( 1 ) n O ( 1 ) m n δnO(1)m1δδ>0mO(1)nO(1)mnδ

W artykule „Nowy algorytm dla optymalnej satysfakcji z 2 ograniczeń i jego implikacje” zauważyłem, że taka struktura danych faktycznie pozwoliłaby ci rozwiązać CNF-SAT w czasie przez pewien czas , gdzie jest liczbą zmiennych. To obaliłoby „hipotezę silnego czasu wykładniczego”, że k-SAT wymaga zasadniczo czasu na nieograniczony . α < 1 v 2 n k2αvα<1v2nk

Aby zobaczyć dlaczego, załóżmy, że czas wstępnego przetwarzania jest ograniczony przez . Rozważ wzór CNF ze zmiennymi i klauzulami . Podzieliliśmy zbiór zmiennych na dwie części, odpowiednio i o rozmiarze i . Wymień wszystkie możliwe przypisania do zmiennych w częściach (otrzymując odpowiednio i ). każde z tych częściowych przypisań z wektorem gdzie w F v n P 1 P 2 v ( 1 - 1 / ( 2 c ) ) v / ( 2 c ) 2 v ( 1 - 1 / ( 2 c ) ) 2 v / ( 2 c ) A i n w i w i [ j ] = 1 j(nm)cFvnP1P2v(11/(2c))v/(2c)2v(11/(2c))2v/(2c)Ainwiwi[j]=1jklauzula nie jest spełniona przez . Mamy więc dwie listy wykładniczo wielu wektorów bitowych.A iFAi

Zauważ, że jest zadowalające, jeśli istnieje wektor z przydziału na i wektor z przydziału na taki że .w 1 p 1 w 2 P 2w 1 , w 2= 0Fw1P1w2P2w1,w2=0

Teraz pozwól i wstępnie przetworz założoną strukturę danych za pomocą wszystkich wektorów z części . Zakłada się, że zajmuje to czas . Uruchom algorytm zapytania dla wszystkich wektorów z przypisań w części . Z założenia przyjmuje to . Niech . P 2 n 2 v / 2 P 1 2 v ( 1 - 1 / ( 2 c ) )n O ( 1 ) m 1 - δ = n O ( 1 ) 2 v - δ v / ( 2 c ) α = 1 / (m=2v/(2c)P2n2v/2P12v(11/(2c))nO(1)m1δ=nO(1)2vδv/(2c)α=1δ/(2c)

Być może uda się uzyskać wydajne przetwarzanie wstępne i czas zapytania przy użyciu istniejących technik. Najbardziej znane algorytmy CNF-SAT tego nie wykluczają. (Dostają coś w rodzaju .) Ale aby obliczyć jest nieco silniejszy - w tej konfiguracji byłoby to jak rozwiązanie MAX CNF-SAT.nO(1)m11/(loglogm)2nn/lognminix,vi

Ryan Williams
źródło
Niesamowite! Ale to nie wyklucza przybliżonych struktur danych, a także czasów zapytań, takich jak , co również byłoby bardzo interesujące. O(mpoly(logn))
ilyaraz,
Nawiasem mówiąc, nie możemy powiedzieć czegoś takiego: „gdyby istniała nawet przybliżona struktura danych z szybkim czasem zapytania, wówczas MAX-SAT byłby zbliżony”.
ilyaraz
Dlaczego obowiązuje równoważność podana w akapicie pierwszym? Myślę, że wewnętrzny produkt może być ogólnie negatywny.
Tsuyoshi Ito,
ilyaraz: Tak, nawet przybliżone struktury danych sugerowałyby przybliżoną wartość MAX-SAT. Tsuyoshi: Dziękuję za wgląd
Ryan Williams
6

Oto jeden pomysł na dokładną odpowiedź, do której podejrzewam, że Chao Xu mógł nawiązać. Po pierwsze zauważ, że równie dobrze możemy znormalizować , jak wskazuje Chao. Teraz rozważ hiperpłaszczyznę normalną do kierunku . Celem jest znalezienie punktu najbliższego tej hiperpłaszczyźnie. W dualności odpowiada to zapytaniu o strzelanie promieniami w układzie hiperpłaszczyzn w celu znalezienia najbliższej płaszczyzny „powyżej” punktu zapytania. Ponieważ można to wstępnie przetworzyć, główną złożonością jest lokalizacja punktu, dlatego problem został zredukowany do złożoności wykonywania lokalizacji punktu w układzie hiperpłaszczyzn. Za pomocą sadzonek można to zrobić w czasie w przestrzeni .xhxO(logn)nd

Suresh Venkat
źródło
1
Powinienem wspomnieć, że jestem również zainteresowany rozsądnym czasem wstępnego przetwarzania, co nie ma miejsca w przypadku, gdy wymiar jest duży.
ilyaraz