Search

International audience; We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general undirected graphs. Our approach is based on assigning probabilities to edges, randomly selecting an edge to be in a perfect matching, and discarding edges that cannot be put in a perfect matching. The probabilities are chosen according to the entries in the doubly stochastically scaled version of the adjacency matrix of the given graph. The experimental analysis on random and real-life graphs shows improvements in the approximation over previous and similar methods from the literature.

Influence maximization (IM) is the problem of finding a seed vertex set that maximizes the expected number of vertices influenced under a given diffusion model. Due to the NP-Hardness of finding an optimal seed set, approximation algorithms are frequently used for IM. In this work, we describe a fast, error-adaptive approach that leverages Count-Distinct sketches and hash-based fused sampling. To estimate the number of influenced vertices throughout a diffusion, we use per-vertex Flajolet-Martin sketches where each sketch corresponds to a sampled subgraph. To efficiently simulate the diffusions, the reach-set cardinalities of a single vertex are stored in memory in a consecutive fashion. This allows the proposed algorithm to estimate the number of influenced vertices in a single step for simulations at once. For a faster IM kernel, we rebuild the sketches in parallel only after observing estimation errors above a given threshold. Our experimental results show that the proposed algorithm yields high-quality seed sets while being up to 119x faster than a state-of-the-art approximation algorithm. In addition, it is up to 62x faster than a sketch-based approach while producing seed sets with 3%-12% better influence scores, Comment: 12 pages. Sent to IEEE Transactions on Knowledge and Data Engineering as a regular paper

For dynamic and continuous data analysis, conventional OLTP systems are slow in performance. Today's cutting-edge high-performance computing hardware, such as GPUs, has been used as accelerators for data analysis tasks, which traditionally leverage CPUs on classical database management systems (DBMS). When CPUs and GPUs are used together, the architectural heterogeneity, that is, leveraging hardware with different performance characteristics jointly, creates complex problems that need careful treatment for performance optimization. Load distribution and balancing are crucial problems for DBMSs working on heterogeneous architectures. In this work, focusing on a hybrid, CPU-GPU database management system to process users' queries, we propose heuristical and machine-learning-based (ML-based) load distribution and balancing models. In more detail, we employ multiple linear regression (MLR), random forest (RF), and Adaboost (Ada) models to dynamically decide the processing unit for each incoming query based on the response time predictions on both CPU and GPU. The ML-based models outperformed the other algorithms, as well as the CPU and GPU-only running modes with up to 27%, 29%, and 40%, respectively, in overall performance (response time) while answering intense real-life working scenarios. Finally, we propose to use a hybrid load-balancing model that would be more efficient than the models we tested in this work.

There is a plethora of data structures, algorithms, and frameworks dealing with major data-stream problems like estimating the frequency of items, answering set membership, association and multiplicity queries, and several other statistics that can be extracted from voluminous data streams. In this survey, we are focusing on exploring randomized data structures called Bloom Filters. This data structure answers whether an item exists or not in a data stream with a false positive probability fpp. In this survey, many variants of the Bloom filter will be covered by showing the strengths of each structure and its drawbacks i.e. some Bloom filters deal with insertion and deletions and others don't, some variants use the memory efficiently but increase the fpp where others pay the trade-off in the reversed way. Furthermore, in each Bloom filter structure, the false positive probability will be highlighted alongside the most important technical details showing the improvement it is presenting, while the main aim of this work is to provide an overall comparison between the variants of the Bloom filter structure according to the application domain that it fits in.

We consider Karp–Sipser, a well-known matching heuristic in the context of data reduction for the maximum cardinality matching problem. We describe an efficient implementation as well as modifications to reduce its time complexity in worst-case instances, both in theory and in practical cases. We compare experimentally against its widely used simpler variant and show cases for which the full algorithm yields better performance.

The problem of finding a maximum cardinality matching in a d-partite d-uniform hypergraph is an important problem in combinatorial optimization and has beentheoretically analyzed by several researchers. In this work, we first devise heuristics for this problem by generalizing the existing cheap graph matching heuristics. Then, we propose a novel heuristic based on tensor scaling to extend the matching via judicious hyperedge selections. Experiments on random, synthetic and real-life hypergraphs show that this new heuristic is highly practical and superior to the others on finding a matching with largecardinality.; Le problème consistant à trouver un couplage maximal dans un hypergraphe uniforme ayant d parts est un problème important en optimisation combinatoire. Dans ce travail, nous concevons d’abord des heuristiques pour ce problème en généralisant les heuristiques de couplage dans des graphes. Ensuite, nous proposons une nouvelle heuristique basée sur des méthodes de mise à l’échelle de tenseur pour étendre le couplage via des sélections judicieuses d’hyperarêtes. Des expériences sur des hypergraphes aléatoires, synthétiques et réels montrent que cette nouvelle heuristique est simple à mettre en pratique et supérieure aux autres pour trouver des couplages de grande cardinalité.

We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general graphs. Our approach is based on assigning probabilities to edges.; Nous étudions des méthodes randomiséese efficaces pour approximer le nombre de couplages parfaits dans des graphes bipartis et des graphes généraux. Notre approche se base sur l'assignation de probabilités aux arêtes.

We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general graphs. Our approach is based on assigning probabilities to edges.; Nous étudions des méthodes randomiséese efficaces pour approximer le nombre de couplages parfaits dans des graphes bipartis et des graphes généraux. Notre approche se base sur l'assignation de probabilités aux arêtes.

We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general graphs. Our approach is based on assigning probabilities to edges.

We investigate the problem of partitioning the vertices of a directed acyclic graph into a given number of parts. The objective function is to minimize the number or the total weight of the edges having end points in different parts, which is also known as edge cut. The standard load balancing constraint of having an equitable partition of the vertices among the parts should be met.Furthermore, the partition is required to be {\em acyclic}, i.e., the inter-part edges between the vertices from different parts should preserve an acyclic dependency structure among the parts. In this work, we adopt the multilevel approach with coarsening, initial partitioning, and refinementphases for acyclic partitioning of directed acyclic graphs. We focus on two-way partitioning (sometimes called bisection), as this scheme can be used in a recursive way for multi-way partitioning. To ensure the acyclicity of the partition at all times, we propose novel and efficient coarsening andrefinement heuristics. The quality of the computed acyclic partitions is assessed by computing the edge cut. We also propose effective ways to use the standard undirected graph partitioning methods in our multilevel scheme. We perform a large set of experiments on a dataset consisting of (i)~graphs coming from an application and (ii)~some others corresponding to matrices from a public collection. We report improvements, on average, around 59\% compared to the current state of the art.; Nous étudions le problème du partitionnement des sommets d’un graphe acyclique dirigé en un nombre donné de parties. La fonction objectiveest de minimiser le poids total des arêtes ayant des extrémités dans différentes parties, qui sont également nommées arêtes coupées. La contrainted’équilibrage de charge standard d’avoir une partition équitable des sommets entre les parties doit être respectée. En outre, la partition doit être acyclique, c’est-à-dire, les arêtes coupées doivent préserver une structure de dépendance acyclique entre les parties. Dans ce travail, nous adoptons une approche multiniveaux avec des étapes de contraction, partitionnement initial et raffinement pour le partitionnement acyclique des graphes acycliques dirigés. Nous nous concentrons sur la bissection, car ce schéma peut être utilisé d’une manière récursive pour le partitionnement multi-voies. Pour assurer l’acyclicité du partitionnement à tout moment, nous proposons des méthodes de contraction etde raffinement. La qualité des partitions acycliques calculées est évaluée en calculant la somme des poids des arêtes coupées. Nous proposons également des moyens efficaces afin d’utiliser des méthodes standard de partitionnement de graphes non orientés dans notre schéma multi-niveaux. Nous effectuons un grand nombre d’expériences sur un ensemble de données constitué de (i) graphes provenant d’une application, et (ii) d’autres graphes correspondant à des matrices d’une collection publique. Nous rapportons des améliorations par rapport aux méthodes existantes d’environ 59 % en moyenne.

International audience; The well-known Birkhoff-von Neumann (BvN) decomposition expresses a doubly stochastic matrix as a convex combination of a number of permutation matrices. For a given doubly stochastic matrix, there are many BvN decompositions, and finding the one with the minimum number of permutation matrices is NP-hard. There are heuristics to obtain BvN decompositions for a given doubly stochastic matrix. A family of heuristics are based on the original proof of Birkhoff and proceed step by step by subtracting a scalar multiple of a permutation matrix at each step from the current matrix, starting from the given matrix. At every step, the subtracted matrix contains nonzeros at the positions of some nonzero entries of the current matrix and annihilates at least one entry, while keeping the current matrix nonnegative. Our first result, which supports a claim of Brualdi [Canad. Math. Bull. 25 (1982), pp. 191–199], shows that this family of heuristics can miss optimal decompositions. We also investigate the performance of two heuristics from this family theoretically.; La décomposition de Birkhoff-von Neumann (BvN) exprime une matrice doublement stochastique comme une combinaison convexe d’un nombre de matrices de permutation. Pour une matrice doublement stochastique donnée, il existe de nombreuses décompositions BvN, et trouver celle avec le nombre minimum de matrices de permutation est NP-Hard. Il existe des heuristiques pour obtenir des décompositions BvN. Une famille d’heuristiques est basée sur la preuve originale de Birkhoff et se déroule étape par étape en soustrayant un multiple scalaire d’une matrice de permutation à chaque étape de la matrice actuelle, à partir de la matrice donnée. À chaque étape, la matrice soustraite contient nonzeros aux positions de certaines entrées non nulles de la matrice actuelle et anéantit au moins une entrée tout en maintenant la matrice actuelle non négative. Notre premier résultat, qui soutient une affirmation de Brualdi [Canad. Math. Bull. 25 (1982), pp. 191–199], montre que cette famille d’heuristiques peut manquer des décompositions optimales. Nous étudions également la performance théorique de deux heuristiques de cette famille.

