English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider tradeoffs between the query and update complexities for the(approximate) nearest neighbor problem on the sphere, extending the recentspherical filters to sparse regimes and generalizing the scheme and analysis toaccount for different tradeoffs. In a nutshell, for the sparse regime thetradeoff between the query complexity $n^{\rho_q}$ and update complexity$n^{\rho_u}$ for data sets of size $n$ is given by the following equation interms of the approximation factor $c$ and the exponents $\rho_q$ and $\rho_u$:$$c^2\sqrt{\rho_q}+(c^2-1)\sqrt{\rho_u}=\sqrt{2c^2-1}.$$  For small $c=1+\epsilon$, minimizing the time for updates leads to a linearspace complexity at the cost of a query time complexity $n^{1-4\epsilon^2}$.Balancing the query and update costs leads to optimal complexities$n^{1/(2c^2-1)}$, matching bounds from [Andoni-Razenshteyn, 2015] and [Dubiner,IEEE-TIT'10] and matching the asymptotic complexities of [Andoni-Razenshteyn,STOC'15] and [Andoni-Indyk-Laarhoven-Razenshteyn-Schmidt, NIPS'15]. Asubpolynomial query time complexity $n^{o(1)}$ can be achieved at the cost of aspace complexity of the order $n^{1/(4\epsilon^2)}$, matching the bound$n^{\Omega(1/\epsilon^2)}$ of [Andoni-Indyk-Patrascu, FOCS'06] and[Panigrahy-Talwar-Wieder, FOCS'10] and improving upon results of[Indyk-Motwani, STOC'98] and [Kushilevitz-Ostrovsky-Rabani, STOC'98].  For large $c$, minimizing the update complexity results in a query complexityof $n^{2/c^2+O(1/c^4)}$, improving upon the related exponent for large $c$ of[Kapralov, PODS'15] by a factor $2$, and matching the bound $n^{\Omega(1/c^2)}$of [Panigrahy-Talwar-Wieder, FOCS'08]. Balancing the costs leads to optimalcomplexities $n^{1/(2c^2-1)}$, while a minimum query time complexity can beachieved with update complexity $n^{2/c^2+O(1/c^4)}$, improving upon theprevious best exponents of Kapralov by a factor $2$.

Tradeoffs for nearest neighbors on the sphere