Nastavit křižovatku věštce - Set intersection oracle

A nastavit křižovatku Oracle (SIO) je datová struktura což představuje kolekci sad a může rychle odpovídat na dotazy, zda nastavit křižovatku dvou daných sad není prázdná.

Vstup do problému je n konečné množiny. Součet velikostí všech sad je N (což také znamená, že existuje nanejvýš N odlišné prvky). SIO by mělo rychle odpovědět na jakýkoli dotaz ve formuláři:

„Dělá to S_i protínají množinu S_k"?

Minimální paměť, maximální doba dotazu

Bez jakéhokoli předběžného zpracování lze na dotaz odpovědět vložením prvků S_i do dočasného hash tabulka a poté zkontrolovat každý prvek S_k zda je v hash tabulce. Čas dotazu je ${ displaystyle O (| S_ {i} | + | S_ {j} |) = O (N)}$ .

Maximální paměť, minimální doba dotazu

Alternativně můžeme sady předem zpracovat a vytvořit n-podle-n tabulka, kde jsou již zadány informace o křižovatce. Pak je čas na dotaz ${ displaystyle O (1)}$ , ale požadovaná paměť je ${ displaystyle O (n ^ {2})}$ .

Kompromis

Definujte „velkou sadu“ jako sadu alespoň s ${ displaystyle { sqrt {N}}}$ elementy. Je zřejmé, že existují nanejvýš ${ displaystyle { sqrt {N}}}$ takové sady. Vytvořte tabulku dat průniku mezi každou velkou sadou a každou další velkou sadou. To vyžaduje ${ displaystyle O (N)}$ Paměť. U každé velké sady si navíc ponechejte hashovací tabulku všech jejích prvků. To vyžaduje další ${ displaystyle O (N ^ {3/2})}$ Paměť.

Vzhledem ke dvěma sadám existují tři možné případy:

Obě sady jsou velké. Pak jen včas přečtěte odpověď na křižovatku z tabulky ${ displaystyle O (1)}$ .
Obě sady jsou malé. Potom vložte prvky jednoho z nich do hash tabulky a zkontrolujte prvky druhého; protože sady jsou malé, je požadovaný čas ${ displaystyle O ({ sqrt {N}})}$ .
Jedna sada je velká a jedna sada je malá. Obtočte všechny prvky v malé sadě a zkontrolujte je proti hašovací tabulce velké sady. Požadovaný čas je znovu ${ displaystyle O ({ sqrt {N}})}$ .

Obecně platí, že pokud definujeme „velkou množinu“ jako množinu s alespoň ${ displaystyle N ^ {c}}$ prvků, pak je počet velké sady maximálně ${ displaystyle N ^ {1-c}}$ požadovaná paměť je ${ displaystyle O (N ^ {2-c})}$ a čas dotazu je ${ displaystyle O (N ^ {c})}$ .

Redukce na přibližnou vzdálenost věštce

Problém SIO lze snížit na přibližnou hodnotu vzdálenost věštce (DO) problém následujícím způsobem.^[1]

Vytvořte neorientovaný bipartitní graf, kde jedna část obsahuje uzel pro každou z n množiny a druhá část obsahuje uzel pro každou z (maximálně) N prvky obsažené v sadách.
Mezi sadou a prvkem je hrana, pokud sada obsahuje prvek.

Tento graf má následující vlastnosti:

Pokud se dvě sady protínají, vzdálenost mezi nimi je 2 (od jedné sady k prvku v průsečíku k druhé sadě).
Pokud se dvě sady neprotínají, je vzdálenost mezi nimi alespoň 4.

Takže s DO, jehož aproximační faktor je menší než 2, můžeme vyřešit problém SIO.

Předpokládá se, že problém SIO nemá netriviální řešení. Tj. To vyžaduje ${ displaystyle Omega (n ^ {2})}$ prostor pro včasné zodpovězení dotazů ${ displaystyle O (1)}$ . Pokud je tato domněnka pravdivá, znamená to, že neexistuje DO s aproximačním faktorem menším než 2 a konstantním časem dotazu.^[1]

Reference

^ ^A ^b Patrascu, M .; Roditty, L. (2010). Vzdálenost věštců za hranicí Thorup – Zwick. 51. výroční sympozium IEEE 2010 o základech informatiky (FOCS). str. 815. doi:10.1109 / FOCS.2010.83. ISBN 978-1-4244-8525-3.

[pr10-1] A ^b Patrascu, M .; Roditty, L. (2010). Vzdálenost věštců za hranicí Thorup – Zwick. 51. výroční sympozium IEEE 2010 o základech informatiky (FOCS). str. 815. doi:10.1109 / FOCS.2010.83. ISBN 978-1-4244-8525-3.

[1]