Efficient external memory structures for range-aggregate queries

We present external memory data structures for efficiently answering range-aggregate queries. The range-aggregate problem is defined as follows: Given a set of weighted points in R-d, compute the aggregate of the weights of the points that lie inside a d-dimensional orthogonal query rectangle. The aggregates we consider in this paper include COUNT, sum, and MAX. First, we develop a structure for answering two-dimensional range-COUNT queries that uses O(N/B) disk blocks and answers a query in O(log(B) N) I/Os, where N is the number of input points and B is the disk block size. The structure can be extended to obtain a near-linear-size structure for answering range-sum queries using O(log(B) N) I/Os, and a linear-size structure for answering range-MAX queries in O(log(B)(2) N) I/Os. Our structures can be made dynamic and extended to higher dimensions. (C) 2012 Elsevier B.V. All rights reserved.

Small strong epsilon nets

Let P be a set of n points in R-d. A point x is said to be a centerpoint of P if x is contained in every convex object that contains more than dn/d+1 points of P. We call a point x a strong centerpoint for a family of objects C if x is an element of P is contained in every object C is an element of C that contains more than a constant fraction of points of P. A strong centerpoint does not exist even for halfspaces in R-2. We prove that a strong centerpoint exists for axis-parallel boxes in Rd and give exact bounds. We then extend this to small strong epsilon-nets in the plane. Let epsilon(S)(i) represent the smallest real number in 0, 1] such that there exists an epsilon(S)(i)-net of size i with respect to S. We prove upper and lower bounds for epsilon(S)(i) where S is the family of axis-parallel rectangles, halfspaces and disks. (C) 2014 Elsevier B.V. All rights reserved.

Topics in randomized numerical linear algebra

This thesis studies three classes of randomized numerical linear algebra algorithms, namely: (i) randomized matrix sparsification algorithms, (ii) low-rank approximation algorithms that use randomized unitary transformations, and (iii) low-rank approximation algorithms for positive-semidefinite (PSD) matrices.

Randomized matrix sparsification algorithms set randomly chosen entries of the input matrix to zero. When the approximant is substituted for the original matrix in computations, its sparsity allows one to employ faster sparsity-exploiting algorithms. This thesis contributes bounds on the approximation error of nonuniform randomized sparsification schemes, measured in the spectral norm and two NP-hard norms that are of interest in computational graph theory and subset selection applications.

Low-rank approximations based on randomized unitary transformations have several desirable properties: they have low communication costs, are amenable to parallel implementation, and exploit the existence of fast transform algorithms. This thesis investigates the tradeoff between the accuracy and cost of generating such approximations. State-of-the-art spectral and Frobenius-norm error bounds are provided.

The last class of algorithms considered are SPSD "sketching" algorithms. Such sketches can be computed faster than approximations based on projecting onto mixtures of the columns of the matrix. The performance of several such sketching schemes is empirically evaluated using a suite of canonical matrices drawn from machine learning and data analysis applications, and a framework is developed for establishing theoretical error bounds.

In addition to studying these algorithms, this thesis extends the Matrix Laplace Transform framework to derive Chernoff and Bernstein inequalities that apply to all the eigenvalues of certain classes of random matrices. These inequalities are used to investigate the behavior of the singular values of a matrix under random sampling, and to derive convergence rates for each individual eigenvalue of a sample covariance matrix.

基于乐理的蛇形机器人控制方法研究

根据生物蛇和蛇形机器人的结构及运动特点 ,提出了基于乐理的蛇形机器人控制方法 ,定义了乐理的符号、规则与蛇形机器人控制过程的对应关系 ,编写了蜿蜒运动步态谱 .“勘查者—I”蛇形机器人上实现了蜿蜒运动的控制 .给出了今后的研究方向 .

积分偏移的计算几何与并行实现

The Second Round of Oil & Gas Exploration needs more precision imaging method, velocity vs. depth model and geometry description on Complicated Geological Mass. Prestack time migration on inhomogeneous media was the technical basic of velocity analysis, prestack time migration on Rugged surface, angle gather and multi-domain noise suppression. In order to realize this technique, several critical technical problems need to be solved, such as parallel computation, velocity algorithm on ununiform grid and visualization. The key problem is organic combination theories of migration and computational geometry. Based on technical problems of 3-D prestack time migration existing in inhomogeneous media and requirements from nonuniform grid, parallel process and visualization, the thesis was studied systematically on three aspects: Infrastructure of velocity varies laterally Green function traveltime computation on ununiform grid, parallel computational of kirchhoff integral migration and 3D visualization, by combining integral migration theory and Computational Geometry. The results will provide powerful technical support to the implement of prestack time migration and convenient compute infrastructure of wave number domain simulation in inhomogeneous media. The main results were obtained as follows: 1. Symbol of one way wave Lie algebra integral, phase and green function traveltime expressions were analyzed, and simple 2-D expression of Lie algebra integral symbol phase and green function traveltime in time domain were given in inhomogeneous media by using pseudo-differential operators’ exponential map and Lie group algorithm preserving geometry structure. Infrastructure calculation of five parts, including derivative, commutating operator, Lie algebra root tree, exponential map root tree and traveltime coefficients , was brought forward when calculating asymmetry traveltime equation containing lateral differential in 3-D by this method. 2. By studying the infrastructure calculation of asymmetry traveltime in 3-D based on lateral velocity differential and combining computational geometry, a method to build velocity library and interpolate on velocity library using triangulate was obtained, which fit traveltime calculate requirements of parallel time migration and velocity estimate. 3. Combining velocity library triangulate and computational geometry, a structure which was convenient to calculate differential in horizontal, commutating operator and integral in vertical was built. Furthermore, recursive algorithm, for calculating architecture on lie algebra integral and exponential map root tree (Magnus in Math), was build and asymmetry traveltime based on lateral differential algorithm was also realized. 4. Based on graph theory and computational geometry, a minimum cycle method to decompose area into polygon blocks, which can be used as topological representation of migration result was proposed, which provided a practical method to block representation and research to migration interpretation results. 5. Based on MPI library, a process of bringing parallel migration algorithm at arbitrary sequence traces into practical was realized by using asymmetry traveltime based on lateral differential calculation and Kirchhoff integral method. 6. Visualization of geological data and seismic data were studied by the tools of OpenGL and Open Inventor, based on computational geometry theory, and a 3D visualize system on seismic imaging data was designed.

