Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons

Open Access. Powered by Scholars. Published by Universities.®

Articles 1 - 30 of 150

Full-Text Articles in Physical Sciences and Mathematics

Evaluating Digital Creativity Support For Children: A Systematic Literature Review, Marte Hoff Hagen, Daniela Soares Cruzes, Letizia Jaccheri, Jerry Alan Fails Dec 2023

Evaluating Digital Creativity Support For Children: A Systematic Literature Review, Marte Hoff Hagen, Daniela Soares Cruzes, Letizia Jaccheri, Jerry Alan Fails

Computer Science Faculty Publications and Presentations

Creativity, the process of creating something new and valuable, benefits children by improving their skills and development, encouraging interaction and engagement, and enabling the generation and expression of novel ideas. In recent years, interactive digital tools have emerged to support the user’s creativity in the open-ended creation of new artifacts. However, the question of evaluating the creativity happening in the interplay between children, digital tools, and products is still open. This systematic literature review investigated the evaluations of digital creativity support tools for children and identified 81 peer-reviewed relevant articles from the last 10 years. This research contributes to practitioners …


Janus: Toward Preventing Counterfeits In Supply Chains Utilizing A Multi-Quorum Blockchain, Vika Crossland, Connor Dellwo, Golam Bashar, Gaby G. Dagher Dec 2023

Janus: Toward Preventing Counterfeits In Supply Chains Utilizing A Multi-Quorum Blockchain, Vika Crossland, Connor Dellwo, Golam Bashar, Gaby G. Dagher

Computer Science Faculty Publications and Presentations

The modern pharmaceutical supply chain lacks transparency and traceability, resulting in alarming rates of counterfeit products entering the market. These illegitimate products cause harm to end users and wreak havoc on the supply chain itself, costing billions of dollars in profit loss. In this paper, in response to the Drug Supply Chain Security Act (DSCSA), we introduce Janus, a novel pharmaceutical track-and-trace system that utilizes blockchain and cloning-resistant hologram tags to prevent counterfeits from entering the pharmaceutical supply chain. We design a multi-quorum consensus protocol that achieves load balancing across the network. We perform a security analysis to show robustness …


Understanding The Contribution Of Recommendation Algorithms On Misinformation Recommendation And Misinformation Dissemination On Social Networks, Royal Pathak, Francesca Spezzano, Maria Soledad Pera Nov 2023

Understanding The Contribution Of Recommendation Algorithms On Misinformation Recommendation And Misinformation Dissemination On Social Networks, Royal Pathak, Francesca Spezzano, Maria Soledad Pera

Computer Science Faculty Publications and Presentations

Social networks are a platform for individuals and organizations to connect with each other and inform, advertise, spread ideas, and ultimately influence opinions. These platforms have been known to propel misinformation. We argue that this could be compounded by the recommender algorithms that these platforms use to suggest items potentially of interest to their users, given the known biases and filter bubbles issues affecting recommender systems. While much has been studied about misinformation on social networks, the potential exacerbation that could result from recommender algorithms in this environment is in its infancy. In this manuscript, we present the result of …


Cybersecurity Safeguards: What Cybersecurity Safeguards Could Have Prevented The Intelligence/Data Breach By A Member Of The Air National Guard, Christopher Curtis Royal Aug 2023

Cybersecurity Safeguards: What Cybersecurity Safeguards Could Have Prevented The Intelligence/Data Breach By A Member Of The Air National Guard, Christopher Curtis Royal

Cyber Operations and Resilience Program Graduate Projects

Jack Teixeira, a 21-year-old IT specialist Air National Guard found himself on the wrong side of the US law after sharing what is considered classified and extremely sensitive information about USA's operations and role in Ukraine and Russia war. Like other previous cases of leakage of classified intelligence, the case of Teixeira raises concerns about the weaknesses and vulnerability of federal agencies' IT systems and security protocols governing accessibility to classified documents. Internal leakages of such classified documents hurt national security and can harm the country, especially when such secretive intelligence finds its way into the hands of enemies. Unauthorized …


The X-Ray Variation Of M81* Resolved By Chandra And Nustar, Shu Niu, Fu-Guo Xie, Q. Daniel Wang, Li Ji, Feng Yuan, Min Long Jun 2023

The X-Ray Variation Of M81* Resolved By Chandra And Nustar, Shu Niu, Fu-Guo Xie, Q. Daniel Wang, Li Ji, Feng Yuan, Min Long