Sparse-matrix vector multiplication (SpMV) is one of the widely used and extensively studied kernels in today’s scientific computing and high-performance computing domains. The efficiency and scalability of this kernel is extensively investigated on single-core, multi-core, many-core processors and accelerators, and on distributed memory. In general, a good mapping of an application’s tasks to the processing units in a distributed environment is important since communication among these tasks is the main bottleneck on scalability. A fundamental approach to solve this problem is modeling the application via a graph/hypergraph and partitioning it. For SpMV, several graph/hypergraph models have been proposed. These approaches consider the problem as a balanced partitioning problem where the vertices (tasks) are partitioned (assigned) to the parts (processors) in a way that the total vertex weight (processor load) is balanced and the total communication incurred among the processors is minimized. The partitioning problem is NP-Hard and all the existing studies and tools use heuristics to solve the problem. For graphs, the literature on optimal partitioning contains a number of notable studies; however for hypergraphs, very little work has been done. Unfortunately, it has been shown that unlike graphs, hypergraphs can exactly model the total communication for SpMV. Recently, Pelt and Bisseling proposed a novel, purely combinatorial branch-and-bound-based approach for the sparse-matrix bipartitioning problem which can tackle relatively larger hypergraphs that were impossible to optimally partition into two by using previous methods. This work can be considered as an extension to their approach with two ideas. We propose to use; 1) matrix ordering techniques to use more information in the earlier branches of the tree, and 2) a machine learning approach to choose the best ordering based on matrix features. As our experiments on various matrices will show, these enhancements make the optimal bipartitioning process much faster.

Modular exponentiation lies at the core of many cryptographic schemes and its efficient implementation is a must for a reasonable practical performance. For various applications, multiple exponentiations with different bases and exponents need to be performed and multiplied. Although this multiexponentiation operation can be implemented by individually exponentiating the bases to their corresponding exponents, as discussed in the literature, a significant performance boost can be obtained when the operation is considered as a whole. However, performing separate exponentiations is pleasingly parallelizable but the latter approach requires a careful implementation on a multi-core processor. In this work, we propose a parallel algorithm and implementation based on an existing multi-exponentiation algorithm with precomputation. The experimental results show that the proposed implementation is significantly faster than the existing parallel multi-exponentiation schemes in the literature.

We propose HAMSI (Hessian Approximated Multiple Subsets Iteration), which is a provably convergent, second order incremental algorithm for solving large-scale partially separable optimization problems. The algorithm is based on a local quadratic approximation, and hence, allows incorporating curvature information to speed-up the convergence. HAMSI is inherently parallel and it scales nicely with the number of processors. Combined with techniques for effectively utilizing modern parallel computer architectures, we illustrate that the proposed method converges more rapidly than a parallel stochastic gradient descent when both methods are used to solve large-scale matrix factorization problems. This performance gain comes only at the expense of using memory that scales linearly with the total size of the optimization variables. We conclude that HAMSI may be considered as a viable alternative in many large scale problems, where first order methods based on variants of stochastic gradient descent are applicable., Comment: The software is available at https://github.com/spartensor/hamsi-mf

Matrix factorization is a common task underlying several machine learning applications such as recommender systems, topic modeling, or compressed sensing. Given a large and possibly sparse matrix A, we seek two smaller matrices W and H such that their product is as close to A as possible. The objective is minimizing the sum of square errors in the approximation. Typically such problems involve hundreds of thousands of unknowns, so an optimizer must be exceptionally efficient. In this study, a new algorithm, Preconditioned Model Building is adapted to factorize matrices composed of movie ratings in the MovieLens data sets with 1, 10, and 20 million entries. We present experiments that compare the sequential MATLAB implementation of the PMB algorithm with other algorithms in the minFunc package. We also employ a lock-free sparse matrix factorization algorithm and provide a scalable shared-memory parallel implementation. We show that (a) the optimization performance of the PMB algorithm is comparable to the best algorithms in common use, and (b) the computational performance can be significantly increased with parallelization

Computing a shortest synchronizing word of an automaton is an NP–hard problem. Therefore, heuristics are used to compute short synchronizing words. SynchroP is among the best heuristics in the literature in terms of word lengths. The heuristic and its variants such as SynchroPL have been frequently used as a baseline to judge the quality of the words generated by the new heuristics. Although, its quality is good, the heuristics are significantly slow especially compared to much cheaper heuristics such as Greedy and Cycle. This makes them in- feasible for large-scale automatons. In this paper, we show how one can improve the time performance of SynchroP and its variants by avoiding unnecessary computations which makes these heuristics more competitive than they already are. Our experimental results show that for 2500 states, SynchroP can be made 70–160× faster, via the proposed optimizations. In particular, for 2500 states and 32 letters, the SynchroP execution reduces to 66 seconds from 4745 seconds. Furthermore, the suggested optimizations become more effective as the number of states in the automata increase.

In parallel computing, a valid graph coloring yields a lock-free processing of the colored tasks, data points, etc., without expensive synchronization mechanisms. However, coloring is not free and the overhead can be significant. In particular, for the bipartite-graph partial coloring (BGPC) and distance-2 graph coloring (D2GC) problems, which have various use-cases within the scientific computing and numerical optimization domains, the coloring overhead can be in the order of minutes with a single thread for many real-life graphs. In this work, we propose parallel algorithms for bipartite-graph partial coloring on shared-memory architectures. Compared to the existing shared-memory BGPC algorithms, the proposed ones employ greedier and more optimistic techniques that yield a better parallel coloring performance. In particular, on 16 cores, the proposed algorithms perform more than 4x faster than their counterparts in the ColPack library which is, to the best of our knowledge, the only publicly-available coloring library for multicore architectures. In addition to BGPC, the proposed techniques are employed to devise parallel distance-2 graph coloring algorithms and similar performance improvements have been observed. Finally, we propose two costless balancing heuristics for BGPC that can reduce the skewness and imbalance on the cardinality of color sets (almost) for free. The heuristics can also be used for the D2GC problem and in general, they will probably yield a better color-based parallelization performance especially on many-core architectures., Comment: 11 pages

For commitments on secrets, statistical hiding is a must when we are dealing with a long-term secret or when the secret domain is small enough for a brute-force attack by a powerful adversary. Unfortunately, all the Chinese Remainder Theorem-based verifiable secret sharing schemes in the literature are either insecure or suffer from the vulnerability of computationally hiding commitments. To the best of our knowledge, there exist five such studies where two of them were already proven to be insecure. In this work, we first show that two of the remaining schemes are also insecure, that is, the schemes reveal information on the secret even when the adversary is passive. In addition, the remaining one is only secure against a computationally bounded adversary which can be a problem for secret sharing schemes requiring long-term secret obscurity or using small secret domain. We propose a modification for the latter scheme and prove that the modified scheme is a secure verifiable secret sharing scheme against an unbounded adversary. Lastly, as an application, we show how to use the new scheme for joint random secret sharing and analyze the practicality and efficiency of the proposed schemes. Copyright (C) 2016 John Wiley & Sons, Ltd.

A recent work of Harn and Fuyou presents the first multilevel (disjunctive) threshold secret sharing scheme based on the Chinese Remainder Theorem. In this work, we first show that the proposed method is not secure and also fails to work with a certain natural setting of the threshold values on compartments. We then propose a secure scheme that works for all threshold settings. In this scheme, we employ a refined version of Asmuth-Bloom secret sharing with a special and generic Asmuth-Bloom sequence called the {\it anchor sequence}. Based on this idea, we also propose the first multilevel conjunctive threshold secret sharing scheme based on the Chinese Remainder Theorem. Lastly, we discuss how the proposed schemes can be used for multilevel threshold function sharing by employing it in a threshold RSA cryptosystem as an example.

We investigate hypergraph partitioning-based methods for efficient parallelization of communicating tasks. A good partitioning method should divide the load among the processors as evenly as possible and minimize the inter-processor communication overhead. The total communication volume is the most popular communication overhead metric which is reduced by the existing state-of-the-art hypergraph partitioners. However, other metrics such as the total number of messages, the maximum amount of data transferred by a processor, or a combination of them are equally, if not more, important. Existing hypergraph-based solutions use a two phase approach to minimize such metrics where in each phase, they minimize a different metric, sometimes at the expense of others. We propose a one-phase approach where all the communication cost metrics can be effectively minimized in a multi-objective setting and reductions can be achieved for all metrics together. For an accurate modeling of the maximum volume and the number of messages sent and received by a processor, we propose the use of directed hypergraphs. The directions on hyperedges necessitate revisiting the standard partitioning heuristics. We do so and propose a multi-objective, multi-level hypergraph partitioner called UMPa. The partitioner takes various prioritized communication metrics into account, and optimizes all of them together in the same phase. Compared to the state-of-the-art methods which only minimize the total communication volume, we show on a large number of problem instances that UMPa produces better partitions in terms of several communication metrics.

