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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider static, external memory indexes for exact and approximateversions of the $k$-nearest neighbor ($k$-NN) problem, and show new lowerbounds under a standard indivisibility assumption:  - Polynomial space indexing schemes for high-dimensional $k$-NN in Hammingspace cannot take advantage of block transfers: $\Omega(k)$ block reads areneeded to to answer a query.  - For the $\ell_\infty$ metric the lower bound holds even if we allow$c$-appoximate nearest neighbors to be returned, for $c \in (1, 3)$.  - The restriction to $c < 3$ is necessary: For every metric there exists anindexing scheme in the indexability model of Hellerstein et al.~using space$O(kn)$, where $n$ is the number of points, that can retrieve $k$ 3-approximatenearest neighbors using $\lceil k/B\rceil$ I/Os, which is optimal.  - For specific metrics, data structures with better approximation factors arepossible. For $k$-NN in Hamming space and every approximation factor $c>1$there exists a polynomial space data structure that returns $k$ $c$-approximatenearest neighbors in $\lceil k/B\rceil$ I/Os.  To show these lower bounds we develop two new techniques: First, to handlethat approximation algorithms have more freedom in deciding which result set toreturn we develop a relaxed version of the $\lambda$-set workload technique ofHellerstein et al. This technique allows us to show lower bounds that hold in$d\geq n$ dimensions. To extend the lower bounds down to $d = O(k \log(n/k))$dimensions, we develop a new deterministic dimension reduction technique thatmay be of independent interest.

On the I/O complexity of the k-nearest neighbor problem