Computer Science Faculty Publications and Presentations

Despite advances in our understanding of low-luminosity active galactic nuclei (LLAGNs), the fundamental details about the mechanisms of radiation and flare/outburst in hot accretion flow are still largely missing. We have systematically analysed the archival Chandra and NuSTAR X-ray data of the nearby LLAGN M81*, whose Lbol ∼ 10−5LEdd. Through a detailed study of X-ray light curve and spectral properties, we find that the X-ray continuum emission of the power-law shape more likely originates from inverse Compton scattering within the hot accretion flow. In contrast to Sgr A*, flares are rare in M81*. Low-amplitude variation …


In-Vitro Validated Methods For Encoding Digital Data In Deoxyribonucleic Acid (Dna), Golam Md Mortuza, Jorge Guerrero, Shoshanna Llewellyn, Michael D. Tobiason, George D. Dickinson, William L. Hughes, Reza Zadegan, Tim Andersen Apr 2023

In-Vitro Validated Methods For Encoding Digital Data In Deoxyribonucleic Acid (Dna), Golam Md Mortuza, Jorge Guerrero, Shoshanna Llewellyn, Michael D. Tobiason, George D. Dickinson, William L. Hughes, Reza Zadegan, Tim Andersen

Computer Science Faculty Publications and Presentations

Deoxyribonucleic acid (DNA) is emerging as an alternative archival memory technology. Recent advancements in DNA synthesis and sequencing have both increased the capacity and decreased the cost of storing information in de novo synthesized DNA pools. In this survey, we review methods for translating digital data to and/or from DNA molecules. An emphasis is placed on methods which have been validated by storing and retrieving real-world data via in-vitro experiments.


Tiny Language Models Enriched With Multimodal Knowledge From Multiplex Networks, Clayton Fields, Osama Natouf, Andrew Mcmains, Catherine Henry, Casey Kennington Jan 2023

Tiny Language Models Enriched With Multimodal Knowledge From Multiplex Networks, Clayton Fields, Osama Natouf, Andrew Mcmains, Catherine Henry, Casey Kennington

Computer Science Faculty Publications and Presentations

Large transformer language models trained exclusively on massive quantities of text are now the standard in NLP. In addition to the impractical amounts of data used to train them, they require enormous computational resources for training. Furthermore, they lack the rich array of sensory information available to humans, who can learn language with much less exposure to language. In this study, performed for submission in the BabyLM challenge, we show that we can improve a small transformer model’s data efficiency by enriching its embeddings by swapping the learned word embeddings from a tiny transformer model with vectors extracted from a …


Exploring Transformers As Compact, Data-Efficient Language Models, Clayton Fields, Casey Kennington Jan 2023

Exploring Transformers As Compact, Data-Efficient Language Models, Clayton Fields, Casey Kennington

Computer Science Faculty Publications and Presentations

Large scale transformer models, trained with massive datasets have become the standard in natural language processing. The huge size of most transformers make research with these models impossible for those with limited computational resources. Additionally, the enormous pretraining data requirements of transformers exclude pretraining them with many smaller datasets that might provide enlightening results. In this study, we show that transformers can be significantly reduced in size, with as few as 5.7 million parameters, and still retain most of their downstream capability. Further we show that transformer models can retain comparable results when trained on human-scale datasets, as few as …


Ethics Of Emerging Communication And Collaboration Technologies For Children, Juan Pablo Hourcade, Elizabeth Bonsignore, Tamara Clegg, Flannery Currin, Jerry A. Fails, Georgie Qiao Jin, Summer R. Schmuecker, Lana Yarosh Jan 2023

Ethics Of Emerging Communication And Collaboration Technologies For Children, Juan Pablo Hourcade, Elizabeth Bonsignore, Tamara Clegg, Flannery Currin, Jerry A. Fails, Georgie Qiao Jin, Summer R. Schmuecker, Lana Yarosh

Computer Science Faculty Publications and Presentations

This SIG will provide child-computer interaction researchers and practitioners, as well as other interested CSCW attendees, an opportunity to discuss topics related to the ethics of emerging communication and collaboration technologies for children. The child-computer interaction community has conducted many discussions on ethical issues, including a recent SIG at CHI 2023. However, the angle of communication and collaboration has not been a focus, even though emerging technologies could affect these aspects in significant ways. Hence, there is a need to consider emerging technologies, such as extended reality, and how they may impact the way children communicate and collaborate in face-to-face, …


