Efficient astronomical data condensation using approximate nearest neighbors

Łukasik, Szymon ; Lalik, Konrad ; Sarna, Piotr ; Kowalski, Piotr A. ; Charytanowicz, Małgorzata ; Kulczycki, Piotr

International Journal of Applied Mathematics and Computer Science, Tome 29 (2019) no. 3, pp. 467-476.

Résumé

Extracting useful information from astronomical observations represents one of the most challenging tasks of data exploration. This is largely due to the volume of the data acquired using advanced observational tools. While other challenges typical for the class of big data problems (like data variety) are also present, the size of datasets represents the most significant obstacle in visualization and subsequent analysis. This paper studies an efficient data condensation algorithm aimed at providing its compact representation. It is based on fast nearest neighbor calculation using tree structures and parallel processing. In addition to that, the possibility of using approximate identification of neighbors, to even further improve the algorithm time performance, is also evaluated. The properties of the proposed approach, both in terms of performance and condensation quality, are experimentally assessed on astronomical datasets related to the GAIA mission. It is concluded that the introduced technique might serve as a scalable method of alleviating the problem of the dataset size.

Détail

Keywords: big data, astronomical observation, data reduction, nearest neighbor search, kd-trees
Mots-clés : duży zbiór danych, obserwacja astronomiczna, redukcja danych, wyszukiwanie najbliższego sąsiada, drzewo kd

Bibliographie

[1] Abraham, S., Philip, N.S., Kembhavi, A., Wadadekar, Y.G. and Sinha, R. (2012). A photometric catalogue of quasars and other point sources in the Sloan Digital Sky Survey, Monthly Notices of the Royal Astronomical Society 419(1): 80–94, DOI: 10.1111/j.1365-2966.2011.19674.x.

[2] Arefin, A.S., Riveros, C., Berretta, R. and Moscato, P. (2012). GPU-FS-kNN: A software tool for fast and scalable kNN computation using GPUs, PLoS One 7: e44000, DOI: 10.1371/journal.pone.0044000.

[3] Breunig, M.M., Kriegel, H.-P., Ng, R.T. and Sander, J. (2000). LOF: Identifying density-based local outliers, Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, SIGMOD’00, Dallas, TX, USA, pp. 93–104, DOI: 10.1145/342009.335388.

[4] Bubeck, S. and von Luxburg, U. (2009). Nearest neighbor clustering: A baseline method for consistent clustering with arbitrary objective functions, Journal of Machine Learning Research 10: 657–698.

[5] Burgess, R., Falcão, A.J., Fernandes, T., Ribeiro, R.A., Gomes, M., Krone-Martins, A. and de Almeida, A.M. (2015). Selection of large-scale 3d point cloud data using gesture recognition, in L. Camarinha-Matos et al. (Eds), Technological Innovation for Cloud-Based Engineering Systems, Springer International Publishing, Cham, pp. 188–195, DOI: 10.1007/978-3-319-16766-4 20.

[6] Castro-Ginard, A., Jordi, C., Luri, X., Julbe, F., Morvan, M., Balaguer-Núñez, L. and Cantat-Gaudin, T. (2018). A new method for unveiling open clusters in Gaia: New nearby open clusters confirmed by DR2, Astronomy and Astrophysics 618: A59.

[7] Chung, Y.-Y., Tirthapura, S. and Woodruff, D.P. (2016). A simple message-optimal algorithm for random sampling from a distributed stream, IEEE Transactions on Knowledge and Data Engineering 28(6): 1356–1368, DOI: 10.1109/TKDE.2016.2518679.

[8] Czarnowski, I. and Jedrzejowicz, P. (2017). Learning from examples with data reduction and stacked generalization, Journal of Intelligent Fuzzy Systems 32(2): 1401–1411.

[9] Dutta, H., Giannella, C., Borne, K. and Kargupta, H. (2005). Distributed top-K outlier detection from astronomy catalogs using the DEMAC system, 2007 SIAM International Conference on Data Minning, Minneapolis, MN, USA, pp. 473–478, DOI: abs/10.1137/1.9781611972771.47.

[10] Eastman, C. and Weiss, S. (1982). Tree structures for high dimensionality nearest neighbor searching, Information Systems 7(2): 115–122.

[11] Freudling, W. and Romaniello, M. (2016). Delivering data reduction pipelines to science users, SPIE Proceedings 9910: 99101U, DOI: 10.1117/12.2232734.

[12] Freudling, W. Romaniello, M., Bramich, D.M., Ballester, P., Forchi, V., Garcia-Dablo, C.E., Moehler, S. and Neeser, M.J. (2013). Automated data reduction workflows for astronomy. The ESO Reflex environment, Astronomy and Astrophysics 559: A96, DOI: 10.1051/0004-6361/201322494.

[13] GAIA (2018), GAIA Mission, https://www.cosmos.esa.int/gaia.

[14] Grandinetti, L., Joubert, G., Kunze, M. and Pascucci, V. (2015). Big Data and High Performance Computing, Advances in Parallel Computing, IOS Press, Amsterdam.

