• Login
    View Item 
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016034P5 Programa de Pós-Graduação em Informática
    • Dissertações
    • View Item
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016034P5 Programa de Pós-Graduação em Informática
    • Dissertações
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    SPST-Index : a self pruning splay tree index for database cracking

    Thumbnail
    View/Open
    R - D - PEDRO THIAGO TIMBO HOLANDA.pdf (1.333Mb)
    Date
    2017
    Author
    Holanda, Pedro Thiago Timbó
    Metadata
    Show full item record
    Subject
    Ciência da computação
    Estruturas de dados (Computação)
    Teses
    xmlui.dri2xhtml.METS-1.0.item-type
    Dissertação
    Abstract
    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.
     
    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.
     
    URI
    http://hdl.handle.net/1884/46126
    Collections
    • Dissertações [479]

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_typeThis CollectionBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_type

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV