Skip to Main content Skip to Navigation
Conference papers

Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1

Ioannis Z. Emiris 1, 2 Vasilis Margonis 1 Ioannis Psarros 3
2 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , NKUA - National and Kapodistrian University of Athens
Abstract : Randomized dimensionality reduction has been recognized as one of the fundamental techniques in handling high-dimensional data. Starting with the celebrated Johnson-Lindenstrauss Lemma, such reductions have been studied in depth for the Euclidean (L2) metric, but much less for the Manhattan (L1) metric. Our primary motivation is the approximate nearest neighbor problem in L1. We exploit its reduction to the decision-with-witness version, called approximate near neighbor, which incurs a roughly logarithmic overhead. In 2007, Indyk and Naor, in the context of approximate nearest neighbors, introduced the notion of nearest neighbor-preserving embeddings. These are randomized embeddings between two metric spaces with guaranteed bounded distortion only for the distances between a query point and a point set. Such embeddings are known to exist for both L2 and L1 metrics, as well as for doubling subsets of L2. The case that remained open were doubling subsets of L1. In this paper, we propose a dimension reduction by means of a near neighbor-preserving embedding for doubling subsets of L1. Our approach is to represent the pointset with a carefully chosen covering set, then randomly project the latter. We study two types of covering sets: c-approximate r-nets and randomly shifted grids, and we discuss the tradeoff between them in terms of preprocessing time and target dimension. We employ Cauchy variables: certain concentration bounds derived should be of independent interest.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Ioannis Emiris <>
Submitted on : Saturday, December 7, 2019 - 10:48:21 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM
Long-term archiving on: : Sunday, March 8, 2020 - 2:36:34 PM


Files produced by the author(s)




Ioannis Z. Emiris, Vasilis Margonis, Ioannis Psarros. Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1. APPROX 2019 - Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Sep 2019, Boston, United States. ⟨10.4230/LIPIcs.APPROX-RANDOM.2019.47⟩. ⟨hal-02398741⟩



Record views


Files downloads