Indexing Earth Mover’s Distance over Network Metrics
Ting Wang, Shicong Meng, Jiang Bian · IEEE Transactions on Knowledge and Data Engineering · 2014
The Earth Mover’s Distance (EMD) is a well-known distance metric for data represented as probability distributions over a predefined feature space. Supporting EMD-based similarity search has attracted intensive research effort. Despite the plethora of literature, most existing solutions are optimized for$L^p$feature spaces (e.g., Euclidean space); while in a spectrum of applications, the relationships between features are better captured using networks. In this paper, we study the problem of answering$k$-nearest neighbor ($k$-NN) queries under network-based EMD metrics (NEMD). We proposeOasis, a new access method which leverages the network structure of feature space and enables efficient NEMD-based similarity search. Specifically,Oasisemploys three novel techniques: (i)Range Oracle, a scalable model to estimate the range of$k$-th nearest neighbor under NEMD, (ii)Boundary Index, a structure that efficiently fetches candidates within given range, and (iii)Network Compression Hierarchy, an incremental filtering mechanism that effectively prunes false positive candidates to save unnecessary computation. Through extensive experiments using both synthetic and real data sets, we confirmed thatOasissignificantly outperforms the state-of-the-art methods in query processing cost.