Contact detection algorithms are needed in different areas of science and technology. From digital games and computer graphics to high-performance simulations and robotics. These algorithms require great computational effort and are prone to become the bottlenecks of its applications, even more when this computation must be done in real-time or large-scale systems. With the popularization of GPU cards use for both science and business, it is only natural that parallel implementations for this problem arise in the scientific community. In this work the main contact detection algorithms are analyzed and a numerical experiment is performed, with the goal of finding out which algorithm has better computational performance and memory use, or if they efficiency depends on different scenario features. For performing the experiment, a parallel Discrete ElementMethod application was developed using CUDA/C++ with the main algorithms presented in literature, besides these, the author proposes and implements the Sorting Contact Detection algorithm parallelization, that hadn’t been parallelized until now. The tests have found that the parallel Sorting Contact Detection algorithm is the most efficient in all studied scenarios, achieving a good performance and a superiormemory usage than its peers. / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Algoritmos de detecção de contatos são necessários em diferentes áreas da ciência e tecnologia, de jogos digitais e computação gráfica à simulações de alto desempenho e robótica. Esses algoritmos exigem grande esforço computacional e tendem a ser os gargalos das aplicação as quais fazem parte, principalmente em sistemas de grande escala ou em tempo real. Com a popularização das placas GPUs para uso científico e comercial, é natural que surjam implementações paralelas para esse problema. Nesse trabalho os principais algoritmos de detecção de contatos para GPU são analisados e é realizado umexperimento numérico, com objetivo de descobrir qual algoritmo é o melhor emtermos de desempenho computacional e uso de memória, ou se a eficiência de cada umdepende das diferentes características do cenários. Para a realização do experimento, foi implementado em CUDA/C++ uma aplicação paralela doMétodo dos Elementos Discretos comos principais algoritmos apresentados na literatura, além desses o autor propõe e implementa a paralelização do algoritmo de detecção com ordenação e busca binária que ainda não havia sido paralelizado. Após os testes é constatado que o algoritmo com ordenação e busca é o mais eficiente para todos os cenários estudados, obtendo nos resultados um bom desempenho em tempo de execução e com uso de memória muito superior aos outros.