A Cybersecurity Assessment Of Health Data Ecosystems, Michelle N. Halsey Dec 2022

A Cybersecurity Assessment Of Health Data Ecosystems, Michelle N. Halsey

Cyber Operations and Resilience Program Graduate Projects

This paper is an exploratory study that investigates data collected and used by health plans and reviews the laws and regulations governing this data to identify the gaps in protections and provide recommendations for eliminating these gaps. Health insurance companies collect a wide array of data about the people they insure, data that is often only peripherally relevant to the service these companies provide. The data environment currently consists of seven categories of data: personal health information, summary health information, personally identifiable information, financial information, professional information, biometric information, and lifestyle data or social indicators of health. Much of this …


Deep Near-Infrared Survey Towards The W40 And Serpens South Region In The Aquila Rift: A Comprehensive Catalogue Of Young Stellar Objects, Min Long Nov 2022

Deep Near-Infrared Survey Towards The W40 And Serpens South Region In The Aquila Rift: A Comprehensive Catalogue Of Young Stellar Objects, Min Long

Computer Science Faculty Publications and Presentations

Active star-forming regions are excellent laboratories for studying the origins and evolution of young stellar object (YSO) clustering. The W40–Serpens South region is such a region, and we compile a large near- and mid-infrared catalogue of point sources in it, based on deep near-infrared observations of Canada-France-Hawaii Telescope (CFHT) in combination with Two Micron All Sky Survey (2MASS), UKIRT Infrared Deep Sky Survey (UKIDSS), and Spitzer catalogues. From this catalogue, we identify 832 YSOs, and classify 15, 135, 647, and 35 of them to be deeply embedded sources, Class I YSOs, Class II YSOs, and transition disc sources, respectively. In …


Hierarchical Structure Of Yso Clusters In The W40 And Serpens South Region: Group Extraction And Comparison With Fractal Clusters, Jia Sun, Robert A. Gutermuth, Hongchi Wang, Shuinai Zhang, Min Long Nov 2022

Hierarchical Structure Of Yso Clusters In The W40 And Serpens South Region: Group Extraction And Comparison With Fractal Clusters, Jia Sun, Robert A. Gutermuth, Hongchi Wang, Shuinai Zhang, Min Long

Computer Science Faculty Publications and Presentations

Young stellar clusters are believed to inherit the spatial distribution like hierarchical structures of their natal molecular cloud during their formation. However, the change of the structures between the cloud and the young clusters is not well constrained observationally. We select the W40–Serpens South region (∼7 × 9 pc2) of the Aquila Rift as a testbed and investigate hierarchical properties of spatial distribution of young stellar objects (YSOs) in this region. We develop a minimum spanning tree (MST) based method to group stars into several levels by successively cutting down edges longer than an algorithmically determined critical value. …


Testing Research Software: A Survey, Nasir U. Eisty, Jeffrey C. Carver Nov 2022

Testing Research Software: A Survey, Nasir U. Eisty, Jeffrey C. Carver

Computer Science Faculty Publications and Presentations

Background Research software plays an important role in solving real-life problems, empowering scientific innovations, and handling emergency situations. Therefore, the correctness and trustworthiness of research software are of absolute importance. Software testing is an important activity for identifying problematic code and helping to produce high-quality software. However, testing of research software is difficult due to the complexity of the underlying science, relatively unknown results from scientific algorithms, and the culture of the research software community.

Aims The goal of this paper is to better understand current testing practices, identify challenges, and provide recommendations on how to improve the testing process …


Fairness In Information Access Systems, Michael D. Ekstrand, Anubrata Das, Robin Burke, Fernando Diaz Jul 2022

Fairness In Information Access Systems, Michael D. Ekstrand, Anubrata Das, Robin Burke, Fernando Diaz

Computer Science Faculty Publications and Presentations

Recommendation, information retrieval, and other information access systems pose unique challenges for investigating and applying the fairness and non-discrimination concepts that have been developed for studying other machine learning systems. While fair information access shares many commonalities with fair classification, there are important differences: the multistakeholder nature of information access applications, the rank-based problem setting, the centrality of personalization in many cases, and the role of user response all complicate the problem of identifying precisely what types and operationalizations of fairness may be relevant.

In this monograph, we present a taxonomy of the various dimensions of fair information access and …


Zero Trust Architecture: Framework And Case Study, Cody Shepherd Jul 2022

