Nos últimos anos tem ocorrido uma necessidade crescente de métodos que possam lidar com conteúdo multimídia em larga escala, e com busca de tais informações de maneira eficiente e efetiva. Os objetos de interesse são representados por vetores descritivos (e. g. cor, textura, geometria, timbre) extraídos do conteúdo, associados a pontos de um espaço multidimensional. Um processo de busca visa, então, encontrar dados similares a uma dada amostra, tipicamente medindo distância entre pontos. Trata-se de um problema comum a uma ampla variedade de aplicações incluindo som, imagens, vídeo, bibliotecas digitais, imagens médicas, segurança, entre outras. Os maiores desafios dizem respeito às dificuldades inerentes aos espaços de alta dimensão, conhecidas por curse of dimensionality, que restringem significativamente a aplicação dos métodos comuns de busca. A literatura recente contém uma variedade de métodos de redução de dimensão que são altamente dependentes do tipo de dado considerado. Constata-se também certa carência de métodos gerais de análise que possam prever com precisão o desempenho dos algoritmos propostos. O presente trabalho contém uma análise geral dos princípios aplicáveis aos sistemas de busca em espaços de alta dimensão. Tal análise permite estabelecer de maneira precisa o compromisso existente entre robustez, refletida principalmente na imunidade a ruído, a taxa de erros de reconhecimento e a dimensão do espaço de observação. Além disto, mostra-se que é possível conceber um método geral de mapeamento, para fins de reconhecimento, que independe de especificidades do conteúdo. Para melhorar a eficiência de busca, um novo método de busca em espaços de alta dimensão é introduzido e analisado. Por fim, descreve-se sumariamente uma realização prática, desenvolvida segundo os princípios discutidos e que atende eficientemente aplicações comerciais de monitoramento de exibição de conteúdo em rádio e TV. / In the last few years there has been an increasing need for methods to deal with large scale multimedia content, and to search such information efficiently and effectively. The objects of interest are represented by feature vectors (e. g. color, texture, geometry, timbre) extracted from the content, associated to points in a multidimensional space. A search process aims, therefore, to find similar data to a given sample, typically measuring distance between points. It is a common problem to a wide range of applications that include sound, image, video, digital library, medical imagery, security, amongst others. The major challenges refer to the difficulties, inherent to the high dimension spaces, known as curse of dimensionality that limit significantly the application of the most common search methods. The recent literature contains a number of dimension reduction methods that are highly dependent on the type of data considered. Besides, there has been a certain lack of general analysis methods that can predict accurately the performance of the proposed algorithms. The present work contains a general analysis of the principles applicable to high dimension space search systems. Such analysis allows establishing in a precise manner the existing tradeoff amongst the system robustness, reflected mainly in the noise immunity, the error rate and the dimension of the observation space. Furthermore, it is shown that it is possible to conceive a mapping method, for recognition purpose, that can be independent of the content specificities. To improve the search efficiency, a new high dimension space search method is introduced and analyzed. Finally, a practical realization is briefly described, which has been developed in accordance with the principles discussed, and that addresses efficiently commercial applications relative to radio and TV content broadcasting monitoring.

Nos últimos anos tem ocorrido uma necessidade crescente de métodos que possam lidar com conteúdo multimídia em larga escala, e com busca de tais informações de maneira eficiente e efetiva. Os objetos de interesse são representados por vetores descritivos (e. g. cor, textura, geometria, timbre) extraídos do conteúdo, associados a pontos de um espaço multidimensional. Um processo de busca visa, então, encontrar dados similares a uma dada amostra, tipicamente medindo distância entre pontos. Trata-se de um problema comum a uma ampla variedade de aplicações incluindo som, imagens, vídeo, bibliotecas digitais, imagens médicas, segurança, entre outras. Os maiores desafios dizem respeito às dificuldades inerentes aos espaços de alta dimensão, conhecidas por curse of dimensionality, que restringem significativamente a aplicação dos métodos comuns de busca. A literatura recente contém uma variedade de métodos de redução de dimensão que são altamente dependentes do tipo de dado considerado. Constata-se também certa carência de métodos gerais de análise que possam prever com precisão o desempenho dos algoritmos propostos. O presente trabalho contém uma análise geral dos princípios aplicáveis aos sistemas de busca em espaços de alta dimensão. Tal análise permite estabelecer de maneira precisa o compromisso existente entre robustez, refletida principalmente na imunidade a ruído, a taxa de erros de reconhecimento e a dimensão do espaço de observação. Além disto, mostra-se que é possível conceber um método geral de mapeamento, para fins de reconhecimento, que independe de especificidades do conteúdo. Para melhorar a eficiência de busca, um novo método de busca em espaços de alta dimensão é introduzido e analisado. Por fim, descreve-se sumariamente uma realização prática, desenvolvida segundo os princípios discutidos e que atende eficientemente aplicações comerciais de monitoramento de exibição de conteúdo em rádio e TV. / In the last few years there has been an increasing need for methods to deal with large scale multimedia content, and to search such information efficiently and effectively. The objects of interest are represented by feature vectors (e. g. color, texture, geometry, timbre) extracted from the content, associated to points in a multidimensional space. A search process aims, therefore, to find similar data to a given sample, typically measuring distance between points. It is a common problem to a wide range of applications that include sound, image, video, digital library, medical imagery, security, amongst others. The major challenges refer to the difficulties, inherent to the high dimension spaces, known as curse of dimensionality that limit significantly the application of the most common search methods. The recent literature contains a number of dimension reduction methods that are highly dependent on the type of data considered. Besides, there has been a certain lack of general analysis methods that can predict accurately the performance of the proposed algorithms. The present work contains a general analysis of the principles applicable to high dimension space search systems. Such analysis allows establishing in a precise manner the existing tradeoff amongst the system robustness, reflected mainly in the noise immunity, the error rate and the dimension of the observation space. Furthermore, it is shown that it is possible to conceive a mapping method, for recognition purpose, that can be independent of the content specificities. To improve the search efficiency, a new high dimension space search method is introduced and analyzed. Finally, a practical realization is briefly described, which has been developed in accordance with the principles discussed, and that addresses efficiently commercial applications relative to radio and TV content broadcasting monitoring.