A complexidade dos dados armazenados em grandes bases de dados aumenta cada vez mais, criando a necessidade de novas operações de consulta. Uma classe de operações que tem apresentado interesse crescente são as chamadas Consultas por Similaridade, sendo as mais conhecidas as consultas por Abrangência (\'R IND. q\') e por k-Vizinhos mais Proximos (kNN), sendo que esta ultima obtem quais são os k elementos armazenados mais similares a um dado elemento de referência. Outra consulta que é interessante tanto para consultas diretas quanto como parte de operações de análises mais complexas e a operação de consulta aos k-Vizinhos mais Próximos Reversos (RkNN). Seu objetivo e obter todos os elementos armazenados que têm um dado elemento de referência como um dos seus k elementos mais similares. Devido a complexidade de execução da operação de RkNN, a grande maioria das soluções existentes restringem-se a dados representados em espaços multidimensionais euclidianos (nos quais estão denidas tambem operações cardinais e topológicas, além de se considerar a similaridade como sendo a distância Euclidiana entre dois elementos), ou então obtém apenas respostas aproximadas, sujeitas a existência de falsos negativos. Várias aplicações de análise de dados científicos, médicos, de engenharia, financeiros, etc. requerem soluções eficientes para o problema da operação de RkNN sobre dados representados em espaços métricos, onde os elementos não podem ser considerados estar em um espaço nem Euclidiano nem multidimensional. Num espaço métrico, além dos próprios elementos armazenados existe apenas uma função de comparação métrica entre pares de objetos. Neste trabalho, são propostas novas podas de espaço de busca e o algoritmo RkNN-MG que utiliza essas novas podas para solucionar o problema de consultas RkNN exatas em espaços métricos sem limitações. Toda a proposta supõe que o conjunto de dados esta em um espaço métrico imerso isometricamente em espaço euclidiano e utiliza propriedades da geometria métrica válida neste espaço para realizar podas eficientes por lei dos cossenos combinada com as podas tradicionais por desigualdade triangular. Os experimentos demonstram comparativamente que as novas podas são mais eficientes que as tradicionais podas por desigualdade triangular, tendo desempenhos equivalente quando comparadas em conjuntos de alta dimensionalidade ou com dimensão fractal alta. Assim, os resultados confirmam as novas podas propostas como soluções alternativas eficientes para o problema de consultas RkNN / Data stored in large databases present an ever increasing complexity, pressing for the development of new classes of query operators. One such class, which is enticing an increasing interest, is the so-called Similarity Queries, where the most common are the similarity range queries (\'R IND. q\') and the k-nearest neighbor queries (kNN). A k-nearest neighbor query aims at retrieving the k stored elements nearer (or more similar) to a given reference element. Another important similarity query is the reverse k-nearest neighbor (RkNN), useful both for queries posed directly by the analyst and for queries that are part of more complex analysis processes. The objective of a reverse k-nearest neighbor queries is obtaining the stored elements that has the query reference element as one of their k-nearest neighbors. As the RkNN operation is a rather expensive operation, from the computational standpoint, most existing solutions only solve the query when applied over Euclidean multidimensional spaces (as these spaces also define cardinal and topological operations besides the Euclidean distance between pairs of elements) or retrieve only approximate answers, where false negatives can occur. Several applications, like the analysis of scientific, medical, engineering or financial data, require efficient and exact answers for the RkNN queries over data which is frequently represented in metric spaces, that is where no other property besides the similarity measure exists. Therefore, for applications handling metrical data, the assumption of Euclidean metric or even multidimensional data cannot be used. In this work, we propose new pruning rules based on the law of cosines, and the RkNN-MG algorithm, which uses them to solve RkNN queries in a way that is exact, faster than the existing approaches, that is not limited for any value of k, and that can be applied both over static and over dynamic datasets. The new pruning rules assume that the data set is in a metric space that can be embedded into an Euclidean space and use metric geometry properties valid in this space to perform effective pruning based on the law of cosines combined with the traditional pruning based on the triangle inequality property. The experiments show that the new pruning rules are alkways more efficient than the traditional pruning rules based solely on the triangle inequality. The experiments show that for high high dimensionality datasets, or for metric datasets with high fractal dimensionality, the performance improvement is smaller than for for lower dimensioinality datasets, but it\'s never worse. Thus, the results confirm that the our pruning rules are efficient alternative to solve RkNN queries in general

Orientador: Prof. Dr. Ricardo Suyama / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Engenharia da Informação, Santo André, 2018. / De forma geral a Classificação de Padrões voltada a Processamento de Sinais vem sendo estudada e utilizada para a interpretação de informações diversas, que se manifestam em forma de imagens, áudios, dados geofísicos, impulsos elétricos, entre outros. Neste trabalho são estudadas técnicas de Machine Learning aplicadas ao problema de identificação de instrumentos musicais, buscando obter um sistema automático de reconhecimento de timbres. Essas técnicas foram utilizadas especificamente com cinco instrumentos da categoria de Sopro de Madeira (o Clarinete, o Fagote, a Flauta, o Oboé e o Sax). As técnicas utilizadas foram o kNN (com k = 3) e o SVM (numa configuração não linear), assim como foram estudadas algumas características (features) dos áudios, tais como o MFCC (do inglês Mel-Frequency Cepstral Coefficients), o ZCR (do inglês Zero Crossing Rate), a entropia, entre outros, sendo fonte de dados para os processos de treinamento e de teste. Procurou-se estudar instrumentos nos quais se observa uma aproximação nos timbres, e com isso verificar como é o comportamento de um sistema classificador nessas condições específicas. Observou-se também o comportamento dessas técnicas com áudios desconhecidos do treinamento, assim como com trechos em que há uma mistura de elementos (gerando interferências para cada modelo classificador) que poderiam desviar os resultados, ou com misturas de elementos que fazem parte das classes observadas, e que se somam num mesmo áudio. Os resultados indicam que as características selecionadas possuem informações relevantes a respeito do timbre de cada um dos instrumentos avaliados (como observou-se em relação aos solos), embora a acurácia obtida para alguns dos instrumentos tenha sido abaixo do esperado (como observou-se em relação aos duetos). / In general, Pattern Classification for Signal Processing has been studied and used for the interpretation of several information, which are manifested in many ways, like: images, audios, geophysical data, electrical impulses, among others. In this project we study techniques of Machine Learning applied to the problem of identification of musical instruments, aiming to obtain an automatic system of timbres recognition. These techniques were used specifically with five instruments of Woodwind category (Clarinet, Bassoon, Flute, Oboe and Sax). The techniques used were the kNN (with k = 3) and the SVM (in a non-linear configuration), as well as some audio features, such as MFCC (Mel-Frequency Cepstral Coefficients), ZCR (Zero Crossing Rate), entropy, among others, used as data source for the training and testing processes. We tried to study instruments in which an approximation in the timbres is observed, and to verify in this case how is the behavior of a classifier system in these specific conditions. It was also observed the behavior of these techniques with audios unknown to the training, as well as with sections in which there is a mixture of elements (generating interferences for each classifier model) that could deviate the results, or with mixtures of elements that are part of the observed classes, and added in a same audio. The results indicate that the selected characteristics have relevant information regarding the timbre of each one of evaluated instruments (as observed on the solos results), although the accuracy obtained for some of the instruments was lower than expected (as observed on the duets results).

Submitted by Rosa Assis (rosa_assis@yahoo.com.br) on 2017-03-21T19:40:25Z No. of bitstreams: 2 LEANDRO JUVENCIO MOREIRA.pdf: 1183496 bytes, checksum: b7b7de6c9a5112b9705c906c6cbdaaec (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2017-03-22T15:01:23Z (GMT) No. of bitstreams: 2 LEANDRO JUVENCIO MOREIRA.pdf: 1183496 bytes, checksum: b7b7de6c9a5112b9705c906c6cbdaaec (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-03-22T15:01:23Z (GMT). No. of bitstreams: 2 LEANDRO JUVENCIO MOREIRA.pdf: 1183496 bytes, checksum: b7b7de6c9a5112b9705c906c6cbdaaec (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-12-14 / The data classification is a data mining task with relevant utilization in various areas of application, such as medicine, industry, marketing, financial market, teaching and many others. Although this task is an element search for many autors, there are open issues such as, e.g., in situations where there is so much data, noise data and unbalanced classes. In this way, this work will present a data classifier proposal that combines the SOM (Self-Organizing Map) neural network with INN (Informative Nearest Neighbors). The combination of these two algorithms will be called in this work as SOM-INN. Therefore, the SOM-INN process to classify a new object will be done in a first step with the SOM that has a functionality to map a reduced dataset through an approach that utilizes the prototype generation concept, also called the winning neuron and, in a second step, with the INN algorithm that is used to classify the new object through an approach that finds in the reduced dataset by SOM the most informative object. Were made experiments using 21 public datasets comparing classic data classification algorithms of the literature, from the indicators of reduction training set, accuracy, kappa and time consumed in the classification process. The results obtained show that the proposed SOM-INN algorithm, when compared with the others classifiers of the literature, presents better accuracy in databases where the border region is not well defined. The main differential of the SOM-INN is in the classification time, which is extremely important for real applications. Keywords: data classification; prototype generation; K nearest neighbors; self-organizing / A classificação de dados é uma tarefa da mineração de dados com utilização relevante em diversas áreas de aplicação, tais como, medicina, indústria, marketing, mercado financeiro, ensino e muitas outras. Embora essa tarefa seja elemento de pesquisa de muitos autores, ainda há problemas em aberto como, por exemplo, em situações onde há abundância de dados, dados ruidosos e desbalanceamento de classes. Nesse sentido, este trabalho apresenta uma proposta de classificador de dados em um processo de duas etapas que combina a rede neural SOM (Self-Organizing Maps) com o classificador vizinhos informativos mais próximos ou INN (Informative Nearest Neighbors). A combinação desses dois algoritmos será aqui chamada como SOM-INN. Portanto, o processo de uso do SOM-INN na classificação de um novo objeto será feito em uma primeira etapa com o SOM que tem a funcionalidade de mapear um conjunto reduzido dos dados de treinamento por meio de uma abordagem que utiliza o conceito de geração de protótipo, também denominado de neurônio vencedor e, em uma segunda etapa, com o algoritmo INN que é usado para classificar o novo objeto por meio de uma abordagem que encontra no conjunto de treinamento reduzido pelo SOM os objetos mais informativos. Foram realizados experimentos usando 21 conjuntos de dados públicos, comparando com os algoritmos clássicos da literatura de classificação de dados, a partir dos indicadores de redução do conjunto de treinamento, acurácia, kappa e tempo consumido no processo de classificação. Os resultados obtidos mostram que o algoritmo proposto SOM-INN, quando comparado com outros classificadores da literatura, apresenta acurácia melhor em bases de dados em que a região de fronteira não é bem definida. O principal diferencial do SOM-INN está no tempo de classificação, o que é de suma importância para aplicações reais.

A análise de dados contendo informações sequenciais é um problema de crescente interesse devido à grande quantidade de informação que é gerada, entre outros, em processos de monitoramento. As séries temporais são um dos tipos mais comuns de dados sequenciais e consistem em observações ao longo do tempo. O algoritmo k-Nearest Neighbor - Time Series Prediction kNN-TSP é um método de previsão de dados temporais. A principal vantagem do algoritmo é a sua simplicidade, e a sua aplicabilidade na análise de séries temporais não-lineares e na previsão de comportamentos sazonais. Entretanto, ainda que ele frequentemente encontre as melhores previsões para séries temporais parcialmente periódicas, várias questões relacionadas com a determinação de seus parâmetros continuam em aberto. Este trabalho, foca-se em dois desses parâmetros, relacionados com a seleção de vizinhos mais próximos e a função de previsão. Para isso, é proposta uma abordagem simples para selecionar vizinhos mais próximos que considera a similaridade e a distância temporal de modo a selecionar os padrões mais similares e mais recentes. Também é proposta uma função de previsão que tem a propriedade de manter bom desempenho na presença de padrões em níveis diferentes da série temporal. Esses parâmetros foram avaliados empiricamente utilizando várias séries temporais, inclusive caóticas, bem como séries temporais reais referentes a variáveis ambientais do reservatório de Itaipu, disponibilizadas pela Itaipu Binacional. Três variáveis limnológicas fortemente correlacionadas são consideradas nos experimentos de previsão: temperatura da água, temperatura do ar e oxigênio dissolvido. Uma análise de correlação é realizada para verificar se os dados previstos mantem a correlação das variáveis. Os resultados mostram que, o critério de seleção de vizinhos próximos e a função de previsão, propostos neste trabalho, são promissores / Treating data that contains sequential information is an important problem that arises during the data mining process. Time series constitute a popular class of sequential data, where records are indexed by time. The k-Nearest Neighbor - Time Series Prediction kNN-TSP method is an approximator for time series prediction problems. The main advantage of this approximator is its simplicity, and is often used in nonlinear time series analysis for prediction of seasonal time series. Although kNN-TSP often finds the best fit for nearly periodic time series forecasting, some problems related to how to determine its parameters still remain. In this work, we focus in two of these parameters: the determination of the nearest neighbours and the prediction function. To this end, we propose a simple approach to select the nearest neighbours, where time is indirectly taken into account by the similarity measure, and a prediction function which is not disturbed in the presence of patterns at different levels of the time series. Both parameters were empirically evaluated on several artificial time series, including chaotic time series, as well as on a real time series related to several environmental variables from the Itaipu reservoir, made available by Itaipu Binacional. Three of the most correlated limnological variables were considered in the experiments carried out on the real time series: water temperature, air temperature and dissolved oxygen. Analyses of correlation were also accomplished to verify if the predicted variables values maintain similar correlation as the original ones. Results show that both proposals, the one related to the determination of the nearest neighbours as well as the one related to the prediction function, are promising

Com o crescente aumento no número de imagens geradas em mídias digitais surgiu a necessidade do desenvolvimento de novas técnicas de recuperação desses dados. Um critério de busca que pode ser utilizado na recuperação das imagens é o da dissimilaridade, no qual o usuário deseja recuperar as imagens semelhantes à uma imagem de consulta. Para a realização das consultas são empregados vetores de características extraídos das imagens e funções de distância para medir a dissimilaridade entre pares desses vetores. Infelizmente, a busca por conteúdo de imagens em consultas simples tende a gerar resultados que não correspondem ao interesse do usuário misturados aos resultados significativos encontrados, pois em geral há uma descontinuidade semântica entre as características extraídas automaticamente e a subjetividade da interpretação humana. Com o intuito de tratar esse problema, diversos métodos foram propostos para a diminuição da descontinuidade semântica. O foco principal desta tese é o desenvolvimento de métodos escaláveis para a redução da descontinuidade semântica em sistemas recuperação de imagens por conteúdo em tempo real. Nesta sentido, são apresentados: a formalização de consultas por similaridade que permitem a utilização de múltiplos centros de consulta em espaços métricos como base para métodos de realimentação de relevância; um método exato para otimização dessas consultas nesses espaços; e um modelo para tratamento da diversidade em consultas por similaridade e heurísticas para sua otimização / The increasing number of images captured in digital media fostered the developmet of new methods for the recovery of these images. Dissimilarity is a criteria that can be used for image retrieval, where the results are images that are similar to a given reference. The queries are based on feature vectors automatically extracted from the images and on distance functions to measure the dissimilarity between pair of vectors. Unfortunately, the search for images in simple queries may result in images that do not fulfill the user interest together with meaningful images, due to the semantic gap between the image features and to the subjectivity of the human interpretation. This problem leaded to the development of many methods to deal with the semantic gap. The focus of this thesis is the development of scalable methods aiming the semantic gap reduction in real time for content-based image retrieval systems. For this purpose, we present the formal definition of similarity queries based on multiple query centers in metric spaces to be used in relevance feedback methods, an exact method to optimize these queries and a model to deal with diversity in nearest neighbor queries including heuristics for its optimization

O uso de Internet para a distribuição de fluxos de vídeo tem se mostrado uma tendência atual e traz consigo grandes desafios. O alicerce sobre qual a Internet está fundamentada, comutação por pacotes e arquitetura cliente-servidor, não proporciona as melhores condições para este tipo de serviço. A arquitetura P2P (peer-to-peer) vem sendo considerada como infraestrutura para a distribuição de fluxos de vídeo na Internet. A idéia básica da distribuição de vídeo com o suporte de P2P é a de que os vários nós integrantes da rede sobreposta distribuem e encaminham pedaços de vídeo de forma cooperativa, dividindo as tarefas, e colocando à disposição da rede seus recursos locais. Dentro deste contexto, é importante investigar o que ocorre com a qualidade do serviço de distribuição de vídeo quando a infraestrutura provida pelas redes P2P é contaminada por nós que não estejam dispostos a cooperar, já que a base desta arquitetura é a cooperação. Neste trabalho, inicialmente é feito um estudo para verificar o quanto a presença de nós não-cooperativos pode afetar a qualidade da aplicação de distribuição de fluxo de vídeo em uma rede P2P. Com base nos resultados obtidos, é proposto um mecanismo de incentivo à cooperação para que seja garantida uma boa qualidade de vídeo aos nós cooperativos e alguma punição aos nós não-cooperativos. Os testes e avaliações foram realizados utilizando-se o simulador PeerSim. / Using the Internet for video stream is becoming a trend, but it brings many challenges. The foundation upon which the Internet is based, packet switching and client-server architecture, is not suitable for this type of service. P2P (peer to peer) architecture is being considered as an infrastructure for video streams on the Internet. The basic idea is that the several members of the overlay network cooperate in the task of distributing and fowarding video chunks, making available their local resources to the network. Within this context, it is important to investigate what happens to the quality of service of the video distribution when the infrastructure provided by the P2P network is contaminated with free-riding nodes, which are not willing to cooperate, since the basis of this architecture is cooperation. In this work, study is initially carried out to check how the presence of uncooperative nodes can affect the quality of the distribution application of video streaming on a P2P network. Based on these results, a mechanism is proposed to encourage cooperation in order to be guaranteed a video with good quality to the cooperative nodes and some punishment for those uncooperative. The tests and evaluations were performed using the PeerSim simulator.

O uso de Internet para a distribuição de fluxos de vídeo tem se mostrado uma tendência atual e traz consigo grandes desafios. O alicerce sobre qual a Internet está fundamentada, comutação por pacotes e arquitetura cliente-servidor, não proporciona as melhores condições para este tipo de serviço. A arquitetura P2P (peer-to-peer) vem sendo considerada como infraestrutura para a distribuição de fluxos de vídeo na Internet. A idéia básica da distribuição de vídeo com o suporte de P2P é a de que os vários nós integrantes da rede sobreposta distribuem e encaminham pedaços de vídeo de forma cooperativa, dividindo as tarefas, e colocando à disposição da rede seus recursos locais. Dentro deste contexto, é importante investigar o que ocorre com a qualidade do serviço de distribuição de vídeo quando a infraestrutura provida pelas redes P2P é contaminada por nós que não estejam dispostos a cooperar, já que a base desta arquitetura é a cooperação. Neste trabalho, inicialmente é feito um estudo para verificar o quanto a presença de nós não-cooperativos pode afetar a qualidade da aplicação de distribuição de fluxo de vídeo em uma rede P2P. Com base nos resultados obtidos, é proposto um mecanismo de incentivo à cooperação para que seja garantida uma boa qualidade de vídeo aos nós cooperativos e alguma punição aos nós não-cooperativos. Os testes e avaliações foram realizados utilizando-se o simulador PeerSim. / Using the Internet for video stream is becoming a trend, but it brings many challenges. The foundation upon which the Internet is based, packet switching and client-server architecture, is not suitable for this type of service. P2P (peer to peer) architecture is being considered as an infrastructure for video streams on the Internet. The basic idea is that the several members of the overlay network cooperate in the task of distributing and fowarding video chunks, making available their local resources to the network. Within this context, it is important to investigate what happens to the quality of service of the video distribution when the infrastructure provided by the P2P network is contaminated with free-riding nodes, which are not willing to cooperate, since the basis of this architecture is cooperation. In this work, study is initially carried out to check how the presence of uncooperative nodes can affect the quality of the distribution application of video streaming on a P2P network. Based on these results, a mechanism is proposed to encourage cooperation in order to be guaranteed a video with good quality to the cooperative nodes and some punishment for those uncooperative. The tests and evaluations were performed using the PeerSim simulator.

Com o crescente aumento no número de imagens geradas em mídias digitais surgiu a necessidade do desenvolvimento de novas técnicas de recuperação desses dados. Um critério de busca que pode ser utilizado na recuperação das imagens é o da dissimilaridade, no qual o usuário deseja recuperar as imagens semelhantes à uma imagem de consulta. Para a realização das consultas são empregados vetores de características extraídos das imagens e funções de distância para medir a dissimilaridade entre pares desses vetores. Infelizmente, a busca por conteúdo de imagens em consultas simples tende a gerar resultados que não correspondem ao interesse do usuário misturados aos resultados significativos encontrados, pois em geral há uma descontinuidade semântica entre as características extraídas automaticamente e a subjetividade da interpretação humana. Com o intuito de tratar esse problema, diversos métodos foram propostos para a diminuição da descontinuidade semântica. O foco principal desta tese é o desenvolvimento de métodos escaláveis para a redução da descontinuidade semântica em sistemas recuperação de imagens por conteúdo em tempo real. Nesta sentido, são apresentados: a formalização de consultas por similaridade que permitem a utilização de múltiplos centros de consulta em espaços métricos como base para métodos de realimentação de relevância; um método exato para otimização dessas consultas nesses espaços; e um modelo para tratamento da diversidade em consultas por similaridade e heurísticas para sua otimização / The increasing number of images captured in digital media fostered the developmet of new methods for the recovery of these images. Dissimilarity is a criteria that can be used for image retrieval, where the results are images that are similar to a given reference. The queries are based on feature vectors automatically extracted from the images and on distance functions to measure the dissimilarity between pair of vectors. Unfortunately, the search for images in simple queries may result in images that do not fulfill the user interest together with meaningful images, due to the semantic gap between the image features and to the subjectivity of the human interpretation. This problem leaded to the development of many methods to deal with the semantic gap. The focus of this thesis is the development of scalable methods aiming the semantic gap reduction in real time for content-based image retrieval systems. For this purpose, we present the formal definition of similarity queries based on multiple query centers in metric spaces to be used in relevance feedback methods, an exact method to optimize these queries and a model to deal with diversity in nearest neighbor queries including heuristics for its optimization

We have modeled some magnetic systems, which consists of a number of sublattices, in the mean field approximation. This is possible in crystalline systems formed by two or more magnetic ions coupled by specific interactions such as the crystal field, exchange, among others. The main idea is to solve the microscopic Hamiltonian that models a given magnetic system in order to obtain their magnetic equation of state: M (H, T). For this, we use the appropriate arrangements to different magnetic (ferro-, ferri- and antiferro- magnetic) scheme sublattices. From the solutions of the Hamiltonian (eigenvalues and eigenvectors), physical quantities of interest were determined. In principle we consider systems with localized magnetism due to 3d and 4f electrons with the participation of non-magnetic ligands including 3d-4f systems with the presence of crystal field. In this dissertation we use the model of two-and three sublattices in order to obtain the equation of state for the following systems: RKKY exchange in RNi2B2C, superexchange in (Y3-zRz)(T1xFe1-x)(T2yFe3-y)O12, LixFe3- xO4 and (NixMn1-x)1.5[Cr(CN)6]. In these formulas, R represents a rare earth ion, T1 and T2 represent non-magnetic ions. Some representative cases are presented to illustrate the different equations of state and behavior of sublattices, metamagnetism, temperature compensation, etc. The extension to other similar systems can be direct or need to incorporate additional phenomenological parameters. / Consideramos neste estudo sistemas magnéticos modeláveis mediante sub- redes na aproximação do campo médio. Isto é possível em sistemas cristalinos formados por dois ou mais íons magnéticos acoplados por interações específicas como as do campo cristalino, troca, entre outros. A ideia central é resolver o hamiltoniano microscópico que modela um determinado sistema magnético de maneira a se obter sua equação de estado magnética: M(H,T). Para isto usamos o esquema de sub- redes adequado a diferentes arranjos magnéticos (ferro-, ferri- e antiferro- magnéticos). Com as soluções do hamiltoniano (autovalores e autovetores), grandezas físicas de interesse foram determinadas. Em princípio, consideramos sistemas com magnetismo localizado devido a elétrons 3d e 4f com participação de ligandos não magnéticos incluindo sistemas 3d-4f com presença de campo cristalino. Neste trabalho de dissertação empregamos o modelo de duas e três sub- redes para obter as equações de estado nos seguintes sistemas: troca tipo RKKY em RNi2B2C, supertroca em (Y3-zRz)(T1xFe1-x)(T2yFe3-y)O12, LixFe3-xO4 e (NixMn1- x)1.5[Cr(CN)6]. Nestas fórmulas, R representa um íon de terra rara, T1 e T2 representam íons não magnéticos. Alguns casos representativos são apresentados para exemplificar as diferentes equações de estado e comportamento das sub- redes, metamagnetismo, temperatura de compensação etc. Em princípio, a extensão para outros sistemas semelhantes, usando os modelos apresentados aqui, pode ser direta ou precisar incorporar parâmetros fenomenológicos adicionais.