Zero Trust Architecture: Framework And Case Study, Cody Shepherd

Cyber Operations and Resilience Program Graduate Projects

The world and business are connected and a business does not exist today that does not have potentially thousands of connections to the Internet in addition to the thousands of connections to other various parts of its own infrastructure. That is the nature of the digital world we live in and there is no chance the number of those interconnections will reduce in the future. Protecting from the “outside” world with a perimeter solution might have been enough to reduce risk to an acceptable level in an organization 20 years ago, but today’s threats are sophisticated, persistent, abundant, and can …


The Multisided Complexity Of Fairness In Recommender Systems, Nasim Sonboli, Robin Burke, Michael Ekstrand, Rishabh Mehrotra Jul 2022

The Multisided Complexity Of Fairness In Recommender Systems, Nasim Sonboli, Robin Burke, Michael Ekstrand, Rishabh Mehrotra

Computer Science Faculty Publications and Presentations

Recommender systems are poised at the interface between stakeholders: for example, job applicants and employers in the case of recommendations of employment listings, or artists and listeners in the case of music recommendation. In such multisided platforms, recommender systems play a key role in enabling discovery of products and information at large scales. However, as they have become more and more pervasive in society, the equitable distribution of their benefits and harms have been increasingly under scrutiny, as is the case with machine learning generally. While recommender systems can exhibit many of the biases encountered in other machine learning settings, …


Ethical Implications For Children’S Use Of Search Tools In An Educational Setting, Monica Landoni, Theo Huibers, Emiliana Murgia, Maria Soledad Pera Jun 2022

Ethical Implications For Children’S Use Of Search Tools In An Educational Setting, Monica Landoni, Theo Huibers, Emiliana Murgia, Maria Soledad Pera

Computer Science Faculty Publications and Presentations

In the classroom, search tools enable students to access online resources. While these tools have many benefits in theory, in practice there are also ethical issues to consider. In this article, we discuss a number of ethics-related problems teachers are faced with and they need to find solutions for. Based on our own research experience developing and deploying information discovery tools for the classroom (both in a traditional classroom setting and on the Internet due to the ongoing outbreak of COVID-19), we share insights about ethics and the role of the expert-in-the-loop, teachers, both as co-design partners and liaisons between …


Vigilrx: A Scalable And Interoperable Prescription Management System Using Blockchain, Alixandra Taylor, Austin Kugler, Praneeth Babu Marella, Gaby G. Dagher Mar 2022

Vigilrx: A Scalable And Interoperable Prescription Management System Using Blockchain, Alixandra Taylor, Austin Kugler, Praneeth Babu Marella, Gaby G. Dagher

Computer Science Faculty Publications and Presentations

Achieving interoperability between healthcare providers is a major challenge. Current systems for managing prescription records suffer from data siloing, unnecessary record duplication, and slow record transfers. In many systems, patients do not retain control over their prescription data. Instead, they must use an intermediary to access or transfer their records. Furthermore, record transfers suffer from differing standards between providers, outdated communication methods, and information blocking. Solving these problems necessitates the creation of an interoperable prescription management system. Realizing such a system requires considering security, efficiency, scalability, and other challenges. Recent regulatory actions attempt to address these challenges, but fundamental issues …


Machine Learning Methods For Generating High Dimensional Discrete Datasets, Giuseppe Manco, Ettore Ritacco, Antonino Rullo, Domenico Saccà, Edoardo Serra Mar 2022

Machine Learning Methods For Generating High Dimensional Discrete Datasets, Giuseppe Manco, Ettore Ritacco, Antonino Rullo, Domenico Saccà, Edoardo Serra

Computer Science Faculty Publications and Presentations

The development of platforms and techniques for emerging Big Data and Machine Learning applications requires the availability of real-life datasets. A possible solution is to synthesize datasets that reflect patterns of real ones using a two-step approach: first, a real dataset X is analyzed to derive relevant patterns Z and, then, to use such patterns for reconstructing a new dataset X' that preserves the main characteristics of X. This survey explores two possible approaches: (1) Constraint-based generation and (2) probabilistic generative modeling. The former is devised using inverse mining (IFM) techniques, and consists of generating a dataset satisfying given …


Spoken Language Interaction With Robots: Recommendations For Future Research, Casey Kennington Jan 2022

Spoken Language Interaction With Robots: Recommendations For Future Research, Casey Kennington

Computer Science Faculty Publications and Presentations

