A geometric view of partial order embedding

by Matthew Skala

Applications in linguistics and the Semantic Web motivate the problem of
embedding an arbitrary abstract partial order into a concrete,
computationally feasible one.  Geometric containment orders (of spheres,
ellipsoids, or other objects) provide one important class of candidates
for the well-behaved embedding target; subset containment over arbitrary
finite sets provides another.  Both are amenable to dimensionality
reduction, with or without relaxing the embedding to an approximation.
We review existing results in this area and present our latest work on it.