Networks are commonly used to model traffic patterns, social interactions, or web pages. The vertices in a network do not possess the same characteristics: some vertices are naturally more connected and some vertices can be more important. Closeness centrality (CC) is a global metric that quantifies how important is a given vertex in the network. When the network is dynamic and keeps changing, the relative importance of the vertices also changes. The best known algorithm to compute the CC scores makes it impractical to recompute them from scratch after each modification. In this paper, we propose Streamer, a distributed memory framework for incrementally maintaining the closeness centrality scores of a network upon changes. It leverages pipelined, replicated parallelism, and SpMM-based BFSs, and it takes NUMA effects into account. It makes maintaining the Closeness Centrality values of real-life networks with millions of interactions significantly faster and obtains almost linear speedups on a 64 nodes 8 threads/node cluster.

Date of Conference: 9-12 Sept. 2014 Conference name: 43rd International Conference on Parallel Processing Workshops, 2014 The 1st International Workshop on High Performance Computing for Big Data (HPC4BD) is held on September 10, 2014 in concordance with 43rd International Conference on Parallel Processing (ICPP-2014). The workshop aimed to bring high performance computing (HPC) experts and experts from various application domains together to discuss their Big Data problems. There were four works accepted to be presented in this year's workshop. This foreword presents a summary of the them. © 2014 IEEE.

Softwareklone in einem System erfordern eine hohe Vorsicht im Entwicklungszyklus eines Softwareprojekts. Viele Forscher sind der Ansicht, dass Klone vor allem inkonsistente Klone die Ursache diverser Fehler in Softwaresystemen sind, die sich unbemerkt einschleichen und nicht nachverfolgt werden können. Vor allem die Auswirkungen der inkonsistenten Klone liegen im Interesse vieler Forschungsarbeiten. Jedoch liegen die Forschungsergebnisse der Studien weit auseinander. Im Rahmen dieser Diplomarbeit werden die Auswirkungen der inkonsistenten Klone in einem Softwaresystem analysiert. Des Weiteren analysiert diese Arbeit auf empirischer Basis im Rahmen eines Studiendesigns den Zusammenhang der Inkonsistenten und Fehlern in Softwaresystemen. Die Studie wurde auf drei Industriesystemen durchgeführt und ergab als Resultat, dass Entwickler über fast alle Klonstellen einer Klonklasse informiert sind und diese bei Bedarf zu 58%-92% zeitgleich modifizieren. Es sind lediglich 3%-33% der inkonsistenten Klonklassen fehlerbehaftet und stellen somit eine geringe Gefahr für die Softwareentwicklung. Die umfangreiche Analyse gab den Beschluss, dass die Inkonsistenzen im Vergleich zu exakten Klonen mindestens weniger als die Hälfte einen Fehler verursachen. Weiterhin beweist die Studie, dass durch das Klonen aus Bibliotheken, Klone eine erheblich geringe Anzahl an Fehler darstellen und nach bis zu vier Jahren Klonzeit keinen einzigen Fehler in der gesamten Revisionshistorie verursacht haben. Die Ergebnisse dieser Arbeit beweisen, dass Entwickler bewusst Klonen und dass es durch das bewusste Klonen keinen erhöhten Zusammenhang zwischen inkonsistente Klone und Fehler gibt.

Graph/hypergraph partitioning models and methods have been successfully used to minimize the communication requirements among processors in several parallel computing applications. Parallel sparse matrix-vector multiplication~(SpMxV) is one of the representative applications that renders these models and methods indispensable in many scientific computing contexts. We investigate the interplay of several partitioning metrics and execution times of SpMxV implementations in three libraries: Trilinos, PETSc, and an in-house one. We design and carry out experiments with up to 512 processors and investigate the results with regression analysis. Our experiments show that the partitioning metrics, although not an exact measure of communication cost, influence the performance greatly in a distributed memory setting. The regression analyses demonstrate which metric is the most influential for the execution time of the three libraries used.

Analyzing networks requires complex algorithms to extract meaningful information. Centrality metrics have shown to be correlated with the importance and loads of the nodes in network traffic. Here, we are interested in the problem of centrality-based network management. The problem has many applications such as verifying the robustness of the networks and controlling or improving the entity dissemination. It can be defined as finding a small set of topological network modifications which yield a desired closeness centrality configuration. As a fundamental building block to tackle that problem, we propose incremental algorithms which efficiently update the closeness centrality values upon changes in network topology, i.e., edge insertions and deletions. Our algorithms are proven to be efficient on many real-life networks, especially on small-world networks, which have a small diameter and a spike-shaped shortest distance distribution. In addition to closeness centrality, they can also be a great arsenal for the shortest-path-based management and analysis of the networks. We experimentally validate the efficiency of our algorithms on large networks and show that they update the closeness centrality values of the temporal DBLP-coauthorship network of 1.2 million users 460 times faster than it would take to compute them from scratch. To the best of our knowledge, this is the first work which can yield practical large-scale network management based on closeness centrality values.

Intel Xeon Phi is a recently released high-performance coprocessor which features 61 cores each supporting 4 hardware threads with 512-bit wide SIMD registers achieving a peak theoretical performance of 1Tflop/s in double precision. Many scientific applications involve operations on large sparse matrices such as linear solvers, eigensolver, and graph mining algorithms. The core of most of these applications involves the multiplication of a large, sparse matrix with a dense vector (SpMV). In this paper, we investigate the performance of the Xeon Phi coprocessor for SpMV. We first provide a comprehensive introduction to this new architecture and analyze its peak performance with a number of micro benchmarks. Although the design of a Xeon Phi core is not much different than those of the cores in modern processors, its large number of cores and hyperthreading capability allow many application to saturate the available memory bandwidth, which is not the case for many cutting-edge processors. Yet, our performance studies show that it is the memory latency not the bandwidth which creates a bottleneck for SpMV on this architecture. Finally, our experiments show that Xeon Phi's sparse kernel performance is very promising and even better than that of cutting-edge general purpose processors and GPUs.

We investigate the push-relabel algorithm for solving the problem of finding a maximum cardinality matching in a bipartite graph in the context of the maximum transversal problem. We describe in detail an optimized yet easy-to-implement version of the algorithm and fine-tune its parameters. We also introduce new performance-enhancing techniques. On a wide range of real-world instances, we compare the push-relabel algorithm with state-of-the-art augmenting path-based algorithms and the recently proposed pseudoflow approach. We conclude that a carefully tuned push-relabel algorithm is competitive with all known augmenting path-based algorithms, and superior to the pseudoflow-based ones.; Nous étudions le problème de couplage maximum dans des graphes bipartis. Nous décrivons en détail une version optimisée de l'algorithme en ajustant ses paramètres. L'algorithme est facile à mettre en œuvre. Nous introduisons également de nouvelles techniques pour améliorer la performance de l'algorithme. Sur un large éventail de cas du monde réel, nous comparons l'algorithme Push-Relabel avec des algorithmes basés sur les concepts de chemins augmentants et de pseudoflot récemment proposés. Nous concluons qu'un algorithme de type Push-Relabel soigneusement réglé est en concurrence avec tous les algorithmes connus de type chemins augmentants, et supérieur à ceux de type pseudoflot.

Who is more important in a network? Who controls the flow between the nodes or whose contribution is significant for connections? Centrality metrics play an important role while answering these questions. The betweenness metric is useful for network analysis and implemented in various tools. Since it is one of the most computationally expensive kernels in graph mining, several techniques have been proposed for fast computation of betweenness centrality. In this work, we propose and investigate techniques which compress a network and shatter it into pieces so that the rest of the computation can be handled independently for each piece. Although we designed and tuned the shattering process for betweenness, it can be adapted for other centrality metrics in a straightforward manner. Experimental results show that the proposed techniques can be a great arsenal to reduce the centrality computation time for various types of networks.

The literature search has always been an important part of an academic research. It greatly helps to improve the quality of the research process and output, and increase the efficiency of the researchers in terms of their novel contribution to science. As the number of published papers increases every year, a manual search becomes more exhaustive even with the help of today's search engines since they are not specialized for this task. In academics, two relevant papers do not always have to share keywords, cite one another, or even be in the same field. Although a well-known paper is usually an easy pray in such a hunt, relevant papers using a different terminology, especially recent ones, are not obvious to the eye. In this work, we propose paper recommendation algorithms by using the citation information among papers. The proposed algorithms are direction aware in the sense that they can be tuned to find either recent or traditional papers. The algorithms require a set of papers as input and recommend a set of related ones. If the user wants to give negative or positive feedback on the suggested paper set, the recommendation is refined. The search process can be easily guided in that sense by relevance feedback. We show that this slight guidance helps the user to reach a desired paper in a more efficient way. We adapt our models and algorithms also for the venue and reviewer recommendation tasks. Accuracy of the models and algorithms is thoroughly evaluated by comparison with multiple baselines and algorithms from the literature in terms of several objectives specific to citation, venue, and reviewer recommendation tasks. All of these algorithms are implemented within a publicly available web-service framework (http://theadvisor.osu.edu/) which currently uses the data from DBLP and CiteSeer to construct the proposed citation graph., Comment: 10 pages, 8 figures, 3 tables