BACH TO BASICS: A PERFORMANCE STUDY OF THE SUITES FOR SOLO CELLO BY JOHANN SEBASTIAN BACH, BWV 1007-1012

This dissertation project focuses on J.S. Bach's Six Suites and explores the ideology of the Suites as etudes versus concert pieces. It is my belief that the evolution of the rank of the Suites in a cellist's repertoire today represents more than just historical coincidence. My premise is that the true genius of the Suites lies in their dual role as !&I efficient teaching pieces and superior performance works. Consequently, the maximum use of Bach's Six Suites as pedagogical material heightens both technical ability and deeper appreciation of the art. The dual nature of the Suites must always be emphasized: not only do these pieces provide innumerable opportunities for building cello technique, but they also offer material for learning the fundamentals of melody, harmony, dynamics, phrasing and texture. It is widely accepted among academic musicians that Bach's keyboard music serves as perfect compositions -- the model for music theory, music form and music counterpoint. I argue that we should employ the Cello Suites to this same end. The order in which the Suites are presented was deliberately chosen to highlight the contrasts in the pieces. Because the technical demands of each suite grow progressively from the previous one, they were performed non-consecutively in order to balance the difficulty and depth of each recital. The first compact disc consists of the Third Suite in C Major and Fifth Suite in C minor (with scordatura tuning), emphasizing the parallel keys. The Second Suite in D Minor and the Fourth Suite in E-flat Major comprises the compact disc. Finally, in the third compact disc, the First Suite in G Major and the Sixth Suite in D Major (composed for the five string cello piccola, but played here on a four-string cello) highlights the progression of the Suites.

La música práctica en san Agustín: "vestigium" y "signum"

En distintos momentos de su producción intelectual, Agustín se refirió al asunto de la música. En este artículo mostraremos que Agustín uso dos esquemas conceptuales distintos para describir el fenómeno de la música práctica en su relación con el mundo espiritual, el esquema de las Artes Liberales y el de la teoría del signo, y que en virtud de ello la música sería concebida de dos modos diferentes: como vestigium y como signum del mundo espiritual, respectivamente. Al final del artículo analizaremos la diferencia entre las dos concepciones considerando tres elementos: la naturaleza de la relación entre mundo material y espiritual, el contenido espiritual al que remite y la noción de belleza que implica.

Estudo empírico : motivação e aprendizagem nas aulas de formação musical e classe de conjunto coral : um estudo de caso comparativo

Relatório de Estágio apresentado à Escola Superior de Artes Aplicadas do Instituto Politécnico de Castelo Branco para cumprimento dos requisitos necessários à obtenção do grau de Mestre em Ensino da Música – Formação Musical e Música de Conjunto.

Multi-Prover and parallel repetition in non-classical interactive games

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.

Centor : concept d’interface de spatialisation sonore additive

Cette recherche porte un regard critique sur les interfaces de spatialisation sonore et positionne la composition de musique spatiale, un champ d’étude en musique, à l’avant plan d’une recherche en design. Il détaille l’approche de recherche qui est centrée sur le processus de composition de musique spatiale et les modèles mentaux de compositeurs électroacoustiques afin de livrer des recommandations de design pour le développement d’une interface de spatialisation musicale nommée Centor. Cette recherche montre qu’un processus de design mené à l’intersection du design d’interface, du design d’interaction et de la théorie musicale peut mener à une proposition pertinente et innovatrice pour chacun des domaines d’étude. Nous présentons la recherche et le développement du concept de spatialisation additive, une méthode de spatialisation sonore par patrons qui applique le vocabulaire spectromorphologique de Denis Smalley. C’est un concept d’outil de spatialisation pour le studio qui complémente les interfaces de composition actuelles et ouvre un nouveau champ de possibilités pour l’exploration spatiale en musique électroacoustique. La démarche de recherche présentée ici se veut une contribution au domaine du design d’interfaces musicales, spécifiquement les interfaces de spatialisation, mais propose aussi un processus de design pour la création d’interfaces numériques d’expression artistique.

The Informational Complexity of Learning from Examples

This thesis attempts to quantify the amount of information needed to learn certain tasks. The tasks chosen vary from learning functions in a Sobolev space using radial basis function networks to learning grammars in the principles and parameters framework of modern linguistic theory. These problems are analyzed from the perspective of computational learning theory and certain unifying perspectives emerge.

Symmetry breaking in the genetic code: Finite groups

We investigate the possibility of interpreting the degeneracy of the genetic code, i.e., the feature that different codons (base triplets) of DNA are transcribed into the same amino acid, as the result of a symmetry breaking process, in the context of finite groups. In the first part of this paper, we give the complete list of all codon representations (64-dimensional irreducible representations) of simple finite groups and their satellites (central extensions and extensions by outer automorphisms). In the second part, we analyze the branching rules for the codon representations found in the first part by computational methods, using a software package for computational group theory. The final result is a complete classification of the possible schemes, based on finite simple groups, that reproduce the multiplet structure of the genetic code. (C) 2010 Elsevier Ltd. All rights reserved.