With robotics rapidly advancing, more effective human–robot interaction is increasingly needed to realize the full potential of robots for society. While spoken language must be part of the solution, our ability to provide spoken language interaction capabilities is still very limited. In this article, based on the report of an interdisciplinary workshop convened by the National Science Foundation, we identify key scientific and engineering advances needed to enable effective spoken language interaction with robotics. We make 25 recommendations, involving eight general themes: putting human needs first, better modeling the social and interactive aspects of language, improving robustness, creating new methods …


Developers Perception Of Peer Code Review In Research Software Development, Nasir U. Eisty, Jeffrey C. Carver Jan 2022

Developers Perception Of Peer Code Review In Research Software Development, Nasir U. Eisty, Jeffrey C. Carver

Computer Science Faculty Publications and Presentations

Context Research software is software developed by and/or used by researchers, across a wide variety of domains, to perform their research. Because of the complexity of research software, developers cannot conduct exhaustive testing. As a result, researchers have lower confidence in the correctness of the output of the software. Peer code review, a standard software engineering practice, has helped address this problem in other types of software.

Objective Peer code review is less prevalent in research software than it is in other types of software. In addition, the literature does not contain any studies about the use of peer code …


Drones, Virtual Reality, And Modeling: Communicating Catastrophic Dam Failure, H. R. Spero, I. Vazquez-Lopez, K. Miller, R. Joshaghani, S. Cutchin, J. Enterkine Jan 2022

Drones, Virtual Reality, And Modeling: Communicating Catastrophic Dam Failure, H. R. Spero, I. Vazquez-Lopez, K. Miller, R. Joshaghani, S. Cutchin, J. Enterkine

Computer Science Faculty Publications and Presentations

Dam failures occur worldwide and can be economically and ecologically devastating. Communicating the scale of these risks to the general public and decision-makers is imperative. Two-dimensional (2D) dam failure hydraulic models inform owners and floodplain managers of flood regimes but have limitations when shared with non-specialists. This study addresses these limitations by constructing a 3D Virtual Reality (VR) environment to display the 1976 Teton Dam disaster case study using a pipeline composed of (1) 2D hydraulic model data (extrapolated into 3D), (2) a 3D reconstructed dam, and (3) a terrain model processed from UAS (Uncrewed Airborne System) imagery using Structure …


Understanding Intention For Machine Theory Of Mind: A Position Paper, Casey Kennington Jan 2022

Understanding Intention For Machine Theory Of Mind: A Position Paper, Casey Kennington

Computer Science Faculty Publications and Presentations

Theory of Mind is often characterized as the ability to recognize desires, beliefs, and intentions of others. In this position paper, I look at the literature on modeling Theory of Mind in machines and find that, to date, intention is not usually a focus. I define what I mean by intention—choice with commitment—following prior work. Intention has a long history of research in some communities, and I offer one theoretical framework for modeling intention as a starting point. I take inspiration from how children learn intention through joint attention with others and how that leads to Theory of Mind. I …


Automatic Transformation Of Natural To Unified Modeling Language: A Systematic Review, Sharif Ahmed, Arif Ahmed, Nasir U. Eisty Jan 2022

Automatic Transformation Of Natural To Unified Modeling Language: A Systematic Review, Sharif Ahmed, Arif Ahmed, Nasir U. Eisty

Computer Science Faculty Publications and Presentations

Context: Processing Software Requirement Specifications (SRS) manually takes a much longer time for requirement analysts in software engineering. Researchers have been working on making an automatic approach to ease this task. Most of the existing approaches require some intervention from an analyst or are challenging to use. Some automatic and semi-automatic approaches were developed based on heuristic rules or machine learning algorithms. However, there are various constraints to the existing approaches to UML generation, such as restrictions on ambiguity, length or structure, anaphora, incompleteness, atomicity of input text, requirements of domain ontology, etc. Objective: This study aims to better understand …


Software Engineering Approaches For Tinyml Based Iot Embedded Vision: A Systematic Literature Review, Shashank Bangalore Lakshman, Nasir U. Eisty Jan 2022

Software Engineering Approaches For Tinyml Based Iot Embedded Vision: A Systematic Literature Review, Shashank Bangalore Lakshman, Nasir U. Eisty

Computer Science Faculty Publications and Presentations

