Made available in DSpace on 2016-06-02T19:16:39Z (GMT). No. of bitstreams: 1 6003.pdf: 1982961 bytes, checksum: b1cdb60fd2563c64267195ec9d31f2d5 (MD5) Previous issue date: 2014-02-07 / Financiadora de Estudos e Projetos / The theme of this study is the indexing policy for Coordination of Social Communication (CCSs) in university environments, focusing on indexing clippings. This theme is based on interdisciplinary characterization existing between Science, Technology and Society (STS), Information Science (CI) and Communication Sciences (CC) fields in the context of the area of Knowledge Organization to combine, share and create mechanisms that society closer to the aspects of science and technology. Regarding Social Communication highlights the use of clippings, many organizations and this instrument is appropriating to select news in various media on subjects that interest them. Therefore, the purpose of this research is to investigate the organizational and communicational reality CCS/UFSCar, as a starting point for further studies in order lifting guidelines for establishing a policy of indexing for CCSs from context and Analysis Representation of Information. With this proposition, this research has the objective to contribute to the establishment of a policy index that optimizes the thematic treatment of clippings from the perspective of CCSs in university environments in the context of social cognitive indexer professional clippings and users who retrieve this product informational, from theoretical and methodological foundations provided by the area of Knowledge Organization. The qualitative method was used for theoretical and applied research with socio-cognitive approach, and gave up from the questionnaires and the application of Verbal Protocol Group. The methods used were: application of technical and organizational questionnaires and using the technique of Verbal Protocol Group, involving participants: directors/responsible CCSs ANDIFES linked to the brazilian federal universities; director and indexer CCS/UFSCar as well as users who clippings recover the system used by the unit. The results obtained from the questionnaires was the technical-organizational and socio-historical characterization of CCSs from brazilian federal universities and CCS/UFSCar. Mention some results obtained from the application of Verbal Protocol Group in the form: there is a concern with the procedures used to perform the indexing, there is not a satisfactory representation of the matters contained in the indexed clippings; participants suggest that the retrieved records arranged and are also available by publication type, the recognition by participants in relation to the function of preservation and institutional memory that performs clipping, and no need for a policy of indexing and his record in a manual indexing for CCS/UFSCar. The final consideration from the results obtained that depict the existing interdisciplinary STS, CI and CC fields enables collaboration scenario of theories, methodologies and practices for establishing a policy that involves the entire process of thematic information processing and, consequently, quality in both storage and retrieval of. / A temática deste estudo é a política de indexação para Coordenadorias de Comunicação Social (CCSs) em ambientes universitários, com foco na indexação de clippings. Este tema fundamenta-se na caracterização interdisciplinar existente entre os campos Ciência, Tecnologia e Sociedade (CTS), Ciência da Informação (CI) e Ciências da Comunicação (CC) no contexto da área da Organização do Conhecimento ao combinar, compartilhar e criar mecanismos que aproximem a sociedade aos aspectos ligados à ciência e a tecnologia. No campo da Comunicação Social destaca-se a utilização dos clippings, instrumento este que muitas organizações se apropriam para selecionar notícias em diversos meios de comunicação sobre assuntos que as interessam. Para tanto, a proposta desta pesquisa é investigar a realidade organizacional e comunicacional CCS/UFSCar, como ponto de partida para estudos posteriores, tendo em vista o levantamento de diretrizes para o estabelecimento de uma política de indexação para CCSs a partir do contexto da Análise e Representação da Informação. Com essa proposição, esta pesquisa tem por objetivo geral contribuir para o estabelecimento de uma política de indexação que otimize o tratamento temático de clippings, na perspectiva das CCSs em ambientes universitários, no contexto sociocognitivo do profissional indexador de clippings e dos usuários que recuperam este produto informacional, a partir de fundamentos teóricos e metodológicos disponibilizados pela área da Organização do Conhecimento. A metodologia utilizada foi qualitativa para a pesquisa teórico-aplicada, com abordagem sociocognitiva, e deu-se a partir da aplicação de questionários e da aplicação de Protocolo Verbal em Grupo. As metodologias utilizadas foram: aplicação de questionários técnico-organizacionais e utilização da técnica do Protocolo Verbal em Grupo, envolvendo os participantes: diretores/responsáveis pelas CCSs das universidades federais brasileiras vinculadas à ANDIFES; diretor e indexador da CCS/UFSCar, bem como usuários que recuperam clippings no sistema utilizado pela unidade. O resultado obtido a partir da aplicação dos questionários foi a caracterização técnica-organizacional e sócio-histórica das CCSs das universidades federais brasileiras e da CCS/UFSCar. Citam-se alguns resultados obtidos a partir da aplicação do Protocolo Verbal na modalidade em Grupo: há a preocupação com os procedimentos adotados para a realização da indexação; não há uma representação satisfatória dos assuntos contidos nos clippings indexados; os participantes sugerem que os registros recuperados sejam arranjados e disponibilizados também por tipo de publicação; o reconhecimento por parte dos participantes em relação à função de preservação e memória institucional que o clipping exerce; inexistência e a necessidade de uma política de indexação e seu registro em um manual de indexação para a CCS/UFSCar. As considerações finais a partir dos resultados obtidos retratam que a interdisciplinaridade existente entre os campos CTS, CI e CC permite um cenário de colaboração de teorias, metodologias e práticas para o estabelecimento de uma política que envolva todo o processo do tratamento temático da informação e, consequentemente, qualidade tanto no armazenamento como na recuperação de documentos.

