Abstrakt
Článek se zabývá algoritmy hledání nejlepšího (k-nejlepších) objektů v distribuovaných systémech, zejména na webu. Předpokládáme, že každý zdroj vrací objekty uspořádané podle zvoleného kriteria (kriterií), otázkou je, které zdroje dotazovat, abychom našli nejlepší objekt(y) na co nejméně dotazů.
Známé algoritmy jsou většinou založené na výpočtu gradientu, tj. lokálním odhadu. V tomto článku ukazujeme, že je často možné odhadnout celé pravděpodobnostní rozložení hodnot jevů (za předpokladu nezávislosti či znalosti modelu).
Globální znalost pravděpodobnostního rozložení umožní lépe optimalizovat hledání nejlepších objektů, nicméně experimenty ukazují, že heuristické metody jsou v testovaných příkladech blízko optima. Výpočet optimálního zdroje pro dotaz vede k výpočtu několikanásobných intergrálů; přímý výpočet lze nahradit přibližným výpočtem (např. metodou Monte Carlo).
Alternativní možností je přijmout diskutabilní předpoklad rovnoměrného rozložení a používat odvozené vzorce jako heuristiky.