Literature search is arguably one of the most important phases of the academic and non-academic research. The increase in the number of published papers each year makes manual search inefficient and furthermore insufficient. Hence, automatized methods such as search engines have been of interest in the last thirty years. Unfortunately, these traditional engines use keyword-based approaches to solve the search problem, but these approaches are prone to ambiguity and synonymy. On the other hand, bibliographic search techniques based only on the citation information are not prone to these problems since they do not consider textual similarity. For many particular research areas and topics, the amount of knowledge to humankind is immense, and obtaining the desired information is as hard as looking for a needle in a haystack. Furthermore, sometimes, what we are looking for is a set of documents where each one is different than the others, but at the same time, as a whole we want them to cover all the important parts of the literature relevant to our search. This paper targets the problem of result diversification in citation-based bibliographic search. It surveys a set of techniques which aim to find a set of papers with satisfactory quality and diversity. We enhance these algorithms with a direction-awareness functionality to allow the users to reach either old, well-cited, well-known research papers or recent, less-known ones. We also propose a set of novel techniques for a better diversification of the results. All the techniques considered are compared by performing a rigorous experimentation. The results show that some of the proposed techniques are very successful in practice while performing a search in a bibliographic database., 19 pages, manuscript under review

The literature search has always been an important part of an academic research. It greatly helps to improve the quality of the research process and output, and increase the efficiency of the researchers in terms of their novel contribution to science. As the number of published papers increases every year, a manual search becomes more exhaustive even with the help of today's search engines since they are not specialized for this task. In academics, two relevant papers do not always have to share keywords, cite one another, or even be in the same field. Although a well-known paper is usually an easy pray in such a hunt, relevant papers using a different terminology, especially recent ones, are not obvious to the eye. In this work, we propose paper recommendation algorithms by using the citation information among papers. The proposed algorithms are direction aware in the sense that they can be tuned to find either recent or traditional papers. The algorithms require a set of papers as input and recommend a set of related ones. If the user wants to give negative or positive feedback on the suggested paper set, the recommendation is refined. The search process can be easily guided in that sense by relevance feedback. We show that this slight guidance helps the user to reach a desired paper in a more efficient way. We adapt our models and algorithms also for the venue and reviewer recommendation tasks. Accuracy of the models and algorithms is thoroughly evaluated by comparison with multiple baselines and algorithms from the literature in terms of several objectives specific to citation, venue, and reviewer recommendation tasks. All of these algorithms are implemented within a publicly available web-service framework (http://theadvisor.osu.edu/) which currently uses the data from DBLP and CiteSeer to construct the proposed citation graph., 10 pages, 8 figures, 3 tables

Session 9; International audience

no abstract

Bilgi güvenliği, elektronik iletişimin hayatımızın her alanına girmesi ile birlikte giderek daha çok önemli hale gelmektedir. Bilgi güvenliği kavramının içeriği kullanıldığı uygulamanın çeşidine ve gereksinimlerine göre değişebilmektedir. Fakat kullanılan alan ya da uygulama ne olursa olsun, güvenlik için hangi algoritmalar kullanılırsa kullanılsın, güvenlik ilk önce gerekli kişilerin bilmesi gereken bir anahtarın gizli kalmasına dayanmaktadır.Güvenliğin en önemli unsuru olan anahtarların gizli kalması ve kaybolmaması gereksinimleri değişik problemleri de beraberinde getirmektedir. Anahtarın sadece bir kişide, sunucuda ya da veritabanında saklanması, sistemin güvenliğini o kişinin güvenliğine ve güvenilirliğine indirgemektedir. Bunun yanında şifrenin başka bir kopyasının olmaması da yazılım/donanım arızaları gibi durumlarda anahtarın tamamen kaybedilmesi gibi sakıncalar içermektedir. Anahtarın birden fazla kişide bulunması durumunda ise anahtarı ele geçirmeye çalışan biri için artık bir değil birden fazla hedef vardır ve dolayısıyla, anahtarın güvenliği bu kişilerinin en az güvenliğe sahip olanının güvenliğine indirgenmektedir.Anahtar paylaştırma yöntemleri ilk olarak yukarıda bahsedilen problemleri çözmek için önerilmiştir. Bu yöntemlerdeki anafikir anahtarın belli bir grup içinde öyle paylaştırılmasıdır ki, sadece önceden belirlenen koalisyonlar bir araya geldiğinde anahtarı elde edebilmeli daha küçük koalisyonlar ise anahtar hakkında hiçbir bilgi elde edememelidir. Bu sayede, şirketlerin karar mekanizması uygulamaları, büyük ölçekli finans uygulamaları, nükleer sistemlerin komuta-kontrol uygulamaları gibi alanlarda gizli kalması gereken anahtarlar anahtar paylaştırma yöntemleri kullanılarak saklanabilir.Eşik kriptografisi anahtar paylaştırma yöntemlerinin özel bir hali ile ilgilenir. Eşik kriptografisine dayanan anahtar paylaştırma yöntemlerinde bir koalisyonun içindeki kişi sayısı, büyüklüğü, belli bir eşiği, kısaca t, geçiyorsa, o koalisyon anahtarı elde edebilir. Daha küçük koalisyonlar ise anahtar hakkında hiç bir bilgi elde edemezler. Literatürde ilk önerilen anahtar paylaştıma yöntemlerinden biri Shamir'in eşik kriptografisine dayanan yöntemidir. Shamir bu yöntemde anahtarı t-1 dereceli bir polinomun sabit terimi olarak düşünmüş ve polinomun geçtiği noktaları grup içinde dağıtmıştır. Bu sayede, gerekli olduğunda t büyüklüğündeki bir koalisyon, polinomu yaratarak anahtarı elde edebilir. Bu yöntem sonraları güvenlik üzerine araştırma yapan bilim insanları tarafından kabul görmüş ve değişik uygulamalarda kullanılmıştır. Bu yöntem ile yaklaşık aynı zamanlarda önerilen Blakley'in düzlem geometrisine dayalı anahtar paylaştırma yöntemi ve Asmuth ve Bloom'un önerdiği Çin Kalan Teoremi'ne dayalı yöntem güvenlik açısından gerekli ve yeterli şartları sağladıkları halde araştırmacılar tarafından rağbet görmemişlerdir.Anahtar paylaştırma yöntemleri yukarıda bahsedilen uygulamalar dışında da değişik güvenlik uygulamaları için temel yapı parçacığı görevini görmüşlerdir. Bu uygulamalar, genelde fonksiyon paylaştırma yöntemi olarak bilinen, herhangi bir fonksiyonun çıktısının, herbiri gizli bir fonksiyon girdisine sahip bir grup tarafından, fonksiyon girdileri gizli kalmak şartı ile hesaplanması problemini içerir. Literatürde, anahtar paylaştırma yöntemleri temel alınarak paylaştırılan bu fonksiyonlara RSA, ElGamal ve Paillier gibi açık anahtar algoritmalarının imza yada şifreleme fonksiyonları örnek gösterilebilir. Elektronik seçim gibi yeni nesil uygulamalar fonksiyon paylaştırma yöntemlerini yoğun bir şekilde kullanmaktadır.Daha önce de bahsedildiği gibi, Shamir'in anahtar paylaştırma yöntemi literatürde sıklıkla kullanılan bir yöntem olup diğer anahtar paylaştırma sistemleri pek rağbet görmemektedir. Fakat, bu tezin gösterdiği gibi Çin Kalan Teoremi'ne dayalı anahtar paylaştırma yöntemleri de pratik olarak bu tür uygulamalarda kullanılabilir. Her uygulama değişik güvenlik gereksinimlerine sahip olduğu için, Shamir'in yöntemi değişik eklentiler tasarlanarak çeşitli uygulamalarda kullanılmıştır. Bu tez temel olarak farklı anahtar paylaştırma yöntemlerinin çeşitli uygulamalarda nasıl kullanabileceği üzerine yoğunlaşacaktır. Tezde Çin Kalan Teoremi'ne dayalı bir anahtar paylaştırma yöntemi olan Asmuth-Bloom yöntemi için bazı değişiklikler önerilecektir. Sonra da bu yeni yöntemler kullanılarak kanıtlanabilir güvenliğe sahip fonksiyon paylaştırma yöntemleri ve halihazırda varolan uygulamalarda gereken değişik güvenlik eklentileri tasarlanacaktır. Information security has become much more important since electronic communication is started to be used in our daily life. The content of the term information security varies according to the type and the requirements of the area. However, no matter which algorithms are used, security depends on the secrecy of a key which is supposed to be only known by the agents in the first place.The requirement of the key being secret brings several problems. Storing a secret key on only one person, server or database reduces the security of the system to the security and credibility of that agent. Besides, not having a backup of the key introduces the problem of losing the key if a software/hardware failure occurs. On the other hand, if the key is held by more than one agent an adversary with a desire for the key has more flexibility of choosing the target. Hence the security is reduced to the security of the least secure or least credible of these agents.Secret sharing schemes are introduced to solve the problems above. The main idea of these schemes is to share the secret among the agents such that only predefined coalitions can come together and reveal the secret, while no other coalition can obtain any information about the secret. Thus, the keys used in theareas requiring vital secrecy like large-scale finance applications and commandcontrol mechanisms of nuclear systems, can be stored by using secret sharing schemes.Threshold cryptography deals with a particular type of secret sharing schemes. In threshold cryptography related secret sharing schemes, if the size of a coalition exceeds a bound t, it can reveal the key. And, smaller coalitions can reveal no information about the key. Actually, the first secret sharing scheme in the literature is the threshold scheme of Shamir where he considered the secret as the constantof a polynomial of degree t - 1, and distributed the points on the polynomial to the group of users. Thus, a coalition of size t can recover the polynomial and reveal the key but a smaller coalition can not. This scheme is widely accepted by the researchers and used in several applications. Shamir's secret sharing scheme is not the only one in the literature. For example, almost concurrently, Blakley proposed another secret sharing scheme depending on planar geometry and Asmuth and Bloom proposed a scheme depending on the Chinese Remainder Theorem. Although these schemes satisfy the necessary and sufficient conditions for the security, they have not been considered for the applications requiring asecret sharing scheme.Secret sharing schemes constituted a building block in several other applications other than the ones mentioned above. These applications simply contain a standard problem in the literature, the function sharing problem. In a function sharing scheme, each user has its own secret as an input to a function and the scheme computes the outcome of the function without revealing the secrets. In the literature, encryption or signature functions of the public key algorithms like RSA, ElGamal and Paillier can be given as an example to the functions shared by using a secret sharing scheme. Even new generation applications like electronic voting require a function sharing scheme.As mentioned before, Shamir's secret sharing scheme has attracted much of the attention in the literature and other schemes are not considered much. However, as this thesis shows, secret sharing schemes depending on the Chinese Remainder Theorem can be practically used in these applications. Since each application has different needs, Shamir's secret sharing scheme is used in applications with severalextensions. Basically, this thesis investigates how to adapt Chinese Remainder Theorem based secret sharing schemes to the applications in the literature. We first propose some modifications on the Asmuth-Bloom secret sharing scheme and then by using this modified scheme we designed provably secure function sharing schemes and security extensions. 106

