Solving approximate similarity queries

摘要

Supporting similarity search capabilities in data repositories helps satisfy user information needs rather than only user data needs like conventional DBMSs. This is desired for many modern database applications. However, as the data repository contains high-dimensional data, solutions to similarity search problem become cost-inefficient due to the so-called dimensionality curse. This phenomenon has been observed and shown that in high-dimensional data spaces the probability of overlaps between a query and data regions in a multidimensional access method (MAM) is very high. Hence, the execution of a similarity query may require accessing a vast number of the data regions and the performance of MAMs significantly decreases. Approximate similarity search has been introduced in order to lighten complexities of the problem. However, most research work done so far focuses mainly on approximate nearest neighbor (NN) and range queries in a single-feature data space. In practice, multiple-condition queries appear more frequently and get more complicated to deal with in whatever sense. In this article, we present effcient approaches to three types of approximate similarity queries: approximate multi-feature NN, approximate single-feature NN, and approximate range queries. Specially, we will use the Vague Query System, one among flexible query answering systems for conventional DBMSs, as a case study to illustrate and establish the practical value of our proposed solutions. Experimental results with both synthetic and real data sets will confirm the efficiency of these solutions.