Resilient k-d trees: k-means in space revisited

TY - JOUR

T1 - Resilient k-d trees

T2 - k-means in space revisited

AU - Gieseke, Fabian

AU - Moruz, Gabriel

AU - Vahrenhold, Jan

PY - 2012

Y1 - 2012

N2 - We propose a k-d tree variant that is resilient to a pre-described number of memory corruptions while still using only linear space. While the data structure is of independent interest, we demonstrate its use in the context of high-radiation environments. Our experimental evaluation demonstrates that the resulting approach leads to a significantly higher resiliency rate compared to previous results. This is especially the case for large-scale multi-spectral satellite data, which renders the proposed approach well-suited to operate aboard today's satellites.

AB - We propose a k-d tree variant that is resilient to a pre-described number of memory corruptions while still using only linear space. While the data structure is of independent interest, we demonstrate its use in the context of high-radiation environments. Our experimental evaluation demonstrates that the resulting approach leads to a significantly higher resiliency rate compared to previous results. This is especially the case for large-scale multi-spectral satellite data, which renders the proposed approach well-suited to operate aboard today's satellites.

KW - clustering

KW - data mining

KW - resilient algorithms and data structures

UR - http://www.scopus.com/inward/record.url?scp=84859216475&partnerID=8YFLogxK

U2 - 10.1007/s11704-012-2870-8

DO - 10.1007/s11704-012-2870-8

M3 - Journal article

AN - SCOPUS:84859216475

SN - 2095-2228

VL - 6

SP - 166

EP - 178

JO - Frontiers of Computer Science

JF - Frontiers of Computer Science

IS - 2

ER -