I detta papper studerar vi problemet med att hitta den ungefärliga närmaste granne till en frågepunkt i den höga dimensionella rymden, med fokus på den euklideiska rymden. De tidigare tillvägagångssätten använder locality-bevarande hash funktioner (som tenderar att kartlägga närliggande punkter till samma värde) för att konstruera flera hash tabeller för att säkerställa att frågepunkten hashes till samma hink som dess närmaste granne i minst en tabell. Vår strategi är olika vi använder en (eller några) hash tabell och hash flera slumpmässigt valda punkter i närheten av frågepunkten visar att åtminstone en av dem kommer hash till hinken som innehåller sin närmaste granne. Vi visar att antalet slumpmässigt valda punkter i grannskapet av frågepunkten q krävs beror på entropin av hashvärdet h(p) av en slumpmässig punkt p på samma avstånd från q på dess närmaste granne, givet q och lokaliteten bevara hash funktion h väljs slumpmässigt från hash familjen. Just det, vi visar att om entropin I(h(p)-q, h) = M och g är bunden på sannolikheten att två avlägsna punkter kommer hash till samma hink, då kan vi hitta den ungefärliga närmaste granne i O(n ρ ) tid och nära linjär Õ(n) utrymme där ρ = M/ log(1/g). Alternativt kan vi bygga en datastruktur av storlek Õ(n 1/(1=ρ) ) för att svara på frågor iñ O(d) tid. Genom att tillämpa denna analys på lokaliteten bevara hash funktioner i [17, 21, 6] och justera parametrarna visar vi att c närmaste granne kan beräknas i tid Õ(n ρ ) och nära linjärt utrymme där ρ  och 2.06/c som c blir stor. SODA '06, 22-26 januari, Miami, FL
I REF visar Panigrahy att i stället för att använda ett stort antal haschtabeller som det är fallet i metoden ovan, kan bara ett fåtal användas.
Entropy based nearest neighbor search in high dimensions
{'venue': "SODA '06", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}