Efficient Astronomical Data Condensation Using Approximate Nearest Neighbors

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

doi:10.2478/amcs-2019-0034

Abstract

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.

References

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 Society419(1): 80–94, DOI: 10.1111/j.1365-2966.2011.19674.x.10.1111/j.1365-2966.2011.19674.x
Open DOI Search in Google Scholar Back to article
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 One7: e44000, DOI: 10.1371/journal.pone.0044000.10.1371/journal.pone.0044000
Search in Google Scholar Back to article
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.10.1145/342009.335388
Search in Google Scholar Back to article
Bubeck, S. and von Luxburg, U. (2009). Nearest neighbor clustering: A baseline method for consistent clustering with arbitrary objective functions, Journal of Machine Learning Research10: 657–698.
Search in Google Scholar Back to article
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.10.1007/978-3-319-16766-4_20
Open DOI Search in Google Scholar Back to article
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 Astrophysics618: A59.10.1051/0004-6361/201833390
Search in Google Scholar Back to article
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 Engineering28(6): 1356–1368, DOI: 10.1109/TKDE.2016.2518679.10.1109/TKDE.2016.2518679
Open DOI Search in Google Scholar Back to article
Czarnowski, I. and Jedrzejowicz, P. (2017). Learning from examples with data reduction and stacked generalization, Journal of Intelligent & Fuzzy Systems32(2): 1401–1411.10.3233/JIFS-169137
Search in Google Scholar Back to article
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.1137/1.9781611972771.47
Open DOI Search in Google Scholar Back to article
Eastman, C. and Weiss, S. (1982). Tree structures for high dimensionality nearest neighbor searching, Information Systems7(2): 115–122.10.1016/0306-4379(82)90023-0
Search in Google Scholar Back to article
Freudling, W. and Romaniello, M. (2016). Delivering data reduction pipelines to science users, SPIE Proceedings9910: 99101U, DOI: 10.1117/12.2232734.10.1117/12.2232734
Search in Google Scholar Back to article
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 Astrophysics559: A96, DOI: 10.1051/0004-6361/201322494.10.1051/0004-6361/201322494
Open DOI Search in Google Scholar Back to article
GAIA (2018), GAIA Mission, https://www.cosmos.esa.int/gaia.
Search in Google Scholar Back to article
Grandinetti, L., Joubert, G., Kunze, M. and Pascucci, V. (2015). Big Data and High Performance Computing, Advances in Parallel Computing, IOS Press, Amsterdam.
Search in Google Scholar Back to article
Hassan, A. and Fluke, C.J. (2011). Scientific visualization in astronomy: Towards the petascale astronomy era, Publications of the Astronomical Society of Australia28(2): 150–170.10.1071/AS10031
Search in Google Scholar Back to article
Huang, D. and Chow, T.W.S. (2006). Enhancing density-based data reduction using entropy, Neural Computation18(2): 470–495, DOI: 10.1162/089976606775093927.10.1162/08997660677509392716378523
Open DOI Search in Google Scholar Back to article
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.10.1007/978-3-540-77465-5_4
Open DOI Search in Google Scholar Back to article
Li, L., Zhang, Y. and Zhao, Y. (2008). k-Nearest neighbors for automated classification of celestial objects, Science in China G: Physics, Mechanics and Astronomy51(7): 916–922, DOI: 10.1007/s11433-008-0088-4.10.1007/s11433-008-0088-4
Open DOI Search in Google Scholar Back to article
Ł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.10.1007/978-3-030-18058-4_9
Search in Google Scholar Back to article
Ł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 Physics14(1): 64, DOI: 10.1515/phys-2016-0064.10.1515/phys-2016-0064
Open DOI Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Mitra, P., Murthy, C. and Pal, S.K. (2002). Density-based multiscale data condensation, IEEE Transactions on Pattern Analysis and Machine Intelligence24(6): 734–747, DOI: 10.1109/TPAMI.2002.1008381.10.1109/TPAMI.2002.1008381
Open DOI Search in Google Scholar Back to article
Muja, M. and Lowe, D.G. (2014). Scalable nearest neighbor algorithms for high dimensional data, IEEE Transactions on Pattern Analysis & Machine Intelligence36(11): 2227–2240, DOI: 10.1109/TPAMI.2014.2321376.10.1109/TPAMI.2014.232137626353063
Open DOI Search in Google Scholar Back to article
Olvera-López, J., Ariel Carrasco-Ochoa, J., Martnez-Trinidad, J.F. and Kittler, J. (2010). A review of instance selection methods, Artificial Intelligence Review34(2): 133–143.10.1007/s10462-010-9165-y
Search in Google Scholar Back to article
OpenMP Architecture Review Boards (2015). OpenMP 4.5 Complete Specifications, https://www.openmp.org/wp-content/uploads/openmp-4.5.pdf.
Search in Google Scholar Back to article
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 Discovery7(2): 215–232, DOI: 10.1023/A:1022497517599.10.1023/A:1022497517599
Open DOI Search in Google Scholar Back to article
Ros, F. and Guillaume, S. (2017). DIDES: A fast and effective sampling for clustering algorithm, Knowledge and Information Systems50(2): 543–568, DOI: 10.1007/s10115-016-0946-8.10.1007/s10115-016-0946-8
Open DOI Search in Google Scholar Back to article
Schirmer, M. (2013). THELI: Convenient reduction of optical, near-infrared, and mid-infrared imaging data, The Astrophysical Journal Supplement Series209(2): 21, DOI: 10.1088/0067-0049/209/2/21.10.1088/0067-0049/209/2/21
Open DOI Search in Google Scholar Back to article
Szalay, A. and Gray, J. (2001). The world-wide telescope, Science293(5537): 2037–2040.10.1126/science.293.5537.203711557879
Search in Google Scholar Back to article
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.10.1109/ICDMW.2013.50
Open DOI Search in Google Scholar Back to article
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.10.1109/IJCNN.2009.5178637
Open DOI Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Zhang, Y., Chung, F. and Wang, S. (2018). Fast reduced set-based exemplar finding and cluster assignment, IEEE Transactions on Systems, Man, and Cybernetics: Systems49(5): 1–15.10.1109/TSMC.2017.2689789
Search in Google Scholar Back to article
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.10.1007/978-3-642-40991-2_42
Open DOI Search in Google Scholar Back to article

Efficient Astronomical Data Condensation Using Approximate Nearest Neighbors

Abstract

Paradigm

My account