Solving multiple kth smallest dissimilarity queries for non-metric dissimilarities with the GPU

Text Complet
Solving-multiple-kth.pdf closed access
Sol·licita còpia a l'autor de l'article
En omplir aquest formulari esteu demanant una còpia de l'article dipositat al repositori institucional (DUGiDocs) al seu autor o a l'autor principal de l'article. Serà el mateix autor qui decideixi lliurar una còpia del document a qui ho sol•liciti si ho creu convenient. En tot cas, la Biblioteca de la UdG no intervé en aquest procés ja que no està autoritzada a facilitar articles quan aquests són d'accés restringit.
Compartir
The kth smallest dissimilarity of a query point with respect to a given set is the dissimilarity that ranks number k when we sort, in increasing order, the dissimilarity value of the points in the set with respect to the query point. A multiple kth smallest dissimilarity query determines the kth smallest dissimilarity for several query points simultaneously. Although the problem of solving multiple kth smallest dissimilarity queries is an important primitive operation used in many areas, such as spatial data analysis, facility location, text classification and content-based image retrieval, it has not been previously addressed explicitly in the literature. In this paper we present three parallel strategies, to be run on a Graphics Processing Unit, for computing multiple kth smallest dissimilarity queries when non-metric dissimilarities, that do not satisfy the triangular inequality, are used. The strategies are theoretically and experimentally analyzed and compared among them and with an efficient sequential strategy to solve the problem ​
​Tots els drets reservats