Bugs in code continue to pose a fundamental problem for software reliability and cause expensive failures. The process of removing known bugs is termed debugging, which is a classic methodology commonly performed before code is deployed. Traditionally, debugging is tedious, often requiring much manual effort. A more recent technique that complements debugging is data structure repair, which handles bugs that make it to deployed systems and lead to erroneous behavior at runtime by modifying erroneous program states to recover from errors. While data structure repair presents a promising basis for dealing with bugs at runtime, it remains computationally expensive. Our thesis is that debugging and data structure repair can be integrated to provide the basis of an effective approach for removing bugs before code is deployed and handling them after it is deployed. We present a bi-directional integration where ideas at the basis of data structure repair assist in automating debugging and vice versa. Our key insight is two-fold: (1)a repair action performed to mutate an erroneous object field value to repair it can be abstracted into a program statement that performs that update correctly; and (2)repair actions that are performed repeatedly to fix the same error can be memoized and re-used. We design, develop, and evaluate two techniques that embody our insight. One, we present an automated debugging technique that leverages a systematic constraint-based data structure repair technique developed in previous work and provides suggestions on how to fix a faulty program. Two, we present repair abstractions that are based on the same central ideas as in our automated debugging technique and memoize how an erroneous state was repaired, which enables prioritizing and re-using repair actions when the same error occurs again. The focus of our work is programs that operate on structurally complex data, e.g., heap-allocated data structures that have complex structural integrity constraints, such as acyclicity. Checking such constraints plays a central role in the techniques that lay at the foundation of our work. These techniques require the user to provide the constraints, which poses a burden on the user. To facilitate the use of constraint-based techniques, we present a third technique to check constraint violations at runtime using graph spectra, which have been studied extensively by mathematicians to capture properties of graphs. We view the heap of an object-oriented program as an edge-labeled graph, which allows us to apply results from graph spectra theory. Experimental results show the effectiveness of using graph spectra as a basis of capturing structural properties of a class of commonly used data structures. / text

This paper was written as a bachelor thesis in mathematics. We study adjacency matrices and their eigenvalues to investigate what properties of the corresponding graphs can be determined by those eigenvalues, the spectrum of the graph. The question of which graphs are uniquely determined by their spectra is also covered. Later on we study some methods of finding examples of graphs with shared spectra, also referred to as cospectral graphs.

Η παρούσα εργασία ασχολείται με την ανάκτηση σχήματος. Πιο συγκεκριμένα επικεντρώνεται σε επίπεδα (δισδιάστατα) σχήματα τα οποία είναι μη άκαμπτα και έχουν υποστεί κάμψη ή μεταβάλλονται εξαιτίας της παρουσίας κάποιας άρθρωσης. Τέτοια εύκαμπτα σχήματα συναντάμε καθημερινά στη φύση όπως για παράδειγμα τους μικροοργανισμούς μέχρι και τον ίδιο τον άνθρωπο. Τα κριτήρια ομοιότητας μεταξύ των σχημάτων που χρησιμοποιούνται εδώ είναι Intrinsic. Τέτοια κριτήρια μπορεί κανείς να εξάγει δημιουργώντας ένα τελεστή διάχυσης. Οι τελεστές διάχυσης μπορούν να διατυπωθούν με πολλούς τρόπους. Στην παρούσα εργασία βασιζόμαστε στην πιθανολογική προσέγγιση δημιουργώντας ένα τελεστή (Μητρώο Markov) ενώ ταυτόχρονα λαμβάνουμε ένα τυχαίο περίπατο στα δεδομένα. Ο τελεστής αυτός επιπλέον έχει το πλεονέκτημα ότι μπορεί να προσεγγίσει τον τελεστή Laplace-Beltrami ασχέτως της πυκνότητας δειγματοληψίας των δεδομένων. Ορίζεται λοιπόν ως Απόσταση Διάχυσης η απόσταση δύο σημείων. Η απόσταση αυτή είναι μικρότερη όσο περισσότερα μονοπάτια συνδέουν τα δύο σημεία. Η φασματική ανάλυση του μητρώου αυτού μας επιτρέπει να αναπαραστήσουμε τα δεδομένα μας σε ένα νέο χώρο με σαφή μετρική απόσταση την Ευκλείδεια χρησιμοποιώντας τις ιδιοτιμές και τα ιδιοδιανύσματα που προκύπτουν. Επιπλέον η Ευκλείδεια απόσταση στο νέο χώρο ισούται με την απόσταση Διάχυσης στον αρχικό χώρο. Ο συνδυασμός των φασματικών ιδιοτήτων του μητρώου Διάχυσης με τις Markov διεργασίες οδηγεί σε μία ανάλυση των δεδομένων σε πολλές κλίμακες. Αυτό ισοδυναμεί με το να προχωρήσουμε τον τυχαίο περίπατο μπροστά. Από τις απεικονίσεις αυτές μπορούμε να εξάγουμε ιστογράμματα κατανομής αποστάσεων. Έτσι για κάθε σχήμα και για κάθε κλίμακα λαμβάνουμε ένα ιστόγραμμα κατανομής αποστάσεων. Συνεπώς δύο σχήματα μπορεί να βρίσκονται πολύ κοντά σε μία κλίμακα χρόνου ενώ να βρίσκονται πολύ μακριά σε μία άλλη κλίμακα. Συγκεκριμένα εδώ παραθέτουμε την άποψη η απόσταση των σχημάτων συνδέεται άμεσα με την κλίμακα- χρόνο. Μελετώνται οι ιδιότητες των μικρών, μεσαίων και μεγάλων κλιμάκων κυρίως ως προς τα γεωμετρικά χαρακτηριστικά που μπορούν να περιγράψουν και κατά συνέπεια την ικανότητα να εξάγουν αποδοτικούς περιγραφείς των σχημάτων. Η συνεισφορά της παρούσας Διπλωματικής Εργασίας είναι διπλή: A. Προτείνεται για πρώτη φορά μία νέα μέθοδος κατά την οποία αξιοποιούνται οι ιδιότητες των διαφορετικών κλιμάκων της διεργασίας Διάχυσης που αναφέραμε. Ονομάζουμε τη μέθοδο αυτή Weighted Multiscale Diffusion Distance -WMDD. B. Τα αποτελέσματα που παρουσιάζονται φέρνουν την μέθοδο αυτή στην κορυφή για τις συγκεκριμένες βάσεις σχημάτων (MPEG-7 και KIMIA 99). / This thesis focuses explicitly at shape retrieval applications. More precisely concentrates in planar shapes that are non-rigid, meaning that they might have been articulated or bended. These non-rigid shapes appear in humans’ life like for example bacteria and also the same the human body. The shape pair wise similarity criteria are intrinsic. Such similarity criteria one can take through a Diffusion Operator. Diffusion Operators can be defined in many ways. In this thesis we concern only in the probabilistic interpretation of Diffusion Operators. Thus by constructing a Diffusion Operator we also construct a random Walk on data. This operator converges to the Laplace-Beltrami even if the sampling density of the data is not uniform. Through this framework the Diffusion Distance between two points is defined. This distance gets smaller as much more paths are connecting two points. Spectral decomposition if this diffusion kernel allows us to map, re-represent our data using the eigenvectors and the eigenvalues in a new space with the property of embedding with an explicit metric. These maps are called Diffusion Maps and have the property that diffusion distance in the initial space equals the Euclidean distance in the embedding space. A combination of spectral properties of a Markov matrix with Markov Processes leads to a multiscale analysis. This corresponds to running the random walk forward. From these embeddings we can extract histograms of distributions of distances. Thus for every shape and every scale we have one histogram. Therefore two shapes may be close in one scale but not in another one. The contribution of this Thesis is twofold: A. For first time a new method where the properties of different scales as studied in order to take the advantage of the most discriminative times/ steps of the diffusion process that we described above. We called this method Weighted Multiscale Diffusion Distance- WMDD. B. The results presented here bring our method to the state of the art for the MPEG- and KIMIA 99 databases.