Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

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...

Descripción completa

Detalles Bibliográficos
Autores principales: Karppa, Matti, Kaski, Petteri, Kohonen, Jukka, Ó Catháin, Padraig
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7568719/
https://www.ncbi.nlm.nih.gov/pubmed/33088007
http://dx.doi.org/10.1007/s00453-020-00727-1

Internet

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7568719/
https://www.ncbi.nlm.nih.gov/pubmed/33088007
http://dx.doi.org/10.1007/s00453-020-00727-1

Ejemplares similares