Effective GPU-based Similarity Search

Abstract:

The data currently generated and collected increase fast not only in volume, but also in complexity, which brings great challenges to the field of data analysis. Similarity search has been acknowledged as one of the most important and useful query operators, and it plays a fundamental role of many applications. But the basic similarity operators are not enough to overcome the challenges. First of all, many optimizing strategies tailored to special data types and similarity measures cannot be easily extended to support others. Secondly, the effectiveness of the basic similarity search results is limited, largely because many redundantly similar elements are included.

In this proposal, we aim to propose our solutions to modern similarity search challenges. Two pieces of preliminary work have been accomplished. To tackle the complexity challenge, we propose GENIE, an efficient and parallelizable GPU-based Generic Inverted Index framework, which can support a wide variety of data types and similarity measures. To improve the effectiveness of similarity search results, we study the problem of result diversification, but from a novel perspective based on spatial angles with respect to the query. Two main future research problems are also investigated. The first is to construct diverse nearest neighbor graph. Secondly, we want to learn personal distance metric on top of effective similarity search results.