BU-CE-1001: PDF
A Discretization Method based on Maximizing the Area Under ROC Curve
We present a new discretization method based on Area under ROC Curve (AUC) measure. Maximum Area under ROC Curve Based Discretization (MAD) is a global, static and supervised discretization method. It discretizes a continuous feature in a way that the AUC based only on that feature is to be maximized. The proposed method is compared with alternative discretization methods such as Entropy-MDLP (Minimum Description Length Principle) which is known as one of the best discretization methods, Fixed Frequency Discretization (FFD), and Proportional Discretization (PD). FFD and PD are proposed recently and designed for nave Bayes learning. Evaluations are performed in terms of M-Measure, an AUC based metric for multi-class classification, and accuracy values obtained from nave Bayes and Aggregating One-Dependence Estimators (AODE) algorithms by using real world datasets. Empirical results show that our method is a candidate to be a good alternative to other discretization methods.Keywords: Data Mining, Discretization, Area under ROC Curve
BU-CE-1002: PDF
Causality Analysis in Biological Networks (Ph. D. Thesis)
Systems biology is a rapidly emerging field, shaped in the last two decades or so, which promises understanding and curing several complex diseases such as cancer. In order to get an insight about the system - specifically the molecular network in the cell - we need to work on following four fundamental aspects: experimental and computational methods to gather knowledge about the system, mathematical models for representing the knowledge, analysis methods for answering questions on the model, and software tools for working on these. In this thesis, we propose new approaches related to all these aspects.In this thesis, we define new terms and concepts that helps us to analyze cellular processes, such as positive and negative paths, upstream and downstream relations, and distance in process graphs. We propose algorithms that will search for functional relations between molecules and will answer several biologically interesting questions related to the network, such as neighborhoods, paths of interest, and common targets or regulators of molecules.
In addition, we introduce ChiBE, a pathway editor for visualizing and analyzing BioPAX networks. The tool converts BioPAX graphs to drawable process diagrams and provides the mentioned novel analysis algorithms. Users can query pathways in Pathway Commons database and create sub-networks that focus on specific relations of interest.
We also describe a microarray data analysis component, PATIKAmad, built into ChiBE and PATIKAweb, which integrates expression experiment data with networks. PATIKAmad helps those tools to represent experiment values on network elements and to search for causal relations in the network that potentially explain dependent expressions. Causative path search depends on the presence of transcriptional relations in the model, which however is underrepresented in most of the databases. This is mainly due to insufficient knowledge in the literature.
We finally propose a method for identifying and classifying modulators of transcription factors, to help complete the missing transcriptional relations in the pathway databases. The method works with large amount of expression data, and looks for evidence of modulation for triplets of genes, i.e. modulator - factor - target. Modulator candidates are chosen among the interacting proteins of transcription factors. We expect to observe that expression of the target gene depends on the interaction between factor and modulator. According to the observed dependency type, we further classify the modulation. When tested, our method finds modulators of Androgen Receptor; our top-scoring result modulators are supported by other evidence in the literature. We also observe that the modulation event and modulation type highly depend on the specific target gene. This finding contradicts with expectations of molecular biology community who often assume a modulator has one type of effect regardless of the target gene.
Keywords: Computational biology, bioinformatics, systems biology, pathway informatics, causality analysis.
BU-CE-1003: PDF
Risk Estimation by Maximizing the Area under ROC Curve
Risks exist in many different domains; medical diagnoses, financial markets, fraud detection and insurance policies are some examples. Various risk measures and risk estimation systems have hitherto been proposed and this paper suggests a new risk estimation method. Risk estimation by maximizing the area under a receiver operating characteristics (ROC) curve (REMARC) defines risk estimation as a ranking problem. Since the area under an ROC curve (AUC) is related to measuring the quality of ranking, REMARC aims to maximize the AUC value on a single feature basis to obtain the best ranking possible on each feature. For a given categorical feature, we prove a sufficient condition that any function must satisfy to achieve the maximum AUC. Continuous features are also discretized by a method that uses AUC as a metric. Then, a heuristic is used to extend this maximization to all features of a dataset. REMARC can handle missing data, binary classes and continuous and nominal feature values. The REMARC method does not only estimate a single risk value, but also analyzes each feature and provides valuable information to domain experts for decision making. REMARC's performance is evaluated with many datasets in the UCI repository by using different state-of-the-art algorithms such as Support Vector Machines, nave Bayes, decision trees and boosting methods. Evaluations of the AUC metric show REMARC achieves predictive performance significantly better compared with other machine learning classification methods and is also faster than most of them.Keywords: Risk Estimation, AUC Maximization, AUC, Ranking.
BU-CE-1004: PDF
A Fuzzy Logic-based Approach for Enhancing Depth Perception in Computer Graphics (M. Sc. Thesis)
Rapid progress in 3D rendering and display technologies brings the problem of better visualization of 3D content. Providing correct depth information and enabling the user to perceive the spatial relationship between the objects is one of the main concerns during the visualization of 3D content.In this thesis, we introduce a solution that can either be used for automatically enhancing the depth perception of a given scene, or as a component that suggests suitable rendering methods to application developers.
In this novel solution, we propose a framework that decides on the suitable depth cues for a given 3D scene and the rendering methods which provide these cues. First, the system calculates the importance of each depth cue using a fuzzy logic based algorithm which considers the user's tasks in the application and the spatial layout of the scene. Then, a knapsack model is constructed to keep the balance between the rendering costs of the graphical methods that provide these cues and their contribution to depth perception. This cost-prot analysis step selects the proper rendering methods for the given scene.
In this work, we also present several objective and subjective experiments which show that our automated depth perception enhancement system is statistically (p < 0.05) better than the other method selection techniques that are tested.
Keywords: Depth perception, depth cues, cue combination, computer graphics, perceptually-aware rendering
BU-CE-1005: PDF
From Audiences to Mobs: Crowd Simulation with Psychological Factors (Ph. D. Thesis)
Crowd simulation has a wide range of application areas such as biological and social modeling, military simulations, computer games and movies. Simulating the behavior of animated virtual crowds has been a challenging task for the computer graphics community. As well as the physical and the geometrical aspects, the semantics underlying the motion of real crowds inspire the design and implementation of virtual crowds. Psychology helps us understand the motivations of the individuals constituting a crowd. There has been extensive research on incorporating psychological models into the simulation of autonomous agents. However, in our study, instead of the psychological state of an individual agent as such, we are interested in the overall behavior of the crowd that consists of virtual humans with various psychological states. For this purpose, we incorporate the three basic constituents of affect: personality, emotion and mood. Each of these elements contribute variably to the emergence of different aspects of behavior. We thus examine, by changing the parameters, how groups of people with different characteristics interact with each other, and accordingly, how the global crowd behavior is influenced.In the social psychology literature, crowds are classified as mobs and audiences. Audiences are passive crowds whereas mobs are active crowds with emotional, irrational and seemingly homogeneous behavior. In this thesis, we examine how audiences turn into mobs and simulate the common properties of mobs to create collective misbehavior. So far, crowd simulation research has focused on panicking crowds among all types of mobs. We extend the state of the art to simulate different types of mobs based on the taxonomy. We demonstrate various scenarios that realize the behavior of distinct mob types.
Our model is built on top of an existing crowd simulation system, HiDAC (High-Density Autonomous Crowds). HiDAC provides us with the physical and low-level psychological features of crowds. The user normally sets these parameters to model the non-uniformity and diversity of the crowd. In our work, we free the user of the tedious task of low-level parameter tuning, and combine all these behaviors in distinct psychological factors. We present the results of our experiments on whether the incorporation of a personality model into HiDAC was perceived as intended.
Keywords: Crowd simulation, autonomous agents, simulation of affect, crowd taxonomy, mob behavior.
BU-CE-1006: PDF
Color Graph Representation for Structural Analysis of Tissue Images (M. Sc. Thesis)
Computer aided image analysis tools are becoming increasingly important in automated cancer diagnosis and grading. They have the potential of assisting pathologists in histopathological examination of tissues, which may lead to a considerable amount of subjectivity. These analysis tools help reduce the subjectivity, providing quantitative information about tissues. In literature, it has been proposed to implement such computational tools using different methods that represent a tissue with different set of image features. One of the most commonly used methods is the structural method that represents a tissue quantifying the spatial relationship of its components. Although previous structural methods lead to promising results for different tissue types, they only use the spatial relations of nuclear tissue components without considering the existence of different components in a tissue. However, additional information that could be obtained from other components of the tissue has an importance in better representing the tissue, and thus, in making more reliable decisions.This thesis introduces a novel structural method to quantify histopathological images for automated cancer diagnosis and grading. Unlike the previous structural methods, it proposes to represent a tissue considering the spatial distribution of different tissue components. To this end, it constructs a graph on multiple tissue components and colors its edges depending on the component types of their end points. Subsequently, a new set of structural features is extracted from these "color graphs" and used in the classification of tissues. Experiments conducted on 3236 photomicrographs of colon tissues that are taken from 258 different patients demonstrate that the color graph approach leads to 94.89 percent training accuracy and 88.63 percent test accuracy. Our experiments also show that the introduction of color edges to represent the spatial relationship of different tissue components and the use of graph features defined on these color edges significantly improve the classification accuracy of the previous structural methods.
Keywords: Medical image analysis, graph theory, histopathological image analysis, cancer diagnosis and grading
BU-CE-1007: PDF
Risk Estimation by Maximizing Area Under Receiver Operating Characteristics Curve with Application to Cardiovascular Surgery (M. Sc. Thesis)
Risks exist in many different domains; medical diagnoses, financial markets, fraud detection and insurance policies are some examples. Various risk measures and risk estimation systems have hitherto been proposed and this thesis suggests a new risk estimation method. Risk estimation by maximizing the area under a Receiver Operating Characteristics (ROC) curve (REMARC) defines risk estimation as a ranking problem. Since the area under ROC curve (AUC) is related to measuring the quality of ranking, REMARC aims to maximize the AUC value on a single feature basis to obtain the best ranking possible on each feature. For a given categorical feature, we prove a sufficient condition that any function must satisfy to achieve the maximum AUC. Continuous features are also discretized by a method that uses AUC as a metric. Then, a heuristic is used to extend this maximization to all features of a dataset. REMARC can handle missing data, binary classes and continuous and nominal feature values. The REMARC method does not only estimate a single risk value, but also analyzes each feature and provides valuable information to domain experts for decision making. The performance of REMARC is evaluated with many datasets in the UCI repository by using different state-of-the-art algorithms such as Support Vector Machines, nave Bayes, decision trees and boosting methods. Evaluations of the AUC metric show REMARC achieves predictive performance significantly better compared with other machine learning classification methods and is also faster than most of them.In order to develop new risk estimation framework by using the REMARC method cardiovascular surgery domain is selected. The TurkoSCORE project is used to collect data for training phase of the REMARC algorithm. The predictive performance of REMARC is compared with one of the most popular cardiovascular surgical risk evaluation method, called EuroSCORE. EuroSCORE is evaluated on Turkish patients and it is shown that EuroSCORE model is insufficient for Turkish population. Then, the predictive performances of EuroSCORE and TurkoSCORE that uses REMARC for prediction are compared. Empirical evaluations show that REMARC achieves better prediction than EuroSCORE on Turkish patient population.
Keywords: Risk Estimation, AUC Maximization, AUC, Ranking, Cardiovascular Operation Risk Evaluation
BU-CE-1008: PDF
Real-Time Crowd Simulation in Virtual Urban Environments using Adaptive Grids (M. Sc. Thesis)
Crowd simulation is a relatively new research area, attracting increasing attention from both academia and industry. This thesis proposes Adaptive Grids, a novel hybrid approach for controlling the behavior of agents in a virtual crowd. In this approach, the motion of each agent within the crowd is planned considering both global and local path planning strategies. For global path planning, a cellular adaptive grid is constructed from a regular navigation map that represents the 2-D topology of the simulation terrain. A navigation graph with efficient size is then pre-computed from the adaptive grid for each possible agent goal. Finally, the navigation graph is used to generate a potential field on the adaptive grid by using the connectivity information of the irregular cells. Global path planning per agent has constant time complexity. For local path planning, Helbing Traffic-Flow model is used to avoid obstacles and agents. Potential forces are then applied on each agent considering the local and global decisions of the agent, while providing each agent the freedom to act independently.Keywords: Crowd Simulation, Real-Time Animation, Motion Planning, Urban Visualization.
BU-CE-1009: PDF
Novelty Detection in Topic Tracking (M. Sc. Thesis)
News portals provide many services to the news consumers such as information retrieval, personalized information filtering, summarization and news clustering. Additionally, many news portals using multiple sources enable their users to evaluate developments from different perspectives by richening the content. However, increasing number of sources and incoming news makes it difficult for news consumers to find news of their interest in news portals. Different types of organizational operations are applied to ease browsing over the news for this reason. New event detection and tracking (NEDT) is one of these operations which aims to organize news with respect to the events that they report. NEDT may not also be enough by itself to satisfy the news consumers' needs because of the repetitions of information that may occur in the tracking news of a topic due to usage of multiple sources. In this thesis, we investigate usage of novelty detection (ND) in tracking news of a topic. For this aim, we built a Turkish ND experimental collection, BilNov, consisting of 59 topics with an average of 51 tracking news. We propose usage of three methods; cosine similarity-based ND method, language model-based ND method and cover coefficient-based ND method. Additionally, we experiment on category-based threshold learning which has not been worked on previously in ND literature. We also provide some experimental pointers for ND in Turkish such as restriction of document vector lengths and smoothing methods. Finally, we experiment on TREC Novelty Track 2004 dataset. Experiments conducted by using BilNov show that language model-based ND method outperforms other two methods significantly and category-based threshold learning has promising results when compared to general threshold learning.Keywords: Novelty detection, Topic tracking
BU-CE-1010: PDF
Noun Phrase Chunker for Turkish Using Dependency Parser (M. Sc. Thesis)
Noun phrase chunking is a sub-category of shallow parsing that can be used for many natural language processing tasks. In this thesis, we propose a noun phrase chunker system for Turkish texts. We use a weighted constraint dependency parser to represent the relationship between sentence components and to determine noun phrases.The dependency parser uses a set of hand-crafted rules which can combine morphological and semantic information for constraints. The rules are suitable for handling complex noun phrase structures because of their flexibility. The developed dependency parser can be easily used for shallow parsing of all phrase types by changing the employed rule set.
The lack of reliable human tagged datasets is a significant problem for natural language studies about Turkish. Therefore, we constructed the first noun phrase dataset for Turkish. According to our evaluation results, our noun phrase chunker gives promising results on this dataset.
The correct morphological disambiguation of words is required for the correctness of the dependency parser. Therefore, in this thesis, we propose a hybrid morphological disambiguation technique which combines statistical information, hand-crafted grammar rules, and transformation based learning rules. We have also constructed a dataset for testing the performance of our disambiguation system. According to tests, the disambiguation system is highly effective.
Keywords: Natural Language Processing, Noun Phrase Chunker, Turkish, Shallow Parsing, Morphological Disambiguation.
BU-CE-1011: PDF
BilVideo-7: Video Parsing, Indexing and Retrieval (Ph. D. Thesis)
Video indexing and retrieval aims to provide fast, natural and intuitive access to large video collections. This is getting more and more important as the amount of video data increases at a stunning rate. This thesis introduces the BilVideo-7 system to address the issues related to video parsing, indexing and retrieval.BilVideo-7 is a distributed and MPEG-7 compatible video indexing and retrieval system that supports complex multimodal queries in a unified framework. The video data model is based on an MPEG-7 profile which is designed to represent the videos by decomposing them into Shots, Keyframes, Still Regions and Moving Regions. The MPEG-7 compatible XML representations of videos according to this profile are obtained by the MPEG-7 compatible video feature extraction and annotation tool of BilVideo-7, and stored in a native XML database. Users can formulate text, color, texture, shape, location, motion and spatio-temporal queries on an intuitive, easy-to-use visual query interface, whose composite query interface can be used to formulate very complex queries containing any type and number of video segments with their descriptors and specifying the spatio-temporal relations between them. The multi-threaded query processing server parses incoming queries into subqueries and executes each subquery in a separate thread. Then, it fuses subquery results in a bottom-up manner to obtain the final query result and sends the result to the originating client. The whole system is unique in that it provides very powerful querying capabilities with a wide range of descriptors and multimodal query processing in an MPEG-7 compatible interoperable environment.
Keywords: MPEG-7, video processing, video indexing, video retrieval, multimodal query processing
BU-CE-1012: PDF
Naming Faces On The Web (M. Sc. Thesis)
In this study, we introduce a method to name less-frequently appearing people on the web via naming frequently appearing ones first. Current image search engines are widely used for querying a person, however; retrievals are based on textual content; therefore, the results are not satisfactory. On the other hand, although; face recognition is a long standing problem; it is tested for limited sizes and successful results are acquired just for face images captured under controlled environments. Faces on the web, contrarily are huge in amount and vary in pose, illumination, occlusion and facial attributes. Recent researches on the area, suggest not to use simply the visual or textual content alone, but to combine them both. With this approach, face recognition problem is simplified to a face-name association problem.Following these approaches, in our method textual and visual information is combined to name faces. We divide the problem into two sub problems, first the more frequently appearing faces, then the less-frequently appearing faces on the web images are named. A supervised algorithm is used for naming a specified number of categories belonging to more frequently appearing faces. The faces that are not matched with any category are then considered to be the less-frequently appearing faces and labeled using the textual content. We extracted all the names from textual contents, and then eliminate the ones used to label frequentlyappearing faces before. The remaining names are the candidate categories for lessfrequently appearing faces. Each detected less-frequently appearing face finally matched to the names extracted from their corresponding textual content. In order to prune the irrelevant face images, finally, the most similar faces among this collection are found to be matched with their corresponding category.
In our experiments, the method is applied on two different datasets. Both datasets are constructed from the images captured in realistic environments, varying in pose, illumination, facial expressions, occlusions and etc. The results of the experiments proved that the combination of textual and visual contents on realistic face images outperforms the methods that use either one of them. Besides, handling the face recognition problem as a face-name association, improves the results for the face images collected from uncontrolled environments.
Keywords: Face recognition, face detection, face retrieval, face naming, naming faces, SVM, SIFT.
BU-CE-1013: PDF
Particle Based Modeling and Simulation of Natural Phenomena (Ph. D. Thesis)
This thesis is about modeling and simulation of fluids and cloth-like deformable objects by the physically-based simulation paradigm. Simulated objects are modeled with particles and their interaction with each other and the environment is defined by particle-to-particle forces. We propose several improvements over the existing particle simulation techniques. Neighbor search algorithms are crucial for the performance efficiency and robustness of a particle system. We present a sorting-based neighbor search method which operates on a uniform grid, and can be parallelizable. We improve upon the existing fluid surface generation methods so that our method captures surface details better since we consider the relative position of fluid particles to the fluid surface. We investigate several alternatives of particle interaction schema (i.e. Smoothed Particle Hydrodynamics, the Discrete Element Method, and Lennard-Jones potential) for the purpose of defining fluid-fluid, fluid-cloth, fluid-boundary interaction forces. We also propose a practical way to simulate knitwear and its interaction with fluids. We employ capillary pressure-based forces to simulate the absorption of fluid particles by knitwear. We also propose a method to simulate the flow of miscible fluids. Our particle simulation system is implement to exploit parallel computing capabilities of the commodity computers. Specifically, we implemented the proposed methods on multicore CPUs and programmable graphics boards. The experiments show that our method is computationally efficient and produces realistic results.Keywords: Physically-based simulation, particle system, fluid simulation, neighbor search algorithms, cloth animation, free fluid surface rendering, boundary conditions, mass-spring systems, shared memory parallel computing, GPU, CUDA.
BU-CE-1014: PDF
A Framework for the Use of Wireless Sensor Networks in Forest Fire Detection and Monitoring (M. Sc. Thesis)
Wireless sensor networks have a broad range of applications in the category of environmental monitoring. In this thesis, we consider the problem of forest fire detection and monitoring as a possible application area of wireless sensor networks. Forest fires are one of the main causes of environmental degradation nowadays. The current surveillance systems for forest fires lack in supporting real-time monitoring of every point of the region at all time and early detection of the fire threats. Solutions using wireless sensor networks, on the other hand, can gather temperature and humidity values from all points of field continuously, day and night, and, provide fresh and accurate data to the fire fighter center quickly. However, sensor networks and nodes face serious obstacles like limited energy resources and high vulnerability to harsh environmental conditions, that have to be considered carefully.In our study, we propose a comprehensive framework for the use of wireless sensor networks for forest fire detection and monitoring. Our framework includes proposals for the wireless sensor network architecture, clustering and communication protocols, and environment/season-aware activity-rate selection schemes to detect the fire threat as early as possible and yet consider the energy consumption of the sensor nodes and the physical conditions that may hinder the activity of the network. We also implemented a simulator to validate and evaluate our proposed framework, which is using an external fire simulator library. We did extensive simulation experiments and observed that our framework can provide fast reaction to forest fires while also consuming energy efficiently.
Keywords: Wireless sensor networks, forest fire detection, fire forecast.
BU-CE-1015: PDF
Efficiency and Effectiveness of XML Keyword Search Using a Full Element Index (M. Sc. Thesis)
In the last decade, both the academia and industry proposed several techniques to allow keyword search on XML databases and document collections. A common data structure employed in most of these approaches is an inverted index, which is the state-of-the-art for conducting keyword search over large volumes of textual data, such as world wide web. In particular, a full element-index considers (and indexes) each XML element as a separate document, which is formed of the text directly contained in it and the textual content of all of its descendants. A major criticism for a full element-index is the high degree of redundancy in the index (due to the nested structure of XML documents), which diminishes its usage for large-scale XML retrieval scenarios. As the first contribution of this thesis, we investigate the efficiency and effectiveness of using a full element-index for XML keyword search. First, we suggest that lossless index compression methods can significantly reduce the size of a full element-index so that query processing strategies, such as those employed in a typical search engine, can efficiently operate on it. We show that once the most essential problem of a full element-index, i.e., its size, is remedied, using such an index can improve both the result quality (effectiveness) and query execution performance (efficiency) in comparison to other recently proposed techniques in the literature. Moreover, using a full element-index also allows generating query results in different forms, such as a ranked list of documents (as expected by a search engine user) or a complete list of elements that include all of the query terms (as expected by a DBMS user), in a unified framework. As a second contribution of this thesis, we propose to use a lossy approach, static index pruning, to further reduce the size of a full element-index. In this way, we aim to eliminate the repetition of an element's terms at upper levels in an adaptive manner considering the element's textual content and search system's ranking function. That is, we attempt to remove the repetitions in the index only when we expect that removal of them would not reduce the result quality. We conduct a well-crafted set of experiments and show that pruned index files are comparable or even superior to the full element-index up to very high pruning levels for various ad hoc tasks in terms of retrieval effectiveness. As a final contribution of this thesis, we propose to apply index pruning strategies to reduce the size of the document vectors in an XML collection to improve the clustering performance of the collection. Our experiments show that for certain cases, it is possible to prune up to 70% of the collection (or, more specifically, underlying document vectors) and still generate a clustering structure that yields the same quality with that of the original collection, in terms of a set of evaluation metrics.Keywords: Information Retrieval, XML Keyword Search, Full Element-Index, LCA, SLCA, Static Pruning, Clustering.
BU-CE-1016: PDF
Hypergraph Partitioning through Vertex Separators on Graphs
The modeling flexibility provided by hypergraphs has drawn a lot of interest from the combinatorial scientific community, leading to novel models and algorithms, their applications, and development of associated tools. Hypergraphs are now a standard tool in combinatorial scientific computing. The modeling flexibility of hypergraphs however, comes at a cost: algorithms on hypergraphs are inherently more complicated than those on graphs, which sometimes translate to nontrivial increases in processing times. Neither the modeling flexibility of hypergraphs, nor the runtime efficiency of graph algorithms can be overlooked. Therefore, the new research thrust should be how to cleverly trade-off between the two. This work addresses one method for this trade-off. by solving the hypergraph partitioning problem by finding vertex separators on graphs. Specifically, we investigate how to solve the hypergraph partitioning problem by seeking a vertex separator on its net intersection graph (NIG), where each net of the hypergraph is represented by a vertex, and two vertices share an edge if their nets have a common vertex. We propose a vertex-weighting scheme to attain good node-balanced hypergraphs, since NIG model cannot preserve node balancing information. Vertex-removal and vertex-splitting techniques are described to optimize cutnet and connectivity metrics, respectively, under the recursive bipartitioning paradigm. We also developed an implementation for our GPVS-based HP formulations by adopting and modifying a state-of-the-art GPVS tool onmetis. Experiments conducted on a large collection of sparse matrices confirmed the validity of our proposed techniques.Keywords: hypergraph partitioning; combinatorial scientific computing; graph partitioning by vertex separator; sparse matrices.
BU-CE-1017: PDF
Hypergraph-Partitioning-Based Models and Methods for Exploiting Cache Locality in Sparse-Matrix Vector Multiplication
The sparse matrix-vector multiplication (SpMxV) is an important kernel operation widely used in linear solvers. The same sparse matrix is multiplied by a dense vector repeatedly in these solvers to solve a system of linear equations. High performance gains can be obtained if we can take the advantage of today's deep cache hierarchy in SpMxV operations. Matrices with irregular sparsity patterns make it difficult to utilize data locality effectively in SpMxV computations. Different techniques are proposed in the literature to utilize cache hierarchy effectively via exploiting data locality during SpMxV. In this work, we investigate two distinct frameworks for cache-oblivious SpMxV: single matrix-vector multiply and multiple submatrix-vector multiplies. For the single SpMxV framework, we propose two cache-size-aware top-down row/column-reordering approach based on 1D and 2D sparse matrix partitioning by utilizing the recently proposed appropriate hypergraph models of sparse matrices. The multiple SpMxV framework depends on the partitioning a matrix into multiple nonzero-disjoint submatrices. For an effective matrix-to-submatrix partitioning required in this framework, we propose a cache-size-aware top-down approach based on 2D sparse matrix partitioning by utilizing the recently proposed fine-grain hypergraph model. For this framework, we also propose a traveling salesman formulation for an effective ordering of individual SpMxV operations. We evaluate the validity of our models and methods on a wide range of sparse matrices. Experimental results show that proposed methods and models outperform state-of-the-art schemes.Keywords: cache locality, sparse matrices, matrix-vector multiplication, matrix reordering, computational hypergraph model, hypergraph partitioning, traveling salesman problem.