Partially-Observed Graph Abstractions for AuthorshipIdentification and Process Interference PredictionbyRudolf PleschB. Applied Science, The University of British Columbia, 2014A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of Applied ScienceinTHE FACULTY GRADUATE AND POSTDOCTORAL STUDIES(Electrical and Computer Engineering)The University of British Columbia(Vancouver)February 2017c© Rudolf Plesch, 2017AbstractPairwise interactions between objects can be modeled as a graph, which is a setof nodes and edges that each connect a pair of nodes. We consider the problem ofpredicting whether edges exist between nodes based on other pairs of nodes that wehave observed. From a partially-observed graph we extract several neighbourhoodand path features, then evaluate several machine learning algorithms for predictingwhether edges will exist between unobserved nodes. K-Nearest Neighbours wasfound to be the best classifier. We propose the novel use of path on a weightedgraph as a feature used for prediction.We apply this abstraction to predicting collaboration between authors in an on-line publication database. The unweighted graph contains an edge if two authorscollaborated and the weighted graph encodes the number of collaborations. Pre-diction error rates were less than 3% under ten-fold cross-validation.We also apply this abstraction to predicting whether processes running on thesame hardware will compete for resources. The unweighted graph contains an edgeif a process executed in more time than when running with another than by itself.The weighted graph had an edge weight that was the increase in execution time.Prediction error rates were less than 14% under ten-fold cross-validation.iiPrefaceI designed the graph abstraction for the authorship identification. My supervisorSathish Gopalakrishnan prompted me to consider the process interference applica-tion.The work in Chapter 3 was part of a group project by Hootan Rashtian andRudolf Plesch. I performed the link prediction work presented in the chapter in itsentirety. Our project neatly divided between the link prediction component and atext mining component. Hootan Rashtian contributed the text mining component.The work in Chapter 4 is part of a group project with Naga Raghavendra Suryaand Rudolf Plesch. I identified the research problem, adapted the graph abstractionto this purpose, and implemented the machine learning algorithm. He created thedata set and found some of the benchmarks. That project presented a differentmethod of creating the weighted graph, which I’ve since refined, improving theresults.These works have not been published.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Inference on Partially Observed Graphs . . . . . . . . . . . . . . . . 52.1 Feature Selection . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.1 Neighbourhood Features . . . . . . . . . . . . . . . . . . 62.1.2 Path Features . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Statistical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Relationship to Matrix Completion . . . . . . . . . . . . . . . . . 83 Application to Authorship Identification . . . . . . . . . . . . . . . . 103.1 Graph Construction . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12iv3.2.1 Feature Distribution . . . . . . . . . . . . . . . . . . . . 123.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 Application to Process Interference . . . . . . . . . . . . . . . . . . 164.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.2 Graph Construction . . . . . . . . . . . . . . . . . . . . . . . . . 194.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.3.1 Feature Distribution . . . . . . . . . . . . . . . . . . . . 244.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30A List of Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 34vList of TablesTable 3.1 Average Classification Error Rate (CER) over several runs ofcross-validation for all classifiers. . . . . . . . . . . . . . . . . 12Table 4.1 Density of graph and CER for several choices of SC thresholdT . CER is the fraction of correct predictions over the test set. . 24viList of FiguresFigure 3.1 Scatter plot of the Adamic/Adar score and number of commonneighbours for the authorship collaboration graph. Red pointsare collaborating pairs and blue points are non-collaboratingpairs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Figure 3.2 Scatterplot of Katz score and weighted shortest path for thedata set. Red points are collaborating pairs and blue points arenon-collaborating pairs. . . . . . . . . . . . . . . . . . . . . 14Figure 3.3 Scatterplot of unweighted and weighted shortest path for thedata set. Red points are collaborating pairs and blue points arenon-collaborating pairs. . . . . . . . . . . . . . . . . . . . . 15Figure 4.1 Process of creating unweighted contention graph. Red pairswere classified as interfering, while green ones were not. . . . 20Figure 4.2 Process of creating weighted contention graph. The edge weightis the inverse of the Slowdown Coefficient (SC). . . . . . . . . 21Figure 4.3 The interference graph generated when setting T=2.5. . . . . 22Figure 4.4 Slowdown Coefficients distribution of a typical application. . 23Figure 4.5 Scatter plot of the Adamic/Adar score and number of commonneighbours for the process interference graph. Red points arepairs that interfered and blue points are pairs that did not. . . . 25Figure 4.6 Scatter plot of the weighted and unweighted shortest path forthe process interference graph. Red points are pairs that inter-fered and blue points are pairs that did not. . . . . . . . . . . 26viiGlossarySGD Stochastic Gradient DescentKNN K-Nearest NeighboursSVM Supported Vector MachinesSC Slowdown CoefficientLLC Last-Level CacheCER Classification Error Rate, the fraction of misclassified objects in the testset.viiiAcknowledgmentsI’d like to thank Tibi, Carmen, and Talise; Sathish Gopalakrishnan for letting meexplore and asking so little of me; Alex Bouchard-Coˆte´, Jozsef Nagy, and MarkBottrill for showing me what a great teacher can do. What I’ve achieved attestspoorly to their teaching.ixChapter 1IntroductionA graph is an abstraction that can encode pairwise interactions between objects. Itis defined as a set of objects, called nodes, and a set a set of edges which link twonodes together. Graphs can also be weighted, where a real-number is assigned toeach edge, known as a weight. A partially-observed graph is one where we haveobserves a set of pairs of nodes and we know whether there are edges betweenthe nodes or not. Based on these observations, we extract some features fromthe graph and attempt to predict whether edges exist between unobserved pairs ofnodes. This problem has been studied in the field of social networks, where it isknown as link prediction [18][8][16]. In this domain, the questions researchersusually pose is whether two users of a social network who are not linked are likelyto become linked. These applications have only considered unweighted graphs.In this work we propose building a weighted graph and using weighted paths as anew feature for predicting these interactions. We also apply these methods to twonovel applications: authorship collaboration in a scientific publication database andprocess interference on a multi-core system.In each of the applications we encode the objects in the application as nodeand the event we are trying to predict as an edge on a graph. We then observesome interactions between objects and we construct two graphs: a weighted and anunweighted one. We extract some topological features of the graph and attempt topredict whether edges exist between the nodes we have not observed in the graph.Using 10-fold cross-validation, we evaluate several machine learning algorithms1for predicting the existence of edges. We also evaluate the topological graph fea-tures we extracted to show which have the most predictive power.The problem of predicting whether edges exist in a partially-observed graphis closely related to the mathematical study of matrix completion, which seeksto complete a matrix using only observations of a few entries[13]. While we donot apply matrix completion methods to our problems, we discuss the how matrixcompletion applies to our problem and give some directions for future research.Our first application of link prediction is predicting collaborations in an on-line publication database. The link prediction will be used to augment traditionaltext mining methods in a system used to disambiguate author names in a database.Ambiguous author names can exist because authors can sometime use full names,sometimes initials, and inconsistent use of accents. They can also occur when mul-tiple authors share a name. Disambiguating author names is an important problemin online publication databases because it enables accurate accumulation of papersby author.Currently, authorship identification is preformed by mining the text of a workfor certain features. This does not apply, however, to scientific publications whichoften have several authors, some of which may not have contributed to the papertext. We encoded co-authored publications as edges on an unweighted graph andrecurring co-authorships as decreasing edge weights on a weighted graph. Our linkprediction error rate was less than 3%.The second application is predicting whether two user processes that are run-ning on one piece of hardware will interfere with each other. This is an importantindustry problem because much of today’s computation is performed in large dat-acentres instead of on dedicated hardware. For example, services like Amazon’sAWS sell computation time to users and promise a number of cores and an amountof memory, this may be less than the number of cores and memory of a unit of hard-ware in the datacentre and the provider may choose to put several users’ jobs onone piece of hardware. Running multiple processes on a single piece of hardwarecan reduce the hardware needed for computations, but it risks that the processesrunning on the hardware will compete for resources and the performance will de-grade below an acceptable level. Using a method to predict which jobs can beco-located on a piece of hardware would be valuable for the service provider. Sim-2ilar benefits can be achieved in a distributed computation framework like Spark[31]and MapReduce[7] which distribute parallel computations between hardware in adatacentre.Previous efforts towards solving this problem rely on complex instrumentation,such as hardware counters to count cache misses, to predict whether they will in-terfere when co-located on the same hardware. Some solutions propose modifyingthe virtual memory system of the operating system[26]. Others propose chang-ing hardware to split the processor cache between several processes[5][23]. Bothof these changes would be very difficult for a service provider to implement in adata centre. In contrast to these complex solutions, the one we propose requiresonly observations of interference between pairs of processes to make predictionsabout which would interfere. Rather than using complex instrumentation to detectinterference, we used an easy-to-collect quality of service measure to detect inter-ference: the increase of execution time of processes when co-located over whenrunning with no other processes on the hardware. To the best of our knowledge,nothing like this method has been attempted.We modeled the processes as nodes on a graph and we added edges to an un-weighted graph if the co-located processes’ runtime increase was over a threshold.We added the inverse of this increase as the weight of an edge in an unweightedgraph. For several levels of the interference threshold, we achieved good predictionaccuracy.This algorithm can be used as a flexible framework for modeling interference.For example, encoding a combination of slowdown and increase in Last-LevelCache (LLC) misses as an edge on the graph may also potentially be effective as apredictor of interference. This should be viewed as a tradeoff between predictionaccuracy and simplicity of gathering the data needed to build the graph. The noveluse of this graph abstraction for process interference allows the use of graph algo-rithms to solve other problems. For example Xie and Loh consider clustering ofprocesses [29]. A minimum cut of the graph is a clustering of the processes.We first present the partially-observed graph abstraction, showing the featureswe extracted from the weighted and unweighted graphs. We also show how thisproblem relates to matrix completion. Next we describe the application of the thisabstraction to the authorship collaboration network and show the prediction results3and scatter plots of the features to show correlations and predictive power of thefeatures. Finally, we apply the graph abstraction to process interference prediction.We show how we generated the data set and the resulting graphs and scatter plotsof the features.4Chapter 2Inference on Partially ObservedGraphsA graph is described by a set of nodes and a set of edges, each of which connecttwo nodes in the node set. This abstraction can be used to model interactionsbetween pairs of objects, denoted by the existence of an edge between them. If areal-numbered weigh is assigned to an edge, then the edges can also encode thedegree that an interaction occurs. The former is referred to as a unweighted graph,while the latter is referred to as a weighted graph.A partially observed graph is a graph where we assume that we know whetheredges exist or not between only a subset of the pairs of nodes in the graph. Basedon this information we extract some topological features of the graph and attemptto predict whether edges exist or not between pairs of edges that we have not ob-served. This is also known in the literature, especially in the context of social net-work graphs, as link prediction[18][8][16]. It is also closely related to the problemof matrix completion.This problem can be approached as a two-class classification problem, wherepairs of nodes are either classified as having an edge between them or not basedon topographical features of the graph. There are several satisfactory surveys onthis subject, including [9], and [18], however, to the best of our knowledge, it is anovel contribution of this work to propose extracting path features from a weightedgraph.52.1 Feature SelectionWe constructed two graphs to represent the problems of interest. The first is anunweighted graph which encodes the only the interactions between the pairs ofobject. We also constructed a weighted graph with positive real-numbered weightsassigned to each edge. The edge weights were assigned in a method specific to theapplication. From these graphs, we extracted several computationally inexpensivepath and neghbourhood features commonly used for link prediction.2.1.1 Neighbourhood FeaturesIn the following descriptions, let Γ(n) denote the neghbourhood of node n, whichis the set of nodes that it is directly connected to with an edge.Number of common neighbors For nodes n and m:|Γ(n)∩Γ(m)|Jaccard similarity of neighbors For nodes n and m:|Γ(n)∩Γ(m)||Γ(n)∪Γ(m)|Number of common neighbors of neighbors For nodes n and m:∣∣∣∣∣∣ ⋃x∈Γ(n)Γ(x) ∩⋃y∈Γ(m)Γ(y)∣∣∣∣∣∣Adamic/Adar For nodes n and m:∑z∈Γ(m)∩Γ(n)1log |Γ(z)|The Adamic/Adar measure from the above list warrants some explanation. It wasproposed By Adamic and Adar in [1] as a computationally cheaper alternative tothe PageRank algorithm[21]. This is similar to common neighborhood, but weights6common neighbors with a smaller degree more highly. The intuition behind this isthat a less popular common neighbour may carry more information than a popularone.2.1.2 Path FeaturesPath features are also used in literature to solve the link prediction problem, al-though they are more computationally intensive. Shortest path on an unweightedgraph is commonly used[18][8]. However, to the best of our knowledge usingshortest path on a weighted graph is had not been considered. As described in Sec-tion 3.1 and Section 4.2 this method lends itself well to both of our applications.In the cases that there was no path between two nodes, we set the shortest path to1,000,000,000, which is much larger than any path in the graph.A family of more computationally intensive set of path features that have beenconsidered in literature are PageRank[21], SimRank[12], and Katz centrality[14].From these methods we chose to consider Katz centrality because it had an ex-act, non-iterative algebraic formulation. Katz centrality considers all paths of agiven length between a pair of nodes and assigns more weights to shorter paths bymultiplying them with a decay coefficient β . The Katz centrality is computed as∞∑l=1β l#(paths with length l between nodes).Alternatively this can be computed by inverting the adjacency matrix A of the graph(I−βA)−1− I, giving the Katz centrality of all pairs of nodes. Since the adjacencymatrix of our biggest graph was just on the border of being invertible on a powerfulPC, we chose to implement this matrix inversion method, setting β = 0.01 to givea well-conditioned matrix.2.2 Statistical AnalysisThe prediction of edges emerging in a graph is a two-category classification prob-lem: determining, given a set of graph characteristics, whether an edge will existbetween a pair of nodes or not. A common approach for evaluating models in ma-chine learning is to withhold a part of the data set for testing, train the model on the7remaining data, then evaluate the predictive performance of the model on the with-held data. To evaluate our models, we used 10-fold cross-validation. We dividedthe set of node pairs randomly into ten approximately equally-sized sets. We usedeach set once as a test set while training the algorithm on the remaing sets. Foreach training set, we build both the unweighted and the weighted graphs from onlythose pairs in the set, then computed all the features for these observed graphs.We evaluated several parametric and non-parametric models for predicting theemergence of edges in the graph. Simple linear models like Linear DiscriminantAnalysis and Generalized Linear Models do not work in this application becausesome of the features we considered are highly, for example the Adamic/Adar scoreand the number of common neighbours, are highly correlated. This causes thematrices that these algorithms would have to invert are very ill-conditioned be-cause the vectors representing two highly correlated features are nearly co-linear.A parametric model that we applied to our problem is Stochastic Gradient De-scent (SGD), which is not affected by these colinearity problems because it usesgradients rather than matrix inversion. Non-parametric models that we consideredare K-Nearest Neighbours (KNN), Random Forests, Boosted Stumps, and Sup-ported Vector Machiness (SVMS). For all the classifiers, we report the Classifica-tion Error Rate (CER) averaged over all the folds of cross-validation.We used the implementations of the machine learning models given in thescikit-learn Python library[22].2.3 Relationship to Matrix CompletionIf one considers the representation of a graph as a symmetric adjacency matrix, thenpredicting the existence of edges based on observations of some edges is a matrixcompletion problem. This problem appears many fields including recommenda-tion systems and signal processing or sparse sensing. The problem formulation,described most clearly by Kalofolias at al.[13], is given a matrix M ∈ Rn×m whichis assumed to be low-rank and a set Ω of observations of entries of M such thatMi, j : (i, j) ∈Ω⊆ {1, ...,n}×{1, ...,m},8findminX∈Rn×mrank(X) subject to Xi, j =Mi, j∀(i, j) ∈Ω. (2.1)The problem in Equation 2.1 is NP-hard, so the minimization performed in practice[3][24] is to instead minimizeminX∈Rn×mtr((XXT )1/2) subject to Xi, j =Mi, j∀(i, j) ∈Ω (2.2)which is convex, but not smooth. The advantage of this approach is that efficientalgorithms for solving these optimizations exists and [3] gives a bound for thenumber of observations needed to reconstruct the matrix and [24] slightly improveson these bounds.In the recommender systems application, the matrix M has m rows that rep-resent users and n rows that represent items, for example items in a online store.The entry of Mi, j represents user i’s rating of item j, whether explicitly observedor inferred from the matrix completion. The recommended system completes thismatrix in the hope that it can then recommend users items that they will rate highly.The low-rank assumption of the underlying matrix is justified by the assumptionthat there exist similar users producing similar rows in M and similar items, pro-ducing similar columns in M.If we force M to be square and symmetric, we can adapt this method to in-ferring the adjacency matrix of a graph. This has not been done, to the best ofour knowledge, likely because the low-rank assumption of the adjacency matrixdoes not apply to general graphs. However, in both of the applications consideredbelow, our assumption on the outset is that the processes or authors behave simi-larly meaning the underlying graph is structured into some clusters and suggestingthat the adjacency matrix may be low-rank. Kira´ly and Tomioka[15] also givenecessary and sufficient conditions for reconstructing matrices of arbitrary rank.Applying these methods to reconstructing the adjacency matrix of a graph withsome structure would be an interesting direction for future work.9Chapter 3Application to AuthorshipIdentificationWe first applied the partially observed graph abstraction to the graph formed byauthors collaborating on publications in an online publication repository. This wassome preliminary work towards the problem of disambiguating names of authorsthat share names or initials. Applying the link prediction to disambiguation ofnames was preformed by a colleague and is orthogonal to this work, but the linkprediction algorithm we developed is extremely effective and is presented below.An intuitive solution to author name disambiguation is to use an author’s writingstyle as proposed by De Vel et al.[6] and Stamatatos[25]. However these methodsdon’t apply when a document is written by several authors, also some given authorsmay not even have written any part of the document while still having a legitimatecontribution to the publication. Using link prediction for this task is attractivebecause it can determine whether an author collaborated on a publication whileonly considering past collaborations.There has been ample work in the field of link prediction in social networks,see [8], [16], and [18] for comprehensive surveys of the field. Because these tech-niques have only been used to predict links emerging in social and other networks,these authors have not considered a notion of recurring links. In our application,however, recurring collaborations are also of interest. We encode multiple col-laborations as parallel edges on a graph and show that the same link prediction10methodology can be used to predict recurring interactions with very good accu-racy.3.1 Graph ConstructionWe built a graph from a snapshot of the arXiv high energy physics publicationsdatabase. This was used for a data mining competition in 2003 and is freely avail-able from Cornell University. From the file containing the abstracts of all the pa-pers, we extracted the names of the authors that collaborated on each paper. Westripped all the accents and other special characters from the names and treated allauthors with the same surnames and initials as the same person. This approxima-tion was necessary because there was no automatic way of resolving this ambiguityand manual resolution was prohibitively difficult. In practice, few of these casesoccurred. We also ignored papers in the database with a single author, since theywere irrelevant to our analysis. After completing this process, our database con-tained 9066 authors, forming 17390 collaborating pairs.We constructed both an unweighted graph, where we added an edge if twoauthors had collaborated at any point, and a weighted graph, which encoded howmany times a pair of authors had collaborated. Reasoning that more frequent col-laboration between authors signaled a closer relationship, we modeled recurringcollaborations as parallel unit resistances in an electric circuit, each new collabora-tion lowering the edge weight. The final edge weight was the inverse of the numberof collaborations. This means that shortest paths among frequently-collaboratinggroups have smaller weights. Note that a pair of authors may have collaborated inthe test and training sets, in this case the training graphs will have edges betweenthese two authors and the test of the algorithm will attempt to predict whether thispair of authors collaborated in the test set. This differs from the link predictionproblem on social networks, which doesn’t as whether a pair of people on the net-work that are known to have a link will link again. The features were calculatedwith these edges included and the prediction algorithm was queried for pairs thatalready had edges between them. It is a novel contribution of this work to showthat predictions can be made accurately in this scenario.113.2 ResultsWe varied the parameters of all the classification algorithms under considerationand present the best results, except in the case of KNN, where we present resultsfor both 10 and 50 neighbours, since both performed very well. The CER for allthe classifiers considered are given in Table 3.1.Tree-based classifiers: Random forests and boosted stumps were the worst-performingclassifiers. Changing the number of trees and the depth of trees used did notdramatically improve performance. An interesting observation is that in ev-ery cross-validation fold, the error of boosted trees and random forests wasidentical. They likely made errors on the same data points.SVM: These classifiers showed consistently mediocre performance in all tests.SGD: This algorithm showed very good classification error rate in many crossvalidation tests, reaching as low as 4%. However, as sometimes happenswith this classifier, convergence problems in a few test led to 25% error rate.KNN: This was by far the best classifier, using a single nearest neighbor produceda classification error rate of 4%. Increasing the number of neighbor loweredthe classification error rate until to plateaued at 50 neighbors.Classifier SVM SGD Random Boosted KNN 10 KNN 50Forest StumpsCER 0.09289 0.07244 0.1031 0.1031 0.04927 0.02975Table 3.1: Average CER over several runs of cross-validation for all classi-fiers.3.2.1 Feature DistributionAnalyzing the distribution of features of the pairs of collaborating authors in thedata set shows which features were most important for predicting new collabora-tions. The scatter plot in Figure 3.1 shows the distribution of Adamic/Adar scoreand number of common neighbours. These two features are highly correlated. The12Figure 3.1: Scatter plot of the Adamic/Adar score and number of commonneighbours for the authorship collaboration graph. Red points are col-laborating pairs and blue points are non-collaborating pairs.common neighbours of neighbours and the Jaccard similarity of the neighboursare also correlated to these features. This suggests that eliminating all but one ofthese features from the model would not affect its performance. It is also a prop-erty of this data set that overwhelmingly nodes without common neighbours didnot collaborate. This is an important feature of the data set. It shows that is madeup of densely-connected communities, this is the main reason that prediction is soaccurate for this data set.The Katz score is a very effective classifier. As can be seen in Figure 3.2,exclusively pairs with a low Katz score did not collaborate in the test set. Thisshould be weighed against the computational complexity of inverting the adjacencymatrix of the graph, which is required for calculating the Katz score. Figure 3.2shows a strange bimodal distribution of Katz scores. This it probably another quirkof the data set, perhaps happening because of some densely-connected cliques. TheKatz score is also surprisingly uncorrelated to the weighted shortest path betweennodes.Figure 3.3 shows the Scatterplot of weighted and unweighted shortest paths13Figure 3.2: Scatterplot of Katz score and weighted shortest path for thedata set. Red points are collaborating pairs and blue points are non-collaborating pairs.between nodes. These features are unsurprisingly correlated, but there is a cleartrend that among pairs with the same unweighted shortest paths, ones with smallerweighted shortest paths are more likely to collaborate, justifying the novel use ofunweighted shortest path as a feature.3.3 ConclusionIn this chapter we adapted link prediction on social networks to predict new andrecurring collaborations between authors in a snapshot of the arXiv high-energyphysics publication database. It is a novel contribution of this work to show thatthe standard link prediction machinery can be used with no modifications to pre-dict recurring interactions between agents in a network. We encoded publicationsas edges of an unweighted graph and used standard link prediction methods toextract features from this graph. It is also a novel contribution of this work toencode repeated publications as decreasing edge weight in a weighted graph anduse weighted shortest path as a feature to predict edges. We show that weightedand unweighted shortest path are only weakly correlated and that the addition of14Figure 3.3: Scatterplot of unweighted and weighted shortest path for thedata set. Red points are collaborating pairs and blue points are non-collaborating pairs.weighted shortest path is justified for prediction accuracy.We assessed several machine learning algorithms and determined that the rel-atively computationally inexpensive KNN is most efficient for predicting new in-teractions on this graph. Prediction error was less than 3%. Future work includesfinding better features and optimizing machine learning algorithms.Such accurate link prediction can be used to disambiguate author names inan online without mining the text of a publication. Our future work is combinelink prediction and textual features to build a complete solution to disambiguatingauthor names in a publication database.15Chapter 4Application to ProcessInterferenceRecent years have seen an increase in computation performed in large data centreswhere heterogeneous computing jobs are scheduled on networked or otherwiseinterconnected pieces of hardware, referred to as nodes. One application of thissystem is distributed computation frameworks. For example many big data appli-cations like Spark [31], Microsoft’s Dryad [11], and Google’s MapReduce [7] seekto distribute parallel workloads over many computing nodes in a datacenter. An-other family of example are systems like Amazon’s AWS and Microsoft’s Azurewhich give users access to virtual machines which run on nodes in a data centre.Finally, Amazon’s Lambda Serverless Compute architecture would be a good ap-plication of this framework. It gives users a service which abstracts away the serveror container in which an application is running. The user simply provides a set ofcallback that is triggerd by a set of events. Amazon automatically handles placingthe jobs that implement these callbacks on compute nodes in its datacentres.It is tempting for service providers to schedule several independent jobs on onenode, since this would allow them to increase the number of jobs that can run inthe same data centre. However, scheduling several jobs on one node causes thesenodes to compete for resources. The jobs can compete for resources like network,memory capacity, and hard drive I/O, all which are common to all processors andcores on a node. In a multicore processor, even when all the threads required16by the jobs can be placed on a processor simultaneously, there are still severalshared resources on the chip like LLC, memory bus, and pre-fetching hardware.Scheduling applications on the same node that compete for resources can cause theperformance of these applications to degrade to an unacceptable level. Because ofthe variety of resource requirements of different jobs predicting which jobs can beco-located is not trivial, even with advanced profiling of jobs, because performanceof applications can decrease due to a complex interplay of resource contentions.In this application we develop a completely novel algorithm that predicts slow-down of co-located jobs using a graph model and the techniques developed above.Our algorithm defines degradation as an increase in the execution time and encodesit as an edge in a graph. This allows us to predict which jobs we can schedule onthe same node without modifying the operating system of the node or the users’jobs to gather any profiling data. The algorithm can also be directly extended toencode any performance degradation measure as an edge in a graph. The strengthof our algorithm is that it treats the user applications as a black box. A serviceprovider looking to use this method does not have to implement complex hardwaresupport for monitoring system events or complex resource management algorithmsat an operating system level to attempt to reduce resource contention. The serviceprovider would also not need to modify the users’ application to gather profilingdata.4.1 Related WorkIt is common in previous literature to consider contention on the LLC as the onlymeasure of contention. See [23] for an example where two applications are said tointerfere if any of them experience more LLC misses compared to when they arenot co-located. Note, however, that performance of an application can degrade formore reasons than LLC contention. Note also that increase in LLC misses beyonda threshold can also be used as the criterion for adding a edge into our graph andall the same machinery can be used. Other researchers have attempted to clas-sify applications using schemes like Stack Distance Completion [4] and AnimalClasses [29]. A partitioning of the interference graph also induces a clustering ofthe applications.17Previous work on addressing the problem of resource contention in multicoresystems has predominantly focused on partitioning the processor caches betweenthe threads that are running on the processors. The most complex solution tothis problem is to provide hardware support for partitioning the processor caches[5][23]. This would be very difficult for a service provider to implement becauseproducing custom processors that support novel functionality if extremely difficultand time-consuming. It would also be difficult to change cache partitioning algo-rithm in hardware, which is problematic because a fixed partitioning may not beoptimal for all co-located process pairs.An alternative to hardware-based cache management is to modify the operatingsystem to manage cache petitioning. The best investigated class of such algorithmsis memory page colouring, which attempts to allocate virtual memory pages tophysical pages in a reserved section of the cache [33][32][27]. Software-basedonline cache management algorithms can rely on hardware counters to optimizecache partitioning [26]. This is problematic because it requires modifying the vir-tual memory system of the operating system, which is extremely difficult[33].Even if we don’t consider the difficulty of implementing cache partitioningmethods, they are still not a complete solution of eliminating contention betweenthreads. As noted by Lin et al.[17], cache partitioning methods can shift contentionaway from the cache to memory bus. Also these methods do not consider othersources of contention that can arise.The method in the most similar to ours is proposed by Zhuravlev et al.[33],which uses LLC miss rate of an application running by itself on a core to scheduleapplications that experience high miss rates on separate cores. This is similar to ourbecause it gathers some a priori knowledge and uses it as a feature for predictinginteractions between unobserved pairs of applications.Another interesting approach is proposed by Herdrich et al.[10]. This mecha-nism simply suggests that to react to performance degradation that may be causedby cache pressure, simply decrease the processor frequency of one of the threadsto reduce the cache pressure. This is clearly a suboptimal use of resources in thescenario that we propose.Another method for addressing this problem is proposed by Mars et al.[19][20].The bubble up system the that they propose uses static analysis of memory ac-18cess patterns of latency-sensitive applications to attempt to predict how sensitivethey would be to co-locating with another, non-latency-sensitive, application. Non-time-critical candidates for pairing are co-located with another application whosesensitivity is known and the amount of degradation they cause are called “bubblescores” and are used to find safe parings. The disadvantage of this method is that itrequires profiling of applications to predict which pairs are safe to co-locate. Yanget al.[30] propose a modification to this scheme which implements dynamic mea-surements of co-location sensitivity. The authors also use use a dynamic methodof halting the non-time-critical appication when pressure on the latency-sensitiveone increases. This online monitoring and measurement uses hardware counters todetect increased contention for shared resources.Another method that uses static profiling to compute workload signature ofuser workloads, then assign them to computational resources is given by Vasic´[28].Like our method, several others[19, 20, 28, 30] also assume that repeated runs ofthe same applications will generate similar system loads and that reusing knownsafe pairings can amortize the effort of finding these safe pairings.To the best of our knowledge, our solution is the only one that treats the usersprocesses as black boxes and simply tries to find similarities based on observed in-teractions. This avoids the complication of gathering metrics on where contentionoccurs to make predictions. It also avoids modifications to operating system sched-ulers and virtual memory systems and even more difficult and costly changes tohardware.4.2 Graph ConstructionWe crated the data set for this experiment by collecting several popular benchmarksuites, including PARSEC, METIS, the NAS benchmark suite provided by NASA.To represent varied user applications, our list of benchmarks included also in-cluded Java, MATLAB, and Python programs. The full list is given in Appendix A.We considered both benchmarks that model modern big data applications such aswould commonly run in a distributed environment and more typical benchmarks.We defined a degradation in performance as follows. Consider applications iand j. Over several executions of application i with no other user process running19Figure 4.1: Process of creating unweighted contention graph. Red pairs wereclassified as interfering, while green ones were not.on the hardware, we measure the average execution time and call it “single-run(i)”.Likewise, let “co-run(i, j)” be the average run time of application i over several runsof while application j is also running on the hardware. Note that this is not equalto “co-run( j,i)”. We define Slowdown Coefficient (SC) for applications i and j asSC(i, j) =co-run(i, j)single-run(i)(4.1)andSC( j, i) =co-run( j, i)single-run( j).We set a threshold T as a limit to the SCS of two applications beyond which weconsidered the slowdown to be unacceptable and the processes to interfere whenco-located. Varying T caused the density of the graph to vary, we investigatedseveral values of T to simulate various level of time-criticality of the jobs runningon the system.The first graph that we constructed to encode the interaction between processeswas an unweighted graph. In this graph we simply added an edge ifmax(SC(i, j),SC( j, i))> T. (4.2)To clarify this, consider applications A, B, C, and D. We run all pairs on the samehardware and calculate the SC according to Equation 4.1, we then insert an edge ifthe condition in Equation 4.2. The resulting graph is shown in Figure 4.1.20Figure 4.2: Process of creating weighted contention graph. The edge weightis the inverse of the SC.We also constructed a weighted graph to encode the interference. The weightof an edge between two nodes prepresenting applications i and j is given bywi j = 1max(SC(i, j),SC( j,i)) if max(SC(i, j),SC( j, i))> T,no edge otherwise (4.3)The intuition behind using the inverse of the maximum SC is that there should be asmaller shortest path between processes that interfere with each other if they inter-fere more. For the same group of application in Figure 4.1, the resulting weightedgraph is shown in Figure 4.2. Note that in most casesSC(i, j) 6= SC( j, i).This may seem strange, but asymmetrical interference has been noted previouslyin literature. Xie and Loh[29] observed that the memory access patterns of someapplications made them insensitive to being paired, while others showed high sen-sitivity to pairing. Co-locating these applications perturbs only one application inthe pair.Our data set had 43 applications, which gives 903 possible pairs. All testswere performed on a system with an Intel Core 2 Duo running at 2.33 GHz and 2GB of RAM. The the machine was running a Fedora 23 Linux operating system.The application were all single-threaded, meaning that there were always enoughcores available to run both applications. This is a simulation of running serveral21Figure 4.3: The interference graph generated when setting T=2.5.containers in which user applications run on one physical compute node and havingthe sum of the cores reported by each container be the same as the number of coreson the compute node.The interference graph generated with T = 2.5 is shown in Figure 4.3. As wecan see, several applications interfere with almost all others, while many applica-tions only interfere with a few and can easily be co-located.22Figure 4.4: Slowdown Coefficients distribution of a typical application.4.3 ResultsAfter co-locating and running all the pairs of applications, we first wanted to seethe distribution of SCS. We chose a typical application, and plotted a histogramof its SCS when co-located with all other applications in the data set in Figure 4.4.For ease of exposition, we binned these slowdown coefficients into intervals of size0.5.23Studying many such histograms showed us that the SC values lay mostly be-tween one and five. To simulate many real-world situations in which differentlevels of slowdown may be acceptable, we tested our machine learning algorithmon graphs created with the SC threshold T set to 1.5, 2, 2.5, and 3. Analyzing moreextreme values were not interesting because in the case of T < 1.5 nearly all edgeswere present in the graph, while with T > 3 would result in a graph with nearlyno edges. In both of these cases, accurate prediction is trivially simple since in thecase of a very sparse graph a predictor that always predicts no edge can performvery well. Similarly, in a very dense graph, a predictor that always predicts an edgeperforms very well. Where our algorithm performs better than these predictors itdemonstrates that it is making useful predictions. As in the result in Section 3.2,KNN was the best classifier. The results for all the values of T considered and thenumber of edges that appeared in the graph are given in Table 4.1. As we can see,the algorithm gives statistically significant predictions at T = 2 and T = 2.5. Ta-SC Threshold Number of Edges Probability Prediction Predictionin Graph of Edge Error Rate Error Rate75% 90%1.5 694 0.76 0.75 0.362 327 0.36 0.45 0.242.5 118 0.14 0.24 0.123 88 0.097 0.20 0.094Table 4.1: Density of graph and CER for several choices of SC threshold T .CER is the fraction of correct predictions over the test set.ble 4.1 also shows that after observing 75% of the pairs the model does not performbetter that the trivial classifier. After observing 90%, however, it performs better.4.3.1 Feature DistributionAs above, we can examine feature distributions to show which features were bestfor predicting which processes will interfere when co-located. Figure 4.5 shows thedistribution of common neighbours and a Adamic/Adar score with red dots beingpairs that interfered and blue dots being pairs that did not. As in the collaborationnetwork in Section 3.2, the two features were highly correlated. An interesting in-24Figure 4.5: Scatter plot of the Adamic/Adar score and number of commonneighbours for the process interference graph. Red points are pairs thatinterfered and blue points are pairs that did not.sight is that neither feature was a good predictor of interference unlike in the authorcollaboration application where very few author pairs with common neighbours didnot go on to collaborate, compare Figure 3.1. The Katz score and unweighted pathalso behaved as above.In this application unweighted shortest path, which is a novel contribution ofthis work, was a powerful classifier; more so than in the authorship collaborationapplication. The distribution of unweighted and weighted shortest paths for thegraphs are shown in Figure 4.6. The pairs towards the left the image are morelikely to interfere than the nodes towards the bottom. This justifies the novel useof the weighted shortest path as a predictor of interference between processes.4.4 ConclusionThis work proposes a novel application of partially-observed graphs to modelinginterference between processes running on the same physical hardware. We ran acollection of benchmarks on a computer singly and in pairs and modeled interfer-25Figure 4.6: Scatter plot of the weighted and unweighted shortest path for theprocess interference graph. Red points are pairs that interfered and bluepoints are pairs that did not.ence in pairs of processes as a large increase in the execution time of the processwhen co-located. We used a machine learning algorithm to predict which edgeswould appear in the interference graph, with promising results.This method should be considered a framework for predicting interference be-tween processes since the abstraction is general enough to encode any pairwiseinteraction of processes as a graph, then use the machine learning algorithms topredict the outcome of new interactions. For example increased LLC misses oreven a combination of LLC miss and execution time increases can be encoded asan edge in the graph. This is a tradeoff between ease of implementing the requiredinstrumentation to detect contention and a potential increase in the accuracy ofpredictions. Further research remains for finding good combinations of measure-ments.Using the interference graph as an abstraction also enables us to use graphalgorithms to interpret the observed interference data. For example, partitioningthe interference graph by using a minimum cutting algorithm induces a clustering26of the applications into groups that interfere with each other. Bansal, Blum, andChawla [2] also propose a method of clustering items on a graph by partitions thatmaximize similarity of items that inside the partitions. This would be a natural fitfor our graph abstraction of process interference. Likewise colourings of the graphindicate the number of compute nodes required to simultaneously schedule a set ofprocesses with no interference.A natural direction for future work would be to attempt to determine an algo-rithm for running applications against other to determine a co-location scheme withminimal disruption, since users may not accept a datacenter running their applica-tions with interference to determine an optimal scheme. Intuitively a hierarchicalclustering using a series of graph cuts may be a direction to explore since exploringthese clusters as a tree may yield a good co-location scheme in few tests. If the ma-trix completion methods discussed in Section 2.3 are effective for this applicationthe accuracy of predictions could be bounded by the number of observations.To the best of our knowledge, ours is the first method for predicting interfer-ence that does not require modifications to the operating system scheduler, virtualmemory system, or hardware. Our method also does not require profiling of userapplications. This makes it easier to implement in an existing system and it wouldmake increasingly better predictions about which applications to co-locate.27Chapter 5ConclusionIn this work we applied the partially-observed graph abstraction commonly used inlink prediction on social networks to two novel applications with good results. Forboth applications we encoded interactions between objects as edges in weightedand unweighted graphs. We extracted some topographical features from thesegraphs and used them for a two-class classification problem in which we attemptedto predict whether unobserved pairs of nodes would interact. We used 10-foldcross-validation to evaluate several model for this prediction task and found thatKNN was the best classifier.The application is predicting whether authors in a online database would co-author papers together. We modeled co-authorships as edges in a graph and pre-dicted whether unobserved pairs of authors would interact. We achieved predictionerror rate of less than 3%. Our study showed that the neighbourhood features arehighly correlated and all but one can be removed without significantly changingprediction accuracy. The Katz score is a very powerful predictor, but is compu-tationally very expensive. The novel contribution of using weighted shortest pathis justified for this application. When the unweighted shortest path between pairsof authors is the same, pairs that have a smaller weighted shortest path betweenthem are more likely to collaborate. The graph in this application is very sparseand highly structured, making prediction effective.The next application is predicting whether two processes running on the samepiece of hardware will interfere with each other by competing for shared resources.28We modeled slowdown in the processes when co-located on the same hardware asedges in a graph. The resulting predictions accuracy was also promising. Thismodel is flexible enough to encode other measures of slowdown as edges on thegraph, for example a combination of increased LLC misses and increased executiontime. Modeling the interactions between processes as a graph also allows us to usegraph algorithms for processing this data. For example, a minimum cut of thisgraph is a clustering of processes that interfere. Unlike all previous methods forpredicting process inter-process interference, our method does not require complexmodifications to the operating system or the hardware to implement. This meansthat it can be easily implemented in a datacenter without major modifications.The prediction for the authorship collaboration was very effective because thegraph is made up of many densely connected communities. This means that theunderlying graph is sparse and highly structured. The process interference graph,does not display this structure, which makes prediction more difficult. This canalso be seen in the feature scatter plots in Section 4.3, which are not as neatlydivided between conflicting and non-conflicting pairs as in Section 3.2. Making amuch larger process interference graph and varying the interference threshold toinvestigate if this graph exhibits similar structure to the authorship collaborationgraph may reveal whether prediction accuracy can be improved.29Bibliography[1] L. A. Adamic and E. Adar. Friends and neighbors on the web. Socialnetworks, 25(3):211–230, 2003. → pages 6[2] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. MachineLearning, 56(1-3):89–113, 2004. → pages 27[3] E. J. Cande`s and B. Recht. Exact matrix completion via convexoptimization. Foundations of Computational mathematics, 9(6):717–772,2009. → pages 9[4] D. Chandra, F. Guo, S. Kim, and Y. Solihin. Predicting inter-thread cachecontention on a chip multi-processor architecture. In 11th InternationalSymposium on High-Performance Computer Architecture, pages 340–351.IEEE, 2005. → pages 17[5] S. Cho and L. Jin. Managing distributed, shared l2 caches through os-levelpage allocation. In Proceedings of the 39th Annual IEEE/ACM InternationalSymposium on Microarchitecture, pages 455–468. IEEE Computer Society,2006. → pages 3, 18[6] O. De Vel, A. Anderson, M. Corney, and G. Mohay. Mining e-mail contentfor author identification forensics. ACM Sigmod Record, 30(4):55–64, 2001.→ pages 10[7] J. Dean and S. Ghemawat. Mapreduce: simplified data processing on largeclusters. Communications of the ACM, 51(1):107–113, 2008. → pages 3, 16[8] M. A. Hasan and M. J. Zaki. A survey of link prediction in social networks.In C. C. Aggarwal, editor, Social Network Data Analytics, pages 243–275.Springer US, 2011. ISBN 978-1-4419-8461-6.doi:10.1007/978-1-4419-8462-3 9. URLhttp://dx.doi.org/10.1007/978-1-4419-8462-3 9. → pages 1, 5, 7, 1030[9] M. A. Hasan, V. Chaoji, S. Salem, and M. Zaki. Link prediction usingsupervised learning. In In Proc. of SDM 06 workshop on Link Analysis,Counterterrorism and Security, 2006. → pages 5[10] A. Herdrich, R. Illikkal, R. Iyer, D. Newell, V. Chadha, and J. Moses.Rate-based qos techniques for cache/memory in cmp platforms. InProceedings of the 23rd international conference on Supercomputing, pages479–488. ACM, 2009. → pages 18[11] M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly. Dryad: distributeddata-parallel programs from sequential building blocks. In ACM SIGOPSOperating Systems Review, volume 41, pages 59–72. ACM, 2007. → pages16[12] G. Jeh and J. Widom. Simrank: a measure of structural-context similarity. InProceedings of the eighth ACM SIGKDD international conference onKnowledge discovery and data mining, pages 538–543. ACM, 2002. →pages 7[13] V. Kalofolias, X. Bresson, M. M. Bronstein, and P. Vandergheynst. Matrixcompletion on graphs. CoRR, abs/1408.1717, 2014. URLhttp://arxiv.org/abs/1408.1717. → pages 2, 8[14] L. Katz. A new status index derived from sociometric analysis.Psychometrika, 18(1):39–43, 1953. ISSN 0033-3123.doi:10.1007/BF02289026. URL http://dx.doi.org/10.1007/BF02289026. →pages 7[15] F. Kira´ly and R. Tomioka. A combinatorial algebraic approach for theidentifiability of low-rank matrix completion. arXiv preprintarXiv:1206.6470, 2012. → pages 9[16] D. Liben-Nowell and J. Kleinberg. The link-prediction problem for socialnetworks. Journal of the American society for information science andtechnology, 58(7):1019–1031, 2007. → pages 1, 5, 10[17] J. Lin, Q. Lu, X. Ding, Z. Zhang, X. Zhang, and P. Sadayappan. Gaininginsights into multicore cache partitioning: Bridging the gap betweensimulation and real systems. In 2008 IEEE 14th International Symposium onHigh Performance Computer Architecture, pages 367–378. IEEE, 2008. →pages 1831[18] L. L and T. Zhou. Link prediction in complex networks: A survey. PhysicaA: Statistical Mechanics and its Applications, 390(6):1150 – 1170, 2011.ISSN 0378-4371. doi:http://dx.doi.org/10.1016/j.physa.2010.11.027. URLhttp://www.sciencedirect.com/science/article/pii/S037843711000991X. →pages 1, 5, 7, 10[19] J. Mars, L. Tang, R. Hundt, K. Skadron, and M. L. Soffa. Bubble-up:Increasing utilization in modern warehouse scale computers via sensibleco-locations. In Proceedings of the 44th annual IEEE/ACM InternationalSymposium on Microarchitecture, pages 248–259. ACM, 2011. → pages 18,19[20] J. Mars, L. Tang, K. Skadron, M. L. Soffa, and R. Hundt. Increasingutilization in modern warehouse-scale computers using bubble-up. IEEEMicro, 32(3):88–99, 2012. → pages 18, 19[21] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citationranking: bringing order to the web. 1999. → pages 6, 7[22] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel,M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos,D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn:Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011. → pages 8[23] M. K. Qureshi and Y. N. Patt. Utility-based cache partitioning: Alow-overhead, high-performance, runtime mechanism to partition sharedcaches. In Proceedings of the 39th Annual IEEE/ACM InternationalSymposium on Microarchitecture, pages 423–432. IEEE Computer Society,2006. → pages 3, 17, 18[24] B. Recht. A simpler approach to matrix completion. Journal of MachineLearning Research, 12(Dec):3413–3430, 2011. → pages 9[25] E. Stamatatos. A survey of modern authorship attribution methods. Journalof the American Society for information Science and Technology, 60(3):538–556, 2009. → pages 10[26] G. E. Suh, S. Devadas, and L. Rudolph. A new memory monitoring schemefor memory-aware scheduling and partitioning. In High-PerformanceComputer Architecture, 2002. Proceedings. Eighth International Symposiumon, pages 117–128. IEEE, 2002. → pages 3, 1832[27] G. Taylor, P. Davies, and M. Farmwald. The tlb slicea low-cost high-speedaddress translation mechanism. ACM SIGARCH Computer ArchitectureNews, 18(2SI):355–363, 1990. → pages 18[28] N. Vasic´, D. Novakovic´, S. Miucˇin, D. Kostic´, and R. Bianchini. Dejavu:accelerating resource allocation in virtualized environments. In ACMSIGARCH computer architecture news, volume 40, pages 423–436. ACM,2012. → pages 19[29] Y. Xie and G. Loh. Dynamic classification of program memory behaviors incmps. In the 2nd Workshop on Chip Multiprocessor Memory Systems andInterconnects. Citeseer, 2008. → pages 3, 17, 21[30] H. Yang, A. Breslow, J. Mars, and L. Tang. Bubble-flux: Precise online qosmanagement for increased utilization in warehouse scale computers. InACM SIGARCH Computer Architecture News, volume 41, pages 607–618.ACM, 2013. → pages 19[31] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica. Spark:cluster computing with working sets. HotCloud, 10:10–10, 2010. → pages3, 16[32] X. Zhang, S. Dwarkadas, and K. Shen. Towards practical pagecoloring-based multicore cache management. In Proceedings of the 4thACM European conference on Computer systems, pages 89–102. ACM,2009. → pages 18[33] S. Zhuravlev, S. Blagodurov, and A. Fedorova. Addressing shared resourcecontention in multicore processors via scheduling. In ACM Sigplan Notices,volume 45, pages 129–142. ACM, 2010. → pages 1833Appendix AList of BenchmarksThe benchmarks suites used in the experiments in Chapter 4 can be found at:• METIS https://pdos.csail.mit.edu/archive/metis/• PARSEC http://parsec.cs.princeton.edu• NAS Parallel https://www.nas.nasa.gov/publications/npb.html• NAS OMP https://github.com/wzzhang-HIT/NAS-Parallel-Benchmark/tree/master/NPB3.3-OMP• NAS Java https://www.nas.nasa.gov/publications/npb.html• HiBench https://github.com/intel-hadoop/HiBench• LAPACK http://www.netlib.org/lapack• Whetstone http://www.roylongbottom.org.uk/whetstone.htm• Python 3 Benchmarks https://benchmarksgame.alioth.debian.org/u64q/python.html• Dhrystone https://github.com/Keith-S-Thompson/dhrystone/tree/master/v2.134
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Partially-observed graph abstractions for authorship...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Partially-observed graph abstractions for authorship identification and process interference prediction Plesch, Rudolf 2017
pdf
Page Metadata
Item Metadata
Title | Partially-observed graph abstractions for authorship identification and process interference prediction |
Creator |
Plesch, Rudolf |
Publisher | University of British Columbia |
Date Issued | 2017 |
Description | Pairwise interactions between objects can be modeled as a graph, which is a set of nodes and edges that each connect a pair of nodes. We consider the problem of predicting whether edges exist between nodes based on other pairs of nodes that we have observed. From a partially-observed graph we extract several neighbourhood and path features, then evaluate several machine learning algorithms for predicting whether edges will exist between unobserved nodes. K-Nearest Neighbours was found to be the best classifier. We propose the novel use of path on a weighted graph as a feature used for prediction. We apply this abstraction to predicting collaboration between authors in an on-line publication database. The unweighted graph contains an edge if two authors collaborated and the weighted graph encodes the number of collaborations. Prediction error rates were less than 3% under ten-fold cross-validation. We also apply this abstraction to predicting whether processes running on the same hardware will compete for resources. The unweighted graph contains an edge if a process executed in more time than when running with another than by itself. The weighted graph had an edge weight that was the increase in execution time. Prediction error rates were less than 14% under ten-fold cross-validation. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2017-03-02 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0343049 |
URI | http://hdl.handle.net/2429/60773 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2017-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2017_may_plesch_rudolf.pdf [ 1.21MB ]
- Metadata
- JSON: 24-1.0343049.json
- JSON-LD: 24-1.0343049-ld.json
- RDF/XML (Pretty): 24-1.0343049-rdf.xml
- RDF/JSON: 24-1.0343049-rdf.json
- Turtle: 24-1.0343049-turtle.txt
- N-Triples: 24-1.0343049-rdf-ntriples.txt
- Original Record: 24-1.0343049-source.json
- Full Text
- 24-1.0343049-fulltext.txt
- Citation
- 24-1.0343049.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0343049/manifest