GeoMetric Embedding Kit 2.0

Applications Presentation

A recent Embedding Applications Presnetation including Distance Estimation and distributed Multicast Tree results.

Publications

[1] Yuval Shavitt and Tomer Tankel. Hyperbolic embedding of Internet graph for Distance Estimation and Overlay Construction (previously: On Internet embedding in Hyperbolic spaces for Overlay construction and Distance Estimation)

Abstract IEEE/ACM Trans. on Networking, April 2008.

[2] Yuval Shavitt and Tomer Tankel. On the curvature of the interent and its usage for Overlay Construction and Distance Estimation

Abstract IEEE INFOCOM 2004, March 2004, Hong-Kong.

[3] Yuval Shavitt and Tomer Tankel. Big-Bang Simulation for embedding network distances in Euclidean space

IEEE/ACM Trans. on Networking, Dec. 2004

Software

  • GeoMetric Embedding Kit 2.0: (win2k(VC6/7) or win2k(VC8))
    This is a flexible model designed for embedding various metrics, such as graph, in Geometric Space, using a wide variety of embedding solvers.

The kit comprises of

    1. GeometricApprox.dll
      Generic Geometric Space Embedder. Supports two modes of embedding:
      1. N nodes.
        Calculates coordinates of all N nodes using all N*(N-1)/2 distances.
      2. Single node.
        Calculates coordinates of single node given its N distances from other nodes, using their existing coordinates, which were calculated earlier by N nodes mode.

 

    1. TGeoApprox.exe
      Test program for embedding simulated metric.
    2. GeoSolver.exe
      Utility program for reading metric from input file and embedding it.
  • Graph metric launch script
    Available separately from the embedding kit. Creates metric from input graph and calls Graph_Embedding_Solver matlab function. This function launches one of the embedding solvers that are described in [2], according to the method_name command-line parameter:
    1. GX.M and GXH.M: Euclidean and Hyperbolic BBS method
      Available in the common GeometricApprox.dll which is part of embedding kit.
    2. GX.DHS and GXH.DSH: Euclidean and Hyperbolic Down-Hill Simplex method
      Available in the GdhSimplex.dll, which is part of embedding kit.
    3. MDS: Multi-Dimensional Scaling
      Implemented as matlab script.
    4. SDP: Semi-Definite-Programming
      Implemented as matlab script and SDP solver executable .
    5. M2R: MST2RST Topology Aggregation metohd
      Launch a separate executable .
  • Here are instructions on how to unpack, compile and run the distribution.
  • Here is FAQ of installation, compilation and the numerical method.

Members

Alumni

Contact information:

Tel Aviv University
Ramat Aviv 69978
ISRAEL
Tel: +972 3 640 8659
Fax: +972 3 640 5027 or 7095

tankel@eng.tau.ac.il
Last updated 2004/11/10
This material is based upon work supported by a grant from the United States Israel Binational Science Foundation (BSF), Jerusalem, Israel. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.