Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

Matti Karppa, Petteri Kaski, Jukka Kohonen*, Padraig Ó Catháin

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

4 Downloads (Pure)

Abstract

We derandomize Valiant’s (J ACM 62, Article 13, 2015) subquadratic-time algorithm for finding outlier correlations in binary data. This demonstrates that it is possible to perform a deterministic subquadratic-time similarity join of high dimensionality. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same parameter range as Valiant’s randomized algorithm, but the precise constants we save over quadratic scaling are more modest. Our main technical tool for derandomization is an explicit family of correlation amplifiers built via a family of zigzag-product expanders by Reingold et al. (Ann Math 155(1):157–187, 2002). We say that a function f: { - 1 , 1 } d→ { - 1 , 1 } D is a correlation amplifier with threshold 0 ≤ τ≤ 1 , error γ≥ 1 , and strength p an even positive integer if for all pairs of vectors x, y∈ { - 1 , 1 } d it holds that (i) | ⟨ x, y⟩ | < τd implies | ⟨ f(x) , f(y) ⟩ | ≤ (τγ) pD; and (ii) | ⟨ x, y⟩ | ≥ τd implies (⟨x,y⟩γd)pD≤⟨f(x),f(y)⟩≤(γ⟨x,y⟩d)pD.

Original languageEnglish
Pages (from-to)3306-3337
Number of pages32
JournalAlgorithmica
Volume82
Issue number11
Early online date1 Jan 2020
DOIs
Publication statusPublished - Nov 2020
MoE publication typeA1 Journal article-refereed

Keywords

  • Correlation
  • Derandomization
  • Expander graph
  • Outlier
  • Similarity search

Fingerprint

Dive into the research topics of 'Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time'. Together they form a unique fingerprint.

Cite this