XI ÖZET Çağdaş tiyatro yazarlarımızdan Sabahattin Engin'in Hayatı- Sanatı - Eserleri adlı çalışmamızda yazarımızı ve eserlerini tanıtmaya çalıştık. Çalışmamız üç bölümden oluşmaktadır. Birinci bölümde, önce yazarın hayatım verdik. Daha sonra yazarın sanat anlayışını belirlemeye çalıştık. Bu bölümde son olarak yazarın bütün eserlerinin( oyunları, yazıları ve diğer eserleri) bir bibliyografyasını verdik. İkinci bölümde yazarın yayımlanmış yirmi eserini `Tanıtım, Özet, Değerlendirme, Kişiler, Zaman, Mekan, Dil ve Üslup` başlıkları altında inceledik. Bölümün sonunda `Sabahattin Engin'in Oyunları Hakkında Genel Bir Değerlendirme` başlığıyla bir değerlendirme yaptık. Üçüncü bölümde ise yazarın bugüne kadar yayımlanmış yazılarından bazılarının `Türk Edebiyatıyla İlgili Olanlar` ve `Batı Edebiyatıyla İlgili Olanlar` başlıkları altında metinlerini verdik. xn ABSTRACT We have tried to introduce one of our contamporary play writers Sabahattin Engin in this study called ` Sabahattin Engin's Life, Art, and Works`. This work, in this content, bears the characteristics of being the first. Our study consists of three chapters. In the first chapter we gave the writer's life first. Then we tried to identify the writers' s understanding of art. And finanally, we gave a bibliography of the writer's all Works ( his plays, his writings published in the press and literary reviews. In the Second Chapter we studied writer's already published twenty works under the titles as, ` Introduction, Abstract, Evaluatron, Characters, Time, Place, Language and Literary Style` In the Thirdy Chapter we gave the texts out of some of his writings under the titles as, ` His Writings Related to Turkish Literature` and ` His Writings Related to Western Literature`. 398

Cataloged from PDF version of article. Kaya, Kamer M.S.

ÇÃÃà à à Ãà à Ãà ÃÃÃÃà à ÃÃà ÃÃÃÃà ÃÇÃà Ãà ÃÃà ÇÃà à Çà ÃÃÃà à ÃÇà Ãà ÃÃà ÃÃà à ÇÃà à ÃÃà à ÃÃÃÃà à ÇÃà Ãà ÃÃà à Ãà à ÃÃà Ãà à ÃÃà ÃÃÃà ÃÃÃÃà à Öà İÃ Ã İ Ö Ãà à Ãà ş Ãà à à ÃÃÃà Ãà à à ÃÖà º Öº Ã Ã İ ÃÃÃÃÃÃÃş ¾¼¼ÇÖà ÃÃİ ÃÃà à à Ãà à ÃÖ ÃÃ Ö Ã ÃÃÖ Ã ÃÃÃ İ Ã Ãà à ÃÃÃà à ÃÖà ùà Öà à à Ãà Ãà à ÃÃà à à ÃÃ Ö Ö ÃÖ Ã Ö Ã Ãà Ãà Ãİ Ãà à à ÖÃÃà à Ãà à Öº à ÃÖà à à à Ãà ÃÃ Ö Ã Ã ÃÃÃÃà à İÃÃà ÃÃ Ö Ã ÃÃÖ Ã Ã Ã ÃÃ İ Öİ Ã Ãà à ÃÖ ÃÃ Ö Ã Ãà à à à à ÃÃ Ö Ã ÃÃà à ÃÃÃÃÃ Ö Ö Ö Ã Öà à à ÃÃ Ã Ã İ Ãà à Öº ÃÃà ÃÃ Ö Ã Ã ÃÖ şÃ ÃÃÖ Ö Ö Ö Ã Öà à à Ãà à Ãà à à à à ÃÃ Ö Ã Ã ÃÖà ÃÃİ Ãùà Ãà à ÃÃÃ Ã Ã İ Ã Ãà ÖÃÃ İ Ã Öà Ãà à à ÃÃ İ Ã Ã İ Ã ÃÃÃ Ö Ãà Öà à ÃÃà à à à à Öº à ÃÃÖ ÃÖ ÃÃ Ö Ã Ã Ã Ãà Ãà à ÃÖà ¹à ÃÃà ÃÃÃÃà Ãà à à Ãà à ÃÖ Ã Ã Ã Ãş à à à Öà à ÃÃ Ö Ãà à ÃÃÖ Ã İÃÖÃÃà ÃÖ Ã Ã Ã Ã Ã Öà Öÿà à İà Öİ Ã Ã Ã ÃÃ Ö ÂºÃà à Ãà Öà à à à Ãİ ÃÃ Ã Ã Ö ÖÖ ÃÖ Ã ÃÃ Ö ş ÃÖ Ã ÃÃÃÖà à à à ÃÖ Ã ÃÃÃÃà à ÃÃ Ö Ö ÃÖà à à Ãà Ãà Ãà Ãà ÖºÇÃ Ö Ã Ã İ Ã Ã Ã Ã İ Ã Ãà Öà à Ãà ÃÃÃÃà à İÃÃà ÃÃ Ö Ã Ã ÃÃ Ã Ö Ãà Öà ÃÃà à à à ÃÃ Ö Ã Ã Ãà à İÃÃÃ Ö Ã Ãà ÃÃÃà Ãà Ãà à à Öºà à ÃÃ Ã Ö Ãà ÃÃÃ Ã Ã Ö Ã Ã ÃÃ Ã Ã Ã İ Ã ÃÃ Ã Ã Ö Ã Ã İÃÖÃÃÃà à Ãà ÃÃÃÃÃ İ Ã Ãà ÃÃÃà Ãà Ãà à à à İà Ãà à İÃÃÃÃ Ö Ã Ö Ã Ã Ãà Ãà Öº Ã İ ÃÃ Ö İ Ö Ã Ã Ã Ãİ ÃÃ Ã Ã Ö Ã ÃÃÖ Ã ÃÃÃ İ ÃÃÃÃà à Ãà à ÃÖà ÃÃ Ö Ã Ö Ã ÃÃ Ö Ã Ã Ã İÃ Ö Ã ÃÃÃÃ Ã Ö ÃÃ Ö Ã Ã Â¿ à Ãİ Ã ÃÃà ÃÃÃÃ Ö Ã Ã Ã ÃÃ İ İ Ã Ãà ÃÖ Ã Öà Ãà à ÃÃÃÃÃà Öà Ãà ÖÂºÃ Ã Ö ÃÃÃ Ã Ã Ö ÃÖ Ã Ã Ã Ãà à ş ÃÖà ÃÃİ ÃÃà à à ÃÖ ÃÃ Öş ÃÃÖ Ã ÃÃÂ¹Ã İ Ã Ãà à ÃÃÃà à ÃÖà ÃÃ Ö ş İ Ã Ã Ã Ã İ Ã Ãà Öà ºà ÃÃà ÃÃà à ÃÃà ¹ÃÃÃÃÇà à Ãù à à ÃÃÃÃÃà ÃÇà ÃÃÃà à à ÃÃÃÃ Ç Ã ÃÃà Ãà ÃÃÃÃà à Çà à à ÃÇ Ã ÇÃà à Ãà ùÃà ÃÃÃÃÃÇÃà ÃÃÃà à Öà İúú à ÃÃÃÃÃ Ö Ã Ã ÖÃÃÃà Öà ÃÃÖ ÃÖà º Öº Ã Ã İ ÃÃà ÃÃÃş ¾¼¼à à Ãà à à à Ãà Ãà Ãà ¬à ¹à Öà à à à Ãà à Öà à ÃÃà à Ãà Ö¹Ãà à Ãà à ÃÖÃà ÃÖ ÃÃÃİ ÃÃà ÃÃÃÖà Ãà ÃÃà à ÃÃÃ Ã Ö Ãà ÖÃÃà ÃÃúà à Ãà à ÃÖ Ãà ÃÖ ÃÃÃİ ÃÖÃÃÃà ÃÖ Ã Ã ÃÖÃ Ã Ã Ö Ãà ÃÃÃÃÖà à à Ãà ÃÃÖ Ã Ã Ãà ÃÃÃÃÃ Ö İ Ö Ã Ö ÃÃ Û Ã Ã Ã Ãà à ÃÃà Ãà ÖİÃÃÃà à Ãà à à à Ãà à à à à à ú à à ÃÛ Ã ÃÃ Ã Ö İ Ã ÃÃ Ö Ã Ö ÃÃà à ÃÖà Ãà à à à ÜÃÃà à à à ¬à ¹à Öà ÃÃ Ö Ã Ãà ÃÃà à à ÃÃà ÃùÃà à Ãà à à à ÃÃ Ã Ö Ã Ãà à Ãà ÜÃÖ Ãà Ãà Ãà Ûà à à ÃÃ Ö Ã Ãúà ÃÖÃÃÃà ÃÖ Â¹Ã Ã Ã Ãà à ÃÃÖÃ Û ÃÃÃÃà à à à Ãà à Ãà ùà ÃÃş Ö Â¬Ã Ã ÃÃ Ã Ü Ãà Ãà ÃÖ Öà à à ú ÃÖ Ã Ö Â¬Ã Ã ÃÃ Ã ÃşÛÃà Ãà ÃÖ Ã ÃÃà à Ãà à İÃ Ö Ö Ã Ã Ûà à à Ãà İÃ Ö Ö Ã Â¹Ã Öà à Ãà à ¹à ÃÖÃÃà à ÃÃş Û ÃÖÃÃÃà Ãà ÃÃ Ã Ö Ã Ã Â¹ ÃÃÖÃà à Ãà ÃÃÖ Ãà à ÃÖ Ö Â¬Ã Ã Ã Ãà Ãà Ãà ÃÃà ÃÖ Ã Ãà ÃÛà ÃÃà à à Ãà Ãà ¹à ÃÃú ÃÃà à Ãà à à Ãà à ÃÃÃş à ÃÃÃÃà à Ãà à ÃÖÃÃÃà à ÃÃÃà à ÃÃà à ÃÃà ÃÃ Ã Ã Ö Ã Ã Â¹ ÃÃÖÃà à Ãù à ÃÖ Ãà à Ãà Ãà ÃÃÃİşÃÃ Ã Ö Â« à à à Ãà à à Ãİ Ãà Ãà à ÃÃÃÃà à Ãà à à à ÃÃÃà à Ãú ÜÃ Ö Ã ÃÃ Ã Ö ÃÃÃÃà ÃÃ Û Öà à ÃİÃà à ÃÃİ ÃÖà à Öùà ÃÃà à Ãà Ö¹ÃÃ Ã Ö Ã ÛÃÖ Ã Ã ÃÛ Ã Ãà ÃÖÃÃÃà ÃÖ Â¹Ã Ã Ã Ãà ÃÃÃÖÃ Ã Ö ÃÖÃà Ãà ÃÃ Ö Ã ÃÃ Ö İ ÃÃÃÃÖà à à ÃÃÖà ºà İÛÃÖ Ã Ãà à Ãà à ş ¬à ¹à ÖÃ Ã Ã Ãş à Öà à ÃÃà à Ãà Ö¹Ãà à Ãà ùÃÖÃÃş Ã Ö Ã Ã Â¹ ÃÃÖÃà à Ãú 74

In multilevel secret sharing, a secret is shared among a set of hierarchically organized participants in a way that the members of the superior compartments are more powerful and can replace the participants of an inferior one to form an authorized coalition during secret reconstruction. In this work, we first show that the only existing multilevel threshold secret sharing scheme based on the Chinese Remainder Theorem CRT is not secure and fails to work with certain natural threshold settings on compartments. As the main contribution, we propose a secure CRTbased scheme that works for all threshold settings. In the proposed scheme, we employ a refined version of Asmuth-Bloom secret sharing with a special and generic Asmuth-Bloom sequence called the anchor sequence. Based on this novel idea, we also propose the first multilevel conjunctive threshold secret sharing scheme based on the Chinese Remainder Theorem.

oşut bir uygulamanın görev etkileşim çizgesi komşu görevlerin farklı renklerle boyandığında birbirleri ile aynı renkteki görevler aynı anda pahalı bir senkronizasyon veri yapısı kullanılmadan aynı anda çalıştırılabilmektedir. Bu tür bir çalıştırmada bir renkteki görevler bitirilmeden, başka bir renkteki görev koşut halde şlenemeyeceğinden boyama esnasında kullanılan renk sayısı koşut uygulamanın çalıştırılması esnasında karşılaşılacak senkronizasyon adım sayısını belirtmektedir. Literatürde çizge boyama problemi ''bir çizgeyi mümkün olan en az sayıda renk kullanarak komşu noktalara farklı renkler vermek'' olarak tanımlanmıştır ve bir optimizasyon problemi olarakgörüldüğünde NP-Hard sınıfındadır. Çizge boyama probleminin farklı çeşitleri de paralel hesaplama, özellikle paralel bilimsel hesaplama alanında önemlidir. Problemin yukarıda bahsedilen basit halinde 1-uzaklık kullanılırken, k-uzaklık tanımı da özellikle k = 2 için pratikte kullanılmaktadır. Bu tezde de bu problem üzerine yoğunlaşılmıştır. Problemin genel hali ''bir çizgeyi mümkün olan en az sayıda renk kullanarak birbirinden k ve daha az uzaklıktaki nokta ikililerine farklı renkler vermek'' olarak tanımlanabilir. Literatürde bu problem için az renk kullanan buluşsal yöntemler önerilmiştir ve bu yöntemler k = 1 için oldukça hızlıdır. Fakat k = 2 için özellikle büyük çizgelerde bu buluşsalyöntemler dakikalar mertebesinde zaman alabilmektedirler. Çizge boyamanın bir uygulamanın çalışması için sadece bir ön işlem olduğu düşünüldüğünde bu işlemin getirdiği ekstra zamanın mümkün olduğu kadar az olması işlemin uygulanabilirliği için önemlidir. Bu tezde 2-uzaklık çizge boyama ve bu problemin farklı bir türü olan iki parçalı çizge boyama problemleri için iyimser ve açgözlü buluşsal yöntemler önerilmiştir. Bu yöntemler çok çekirdekli işlemcilerde ve Grafik İşleme Ünitelerinde koşut olarak gerçeklenmiş, ve ölçeklenebilirlikleri analiz edilmiştir. Yapılan deneylerde önerilen yöntemlerin ölçeklenebilir ve 16 çekirdek kullanıldığında literatürdeki yöntemlerden ortalama 25 kat hızlı oldukları görülmüş, özellikle sosyal ağ karakteri taşıyan çizgeler için büyük performansartışı sağladığı saptanmıştır. Yine bu tez çerçevesinde aynı renge sahip nokta kümelerinin eleman sayılarının birbirine yakın olması üzerine de çalışılmıştır. Bu tür dengeli dağılımlı bir boyama, uygulamanın çok çekirdekli işlemciler ve özellikle GİÜ'ler üzerinde çalışması esnasında her senkronizasyon adımında bütün çekirdekleri doyuracak kadar iş yükü olmasını sağlayacağından yüksek performans için önemli olabilmektedir. Bu tezde neredeyse hiç ekstra külfet getirmeden bunu sağlayabilecek iki yöntem önerilmiştir. Yapılan deneylerde bu yöntemlerin başarılı olduğu sonucuna varılmıştır. In parallel computing, a valid graph coloring yields a lock-free processing of the colored tasks, data points, etc., without expensive synchronization mechanisms. However, the coloring stage is not free and the overhead can be significant. In particular, for distance-2 graph coloring (D2GC) and bipartite graph partial coloring (BGPC) problems, which have various use-cases within the scientific computing and numerical optimization domains, the coloring overhead can be in the order of minutes with a single thread for many real-life graphs, having millions and billions of vertices and edges.In this thesis, we propose a novel greedy algorithm for the distance-2 graph coloring problem on shared-memory architectures. We then extend the algorithm to bipartite graph partial coloring problem, which is structurally very similar to D2GC. The proposed algorithms yield a better parallel coloring performance compared to the existing shared-memory parallel coloring algorithms, by employing greedier and more optimistic techniques. In particular, when compared to the state-of-the-art, the proposed algorithms obtain 25x speedup with 16 cores, without decreasing the coloring quality. Moreover, we extend the existing distance-2 graph coloring algorithm to manycore architectures. Due to architectural limitations, the multicore algorithm can not easily be extended to manycore. Thus several optimizations and modifications are proposed to overcome such obstacles. In addition to multi and manycore implementations, we also offer novel optimizations for both D2GC and BGPC on social network graphs. Exploiting the structural properties of social graphs, we propose faster heuristics to increase the performance without decreasing the coloring quality. Finally, we propose two costless balancing heuristics that can be applied to both BGPC and D2GC, which would yield a better color-based parallelization performance with a better load-balancing, especially on manycore architectures. 92

Hiperçizge parçalama literatürde oldukça popüler bir problemdir. Dağıtık algoritmalar ve VLSI devre tasarımı gibi uygulamaların performasi bu yöntemle büyük ölçüde arttırılabilir. Son 20 yılda, hiperçizgeyi hızlı bir şekilde parçalayabilen araçlar geliştirilmiştir. Ancak bu problem NP-Zor olduğu için, bu araçlar sezgisel yöntemlere dayanmaktadır. Bu yüzden genelde optimal olmayan sonuçları bulmaktadırlar. Optimal hiperçizge problemi üzerine sezgisel yöntemlere dayalı çalışmalara nazaran çok daha az sayıda araştırma bulunmaktadır. Bu tezde, literatürdeki bir çok metriğe göre optimal parçalamayi bulan, PHaraoh isimli koşut hiperçizge parçalama aracı sunulmaktadır. Optimal sonuçların bulunması sayesinde, böyle bir araç, daha önceden geliştirilen hiperçizge parçalama araçlarının gerçek performansını, olası en iyi sonuçile karşılaştırarak ölçmemizi sağlar. PHaraoh herhangi bir parçalama ile başlatılabilir ve bu sonucu sürekli olarak geliştirmeye çalışır. Bu sayede, istenen optimal hiperçizge parçalama islemini verilen sürede tamamlayamasa bile, baslangıçta verilen parçalamanın kalitesini iyileştirebilir. Gerçek hayattaki uygulamalarda karşılaşılan hiperçizge modelleri üzerinde yaptığımız deneylere göre, PHaraoh pratikte en çok kullanılan araçların ürettiği parçalamaların kalitesini dal ve sınır arama yöntemini kullanarak büyük ölçüde iyileştirmektedir. Arama uzayında bulunan optimal parçalamanın bulunma süresini kısaltmak icin, `usta yamak` ve `iş çalma` yöntemlerine dayalı koşut algoritmalardan faydalandik. Daha önceki çalışmalarımızda ve bu tezde yaptığımız deneylere göre hiperçizge parçalama problemi icin dal ve sınır ağacındaki öğelerin sırası PHaraoh'ın performansını önemli oranda etkilemektedir. Bu tezde, değişik sıralama yöntemleri önerip, bunların PHaraoh'ın çalışma süresini nasıl değiştirdiğini ve bu değişikliğin nedenlerini hiperçizgelerin özelliklerine bağlayarak açıkladık. Hypergraph partitioning into K parts has many applications in practice such as distributed algorithms and very large scale integrated circuit (VLSI) design. There are various tools proposed in the literature which can partition a given hypergraph very fast. However, since the problem is NP-Hard and the traditional approaches heavily use heuristics, these tools do not provide an optimal partition. There is limited research on partitioning hypergraphs optimally. In this thesis, we proposePHaraoh, a parallel hypergraph partitioner that can provide optimal partitions for many metrics used in the literature. Such a partitioner is important in practice since it enables us to evaluate the true performance of the existing tools. Furthermore, PHaraoh can be started with an initial partition. Thanks to that, even an optimal solution is not found within the given time limit, PHaraoh improves the cost of the provided initial partition. Experimental results on hypergraphs obtained from real life matrices show that the quality of the partitions of existing tools can be improved significantly for most of the hypergraphs. In order to increase the speed up the search-space exploration, we experimented with both master-slave and work-stealing parallelization. It also has been shown that the runtime of the algorithm highly depends on the order of the items in the branch and bound tree. In this study, we propose different ordering strategies which can offer great speed ups depending on the characteristics of the hypergraph. 85

Karmaşık sistemlerin geliştirilmesinde, test etme en pahalı ve en çok zaman alan evredir. Model tabanlı testler yüksek kaliteli deney kurgusunu otomatik üretmede kullanılan yaklaşımlardan birisidir. Deney kurgusunu otomatik üretme test etmenin en zorlu parçalarından biridir. Sonlu durum makineleri ya da özdevinimler gibi biçimsel modeller, otomatik deney grubunu üretmek için kullanılmaktadır. Sistem belirli bir duruma senkronize edildikten sonra testler uygulanır ve bu belirli duruma gelebilmek için sıfırlama kelimeleri kullanılmaktadır. Daha kısa deney süreleri için en kısa sıfırlama kelimesini hesaplamak önemlidir, ancak en kısa sıfırlama kelimesini hesaplamak NP–hard bir problemdir. Bu nedenle kısa sıfırlama kelimelerini hesaplamak için sezgisel yöntemler kullanılmaktadır. GREEDY algoritması bu alanda bilinen en hızlı sezgisel algoritmadır. Bu tezde, GREEDY algoritmasını hızlandıran yaklaşımlar sunulmaktadır. İlk olarak GREEDY algoritmasının paralelleştirilmesine odaklanılmaktadır. İkinci olarak ise tembel bir yaklaşım önererek sıfırlama kelimesinin üretilmesi için gerekli bilgilerin hazırlanma süreci ertelenmektedir. Aynı zamanda, GREEDY algoritması için benzer algoritmik iyileştirilmeler önerilmektedir. Deney sonuçlarımız özdevinim büyüklügüne bağlı olarak GREEDY algoritmasının 500 kat daha hızlı hale getirilebileceğini göstermektedir. Önerilen geliştirmeler özdevinim büyüklügü arttıkça daha etkili hale gelmektedir. Testing is the most expensive and time consuming phase in the development of complex systems. Model–based testing is an approach that can be used to automate the generation of high quality test suites, which is the most challenging part of testing. Formal models, such as finite state machines or automata, have been used as specifications from which the test suites can be automatically generated. The tests are applied after the system is synchronized to a particular state, which can be accomplished by using a synchronizing word. Computing a shortest synchronizing word is of interest for practical purposes, e.g. for a shorter testing time. However, computing a shortest synchronizing word is an NP–hard problem. Therefore, heuristics are used to compute short synchronizing words. GREEDY is one of the fastest synchronizing heuristics currently known. In this thesis, we present approaches to accelerate GREEDY algorithm. Firstly, we focus on parallelization of GREEDY. Second, we propose a lazy execution of the preprocessing phase of the algorithm, by postponing the preparation of the required information until it is to be used in the reset word generation phase. We suggest other algorithmic enhancements as well for the implementation of the heuristics. Our experimental results show that depending on the automata size, GREEDY can be made 500⇥ faster. The suggested improvements become more effective as the size of the automaton increases. 52

Profesyonel ağlarda bireylerin birbirine tavsiye edilmesi bir bağlantı tahmini problemi olarak ele alınabilir. Bu amaç doğrultusunda öğrenme tabanlı yöntemler, hem tahmin hem de çıkarsama yapma hedefleri için uygundur. Bu yöntemlerin uygulanması kolaydır ve büyük ölçekli veri setleri için hesaplanabilirlik açısından da uygundurlar. Bu tezde, Türkiye'nin akademik işbirliği ağında, yazarların ve makalelerin önerilmesi için bağlantı tahmin modelleri araştırılmıştır. Modeller ve hipotezler için kavramsal bir arka plan oluşturmak amacıyla veri setini belirli görselleştirme araçları ve temel istatistikler kullanarak inceliyoruz. Bir yan ürün olarak, mevcut modellerin ve kullandıkları bilgi kaynaklarının olası eksikliklerini de vurguluyoruz. Kavramsal arka planı ve potansiyel dezavantajları hesaba katarak mevcut modelleri uyguluyor, karşılaştırıyor ve farklılıklarını ortaya koyuyor ve hipotezimizi test ediyoruz. Tüm bu modelleri eniyileme problemleri olarak ele alıyor ve birinci dereceden eniyileme yöntemlerini kullanarak çözüyoruz. Sonuçları, tahmin isabeti açısından değerlendiriyor ve anlamlarını da yorumluyoruz. Elde ettiğimiz sonuçlar, sahip olduğumuz veri seti için özel olsa da, kullandığımız teknikler diğer ağ veri setleri ile uygulanabilecek kadar geneldir. Recommendation of individuals in a professional network can be thought as a link prediction problem. For this purpose, learning based methods are suitable for both prediction and inference goals. These methods are also easy to implement and they are computationally tractable for large scale datasets. In this thesis, we investigate link prediction models for recommendation of authors and papers in academic collaboration network of Turkey. We examine the dataset with certain visualization tools and basic statistics, in order to form a conceptual background for our models and hypothesis. As a byproduct, we highlight potential drawbacks of existing models and the information resources they use. Taking the conceptual background and potential drawbacks into account, we implement, compare and contrast existing models, and test our hypothesis. We cast all of these models as optimization problems and solve them by using first order optimization methods. We evaluate their results in terms of prediction accuracy and provide interpretation about their meaning as well. While the results that we have obtained are special for the given dataset that we have, techniques that we have used are generic enough to be implemented with other graph datasets. 45

Günümüzde, veri setlerinin boyutundaki artış ile tavsiye sistemleri gibi uygulamalardaki bu verilerle çalışmayı sağlayacak hızlı ve tutarlı araçların gereksinimi, en kısa sürede tüm kaynakları kullanarak istenen çalışmaları yapabilen yeni düzenlenmiş modeller üzerinde büyük bir ilgi oluşmasını sağladı.Bu çalışmada, paralelleşmiş büyük ölçekli matris faktorizasyon problemi için bir sistem oluşturduk.Bu tür problemleri çözmek için en çok kullanılan, en başarılı yöntemlerden biri optimizasyon teknikleridir. Optimizasyon yöntemleri, iterasyonları gerçekleştirmek için gradyan vektörlerine gerek duymaktadır. Bu tür problemlerin çözümünde zamanın çoğu gradyan ve fonksiyon değerlerinin hesaplanmasında harcanmaktadır. Bu çalışmada, matris faktorizasyonunda daha önce kullanılmayan, yeni bir yöntem uyguladık. Paralelizasyon için CPU ve GPU uygulamalarını gösterdik. Çalışmamızda da görüldüğü gibi, önerilen paralelizasyon oldukça iyi ölçeklenmektedir. MovieLens veri seti üzerindeki çalışmamızı raporladık. Sonuçlarımız gösteriyor ki iterasyon sayısını azaltmada önerdiğimiz yöntem oldukça başarılı. İstenilen RMSE değerleri ile birlikte umut vadeden ölçeklenir değerlere ulaştık. During recent years, the exponential increase in data sets' sizes and the need for fast and accurate tools which can operate on these huge data sets in applications such as recommendation systems has led to an ever growing attention towards devising novelmethods which can incorporate all the available resources to execute desired operations in the least possible time. In this work, we provide a framework for parallelized large-scale matrix factorization problems. One of the most successful and used methods to solve these problems is solving them via optimization techniques. Optimization methods require gradient vectors to update the iterates. The time spent to solve such a problem is mostly spent on calls to gradient and function value evaluations. In this work, we have used a recent method, which has not been used before for matrix factorization. When it comes to parallelization, we present both CPU and GPU implementations. As our experiments show, the proposed parallelization scales quite well. We report our results on Movie- Lens data set. Our results show that the new method is quite successful in reducing the number of iterations. We obtain very good RMSE values with significant promising scaling figures. 54

Yazılım sistemleri daha karmaşık hale geldikçe, bu tip sistemleri düşük maliyetli test etmek için etkili tekniklere olan talep de artmaktadır. Bunlara örnek olarak web sunucuları (Apache vb.) ve veritabanları (MsSQL vb.) gibi yapılandırılabilirliği yüksek yazılım sistemleri verilebilir. Bu sistemler birbiriyle etkileşim içinde olan birçok yapılandırabilir parametrelere sahiptir ve bu etkileşimler üstel büyüme hızıyla parametre konfigürasyonla- rının sayısının artmasına yol açar. Bundan dolayı, bu tip yazılım sistemleri parametrelerin etkileşimlerinden dolayı oluşabilecek hatalara karşı daha çok eğilimlidir.Bu soruna bir çözüm olarak konfigürasyon uzayını sistematik şekilde kümeleyip ve bu kümeleri ayrı ayrı test eden kombinatoryal etkileşim testi (combinatorial interaction testing) verilebilir. Kombinatoryal etkileşim testi, az sayıda parametre konfigürasyonları içeren test senaryoları olarak kullanılması için kapsayan diziler adı verilen objeleri üretir. Bir /textit{t-yollu kapsayan dizisi} (t-way covering array) test edilecek sistemin bütün t-yollu parametrelerinin değer kombinasyonlarını en küçük sayıda konfigürasyon kullanarak kapsamayı hedefler. Yapılan birçok araştırmanın kayda değer çoklukta hataların küçük sayıda parametre etkileşimlerinden kaynaklandı{g}ını göstermesinin ardından, kapsayan dizinin uygulamalarına özellikle teşvik edilmiştir.Yine de, özellikle de konfigürasyon uzayı büyük olduğunda ve sistem içinde parametreler arasında bazı konfigürasyonları geçersiz kılan kısıtlamalar olduğunda, minimum sayıda konfigürasyon içeren kapsayan diziler oluşturmak kolay bir iş değildir. Bundan ötürü, bu çalışma alanı farklı alandan birçok araştırmacıların ilgisini çekmektedir. çoğu çalışma ölçeklendirme konusunda sorun yaşamasına rağmen, kapsayan dizi oluşturma konusunda bazı başarılı çalışmalarda yapılmıştır. Fakat, konfigürasyon uzayı büyüdükçe, çoğu yaklaşım zorlanmaya başlar.Kombinatorik problemler, bizim durumda kapsayan dizi oluşturmak, çoğunlukla etkili sayma teknikleri kullanılarak çözülür. Bu varsayımı baz alarak, sayma problemlerinin kolay bir iş olmasından ve paralel programlama teknikleri kullanılarak verimli bir şekilde çözülebileceğinden dolayı, kapsayan dizilerin paralel algoritmalar kullanılarak etkili bir şekilde oluşturulabileceğine dair öngörüde bulunuyoruz. Farklı mimariler farklı araştır- ma alanlarında daha etkili olabileceğinden dolayı, biz GPU tabanlı paralel programlama teknikleri kullanmaya karar verdik. çünkü GPU'ların aritmetik hesaplama birimleri küçük olmasına karşın, yüzlerce çekirdekleri, hatta bazen binlerce çekirdekleri olabilir. Bu çekirdeklerin kapasiteleri kısıtlı ve sınırlı olmalarına rağmen, bizim tek yapmak istedi- ğimiz defalarca basit sayma işlemleri olduğu için bizim çalışmamızda amacımıza çok iyi hizmet ederler. Bu fikrimizi hesaplama zamanını azaltmak için daha önce birçok defa kapsayan dizi oluşturmada kullanılmış ve çoğu zaman en küçük boyutlarda sonuçlar vermiş olan benzetilmiş tavlama algoritması (simulated annealing) üzerinde uyguladık. Bunlara ek olarak, benzetilmiş tavlama algoritmasının her adımında paralel olarak çoklu sayıda komşu durumları üretebilen bir teknik geliştirdik. Son olarak da, uzayı tamamen rastgele aramanın kötü etkisini düşürmek ve kapsayan dizilerin boyutunu daha da azaltmak için SAT (SATisfiability) algoritması ve paralel programlama teknikleri kullanarak melez bir yaklaşım öne sürdük. As software systems becomes more complex, demand for efficient approaches to test these kind of systems with a lower cost is increased highly, too. One example of such applications can be given highly configurable software systems such as web servers (e.g. Apache) and databases (e.g. MySQL). They have many configurable options which interact each other and these option interactions lead having exponential growth of option configurations. Hence, these software systems become more prone to bugs which are caused by the interaction of options.A solution to this problem can be combinatorial interaction testing which systematically samples the configuration space and tests each of these samples, individually. Combinatorial interaction testing computes a small set of option configurations to be used as test suites, called covering arrays. A /textit{t-way covering array} aims to cover all t-length option interactions of system under test with a minimum number of configurations where t is a small number in practical cases. Applications of covering arrays are especially encouraged after many researches empirically pointed out that substantial number of faults are caused by smaller value of option interaction. Nevertheless, computing covering arrays with a minimal number of configurations in a reasonable time is not easy task, especially when the configuration space is large and system has inter-option constraints that invalidate some configurations. Therefore, this study field attracts various researchers. Although most of approaches suffer in scalability issue, many successful attempts have been also done to construct covering arrays. However, as the configuration scape gets larger, most of the approaches start to suffer.Combinatorial problems e.g., in our case constructing covering arrays, are mainly solved by using efficient counting techniques. Based on this assumption, we conjecture that covering arrays can be computed using parallel algorithms efficiently since counting is an easy task which can be carried out with parallel programming strategies. Although different architectures are effective in different researches, we choose to use GPU-based parallel computing techniques since GPUs have hundreds even sometimes thousands of cores however with small arithmetic logic units. Despite the fact that these cores are exceptionally constrained and limited, they serve our purpose very well since all we need to do is basic counting, repeatedly. We apply this idea in order to decrease the computation time on a meta-heuristic, search method simulated annealing, which is well studied in construction of covering arrays and, in general, gives the smallest size results in previous studies. Moreover, we present a technique to generate multiple neighbour states in each step of simulated annealing in parallel. Finally, we propose a novel hybrid approach using SAT solver with parallel computing techniques to decrease the negative effect of pure random search and decrease the covering array size further. Our results prove our assumption that parallel computing is an effective and efficient way to compute combinatorial objects. 104