Internet of Things (IoT) has catapulted human ability to control our environments through ubiquitous sensing, communication, computation, and actuation. Over the past few years, IoT has joined forces with Machine Learning (ML) to embed deep intelligence at the far edge. TinyML (Tiny Machine Learning) has enabled the deployment of ML models for embedded vision on extremely lean edge hardware, bringing the power of IoT and ML together. However, TinyML powered embedded vision applications are still in a nascent stage, and they are just starting to scale to widespread real-world IoT deployment. To harness the true potential of IoT and ML, …


Incremental Unit Networks For Distributed, Symbolic Multimodal Processing And Representation, Mir Tahsin Imtiaz, Casey Kennington Jan 2022

Incremental Unit Networks For Distributed, Symbolic Multimodal Processing And Representation, Mir Tahsin Imtiaz, Casey Kennington

Computer Science Faculty Publications and Presentations

Incremental dialogue processing has been an important topic in spoken dialogue systems research, but the broader research community that makes use of language interaction (e.g., chatbots, conversational AI, spoken interaction with robots) have not adopted incremental processing despite research showing that humans perceive incremental dialogue as more natural. In this paper, we extend prior work that identifies the requirements for making spoken interaction with a system natural with the goal that our framework will be generalizable to many domains where speech is the primary method of communication. The Incremental Unit framework offers a model of incremental processing that has been …


Symbol And Communicative Grounding Through Object Permanence With A Mobile Robot, Josue Torres-Fonseca, Catherine Henry, Casey Kennington Jan 2022

Symbol And Communicative Grounding Through Object Permanence With A Mobile Robot, Josue Torres-Fonseca, Catherine Henry, Casey Kennington

Computer Science Faculty Publications and Presentations

Object permanence is the ability to form and recall mental representations of objects even when they are not in view. Despite being a crucial developmental step for children, object permanence has had only some exploration as it relates to symbol and communicative grounding in spoken dialogue systems. In this paper, we leverage SLAM as a module for tracking object permanence and use a robot platform to move around a scene where it discovers objects and learns how they are denoted. We evaluated by comparing our system’s effectiveness at learning words from human dialogue partners both with and without object permanence. …


Measuring Fairness In Ranked Results: An Analytical And Empirical Comparison, Amifa Raj, Michael D. Ekstrand Jan 2022

Measuring Fairness In Ranked Results: An Analytical And Empirical Comparison, Amifa Raj, Michael D. Ekstrand

Computer Science Faculty Publications and Presentations

Information access systems, such as search and recommender systems, often use ranked lists to present results believed to be relevant to the user's information need. Evaluating these lists for their fairness along with other traditional metrics provides a more complete understanding of an information access system's behavior beyond accuracy or utility constructs. To measure the (un)fairness of rankings, particularly with respect to the protected group(s) of producers or providers, several metrics have been proposed in the last several years. However, an empirical and comparative analyses of these metrics showing the applicability to specific scenario or real data, conceptual similarities, and …


Introduction To Using Python In The Digital Humanities, Elisabeth Shook Dec 2021

Introduction To Using Python In The Digital Humanities, Elisabeth Shook

Library Faculty Publications and Presentations

The materials here are from the Python for Digital Humanities Workshop taught on December 13, 2021 for the Boise State University Digital Humanities Group. This 3-hour workshop was created to provide both a very brief introduction to the various capabilities of Python and a small lesson in using Python to pull meaningful insight out of text files.


Cuts: Scaling Subgraph Isomorphism On Distributed Multi-Gpu Systems Using Trie Based Data Structure, Lizhi Xiang, Arif Khan, Edoardo Serra, Mahantesh Halappanavar, Aravind Sukumaran-Rajam Nov 2021

Cuts: Scaling Subgraph Isomorphism On Distributed Multi-Gpu Systems Using Trie Based Data Structure, Lizhi Xiang, Arif Khan, Edoardo Serra, Mahantesh Halappanavar, Aravind Sukumaran-Rajam

Computer Science Faculty Publications and Presentations

Subgraph isomorphism is a pattern-matching algorithm widely used in many domains such as chem-informatics, bioinformatics, databases, and social network analysis. It is computationally expensive and is a proven NP-hard problem. The massive parallelism in GPUs is well suited for solving subgraph isomorphism. However, current GPU implementations are far from the achievable performance. Moreover, the enormous memory requirement of current approaches limits the problem size that can be handled. This work analyzes the fundamental challenges associated with processing subgraph isomorphism on GPUs and develops an efficient GPU implementation. We also develop a GPU-friendly trie-based data structure to drastically reduce the intermediate …