Orientador: Mariângela Spotti Lopes Fujita / Resumo: Na contemporaneidade, os repositórios institucionais possibilitam a reunião, armazenamento, tratamento, preservação e visibilidade dos recursos informacionais produzidos no âmbito acadêmico. Considerando-se que o campo da Organização do Conhecimento possui os fundamentos teórico-práticos necessários no que tange aos problemas de representação e recuperação em sistemas de recuperação da informação, a proposição da tese foi investigar/avaliar o processo de indexação de assuntos em repositórios institucionais no contexto de bibliotecas universitárias e sua influência na recuperação da informação pelos usuários, visando o aprimoramento do tratamento/da representação temática da informação documental e da recuperação por assuntos. O objetivo geral da pesquisa foi contribuir para a implementação/melhorias de diretrizes de indexação de assuntos em repositórios institucionais no contexto de bibliotecas universitárias, possibilitando a adequada representação e recuperação por assuntos nestes sistemas de recuperação da informação. Para tanto, foram delineados os seguintes objetivos específicos: a) realizar estudo teórico sobre os repositórios institucionais como sistemas de recuperação da informação e do processo de indexação de assuntos em perspectiva dicotômica: do tratamento/da representação e da recuperação por assuntos no contexto de bibliotecas universitárias; b) investigar o tratamento/a representação temática da informação documental em repositórios institucionais no contexto d... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: In present times, the institutional repositories enable the gathering, storage, treatment, preservation and visibility of information resources produced in the academic field. Considering that the Knowledge Organization field has the necessary theoretical-practical foundations regarding the issues of representation and retrieval in information retrieval systems, the proposition of the thesis was to investigate/evaluate the subject indexing process in institutional repositories in the context of academic libraries and its influence on information retrieval by users, aiming at improving the treatment/thematic representation of documentary information and subject retrieval. The general objective of the research was to contribute to the implementation / improvement of subject index guidelines in institutional repositories in the context of academic libraries, enabling the adequate representation and subject retrieval in information retrieval systems. To this end, the following specific objectives were outlined: a) conducting a theoretical study on institutional repositories as information retrieval systems and the subject index process within in a dichotomous perspective: of the treatment/of the representation and of the subject retrieval in the context of academic libraries; b) investigating the treatment/the thematic representation of documentary information in institutional repositories in the context of academic libraries, by means of the application of organizational diagnos... (Complete abstract click electronic access below) / Resumen: En los tiempos contemporáneos, los repositorios institucionales permiten la recolección, almacenamiento, tratamiento, preservación y visibilidad de los recursos informacionales producidos en el campo académico. Considerando que el campo de la Organización del Conocimiento presenta los fundamentos teórico-prácticos necesarios en cuanto a los problemas de representación y recuperación en los sistemas de recuperación de información, la propuesta de la tesis fue investigar/evaluar el proceso de indización por materias en repositorios institucionales y su influencia en la recuperación de información por los usuarios, pretendiendo el perfeccionamiento del tratamiento temático de la información documental y de la recuperación por materias en estos sistemas de recuperación tanto en el contexto de bibliotecas universitarias como en el ámbito académico. El objetivo general de la investigación fue contribuir a la implementación/mejoras de directrices de indización por materias en repositorios institucionales en el contexto de bibliotecas universitarias, posibilitando la adecuada representación y recuperación por materias en estos sistemas de recuperación de información. Para ello, fueron delineados los seguientes objetivos específicos: a) realizar un estudio teórico sobre el proceso de indización por materias desde la perspectiva de la Organización del Conocimiento en perspectiva dicotómica: del tratamiento/de la representación y de la recuperación por materias en el contexto de bibliot... (Resumen completo clicar acceso eletrônico abajo) / Doutor

