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

Nearest neighbor searching is a fundamental computational prob- lem. A set of n data points is given in real d-dimensional space, and the problem is to preprocess these points into a data structure, so that given a query point, the nearest data point to the query point can be reported e- ciently. Because data sets can be quite large, we are primarily interested in data structures that use only O(dn) storage. A popular class of data structures for nearest neighbor searching is the kd-tree and variants based on hierarchically decomposing space into rectangu- lar cells. An important question in the construction of such data structures is the choice of a splitting method, which determines the dimension and splitting plane to be used at each stage of the decomposition. This choice of splitting method can have a signicant influence on the eciency of the data structure. This is especially true when data and query points are clustered in low dimen- sional subspaces. This is because clustering can lead to subdivisions in which cells have very high aspect ratios. We compare the well-known optimized kd-tree splitting method against two alternative splitting methods. The rst, called the sliding-midpoint method, which attempts to balance the goals of producing subdivision cells of bounded aspect ratio, while not producing any empty cells. The second, called the minimum-ambiguity method is a query-based approach. In addition to the data points, it is also given a training set of query points for preprocessing. It employs a simple greedy algorithm to select the splitting plane that mini- mizes the average amount of ambiguity in the choice of the nearest neighbor for the training points. We provide an empirical analysis comparing these two methods against the optimized kd-tree construction for a number of syntheti- cally generated data and query sets. We demonstrate that for clustered data and query sets, these algorithms can provide signicant improvements over the standard kd-tree construction for approximate nearest neighbor searching.

Analysis of approximate nearest neighbor searching with clustered point sets