[15] Hassan, A. and Fluke, C.J. (2011). Scientific visualization in astronomy: Towards the petascale astronomy era, Publications of the Astronomical Society of Australia 28(2): 150–170.

[16] Huang, D. and Chow, T.W.S. (2006). Enhancing density-based data reduction using entropy, Neural Computation 18(2): 470–495, DOI: 10.1162/089976606775093927.

[17] Kulczycki, P. (2008). Kernel estimators in industrial applications, in B. Prasad (Ed.), Soft Computing Applications in Industry, Springer, Berlin/Heidelberg, pp. 69–91, DOI: org/10.1007/978-3-540-77465-5 4.

[18] Li, L., Zhang, Y. and Zhao, Y. (2008). k-Nearest neighbors for automated classification of celestial objects, Science in China G: Physics, Mechanics and Astronomy 51(7): 916–922, DOI: 10.1007/s11433-008-0088-4.

[19] Łukasik, S., Lalik, K., Sarna, P., Kowalski, P.A., Charytanowicz, M. and Kulczycki, P. (2019). Efficient astronomical data condensation using fast nearest neighbor search, in P. Kulczycki et al. (Eds), Information Technology, Systems Research and Computational Physics, Advances in Intelligent Systems and Computing, Vol. 945, Springer, Berlin/Heidelberg, pp. 107–115.

[20] Łukasik, S., Moitinho, A., Kowalski, P.A., Falcão, A., Ribeiro, R.A. and Kulczycki, P. (2016). Survey of object-based data reduction techniques in observational astronomy, Open Physics 14(1): 64, DOI: 10.1515/phys-2016-0064.

[21] MPI Forum (2015). MPI: A Message-passing Interface Standard: Version 3.1, High-Performance Computing Center, Stuttgart, https://www.mpi-forum.org/docs/mpi-3.1/mpi31-report.pdf.

[22] Mitra, P., Murthy, C. and Pal, S.K. (2002). Density-based multiscale data condensation, IEEE Transactions on Pattern Analysis and Machine Intelligence 24(6): 734–747, DOI: 10.1109/TPAMI.2002.1008381.

[23] Muja, M. and Lowe, D.G. (2014). Scalable nearest neighbor algorithms for high dimensional data, IEEE Transactions on Pattern Analysis Machine Intelligence 36(11): 2227–2240, DOI: 10.1109/TPAMI.2014.2321376.

[24] Olvera-López, J., Ariel Carrasco-Ochoa, J., Martnez-Trinidad, J.F. and Kittler, J. (2010). A review of instance selection methods, Artificial Intelligence Review 34(2): 133–143.

[25] OpenMP Architecture Review Boards (2015). OpenMP 4.5 Complete Specifications, https://www.openmp.org/wp-content/uploads/openmp-4.5.pdf.

[26] Rocke, D.M. and Dai, J. (2003). Sampling and subsampling for cluster analysis in data mining: With applications to sky survey data, Data Mining and Knowledge Discovery 7(2): 215–232, DOI: 10.1023/A:1022497517599.

[27] Ros, F. and Guillaume, S. (2017). DIDES: A fast and effective sampling for clustering algorithm, Knowledge and Information Systems 50(2): 543–568, DOI: 10.1007/s10115-016-0946-8.

[28] Schirmer, M. (2013). THELI: Convenient reduction of optical, near-infrared, and mid-infrared imaging data, The Astrophysical Journal Supplement Series 209(2): 21, DOI: 10.1088/0067-0049/209/2/21.

[29] Szalay, A. and Gray, J. (2001). The world-wide telescope, Science 293(5537): 2037–2040.

[30] Wang, D., Shi, L. and Cao, J. (2013). Fast algorithm for approximate k-nearest neighbor graph construction, 2013 IEEE 13th International Conference on Data Mining Workshops, Dallas, TX, USA, pp. 349–356, DOI: 10.1109/ICDMW.2013.50.

[31] Wang, X., Tino, P., Fardal, M.A., Raychaudhury, S. and Babul, A. (2009). Fast Parzen window density estimator, 2009 International Joint Conference on Neural Networks, Atlanta, GA, USA, pp. 3267–3274, DOI: 10.1109/IJCNN.2009.5178637.

[32] Yianilos, P.N. (1993). Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’93, Austin, TX, USA, Vol. 93, pp. 311–321.

[33] Zhang, Y., Chung, F. and Wang, S. (2018). Fast reduced set-based exemplar finding and cluster assignment, IEEE Transactions on Systems, Man, and Cybernetics: Systems 49(5): 1–15.

[34] Zhang, Y.-M., Huang, K., Geng, G. and Liu, C.-L. (2013). Fast kNN graph construction with locality sensitive hashing, in H. Blockeel et al. (Eds), Machine Learning and Knowledge Discovery in Databases, Springer, Berlin/Heidelberg, pp. 660–674, DOI: 10.1007/978-3-642-40991-2 42.