Direction des Relations et Internationales (DRI)

Programme INRIA "Equipes Associées"

I. DEFINITION

Rapport financier 2009

Avant de remplir les tableaux, consultez les règles au paragraphe "Financement" de la page d'accueil du programme.

Remarks:

• Quentin Mérigot's and Pooran Memari's visits to Stanford have cost less than expected because they obtained additional support from the région PACA (1800 euros in total).
• Quentin's mission to SPM'09 has cost less than expected because he obtained a travel grant from SIAM to cover his registration fee and housing expenses (500 euros in total).
• The remainder of the 2009 budget will be used to cover the travel expenses of a student from Geometrica for his visit to Stanford next year (see our exchange program for 2010 below). The dates of this visit have not yet been set but should be before the end of the calendar year, so all the 2009 budget will be spent by that time.

Bilan des échanges effectués en 2009

• Quentin Mérigot spent a month and a half in Stanford in the Spring: he finalized his paper with Maksim Ovsjanikov on integral curvature estimation from point cloud data.
• Steve Oudot spent a month in Stanford in the Summer: he started a new project with Camille Wormser (ETH) and Leonidas Guibas on the efficient computation of Rips filtrations in medium and high dimensions based on a pruning strategy.
• In July, Leonidas Guibas and five students from Stanford (Facundo Mémoli, Mikael Vejdemo-Johansson, Dmitriy Morozov, Peter Huang, and Maksim Ovsjanikov) spent a few days in Paris to attend the TGDA workshop. Mikael and Dmitriy stayed longer (10 days for Mikael, 3 weeks for Dmitriy) to interact with the members of Geometrica in Saclay on topics related to the novel zig-zag persistence theory.
• Pooran Memari is currently spending a month and a half at Stanford, where she is exploring the potential applications of the 3d shape reconstruction technique from cross-sections she has devised with her advisor Jean-Daniel Boissonnat.
• Frédéric Chazal and Jean-Daniel Boissonnat will each spend 2 weeks in Stanford in early 2010. Their travel expenses will be covered by the 2009 budget of TGDA.
• Jean-Daniel's visit will occur right after the 20th Symposium on Discrete Algorithms (SODA'10) in Austin, which he will attend with Steve Oudot, Frédéric Chazal and Leonidas Guibas. They will meet to discuss about the future of TGDA. Jean-Daniel's, Steve's and Frédéric's missions will be covered by the 2009 budget of the associated team.
• Finally, let us mention that, in addition to the above exchanges, Primoz Skraba, a PhD student from the Geometric Computing group, joined Geometrica in 2009 for a one-year post-doctoral internship. He contributed actively to the elaboration of the scalar fields analysis algorithm, as well as to its adaptation in the context of clustering.

1. Chercheurs Seniors

(1) DR / CR / professeur
(2) colloque, thèse, stage, visite....
(3) précisez l'unité (mois, semaine..)

2. Juniors

(1) post-doc / doctorant / stagiaire
(2) colloque, thèse, stage, visite....
(3) précisez l'unité (mois, semaine..)

III. PREVISIONS 2010

Programme de travail

Since 2009, the Geometrica group has been part of a joint effort with the Geometric Computation and Applied Topology groups at Stanford University to develop the successor of the PLEX library, now considered a standard in computational topology. The new library, named CULT ( Computational Unified Library for Topology), will offer a vast set of tools that reflect the state of the art in the field. It should be able to handle very large and high-dimensional data sets within reasonable amount of time and space, while keeping enough flexibility for people to be able to build their own algorithms upon it. Potential interactions with other libraries like CGAL will also be investigated. We are setting the development of the first release of the library among our primary goals for the upcoming years, and especially for 2010.

Algorithmic aspects

Making the library effective will require a lot of work on designing new data structures whose complexities scale up reasonably with the size and dimensionality of the input data. To give an idea of the challenge, each time the dimension of the Rips complex is increased by one, its size is multiplied roughly by ten. As a result, people commonly have to deal with complexes containing dozens of millions of simplices. Such complexes do not fit into main memory, at least with a naive data representation. On the other hand, brute-force compression of the data results in prohibitively slow access times. A trade-off between space and time has to be found, which will be one of the objectives of Marc Glisse, a new chargé de recherches joining Geometrica and TGDA this Fall.

Another way of dealing with massive data sets is to design out-of-core algorithms. Our clustering scheme is one example: even though the input is in the form of a distance matrix, the algorithm only has to scan the matrix once and column-wise, loading only one column at a time in main memory. As a result, the algorithm can deal with data sets containing millions of points within a few minutes, with a memory consumption that is only linear in the size of the point cloud. This property motivated our choice of making this code the very first one to be inserted in the CULT library, so as to set a standard for future code developments. Can other algorithms in the computational topology literature be made out-of-core?

Another question related to data structures is how fast they can be updated under point insertions and deletions. Constructions in topological data analysis mostly rely on comparisons between distances, simply because more elaborate geometric predicates are difficult (if at all possible) to implement in high dimensions. Thus, nearest neighbor queries and reverse nearest neighbor queries are by far the most common during updates. Alhough the former type of queries has been well studied in the past and can be performed reasonably fast, there is hardly any literature on the latter type of queries. We are currently collaborating with two Ph.D. students in the Theory group at Stanford University to devise a data structure based on Locality-Sensitive Hashing (LSH) that answers (approximate) reverse nearest neighbor queries in sublinear time, with a complexity that scales up polynomially with the ambient dimension. This data structure uses LSH as a black-box and reduces the approximate reverse nearest neighbor problem to the Point Location Among Equal Balls problem, in the same spirit as in the original LSH paper but with a completely different construction. A paper on the subject is currently being written and should be submitted in 2010. Then, the dynamic version of the problem, where new data points may be inserted or old ones deleted, will be considered.

Targeted applications

Many potential applications of our work might be considered, and our hope is that the CULT library eventually becomes a standard tool for developing such applications. In a near future we intend to focus primarily on the following ones:

• Soft clustering: the stability properties of our persistence-based clustering algorithm open the door to a more statistical approach to clustering: since parts of the clusters remain stable under perturbations of the underlying density function, we can conduct multiple runs of the algorithm with random pertubations of the input data, and find correspondences between the outputs of different runs. Each point can then be assigned a quantitative measure of its classification stability over the runs. What is the gain of such an approach? Does it bring in some more stability? Does it allow to better approximate the basins of attraction of the density function?
• Partial shape comparison: our persistence-based signatures for shapes are global, therefore they can only be used for global shape classification. What can be said when only parts of two given shapes coincide? Can we derive more local yet still meaningful signatures in this context? We have just hired a master student to make preliminary experiments and evaluate the difficulty of the problem.

Mathematical aspects

In the context of topological inference from point cloud data, people have been primarily interested in the early parts of the filtrations they built, as the rest of these ever-growing families of complexes quickly became too big to be stored. The bottomline was that inferring the homology of the space underlying the input point cloud only required to know the beginning of the barcode associated with the filtration. In fact, the very notion of the {\em space underlying the data} is subject to interpretation and depends on the scale at which the data is inspected. Take for instance a point cloud sampled from a helicoidal curve that is drawn on the Clifford torus in R^4. This data set admits at least three candidate underlying spaces: at a small scale, the curve; at a larger scale, the torus; and at an even larger scale, the 3-sphere of radius sqrt(2) on which the Clifford torus is naturally embedded. One might also add the point cloud itself and R^4 at either ends of the spectrum. It would be very interesting to see if these various possible answers appear in the barcodes of our filtrations, with transition effects between scales. For this we need to be able to compute the full filtrations, or at least to approximate their full barcodes. Two projects in this direction have been started:

• the first one uses the so-called Sparse Voronoi Refinement strategy to enrich the input point cloud in such a way that the size of the Delaunay triangulation becomes resonable. Then, the offsets filtration of the input point cloud can be approximated by its trace over the Voronoi tesselation. This approach is suitable for datasets lying in medium-dimensional Euclidean spaces.
• another more high-dimensional approach builds a standard Rips filtration but while doing its prunes out some of the vertices, depending on certain intrinsic coverage criteria. The complexity of the approach depends only on the intrinsic dimensionality of the data, not on the ambient dimension, but the price to pay is an increased error in the approximation of the barcode. Can this error be bounded?

Programme d'échanges avec budget prévisionnel

1. Echanges

Our goal for 2010 will be to keep up the rate of exchanges to the same level as in 2008-2009, especially at junior level :

• Geometrica will send at least one PhD student to Stanford for a long-term stay (2-3 months). The choice of the student and dates are still under discussion at this time (maybe Arijit Ghosh or Claire Caillerie), since Quentin and Pooran will have left the group after completing their PhDs.
• Differently from this year, some students from Stanford will make long-term visits (2-3 months) to INRIA:
  • Maksim Ovsjanikov will spend another 2 to 3 months to maintain the fruitful collaboration between the two groups on the study of curvature estimation from point cloud data and of its applications in shape segmentation and classification.
  • At least another PhD student from Stanford will spend a quarter at INRIA to further develop interactions at junior level. His name (maybe Peter Huang) will depend on our choice of future directions of research for our collaboration, to be discussed at SODA'10 in January.
• At a more senior level, Frédéric Chazal and Jean-Daniel Boissonnat will each spend 2 weeks at Stanford in early 2010, and Steve Oudot will spend a month at Stanford some time in 2010.
• Conversely, Leonidas guibas will spend a month in Saclay during the Fall of 2010.

In addition to the above exchanges, let us mention that the post-doctoral internship of Primoz Skraba in the Geometrica group will be continued in 2010, funded by the ANR grant GIGA (started this Fall). Conversely, Quentin Mérigot will start a post-doctoral internship in the Geometric Computation group at Stanford University in January.

2. Cofinancement

Cette coopération bénéficie-t-elle déjà d'un soutien financier de la part de l'INRIA, de l'organisme étranger partenaire ou d'un organisme tiers (projet européen, NSF, ...) ?

• Leonidas Guibas will provide about 13000 euros through several NSF grants, to cover the local expenses of visitors from Geometrica.
• Geometrica will allocate up to 4000 euros from its ANR grant GIGA and the Digiteo Chair of Vin de Silva, to cover the overhead of our budget in 2010.

3. Demande budgétaire

Indiquez, dans le tableau ci-dessous, le coût global estimé de la proposition et le budget demandé à la DRI dans le cadre de cette Equipe Associée.
(maximum 20 K€ pour une prolongation en 2e année et 10 K€ pour une 3e année).

Remarques ou observations :