O grau de similaridade entre elementos de dados é o fator primordial para a recuperação de informações em Sistemas Gerenciadores de Bases de Dados que manipulam dados complexos, como seqüências genéticas, séries temporais e dados multimídia (imagens, áudios, vídeos, textos longos). Para responder a essas consultas em um tempo reduzido, faz-se necessário utilizar métodos que usam métricas para avaliar a similaridade entre os elementos. Esses métodos são conhecidos como Métodos de Acesso Métricos. Dentre os mais conhecidos na literatura estão a M-tree e a Slim-tree. Existem duas maneiras de executar as operações de construção de índices em qualquer método de acesso: inserindo elemento a elemento ou usando a operação de carga-rápida (bulk-loading). O primeiro tipo de construção é comum e necessário para todo tipo de método de indexação dinâmico. Já as operações de carga-rápida são utilizadas para conjuntos de dados maiores, como por exemplo, na recuperação de backups em bases de dados ou na criação posterior de índices. Nessas situações, a inserção individual tende a ser mais demorada. Realizar uma carga-rápida possibilita a construção de índices com melhor eficiência e em menor tempo, pois há a disponibilidade de todos os dados no instante da criação da estrutura de índices, possibilitando explorar as propriedades do conjunto como um todo. Os Sistemas Gerenciadores de Base de Dados oferecem operações de carga-rápida dos dados nos métodos tradicionais, as quais devem ser supridas também nos Métodos de Acesso Métricos. Neste trabalho, são apresentadas três abordagens, uma técnica para carga-rápida dos dados em Métodos de Acesso Métricos e foi desenvolvido um algoritmo baseado nessa técnica para construir uma Slim-tree. Este é o primeiro algoritmo de carga-rápida baseada em amostragem que sempre produz uma Slim-tree válida, portanto é o primeiro descrito na literatura que pode ser incluído em um Sistema Gerenciador de Base de Dados. Os experimentos descritos neste trabalho mostram que o algoritmo proposto mantém bom agrupamento dos dados e supera o desempenho dos métodos de inserção seqüencial levando em conta tanto o desempenho de construção quanto à eficiência para realizar consultas / The similarity degree between data elements is the primordial factor for information retrieval in databases that handle complex data, such as genetic sequences, time series and multimedia objects (long images, audio, videos, texts). To answer these queries in a reduced time, it is necessary methods that use metrics to evaluate the similarity between elements. These methods are known as Metric Access Methods. The most known Metric Access Methods in the literature are the M-tree and the Slim-tree. There are two ways to build index in any access method: inserting element one by one or using the bulk-load operation. The first build type is very common and required for all kinds of dynamic access methods. The bulk-load operations are used for bigger datasets, as for example, in the recovery of backups and re-creation of database indexes. In these situations, the individual insertion takes much time. The bulk-load operation makes it possible to construct indexes more efficiently and faster, because it has the availability of the whole data when the index structure are created, and thus, it is possible to explore the properties of the whole set. Database Management Systems offer bulk-load operations for the traditional methods, so it is important that they can be also supplied for Metric Access Methods. This work presents three bulk-loading approaches and it proposes a technique to bulk-load data into Metric Access Methods. An algorithm based on this technique was developed to construct a Slim-tree. This is the first bulk-load algorithm based on sampling that always produces a valid Slim-tree, therefore is the first one described in literature that can be enclosed in a Database Management System. The experiments show that this algorithm keeps good clustering of data and in such a way that it surpasses the performance of sequential insertion, taking into account the construction performance and the efficiency to perform queries

