Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Almeida, Eduardo Cunha de | - |
Autor(es): dc.contributor | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática | - |
Autor(es): dc.creator | Holanda, Pedro Thiago Timbó | - |
Data de aceite: dc.date.accessioned | 2019-08-21T23:16:51Z | - |
Data de disponibilização: dc.date.available | 2019-08-21T23:16:51Z | - |
Data de envio: dc.date.issued | 2017-09-18 | - |
Data de envio: dc.date.issued | 2017-09-18 | - |
Data de envio: dc.date.issued | 2017 | - |
Fonte completa do material: dc.identifier | http://hdl.handle.net/1884/46126 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/1884/46126 | - |
Descrição: dc.description | Orientador : Prof. Dr. Eduardo Cunha de Almeida | - |
Descrição: dc.description | Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 24/02/2017 | - |
Descrição: dc.description | Inclui referências : f. 41-43 | - |
Descrição: dc.description | Área de concentração: Ciência da computação | - |
Descrição: dc.description | Resumo: Em Database Cracking, uma coluna de banco de dados se organiza fisicamente, de maneira autônoma, em partições, um índice é então criado para otimizar o acesso a essas partições. A árvore AVL é a estrutura de dados utilizada para implementar esse índice. Contudo, em termos de cache, ela é particularmente ineficiente para consultas de intervalos, já que seus nós acessados apenas algumas vezes e os nós frequentemente acessados estão espalhados por toda a árvore. Esse trabalho apresenta a Self-Pruning Splay Tree (SPST) que é uma estrutura de dados capaz de reorganizar os dados mais e menos acessados, melhorando o tempo de acesso para as partições mais acessadas. Para cada consulta de intervalo, a SPST rotaciona para a raiz os nós que apontam para os valores do predicado da consulta e o valor médio do intervalo. Eventualmente, os nós mais acessados da árvore irão permanecer próximos a raíz, melhorando a utilização da CPU e a atividade de cache. Os nós menos acessados permanecerão próximos às folhas e serão removidos para limparmos dados que não são utilizados, diminuindo o tamanho do índice e obtendo custos de leitura e atualização menores. Palavras-chave: Database Cracking, Índice para Cracking , Árvore Splay. | - |
Descrição: dc.description | Abstract: In database cracking, a database is physically self-organized into cracked partitions with cracker indices boosting the access to these partitions. The AVL Tree is the current data structure of choice to implement cracker indices. However, it is particularly cache-inefficient for range queries, because the nodes accessed only for a few times (i.e, "Cold Data") and the most accessed ones (i.e, "Hot Data") are spread all over the index. This work presents the Self-Pruning Splay Tree (SPST) data structure to index database cracking and reorganize "Hot Data" and "Cold Data" to boost the access to the cracked partitions. To every range query, the SPST rotates to the root the nodes pointing to the edges and to the middle value of the predicate interval. Eventually, the most accessed tree nodes remain close to the root improving CPU and cache activity. On the other hand, the least accessed tree nodes remain close to the leaves and are pruned to clean up unused data in order to diminish the storage footprint with significant improvements: smaller lookup/update costs. Keywords: Database Cracking, Cracker Index, Splay Tree. | - |
Formato: dc.format | 43 f. : il., algumas color., grafs., tabs. | - |
Formato: dc.format | application/pdf | - |
Formato: dc.format | application/pdf | - |
Relação: dc.relation | Disponível em formato digital | - |
Palavras-chave: dc.subject | Ciência da computação | - |
Palavras-chave: dc.subject | Estruturas de dados (Computação) | - |
Palavras-chave: dc.subject | Teses | - |
Título: dc.title | SPST-Index : a self pruning splay tree index for database cracking | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositório Institucional - Rede Paraná Acervo |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: