Indexing Earth Mover’s Distance over Network Metrics

摘要

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 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 -nearest neighbor (-NN) queries under network-based EMD metrics (NEMD). We propose , a new access method which leverages the network structure of feature space and enables efficient NEMD-based similarity search. Specifically, employs three novel techniques: (i) , a scalable model to estimate the range of -th nearest neighbor under NEMD, (ii) , a structure that efficiently fetches candidates within given range, and (iii) , 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 that