Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for subject:(persistent data structures). Showing records 1 – 2 of 2 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Maria, Clément. Algorithmes et structures de données en topologie algorithmique : Algorithms and data structures in computational topology.

Degree: Docteur es, Informatique, 2014, Nice

La théorie de l'homologie généralise en dimensions supérieures la notion de connectivité dans les graphes. Étant donné un domaine, décrit par un complexe simplicial, elle définit une famille de groupes qui capturent le nombre de composantes connexes, le nombre de trous, le nombre de cavités et le nombre de motifs équivalents en dimensions supérieures. En pratique, l'homologie permet d'analyser des systèmes de données complexes, interprétés comme des nuages de points dans des espaces métriques. La théorie de l'homologie persistante introduit une notion robuste d'homologie pour l'inférence topologique. Son champ d'application est vaste, et comprend notamment la description d'espaces des configurations de systèmes dynamiques complexes, la classification de formes soumises à des déformations et l'apprentissage en imagerie médicale. Dans cette thèse, nous étudions les ramifications algorithmiques de l'homologie persistante. En premier lieu, nous introduisons l'arbre des simplexes, une structure de données efficace pour construire et manipuler des complexes simpliciaux de grandes dimensions. Nous présentons ensuite une implémentation rapide de l'algorithme de cohomologie persistante à l'aide d'une matrice d'annotations compressée. Nous raffinons également l'inférence de topologie en décrivant une notion de torsion en homologie persistante, et nous introduisons la méthode de reconstruction modulaire pour son calcul. Enfin, nous présentons un algorithme de calcul de l'homologie persistante zigzag, qui est une généralisation algébrique de la persistance. Pour cet algorithme, nous introduisons de nouveaux théorèmes de transformations locales en théorie des représentations de carquois, appelés principes du diamant. Ces algorithmes sont tous implémentés dans la librairie de calcul Gudhi.

The theory of homology generalizes the notion of connectivity in graphs to higher dimensions. It defines a family of groups on a domain, described discretely by a simplicial complex that captures the connected components, the holes, the cavities and higher-dimensional equivalents. In practice, the generality and flexibility of homology allows the analysis of complex data, interpreted as point clouds in metric spaces. The theory of persistent homology introduces a robust notion of homology for topology inference. Its applications are various and range from the description of high dimensional configuration spaces of complex dynamical systems, classification of shapes under deformations and learning in medical imaging. In this thesis, we explore the algorithmic ramifications of persistent homology. We first introduce the simplex tree, an efficient data structure to construct and maintain high dimensional simplicial complexes. We then present a fast implementation of persistent cohomology via the compressed annotation matrix data structure. We also refine the computation of persistence by describing ideas of homological torsion in this framework, and introduce the modular reconstruction method for computation. Finally, we present an algorithm to…

Advisors/Committee Members: Boissonnat, Jean-Daniel (thesis director).

Subjects/Keywords: Algorithmes; Structures de données; Complexes simpliciaux; Homologie persistante; Algorithms; Data structures; Simplicial complexes; Persistent homology

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Maria, C. (2014). Algorithmes et structures de données en topologie algorithmique : Algorithms and data structures in computational topology. (Doctoral Dissertation). Nice. Retrieved from http://www.theses.fr/2014NICE4081

Chicago Manual of Style (16th Edition):

Maria, Clément. “Algorithmes et structures de données en topologie algorithmique : Algorithms and data structures in computational topology.” 2014. Doctoral Dissertation, Nice. Accessed January 28, 2020. http://www.theses.fr/2014NICE4081.

MLA Handbook (7th Edition):

Maria, Clément. “Algorithmes et structures de données en topologie algorithmique : Algorithms and data structures in computational topology.” 2014. Web. 28 Jan 2020.

Vancouver:

Maria C. Algorithmes et structures de données en topologie algorithmique : Algorithms and data structures in computational topology. [Internet] [Doctoral dissertation]. Nice; 2014. [cited 2020 Jan 28]. Available from: http://www.theses.fr/2014NICE4081.

Council of Science Editors:

Maria C. Algorithmes et structures de données en topologie algorithmique : Algorithms and data structures in computational topology. [Doctoral Dissertation]. Nice; 2014. Available from: http://www.theses.fr/2014NICE4081


University of Rochester

2. Raman, Rajeev. Eliminating Amortization: On Data Structures with Guaranteed Response Time.

Degree: PhD, 2004, University of Rochester

An efficient amortized data structure is one that ensures that the average time per operation spent on processing any sequence of operations is small. Amortized data structures typically have very non-uniform response times, i.e., individual operations can be occasionally and unpredictably slow, although the average time over the sequence is kept small by completing most of the other operations quickly. This makes amortized data structures unsuitable in many important contexts, such as real-time systems, parallel programs, persistent data structures and interactive software. On the other hand, an efficient (single-operation) worst-case data structure guarantees that every operation will be processed quickly. The construction of worst-case data structures from amortized ones is a fundamental problem which is also of pragmatic interest. Progress has been slow so far, both because the techniques used were of a limited nature and because the resulting data structures had much larger hidden constant factors. I try to address both these issues in this thesis. I consider several inter-related dynamic data structuring problems for which only efficient amortized solutions were known and obtain new worst-case algorithms for them using a unified framework, that of RpebbleS games. These two-player combinatorial games are formulated so that winning strategies translate fairly readily into worst-case algorithms for data structures. I analyze these games and obtain tight bounds on the payoffs to the players. These results are then made to yield new worst-case algorithms for finger search trees, partially and fully persistent linked data structures, fully persistent union-find, dynamic fractional cascading, range trees and segment trees. With my new algorithms I often get worst-case running times that match the old amortized bounds, in a few cases settling for considerable improvements over the best existing worst-case algorithm. Several of the new algorithms are comparable in simplicity to the amortized algorithms they are based on. The data structures considered in this thesis have numerous uses. Persistent data structures support efficient access to old versions of the data structure. They have been used in geometric algorithms, implementations of object oriented languages, optimistic discrete event simulation and tree pattern matching. Fractional cascading, segment trees and range trees are used extensively in geometric algorithms and range trees in databases as well. In addition, pebble games appear to have applications unrelated to data structuring and may also be of independent interest, as they are similar in form to "vector balancing" and "chip firing" games studied by combinatorial mathematicians.

Subjects/Keywords: real-time computation; amortized analysis; computational geometry; data structures; disjoint set union-find; persistent data structures; randomized algorithms; combinatorial games

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Raman, R. (2004). Eliminating Amortization: On Data Structures with Guaranteed Response Time. (Doctoral Dissertation). University of Rochester. Retrieved from http://hdl.handle.net/1802/816

Chicago Manual of Style (16th Edition):

Raman, Rajeev. “Eliminating Amortization: On Data Structures with Guaranteed Response Time.” 2004. Doctoral Dissertation, University of Rochester. Accessed January 28, 2020. http://hdl.handle.net/1802/816.

MLA Handbook (7th Edition):

Raman, Rajeev. “Eliminating Amortization: On Data Structures with Guaranteed Response Time.” 2004. Web. 28 Jan 2020.

Vancouver:

Raman R. Eliminating Amortization: On Data Structures with Guaranteed Response Time. [Internet] [Doctoral dissertation]. University of Rochester; 2004. [cited 2020 Jan 28]. Available from: http://hdl.handle.net/1802/816.

Council of Science Editors:

Raman R. Eliminating Amortization: On Data Structures with Guaranteed Response Time. [Doctoral Dissertation]. University of Rochester; 2004. Available from: http://hdl.handle.net/1802/816

.