Timezone: »

Scaling Up Ordinal Embedding: A Landmark Approach
Jesse Anderton · Javed Aslam

Thu Jun 13 11:00 AM -- 11:20 AM (PDT) @ Room 201

Ordinal Embedding is the problem of placing n objects into R^d to satisfy constraints like "object a is closer to b than to c." It can accommodate data that embeddings from features or distances cannot, but is a more difficult problem. We propose a novel landmark-based method as a partial solution. At small to medium scales, we present a novel combination of existing methods with some new theoretical justification. For very large values of n optimizing over an entire embedding breaks down, so we propose a novel method which first embeds a subset of m << n objects and then embeds the remaining objects independently and in parallel. We prove a distance error bound for our method in terms of m and that it has O(dn log m) time complexity, and show empirically that it is able to produce high quality embeddings in a fraction of the time needed for any published method.

Author Information

Jesse Anderton (Northeastern University)
Javed Aslam (Northeastern University)

Related Events (a corresponding poster, oral, or spotlight)