File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: Similarity search with earth mover's distance at scale

TitleSimilarity search with earth mover's distance at scale
Authors
Advisors
Issue Date2013
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Tang, Y. [唐宇]. (2013). Similarity search with earth mover's distance at scale. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5204926
AbstractEarth Mover's Distance (EMD), as a similarity measure, has received a lot of attention in the fields of multimedia and probabilistic databases, computer vision, image retrieval, machine learning, etc. EMD on multidimensional histograms provides better distinguishability between the objects approximated by the histograms (e.g., images), compared to classic measures like Euclidean distance. Despite its usefulness, EMD has a high computational cost; therefore, a number of effective filtering methods have been proposed, to reduce the pairs of histograms for which the exact EMD has to be computed, during similarity search. Still, EMD calculations in the refinement step remain the bottleneck of the whole similarity search process. In this thesis, we focus on optimizing the refinement phase of EMD-based similarity search by (i) adapting an efficient min-cost flow algorithm (SIA) for the EMD computation, (ii) proposing a dynamic distance bound, which is progressively updated and tightened during the refinement process and can be used to terminate an EMD refinement early, and (iii) proposing a dynamic refinement order for the candidates which, paired with a concurrent EMD refinement strategy, reduces the amount of needless computations. Our proposed techniques are orthogonal to and can be easily integrated with the state-of-the-art filtering techniques, reducing the cost of EMD-based similarity queries by orders of magnitude.
DegreeMaster of Philosophy
SubjectComputer algorithms
Information retrieval
Image processing
Electronic information resource searching
Dept/ProgramComputer Science
Persistent Identifierhttp://hdl.handle.net/10722/198819

 

DC FieldValueLanguage
dc.contributor.advisorCheng, CK-
dc.contributor.advisorMamoulis, N-
dc.contributor.authorTang, Yu-
dc.contributor.author唐宇-
dc.date.accessioned2014-07-10T04:10:17Z-
dc.date.available2014-07-10T04:10:17Z-
dc.date.issued2013-
dc.identifier.citationTang, Y. [唐宇]. (2013). Similarity search with earth mover's distance at scale. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5204926-
dc.identifier.urihttp://hdl.handle.net/10722/198819-
dc.description.abstractEarth Mover's Distance (EMD), as a similarity measure, has received a lot of attention in the fields of multimedia and probabilistic databases, computer vision, image retrieval, machine learning, etc. EMD on multidimensional histograms provides better distinguishability between the objects approximated by the histograms (e.g., images), compared to classic measures like Euclidean distance. Despite its usefulness, EMD has a high computational cost; therefore, a number of effective filtering methods have been proposed, to reduce the pairs of histograms for which the exact EMD has to be computed, during similarity search. Still, EMD calculations in the refinement step remain the bottleneck of the whole similarity search process. In this thesis, we focus on optimizing the refinement phase of EMD-based similarity search by (i) adapting an efficient min-cost flow algorithm (SIA) for the EMD computation, (ii) proposing a dynamic distance bound, which is progressively updated and tightened during the refinement process and can be used to terminate an EMD refinement early, and (iii) proposing a dynamic refinement order for the candidates which, paired with a concurrent EMD refinement strategy, reduces the amount of needless computations. Our proposed techniques are orthogonal to and can be easily integrated with the state-of-the-art filtering techniques, reducing the cost of EMD-based similarity queries by orders of magnitude.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.subject.lcshComputer algorithms-
dc.subject.lcshInformation retrieval-
dc.subject.lcshImage processing-
dc.subject.lcshElectronic information resource searching-
dc.titleSimilarity search with earth mover's distance at scale-
dc.typePG_Thesis-
dc.identifier.hkulb5204926-
dc.description.thesisnameMaster of Philosophy-
dc.description.thesislevelMaster-
dc.description.thesisdisciplineComputer Science-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b5204926-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats