We propose using statistical regular pavings (SRPs) as an efficient and adaptive statistical data structure for processing massive, multi-dimensional data. A regular paving (RP) is an ordered binary tree that recursively bisects a box in $\Rz^{d}$ along the first widest side. An SRP is extended from an RP by allowing mutable caches of recursively computable statistics of the data. In this study we use SRPs for two major applications: estimating histogram densities and summarising large spatio-temporal datasets. The SRP histograms produced are $L_1$-consistent density estimators driven by a randomised priority queue that adaptively grows the SRP tree, and formalised as a Markov chain over the space of SRPs. A way to select an estimate is to run a Markov chain over the space of SRP trees, also initialised by the randomised priority queue, but here the SRP tree either shrinks or grows adaptively through pruning or splitting operations. The stationary distribution of the Markov chain is then the posterior distribution over the space of all possible histograms. We then take advantage of the recursive nature of SRPs to make computationally efficient arithmetic averages, and take the average of the states sampled from the stationary distribution to obtain the posterior mean histogram estimate. We also show that SRPs are capable of summarizing large datasets by working with a dataset containing high frequency aircraft position information. Recursively computable statistics can be stored for variable-sized regions of airspace. The regions themselves can be created automatically to reflect the varying density of aircraft observations, dedicating more computational resources and providing more detailed information in areas with more air traffic. In particular, SRPs are able to very quickly aggregate or separate data with different characteristics so that data describing individual aircraft or collected using different technologies (reflecting different levels of precision) can be stored separately and yet also very quickly combined using standard arithmetic operations.

Made available in DSpace on 2016-04-27T16:58:26Z (GMT). No. of bitstreams: 1 Amarildo Aparecido dos Santos.pdf: 6525411 bytes, checksum: ec2c28d9863cac89f1bf7a7c50f588b8 (MD5) Previous issue date: 2007-10-23 / Secretaria da Educação do Estado de São Paulo / O objetivo do presente trabalho é investigar o envolvimento de alunos da 8ª série do Ensino Fundamental no estudo das propriedades dos polígonos a partir de pavimentação no plano. Refletindo sobre este objetivo surgiu a questão de pesquisa: Em que medida um trabalho de exploração com as pavimentações no plano favorece o estudo das propriedades dos polígonos?, criamos, então, uma seqüência de atividades, utilizando alguns elementos da metodologia de pesquisa denominada engenharia didática. A seqüência foi dividida em três blocos. O primeiro sobre o reconhecimento dos polígonos via manipulação de material concreto; o segundo com o uso do software Cabri Géomètre e o terceiro bloco no ambiente papel e lápis. A pesquisa foi amparada pelos pressupostos teóricos de Parzysz sobre o desenvolvimento do pensamento geométrico; pelas idéias de Machado, que sugere para a construção do pensamento geométrico a articulação entre quatro processos: percepção, construção, representação e concepção; pela teoria dos campos conceituais proposta por Vergnaud. A análise dos resultados obtidos na aplicação da seqüência mostrou que o trabalho realizado pelos alunos nos blocos I e II foi insuficiente para que os alunos atingissem a etapa de validações dedutivas, mas foi importante por solidificar conceitos, tais como o conceito de pavimentação e o conceito de polígono regular