Com o vislumbramento de aplicações que exigiam representações em espaços multidimensionais, surgiu a necessidade de desenvolvimento de métodos de acessos eficientes a estes dados representados em R^d. Dentre as aplicações precursoras dos métodos de acessos multidimensionais, podemos citar os sistemas de geoprocessamento, aplicativos 3D e simuladores. Posteriormente, os métodos de acessos multidimensionais também apresentaram-se como uma importante ferramenta no projeto de classificadores, principalmente classificadores pelos vizinhos mais próximos. Com isso, expandiu-se o espaço de representação, que antes se limitava no máximo a quatro dimensões, para dimensionalidades superiores a mil. Dentre os vários métodos de acesso multidimensional existentes, destaca-se uma classe de métodos baseados em árvores balanceadas com representação em R^d. Estes métodos constituem evoluções da árvore de acesso unidimenisonal B-tree e herdam várias características deste último. Neste trabalho, apresentamos alguns métodos de acessos dessa classe de forma a ilustrar a idéia central destes algoritmos e propomos e implementamos um novo método de acesso, a PCA-tree. A PCA-tree utiliza uma heurística de quebra de nós baseada na extração da componente principal das amostras a serem divididas. Um hiperplano que possui essa componente principal como seu vetor normal é definido como o elemento que divide o espaço associado ao nó. A partir dessa idéia básica geramos uma estrutura de dados e algoritmos que utilizam gerenciamento de memória secundária como a B-tree. Finalmente, comparamos o desempenho da PCA-tree com o desempenho de alguns outros métodos de acesso da classe citada, e apresentamos os prós e contras deste novo método de acesso através de análise de resultados práticos. / The advent of applications demanding the representation of objects in multi-dimensional spaces fostered the development of efficient multi-dimensional access methods. Among some early applications that required multi-dimensional access methods, we can cite geo-processing systems, 3D applications and simulators. Later on, multi-dimensional access methods also became important tools in the design of classifiers, mainly of those based on nearest neighbors technique. Consequently, the dimensionality of the spaces has increased, from earlier at most four to dimensionality larger than a thousand. Among several multi-dimensional access methods, the class of approaches based on balanced tree structures with data represented in Rd has received a lot of attention. These methods constitute evolues from the B-tree for unidimensional accesses, and inherit several of its characteristics. In this work, we present some of the access methods based on balanced trees in order to illustrate the central idea of these algorithms, and we propose and implement a new multi-dimensional access method, which we call PCA-tree. It uses an heuristic to break nodes based on the principal component of the sample to be divided. A hyperplane, whose normal is the principal component, is defined as the one that will split the space represented by the node. From this basic idea we define the data structure and the algorithms for the PCA-tree employing secondary memory management, as in B-trees. Finally, we compare the performance of the PCA-tree with the performance of other methods in the cited class, and present advantages and disadvantages of the proposed access method through analysis of experimental results.

Estudo sobre a representação documentária da informação estatística. A partir do reconhecimento dessa informação como representação de realidades sociais, identificam-se as suas especificidades e as da sua representação documentária visando sua divulgação na Internet e, portanto, a transmissão de informação sem a intermediação presencial do documentalista. Parte-se das premissas que a informação estatística tem características próprias que a diferenciam da informação textual, e que nem todas as recomendações para a construção de linguagem documentária, para representar esse tipo de informação, se aplicam necessariamente à representação de informações estatísticas. Utilizando referenciais da construção da linguagem documentária e da terminologia, sistematizam-se alguns parâmetros para que também o tratamento e a divulgação da informação estatística se realizem como possibilidades para a geração de novos conhecimentos. / This paper deals with the study on the documentary representation of statistical information. From the recognition that the statistical information represents social realities, the study identifies their specificities and their documentary representation, focusing its popularization in Internet and, therefore, its transmission without the presence of the librarian. It is based on two premises: first, the statistical information has characteristics that differentiate it from the textual information, and, second, not all the recommendations for the documentary language construction to represent textual information, necessarily represent statistical information. Using reference of documentary language construction and terminology, some parameters were systematized so that also the treatment and the popularization of the statistical information take place as possibilities of generating new knowledge.

A extração de metadados semânticos de vídeos digitais para uso em serviços de personalização é importante, já que o conteúdo é adaptado segundo as preferências de cada usuário. Entretanto, apesar de serem encontradas várias propostas na literatura, as técnicas de indexação automática são capazes de gerar informações semânticas apenas quando o domínio do conteúdo é restrito. Alternativamente, existem técnicas para a criação manual dessas informações por profissionais, contudo, são dispendiosas e suscetíveis a erros. Uma possível solução seria explorar anotações colaborativas dos usuários, mas tal estratégia provoca a perda de individualidade dos dados, impedindo a extração de preferências do indivíduo a partir da interação. Este trabalho tem como objetivo propor uma arquitetura de personalização que permite a indexação multimídia de modo irrestrito e barato, utilizando anotações colaborativas, mas mantendo-se a individualidade dos dados para complementar o perfil de interesses do usuário com conceitos relevantes. A multimodalidade de metadados e de preferências também é explorada na presente tese, fornecendo maior robustez na extração dessas informações, e obtendo-se uma maior carga semântica que traz benefícios às aplicações. Como prova de conceito, este trabalho apresenta dois serviços de personalização que exploram a arquitetura proposta, avaliando os resultados por meio de comparações com abordagens previamente propostas na literatura / The extraction of semantic information from digital video is important to be used on personalization services because the content is adapted according to each users preferences. However, although it is possible to find several approaches in the literature, automatic indexing techniques are able to generate semantic metadata only when the contents domain is restricted. Alternatively, this information can be created manually by professionals, but this activity is time-consuming and error-prone. A possible solution would be to explore collaborative users annotations, but such approach has the disadvantage of lacking the individuality of annotations, hampering the extraction of users preferences from the interaction. This work has the objective of proposing a generic personalization architecture that allows multimedia indexing procedures to be accomplished in a cheap and unrestricted way. Such architecture uses collaborative annotations, but keeps the individuality of the data in order to augment the users profile with relevant concepts. The multimodality of metadata and users preferences is also explored in this work, which provides robustness during the extraction of semantic information, bringing benefits to applications. This work also presents two personalization services that explore the proposed architecture, along with evaluations that compare the obtained results with previously proposed approaches

Orientador: João Batista Ernest de Moraes / Banca: Sidney Barbosa / Banca: Maria Cristiane Galvão / Resumo: Em Organização da Informação, no aspecto do tratamento da informação, há uma carência de subsídios teóricos referente à análise de documentos fictícios. Na intenção de contribuir teoricamente com o desenvolvimento de um método que facilite a tarefa de análise de assunto em texto narrativo, nos seus aspectos de identificação e seleção de conceitos, buscou-se subsídios teóricos em áreas de interface com a Ciência da Informação, mais especificamente a Lingüística. Esta última proporcionou o conhecimento da estrutura textual do texto narrativo, e a Semântica Discursiva contribuiu com o percurso temático e o percurso figurativo utilizados como ferramentas para análise de assunto de textos narrativos. Objetivou-se, desta forma, a elaboração de um método que facilite a tarefa de análise de assunto, nos aspectos de identificação e seleção de conceitos, para promover a acessibilidade do conteúdo do documento. Para tanto, optou-se pela análise de três contos espíritas, nos quais foi inicialmente identificada, em suas estruturas, a seqüência canônica e, a partir dela, realizou-se a análise do percurso temático e do percurso figurativo, para a identificação de conceitos. Obteve-se como resultados a identificação de temas principais e secundários nos textos narrativos analisados. Com isso, concluiu-se que, o método experimental de análise proposto mostrou-se eficiente para o corpus desta pesquisa, pois possibilitou a identificação de conceitos relevantes que caracterizam os assuntos abordados nos contos, os quais poderão posteriormente ser traduzidos para a linguagem de um sistema de informação. Sugere-se, ainda, o desenvolvimento de um estudo para verificar e confirmar a hipótese surgida durante a realização da presente pesquisa, de que nas fases de Manipulação e Sanção, componentes da seqüência canônica... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: In the field of Knowledge Organization, more specifically in the approach of information usage, there is a lack of theorical assistance concerning to the analysis of fictitious documents. Trying to theorically contribute with the development of a method that makes easier the analysis of subjects in a narrative text, on its aspects of identification and selection of concepts, we researched theorical assistance in interface fields linked to the Science of Knowledge, more specifically Linguistics. This last one provided the Knowledge about the textual structure into the narrative text and the Discursive Semantics contributed with the thematic and figurative courses, used as tools on the analysis of questions form narrative texts. We aimed, therefore, the formulation of a method that could make easier the task of analyzing the subject, its aspects of identification and selection of concepts, in order to foment the accessibility of the content into the document. To achieve it, we opted by the analysis of there spiritualistic tales, in which was initially identified, on its structures, the canonic sequence and, through it, we did the analysis of the thematic and figurative paths, due to the identification of the concepts. The results were the identification of primary and secondary themes in the narrative texts that were analyzed. From it, we concluded that the experimental method of analysis proposed was efficient into the corpus of this research, because allowed us the identification of relevant concepts that characterize the issues approached in the tales, which will, in the future, be translated into a language from the system of information. We still suggest the development of a review to verify and hold true the hypothesis that appeared during this paper, and it states that in levels of Manipulation and Sanction, elements to the canonic sequence... (Complete abstract, click electronic address below) / Mestre

Estudo sobre a representação documentária da informação estatística. A partir do reconhecimento dessa informação como representação de realidades sociais, identificam-se as suas especificidades e as da sua representação documentária visando sua divulgação na Internet e, portanto, a transmissão de informação sem a intermediação presencial do documentalista. Parte-se das premissas que a informação estatística tem características próprias que a diferenciam da informação textual, e que nem todas as recomendações para a construção de linguagem documentária, para representar esse tipo de informação, se aplicam necessariamente à representação de informações estatísticas. Utilizando referenciais da construção da linguagem documentária e da terminologia, sistematizam-se alguns parâmetros para que também o tratamento e a divulgação da informação estatística se realizem como possibilidades para a geração de novos conhecimentos. / This paper deals with the study on the documentary representation of statistical information. From the recognition that the statistical information represents social realities, the study identifies their specificities and their documentary representation, focusing its popularization in Internet and, therefore, its transmission without the presence of the librarian. It is based on two premises: first, the statistical information has characteristics that differentiate it from the textual information, and, second, not all the recommendations for the documentary language construction to represent textual information, necessarily represent statistical information. Using reference of documentary language construction and terminology, some parameters were systematized so that also the treatment and the popularization of the statistical information take place as possibilities of generating new knowledge.

Com o vislumbramento de aplicações que exigiam representações em espaços multidimensionais, surgiu a necessidade de desenvolvimento de métodos de acessos eficientes a estes dados representados em R^d. Dentre as aplicações precursoras dos métodos de acessos multidimensionais, podemos citar os sistemas de geoprocessamento, aplicativos 3D e simuladores. Posteriormente, os métodos de acessos multidimensionais também apresentaram-se como uma importante ferramenta no projeto de classificadores, principalmente classificadores pelos vizinhos mais próximos. Com isso, expandiu-se o espaço de representação, que antes se limitava no máximo a quatro dimensões, para dimensionalidades superiores a mil. Dentre os vários métodos de acesso multidimensional existentes, destaca-se uma classe de métodos baseados em árvores balanceadas com representação em R^d. Estes métodos constituem evoluções da árvore de acesso unidimenisonal B-tree e herdam várias características deste último. Neste trabalho, apresentamos alguns métodos de acessos dessa classe de forma a ilustrar a idéia central destes algoritmos e propomos e implementamos um novo método de acesso, a PCA-tree. A PCA-tree utiliza uma heurística de quebra de nós baseada na extração da componente principal das amostras a serem divididas. Um hiperplano que possui essa componente principal como seu vetor normal é definido como o elemento que divide o espaço associado ao nó. A partir dessa idéia básica geramos uma estrutura de dados e algoritmos que utilizam gerenciamento de memória secundária como a B-tree. Finalmente, comparamos o desempenho da PCA-tree com o desempenho de alguns outros métodos de acesso da classe citada, e apresentamos os prós e contras deste novo método de acesso através de análise de resultados práticos. / The advent of applications demanding the representation of objects in multi-dimensional spaces fostered the development of efficient multi-dimensional access methods. Among some early applications that required multi-dimensional access methods, we can cite geo-processing systems, 3D applications and simulators. Later on, multi-dimensional access methods also became important tools in the design of classifiers, mainly of those based on nearest neighbors technique. Consequently, the dimensionality of the spaces has increased, from earlier at most four to dimensionality larger than a thousand. Among several multi-dimensional access methods, the class of approaches based on balanced tree structures with data represented in Rd has received a lot of attention. These methods constitute evolues from the B-tree for unidimensional accesses, and inherit several of its characteristics. In this work, we present some of the access methods based on balanced trees in order to illustrate the central idea of these algorithms, and we propose and implement a new multi-dimensional access method, which we call PCA-tree. It uses an heuristic to break nodes based on the principal component of the sample to be divided. A hyperplane, whose normal is the principal component, is defined as the one that will split the space represented by the node. From this basic idea we define the data structure and the algorithms for the PCA-tree employing secondary memory management, as in B-trees. Finally, we compare the performance of the PCA-tree with the performance of other methods in the cited class, and present advantages and disadvantages of the proposed access method through analysis of experimental results.

O vetor de sufixo é uma estrutura de dados importante utilizada em muitos problemas que envolvem cadeias de caracteres. Na literatura, muitos trabalhos têm sido propostos para a construção de vetores de sufixo em memória externa. Entretanto, esses trabalhos não enfocam conjuntos de cadeias, ou seja, não consideram vetores de sufixo generalizados. Essa limitação motiva esta dissertação, a qual avança no estado da arte apresentando o algoritmo eGSA, o primeiro algoritmo proposto para a construção de vetores de sufixo generalizados aumentado com o vetor de prefixo comum mais longo (LCP) e com a transformada de Burrows-Wheeler (BWT) em memória externa. A dissertação foi desenvolvida dentro do contexto de bioinformática, já que avanços tecnológicos recentes têm aumentado o volume de dados biológicos disponíveis, os quais são armazenados como cadeias de caracteres. O algoritmo eGSA foi validado por meio de testes de desempenho com dados reais envolvendo sequências grandes, como DNA, e sequências pequenas, como proteínas. Com relação aos testes comparativos com conjuntos de grandes cadeias de DNA, o algoritmo proposto foi comparado com o algoritmo correlato mais eficiente na literatura de construção de vetores de sufixo, o qual foi adaptado para construção de vetores generalizados. O algoritmo eGSA obteve um tempo médio de 3,2 a 8,3 vezes menor do que o algoritmo correlato e consumiu 50% menos de memória. Para conjuntos de cadeias pequenas de proteínas, foram realizados testes de desempenho apenas com o eGSA, já que no melhor do nosso conhecimento, não existem trabalhos correlatos que possam ser adaptados. Comparado com o tempo médio para conjuntos de cadeias grandes, o eGSA obteve tempos competitivos para conjuntos de cadeias pequenas. Portanto, os resultados dos testes demonstraram que o algoritmo proposto pode ser aplicado eficientemente para indexar tanto conjuntos de cadeias grandes quanto conjuntos de cadeias pequenas / The suffix array is an important data structure used in several string processing problems. In the literature, several approaches have been proposed to deal with external memory suffix array construction. However, these approaches are not specifically aimed to index sets of strings, that is, they do not consider generalized suffix arrays. This limitation motivates this masters thesis, which presents eGSA, the first external memory algorithm developed to construct generalized suffix arrays enhanced with the longest common prefix array (LCP) and the Burrows-Wheeler transform (BWT). We especially focus on the context of bioinformatics, as recent technological advances have increased the volume of biological data available, which are stored as strings. The eGSA algorithm was validated through performance tests with real data from DNA and proteins sequences. Regarding performance tests with large strings of DNA, we compared our algorithm with the most efficient and related suffix array construction algorithm in the literature, which was adapted to construct generalized arrays. The results demonstrated that our algorithm reduced the time spent by a factor of 3.2 to 8.3 and consumed 50% less memory. For sets of small strings of proteins, tests were performed only with the eGSA, since to the best of our knowledge, there is no related work that can be adapted. Compared to the average time spent to index sets of large strings, the eGSA obtained competitive times to index sets of small strings. Therefore, the performance tests demonstrated that the proposed algorithm can be applied efficiently to index both sets of large strings and sets of small strings