On Projection Based Operators in l_p Space for Exact Similarity Search

Article type: Research Article

Authors: Wichert, Andreas | Moreira, Catarina

Affiliations: Department of Informatics, INESC-ID / IST - University of Lisboa, Lisboa, Portugal. andreas.wichert@tecnico.ulisboa.pt; catarina.p.moreira@ist.utl.pt

Note: [] Address for correspondence: Department of Informatics, INESC-ID / IST - University of Lisboa, Lisboa, Portugal.

Abstract: We investigate exact indexing for high dimensional lp norms based on the 1-Lipschitz property and projection operators. The orthogonal projection that satisfies the 1-Lipschitz property for the lp norm is described. The adaptive projection defined by the first principal component is introduced.

Keywords: 1-Lipschitz property, curse of dimensionality, nearest neighbour, high dimensional indexing, $l_p$ norm

DOI: 10.3233/FI-2015-1166

Journal: Fundamenta Informaticae, vol. 136, no. 4, pp. 461-474, 2015