Similarity search using the NK interaction graph

Com o crescimento do volume de dados ao longo dos anos, foram desenvolvidas técnicas de busca por similaridade para responder às necessidades dos usuários de diversos segmentos. A evolução das técnicas de busca por similaridade vem permitindo recuperar objetos presentes em grandes bases de dados similares a um objeto fornecido pelo usuário, auxiliando na tomada de decisão cada vez mais correta utilizada em diversos segmentos de estudo e aplicação. Um método de busca por similaridade baseado no grafo de interações NK é proposto. O grafo de interações NK foi originalmente empregado para agrupamento e é construído com base na distância e densidade espacial dos objetos em um conjunto de dados. Duas variações do método são investigadas. Nas duas variações, k objetos são retornados visitando-se vértices do grafo de interações NK a partir do vértice inicial relacionado ao exemplo do conjunto de dados que está mais próximo do objeto a ser consultado. No método NK A, os k objetos relacionados a vértices com arestas incidentes ao vértice inicial são retornados. No método NK B, k vértices são visitados a partir do vértice inicial. O próximo vértice visitado é aquele com aresta incidente ao vértice atual e que está mais próximo do novo objeto a ser consultado. Os k objetos relacionados aos vértices visitados são retornados. Os algoritmos propostos são comparados entre si e com a busca por similaridade baseada apenas na distância. Os resultados experimentais indicam que os métodos propostos apresentam bom desempenho quando existem agrupamentos com formas arbitrárias no conjunto de dados.With the growth in the volume of data over the years, similarity search techniques were applied to respond to the needs of users in different segments. The evolution of similarity search techniques allows retrieving objects present in large databases, such as an object provided by the user, assisting in the decision making increasingly correct, used in several studies and applications. A similarity search method based on the NK interaction graph is proposed. The NK interaction graph was originally employed for clustering and is built based on distance and spatial density of the objects in a dataset. Two variations of the method are investigated. In the two variations, k objects are returned by visiting vertices of the NK interaction graph from the initial vertex related to the example of the dataset that is closer to the object to be consulted. In NK A, the k objects related to vertices with edges incident to the initial vertex are returned. In NK B, k vertices are visited starting from the initial vertex. The next visited vertex is that one with edge incident to the current vertex and that is closest to the new object to be consulted. The k objects related to the visited vertices are returned. The proposed algorithms are compared with each other and with the search for similarity based only on distance. The experimental results indicate that the proposed methods present good performance when there are clusters with arbitrary shapes in the dataset