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

Abstract

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 highradiation 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.

Keywords

data mining / clustering / resilient algorithms and data structures

References

[1] Castano R, Mazzoni D, Tang N, Doggett T, Chien S, Greeley R, Cichy B, Davies A. Learning classifiers for science event detection in remote sensing imagery. In: Proceedings of the 8th International Symposium on Artificial Intelligence, Robotics and Automation in Space. 2005

[2] Wagstaff K L, Bornstein B. K-means in space: a radiation sensitivity evaluation. In: Proceedings of the 26th International Conference on Machine Learning. 2009, 1097-1104

[3] Wagstaff K L, Bornstein B. How much memory radiation protection do onboard machine learning algorithms require? In: Proceedings of the IJCAI-09/SMC-IT-09/IWPSS-09 Workshop on Artificial Intelligence in Space. 2009

[4] May T C, Woods M H. Alpha-particle-induced soft errors in dynamic memories. IEEE Transactions on Electron Devices, 1979, 26(1): 2-9

[5] Kopetz H. Mitigation of transient faults at the system level — the TTA approach. In: Proceedings of the 2nd Workshop on System Effects of Logic Soft Errors, 2006

[6] Finocchi I, Grandoni F, Italiano G F. Designing reliable algorithms in unreliable memories. Computer Science Review, 2007, 1(2): 77-87

[7] MacQueen J B. Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. 1967, 281-297

[8] Vattani A. k-means requires exponentially many iterations even in the plane. In: Proceedings of the 25th Annual Symposium on Computational Geometry. 2009, 324-332

[9] Arthur D, Manthey B, Röglin H. k-means has polynomial smoothed complexity. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science. 2009, 405-414

[10] Ding C, He X. k-means clustering via principal component analysis. In: Proceedings of the 21st International Conference on Machine Learning. 2004, 225-232

[11] Elkan C. Using the triangle inequality to accelerate k-means. In: Proceedings of the 20th International Conference on Machine Learning. 2003, 147-153

[12] Frahling G, Sohler C. A fast k-means implementation using coresets. International Journal of Computational Geometry and Applications, 2008, 18(6): 605-625

[13] Jin R, Goswami A, Agrawal G. Fast and exact out-of-core and distributed k-means clustering. Knowledge and Information Systems, 2006, 10(1): 17-40

[14] Kanungo T, Mount D M, Netanyahu N S, Piatko C D, Silverman R, Wu A Y. An efficient k-means clustering algorithm: analysis and implementation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(7): 881-892

[15] Sakuma J, Kobayashi S. Large-scale k-means clustering with usercentric privacy-preservation. Knowledge and Information Systems, 2010, 25(2): 253-279

[16] Bentley J L. Multidimensional binary search trees used for associative searching. Communications of the ACM, 1975, 18(9): 509-517

[17] de Berg M, Cheong O, van Kreveld M, Overmars M. Computational Geometry: Algorithms and Applications. 3rd ed. Santa Clara: Springer-Verlag, 2008

[18] Dickerson M, Duncan C A, Goodrich M T. k-d trees are better when cut on the longest side. In: Proceedings of the 8th Annual European Symposium. 2000, 179-190

[19] Brodal G S, Fagerberg R, Finocchi I, Grandoni F, Italiano G, Jørgensen A G, Moruz G, Mølhave T. Optimal resilient dynamic dictionaries. In: Proceedings of the 15th Annual European Symposium on Algorithms. 2007, 347-358

[20] Finocchi I, Grandoni F, Italiano G F. Optimal resilient sorting and searching in the presence of dynamic memory faults. Theoretical Computer Science, 2009, 410(44): 4457-4470

[21] Jørgensen A G,　 Moruz G,　 Mølhave T. Priority queues resilient to memory faults. In: Proceedings of the 10th International Workshop on Algorithms and Data Structure. 2007, 127-138

[22] Petrillo U F, Finocchi I, Italiano G F. The price of resiliency: a case study on sorting with memory faults. In: Proceedings of the 14th Annual European Symposium on Algorithms. 2006, 768-779

[23] Caminiti S, Finocchi I, Fusco E G. Local dependency dynamic programming in the presence of memory faults. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science. 2011, 45-56

[24] Brodal G S, Jørgensen A G, Moruz G, Mølhave T. Counting in the presence of memory faults. In: Proceedings of the 20th Annual International Symposium on Algorithms and Computation. 2009, 842-851

[25] Brodal G S, Jørgensen A G, Mølhave T. Fault tolerant external memory algorithms. In: Proceedings of the 11th International Symposium on Algorithms and Data Structures. 2009, 411-422

[26] Boyer R S, Moore J S. MJRTY: a fast majority vote algorithm. In: Automated Reasoning: Essays in Honor of Woody Bledsoe. 1991, 105-118

[27] Bose P, Maheshwari A, Morin P, Morrison J, Smid M, Vahrenhold J. Space-efficient geometric divide-and-conquer algorithms. Computational Geometry: Theory and Applications, 2007, 37(3): 209-227

[28] Frank A, Asuncion A. UCI machine learning repository. 2010,

[29] Hubert L, Arabie P. Comparing partitions. Journal of Classification, 1985, 2(1): 193-218

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg