4 ms·
The method gives a data structure for any metric space, and the quality of the data structure is controlled by how well expanders embed in the metric space. Thi
by thesasho 8y ago
The method gives a data structure for any metric space, and the quality of the data structure is controlled by how well expanders embed in the metric space. This implies interesting results for metrics which are not norms, like geodesics on certain manifolds. The surprise to us was how well this approach works for any norm, however. (I am one of the authors.)
Also, a math correction: spaces which obey the triangle inequality are called metric spaces. The class of normed spaces is more restricted, but still very large.
- macleginn 8y agoBut these more general results are kind of small print, right? The abstracts to both linked articles talk specifically about normed spaces. (Thanks for the correction. I just gave one of the properties, but should’ve been more precise.)
- curious1212 8y agoI don't think the general property of expander graphs is needed, perhaps a relaxed property, such as the following definition: A graph G is a distance(k)-expander if #edges(U, V-U) > c min(#U,#(V-U)) where U is a set of diameter <=k. Now study the embeding. I am also curious about what happens if one use SVM to classify vertices of an expander graph: Let G be an expander graph and let u1,u2 be vertices of G such that d(u1,u2) = diameter of G = an even number 2k. We classify the vertices of G like this: f(u) = 0 if d(u,u1)<=k, f(u)=1 if d(u,u1)>=1, then using SVM applied to the vertices encoded by the rows of the adjancecy matrix. I would expect the SVM algorith to have some special property but I don't know what to expect, the best or worst classification, or the support vectors can gives us some information about symmetries in the graph.