BU-CE-1401: PDF
Top-K Link Recommendation for Development of P2P Social Networks
The common approach for implementing social networks has been using centralized infrastructures, which inherently include problems of privacy, censorship, scalability, and fault-tolerance. Although decentralized systems offer a natural solution, significant research is needed to build an end-to-end peer-to-peer social network where data is stored among trusted users. The centralized algorithms need to be revisited for a P2P setting, where the nodes have connectivity to only neighbors, have no information of global topology, and may go offine and churn resulting in changes of the graph structure. The social graph algorithms should be designed as robust to node failures and network changes. We model P2P social networks as uncertain graphs where each node can go ofine, and we introduce link recommendation algorithms that support the development of decentralized social networks. We propose methods to recommend top-k links to improve the underlying topology and efficiency of the overlay network, while preserving the locality of the social structure. Our approach aims to optimize the probabilistic reachability, improve the robustness of the local network and avoid loss from failures of the peers. We model the problem through discrete optimization and assign a score to each node to capture both the topological connectivity and the social centrality of the corresponding node. We evaluate the proposed methods with respect to performance and quality measures developed for P2P social networks.Keywords: P2P Social Network, Link Recommendation
BU-CE-1402: PDF
Parallel Sparse Matrix-Matrix Multiplication Library
This technical report provides brief information and usage details of our MPI-based outer-product–parallel sparse matrix-matrix multiplication library, which is developed for our research paper entitled “Simultaneous Input and Output Matrix Partitioning for Outer-Product-Parallel Sparse Matrix-Matrix Multiplication.” The library makes use of the sparsity pattern of input and output matrices for distributed-memory parallelism. It performs the sparse matrix-matrix multiplication (SpGEMM) operation of the form C = A×B in two separate phases: First phase consists of communication-free local computation of outer products. Second phase consists of summation of results of the local outer products. The input matrices A and B are respectively partitioned one-dimensional (1D) columnwise and 1D rowwise conformably to enable communication-free local outer-product computations in the first phase. The output matrix C is partitioned on row, column or nonzero basis for mapping the local result summation tasks to processors. The actual SpGEMM computation can be represented by a novel hypergraph model and partitioning the input and output matrices can be established via partitioning this hypergraph model.The partitioning constraint of maintaining balance on part weights corresponds to obtaining computational load balance in the two phases, separately. The partitioning objective of minimizing cutsize corresponds to minimizing communication overhead during the second phase (summation phase).
Keywords: parallel computation, sparse matrices, outer-product--parallel sparse matrix-matrix multiplication, matrix partitioning, hypergraph partitioning
BU-CE-1403: PDF
Musical Instrument Source Separation in Unison and Monaural Mixtures
Musical Instrument Source Separation aims to separate the individual instruments from a mixture. We work on mixtures where there are two instruments, playing the same constant pitch at the same time. When musical instruments play the same note, they overlap with each other and act as a single source. We use statistical source separation algorithms which perform separation by maximizing the statistical independence between the sources. A mixture can be recorded with more than one microphone; this enables us to extract spatial information of the instruments by comparing the recordings. However we work with the monaural case where there is one microphone. Some musical instruments have amplitude modulation and this modulation can be seen in the mixtures. We also aim to detect amplitude modulations to support the source separation success. We use NTF (Non-negative tensor factorization) to perform the separation. NTF separates the mixture into many components. These components should be clustered in order to synthesize the individual sources. We use k-means as well as manual clustering by comparing the SDR (Signal to Distortion Ratio) values of the components with the original sources.Keywords: Source Separation, Statistical Source Separation, Monaural, Unison mixture, NMF, NTF