Algorithme de base

A la base, l'algorithme du crossmatch donsiste à prendre les deux catalogues avec pour chaque source, les coordonnées radec, l'ID et leur cellule healpix. On joint sur l'indice healpix, ce qui reient à faire un produit cartésien dans chaque case, de façon à obtenir toutes les associations possibles de sources dans chaque cases, puis on filtre sur la distance angulaire qui doit être inférieure au rayon de crossmatch.

Avantages et inconvénients

Si on a des tuiles healpix très fournies, le produit carésien va être gigantesque, et cela prendra un temps considérable.

C'est en revance très bien adapté pour des catalogues avec seulement quelques sources par tuiles.

Pistes d'amélioration

On pourrrait adapter la taille des tuiles dynamiquement, mais cela nous pose un problème de collocation des données. De plus il est difficile de prévoir le nomre de souces dans une tuile : Si on se base sur le premier catalogue, on peut en déduire "il faudraist subdiviser" mais il se peut que le catalogue 2 n'aie que très peu de sources pour cette tuile et que cela rende l'initiative inutile.

On pourrait envisager un 2e algo qui soit efficace pour les tuiles très peuplées et choisir entre cet algo et le produit cartésien selon le nombre de sources à traiter.

KD-Tree ou Produit Cartésien ?

KD-Tree Kesaco ?

Le KD-Tree est une généralisation du Quicksort à k dimentions. Il procède par dicotomie pour rechercher un élément. Il itère sur chaque dimention puis recommence le nombre de fois qu'il faut.

Pour l'utiliser, il faut d'abord construire l'arbre puis requêter dedans.

Mise en place du choix d'algorithme

La précédente structure de données ne permettait pas d'accéder facilement à toutes les sources d'une tuile. Or cela est nécéssaire pour pouvoir choisir entre les algos, selon le peuplement. Il a donc fallu changer la structure des données en ayant une liste de sources pour chaque tuile healpix elles mêmes stockées dans un RDD.

Autre subtilité : le KD-tree tel que je l'ai trouvé fonctionne dans des espaces cartésiens. il fallait donc les doordonnées cartésiennes des sources et non équatoriales. La conversion s'effectue au moment du chargement et affinage du catalogue dans HDFS. Ainsi, elle ne ralentit pas l'exécution des crossmatchs.

Attention aux subtilités entre le rayon angulaire de crossmatch en radians et le rayon de crossmatch qui est une distance ( Rxyz=2sin(Rradec/2) )

Critère de choix

Si on pose n et m le nombre de sources dans les catalogues 1 et 2.

La complexité du produit cartésien est en m*n

La complexité du KD-Tree est en (m+n)log2(m)

J'ai fait des tests pour avoir quelques metrics et pouvoir déterminer les constantes.

https://drive.google.com/open?id=0BwQ_Co50PY9vR1RYZjlXVG1PcDA

https://drive.google.com/open?id=0BwQ_Co50PY9vXzRGT3IyTXkzR28

J'en ai donc déduis que ma condition pour operer le produit cartésien devait être : m*n < 7*(n+m)*log2(m) , KD-Tree sinon.

Quel KD-Tree ?

Scipy propose de façons de requêter sur un kd-tree. Soit en intersectant deux KD-trees soit en cherchant chaque point d'un ensemble dans le premier kd-tree.

Lequel utiliser ? Suite à mes metrics, j'ai pu observer que la requête sur les arbres est beaucoup plus efficace pour les grands ensembles, et sensiblement identique pour les petits. Comme on utilisera le produit catrésien pour les petits ensembles, nous sommens surtout intéressés par les requêtes sur les grands ensembles, et nous priviligierons dons la requête sur les arbres.

Metrics : https://drive.google.com/open?id=1eMq3fT_oo3p3COLV2fmspfu_8Jne92SD