Täckträd

Täckträdet är en typ av datastruktur inom datavetenskap som är speciellt utformad för att underlätta snabba upp en sökning av närmaste grannar . Det är en förfining av Navigating Net-datastrukturen och relaterad till en mängd andra datastrukturer som utvecklats för att indexera naturligt lågdimensionella data.

Trädet kan ses som en hierarki av nivåer där den översta nivån innehåller rotpunkten och den nedre nivån innehåller varje punkt i det metriska utrymmet. Varje nivå C är associerad med ett heltalsvärde i som minskar med ett när trädet sjunker. Varje nivå C i täckträdet har tre viktiga egenskaper:

• Kapsling: $C_{i}\subseteq C_{i-1}$
• Täckande: För varje punkt $p\in C_{i-1}$ finns det en punkt $q\in C_{i}$ så att avståndet från $p$ till $q$ är mindre än eller lika med $2^{i}$ och exakt en sådan $q$ är en förälder till $p$ .
• Separation: För alla punkter ${\displaystyle p,q\in C_{i}} , är$ avståndet från $p$ till $q$ större än $2 ^{i}$ .

Komplexitet

Hitta

Liksom andra metriska träd tillåter täckträdet sökningar efter närmaste grannar i $O(\eta *\log {n})$ där $\eta$ är en konstant associerad med dimensionaliteten för datasetet och n är kardinaliteten. För att jämföra kräver en grundläggande linjär sökning ${\displaystyle O(n)} ,$ vilket är ett mycket värre beroende av $n$ . Men i högdimensionella metriska utrymmen är konstanten η ${\displaystyle \eta } icke-trivial, vilket innebär$ den inte kan ignoreras i komplexitetsanalys. Till skillnad från andra metriska träd har täckträdet en teoretisk gräns på sin konstant som är baserad på datasetets expansionskonstant eller fördubblingskonstant (vid ungefärlig NN-hämtning). Gränsen för söktiden är $O(c^{12}\log {n})$ där $c$ är expansionskonstanten för datamängden.

Föra in

Även om täckträd ger snabbare sökningar än det naiva tillvägagångssättet, måste denna fördel vägas mot den extra kostnaden för att underhålla datastrukturen. I ett naivt tillvägagångssätt är det trivialt att lägga till en ny punkt i datasetet eftersom ordningen inte behöver bevaras, men i ett täckträd kan det ta $O(c^{6}\log {n})$ tid. Detta är dock en övre gräns, och vissa tekniker har implementerats som verkar förbättra prestandan i praktiken.

Plats

Täckträdet använder implicit representation för att hålla reda på upprepade punkter. Det kräver alltså bara O(n)-utrymme.

Se även

• Närmaste grannsök
• kd-träd

Anteckningar

Bibliografi

• Alina Beygelzimer, Sham Kakade och John Langford. Täck träd för närmaste granne. I Proc. Internationell konferens om maskininlärning (ICML), 2006.
• JL:s omslagsträdsida . John Langfords sida länkar till papper och kod.
• En C++ Cover Tree-implementering på GitHub .
• En täckträdsimplementering i Java.