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

In this paper, we consider the following query problem: given two weightedpoint sets $A$ and $B$ in the Euclidean space $\mathbb{R}^d$, we want toquickly determine that whether their earth mover's distance (EMD) is larger orsmaller than a pre-specified threshold $T\geq 0$. The problem finds a number ofimportant applications in the fields of machine learning and data mining. Inparticular, we assume that the dimensionality $d$ is not fixed and the sizes$|A|$ and $|B|$ are large. Therefore, most of existing EMD algorithms are notquite efficient to solve this problem due to their high complexities. Here, weconsider the problem under the assumption that $A$ and $B$ have low doublingdimensions, which is common for high-dimensional data in real world. Inspiredby the geometric method {\em net tree}, we propose a novel ``data-dependent''algorithm to avoid directly computing the EMD between $A$ and $B$, so as tosolve this query problem more efficiently. We also study the performance of ourmethod on synthetic and real datasets. The experimental results suggest thatour method can save a large amount of running time comparing with existing EMDalgorithms.

A Data-Dependent Algorithm for Querying Earth Mover's Distance with Low Doubling Dimensions