检索结果-内蒙古大学图书馆

Fast and Effective Retrieval for Large Multimedia Collections

BIG DATA AND COGNITIVE COMPUTING 2021年第3期5卷 33页

作者： Wagenpfeil, Stefan Vu, Binh Mc Kevitt, Paul Hemmje, Matthias Univ Hagen Fac Math & Comp Sci Univ Str 1 D-58097 Hagen Germany Acad Int Sci & Res AISR Derry BT48 7JL North Ireland

The indexing and retrieval of multimedia content is generally implemented by employing feature graphs. These graphs typically contain a significant number of nodes and edges to reflect the level of detail in feature detection. A higher level of detail increases the effectiveness of the results, but also leads to more complex graph structures. However, graph traversal-based algorithms for similarity are quite inefficient and computationally expensive, especially for large data structures. To deliver fast and effective retrieval especially for large multimedia collections and multimedia big data, an efficient similarity algorithm for large graphs in particular is desirable. Hence, in this paper, we define a graph projection into a 2D space (graph Code) and the corresponding algorithms for indexing and retrieval. We show that calculations in this space can be performed more efficiently than graph traversals due to the simpler processing model and the high level of parallelization. As a consequence, we demonstrate experimentally that the effectiveness of retrieval also increases substantially, as the graph Code facilitates more levels of detail in feature fusion. These levels of detail also support an increased trust prediction, particularly for fused social media content. In our mathematical model, we define a metric triple for the graph Code, which also enhances the ranked result representations. Thus, graph Codes provide a significant increase in efficiency and effectiveness, especially for multimedia indexing and retrieval, and can be applied to images, videos, text and social media information.

关键词： indexing retrieval semantics graph algorithm graph Code multimedia

来源：评论

学校读者我要写书评

暂无评论

MMDIT: A tool for the deconvolution and interpretation of mitochondrial DNA mixtures

引用

FORENSIC SCIENCE INTERNATIONAL-GENETICS 2021年 55卷 102568-102568页

作者： Mandape, Sammed N. Smart, Utpal King, Jonathan L. Muenzler, Melissa Kapema, Kapema Bupe Budowle, Bruce Woerner, August E. Univ North Texas Ctr Human Identificat Hlth Sci Ctr 3500 CampBowie Blvd Ft Worth TX 76107 USA Univ North Texas Dept Microbiol Immunol & Genet Hlth Sci Ctr 3500 Camp Bowie Blvd Ft Worth TX 76107 USA

Short tandem repeats of the nuclear genome have been the preferred markers for analyzing forensic DNA mixtures. However, when nuclear DNA in a sample is degraded or limited, mitochondrial DNA (mtDNA) markers provide a powerful alternative. Though historically considered challenging, the interpretation and analysis of mtDNA mixtures have recently seen renewed interest with the advent of massively parallel sequencing. However, there are only a few software tools available for mtDNA mixture interpretation. To address this gap, the Mitochondrial Mixture Deconvolution and Interpretation Tool (MMDIT) was developed. MMDIT is an interactive application complete with a graphical user interface that allows users to deconvolve mtDNA (whole or partial genomes) mixtures into constituent donor haplotypes and estimate random match probabilities on these resultant haplotypes. In cases where deconvolution might not be feasible, the software allows mixture analysis directly within a binary framework (i.e. qualitatively, only using data on allele presence/absence). This paper explains the functionality of MMDIT, using an example of an in vitro two-person mtDNA mixture with a ratio of 1:4. The uniqueness of MMDIT lies in its ability to resolve mixtures into complete donor haplotypes using a statistical phasing framework before mixture analysis and evaluating statistical weights employing a novel graph algorithm approach. MMDIT is the first available open-source software that can automate mtDNA mixture deconvolution and analysis. The MMDIT web application can be accessed online at https://***. edu/mmdit/. The source code is available at https://***/SammedMandape/MMDIT_UI and archived on zenodo (https://***/10.5281/zenodo.4770184).

关键词： Forensic genetics Mitochondrial DNA Mixture deconvolution MMDIT Bioinformatics Statistical phasing graph algorithm massively parallel sequencing

来源：评论

学校读者我要写书评

暂无评论

FAST algorithmS FOR SOLVING PATH PROBLEMS

引用

JOURNAL OF THE ACM 1981年第3期28卷 594-614页

作者： TARJAN, RE STANFORD UNIV STANFORDCA 94305

Let G = (V, E) be a directed graph with a distinguished source vertex s. The single-source path expression problem is to find, for each vertex v, a regular expression P(s, v) which represents the set of all paths in G from s to v A solution to this problem can be used to solve shortest path problems, solve sparse systems of linear equations, and carry out global flow analysis. A method is described for computing path expressions by dwidmg G mto components, computing path expressions on the components by Gaussian elimination, and combining the solutions This method requires O(ma(m, n)) time on a reducible flow graph, where n Is the number of vertices m G, m is the number of edges in G, and a is a functional inverse of Ackermann's function The method makes use of an algonthm for evaluating functions defined on paths in trees. A smapllfied version of the algorithm, which runs in O(m log n) time on reducible flow graphs, is quite easy to implement and efficient m practice. © 1981, ACM. All rights reserved.

关键词： Ackermann's function code optimization compdmg dominators Gaussian ehmmation global flow analysis graph algorithm linear algebra path compression path expression path problem path sequence reducible flow graph regular expressmn shortest path sparse matrix

来源：评论

学校读者我要写书评

暂无评论

APPLICATIONS OF PATH COMPRESSION ON BALANCED TREES

引用

JOURNAL OF THE ACM 1979年第4期26卷 690-715页

作者： TARJAN, RE Department of Computer Science Stanford University Stanford CA

Several fast algorithms are presented for computing functions defined on paths in trees under various assumpuons. The algorithms are based on tree mampulatton methods first used to efficiently represent equivalence relations. The algorithms have [formula omitted] running tunes, where m and n are measures of the problem size and a Is a functional reverse of Ackermann's function By usmg one or more of these algorithms m combination with other techniques, it is possible to solve the followmg graph problems m O(ma(m, n)) tnne, where m Is the number of edges and n Is the number of vertices m the problem graph A Venfymg a minimum spanning tree m an undirected graph (Best previously known time bound O(m log log n).) B Flndmg dominators in a flow graph (Best previously known tune bound O(n log n + m).) C Solvmg a path problem on a reducible flow graph. (Best previously known time bound. O(m log n) ) Application A is discussed. © 1979, ACM. All rights reserved.

关键词： balanced tree dominators equivalence relation global flow analysis graph algorithm minimum spanning tree path compression path problem tree

来源：评论

学校读者我要写书评

暂无评论

A safe and complete algorithm for metagenomic assembly

引用

algorithmS FOR MOLECULAR BIOLOGY 2018年第1期13卷 3-3页

作者： Acosta, Nidia Obscura Makinen, Veli Tomescu, Alexandru I. Univ Helsinki Helsinki Inst Informat Technol Dept Comp Sci Helsinki Finland

Background: Reconstructing the genome of a species from short fragments is one of the oldest bioinformatics problems. Metagenomic assembly is a variant of the problem asking to reconstruct the circular genomes of all bacterial species present in a sequencing sample. This problem can be naturally formulated as finding a collection of circular walks of a directed graph G that together cover all nodes, or edges, of G. Approach: We address this problem with the "safe and complete" framework of Tomescu and Medvedev (Research in computational Molecular biology-20th annual conference, RECOMB 9649: 152-163, 2016). An algorithm is called safe if it returns only those walks (also called safe) that appear as subwalk in all metagenomic assembly solutions for G. A safe algorithm is called complete if it returns all safe walks of G. Results: We give graph-theoretic characterizations of the safe walks of G, and a safe and complete algorithm finding all safe walks of G. In the node-covering case, our algorithm runs in time O(m(2) + n(3)), and in the edge-covering case it runs in time O(m(2)n);n and m denote the number of nodes and edges, respectively, of G. This algorithm constitutes the first theoretical tight upper bound on what can be safely assembled from metagenomic reads using this problem formulation.

关键词： Genome assembly Contig assembly Metagenomics graph algorithm Circular walk

来源：评论

学校读者我要写书评

暂无评论

Electronic Design Automation with graphic Processors: A Survey

引用

FOUNDATIONS AND TRENDS IN ELECTRONIC DESIGN AUTOMATION 2013年第1-2期7卷 1-176页

作者： Deng, Yangdong Mu, Shuai Tsinghua Univ Inst Microelect Beijing Peoples R China

Today's Integrated Circuit (IC) architects depend on Electronic Design Automation (EDA) software to conquer the overwhelming complexity of Very Large Scale Integrated (VLSI) designs. As the complexity of IC chips is still fast increasing, it is critical to maintain the momentum towards growing productivity of EDA tools. On the other hand, single-core Central Processing Unit (CPU) performance is unlikely to see significant improvement in the near future. It is thus essential to develop highly efficient parallel algorithms and implementations for EDA applications, so that their overall productivity can continue to increase in a scalable fashion. Among various emergent parallel platforms, graphics Processing Units (GPUs) now offer the highest single-chip computing throughput. A large body of research, therefore, has been dedicated to accelerating EDA applications with GPUs. This monograph is aimed to develop a timely review of the existing literature on GPU-based EDA computing. Considering the substantial diversity of VLSI CAD algorithms, we extend a taxonomy of EDA computing patterns, which can be used as basic building blocks to construct complex EDA applications. GPU-based acceleration techniques for these patterns are then reviewed. On such a basis, we further survey recent works on building efficient data-parallel algorithms and implementations to unleash the power of GPUs for EDA applications.

关键词： Electronic Design Automation (EDA) VLSI GPU graphics Processor GPGPU logic simulation circuit simulation matrix linear algebra sparse matrix graph traversal graph algorithm dynamic programming simulated annealing structured grid

来源：评论

学校读者我要写书评

暂无评论

A novel method to find out sensory neuron tracts in the Drosophila brain

引用

BMC Neuroscience 2015年第1期16卷 1-2页

作者： Chao-Chun Chuang National Center for High-Performance Computing Taiwan Republic of China

来源：评论

学校读者我要写书评

暂无评论

最小全一问题的解及其算法的研究

最小全一问题的解及其算法的研究

引用

作者：张晓岩南开大学

学位级别：博士

细胞自动机是一种离散动力系统。它包含了由细胞单元的状态构成的配制以及作用在配制上的传递规则。下面我们总是假设G=（V，E）是一个有限无向的简单连通图。图上的每一个顶点可以看作细胞自动机上的一个细胞单元，细胞单元上状态的值... 详细信息

细胞自动机是一种离散动力系统。它包含了由细胞单元的状态构成的配制以及作用在配制上的传递规则。下面我们总是假设G=（V，E）是一个有限无向的简单连通图。图上的每一个顶点可以看作细胞自动机上的一个细胞单元，细胞单元上状态的值或者是0或者是1。如果每一个细胞单元的状态都被赋予了一个值，则所有细胞单元状态值的集合被称为细胞自动机上的一个配制。自动机的演化由局部传递规则决定。如果X是时刻t的一个配制，Y是局部传递规则作用在X后于时刻t+1的配制，那么Y称为X的后继，X被称为Y的前驱。在配制进化领域里的一个基本问题就是研究对于一个给定的目标配制确定它的前驱是否存在的问题。这个问题被称作前驱存在问题。更进一步，如果给定一个界β，寻找基数最多为β的前驱配制问题被称为界定前驱存在问题。给定一个有趣的目标配制1，即目标配制是每一个细胞单元的状态值都为1，我们将以基于局部规则σ+及σ下的图上的细胞自动机作为对象展开研究。对于σ+规则，当初始配制为0，目标配制为1时，相应的前驱存在问题也被称为σ+全一问题或者直接称为全一问题[27]。Peled提出了一个等价的问题被称为点灯问题[22]。类似的，对于σ规则，当初始配制为0，目标配制为1时，相应的前驱存在问题被称为σ全一问题。为方便起见，目标配置的前驱也被称为解。近年来全一问题已经被广泛的研究，见Sutner[29，31]，Barua和Ramakrishnan[2]以及Dodis和Winkler[11]。全一问题解的存在性问题已经被完全解决。用线形代数的方法，Sutner[28]证明了全一问题的解总是存在的，并给出了n×n的格子图上解的一些计数结果。Sutner曾提问是否可用图论的方法证明解的存在性问题[28]。Erikisson et al.[13]给出了解存在性的图论证明。进而，Chen et al.[6]给出了一个精巧的图论算法用来找到一般图上的解。如果我们也要求前驱配制中非零状态的细胞单元个数最少，相应的问题被简称为最小全一问题。这个问题已经被证明对于任意图是NP-完全问题[25]。最近，Broersma和Li又证明了对于二部图这个问题也是NP-完全的[3]。全一问题也可以被称为点点问

关键词： (minimum)σ+ all-ones problem (minimum) (general)σall-ones problem tree unicyclic graph bicyclic graph graph algorithm minimum weight perfect matching linear time

来源：评论

学校读者我要写书评

暂无评论

A UNIFIED APPROACH TO PATH PROBLEMS

引用

JOURNAL OF THE ACM 1981年第3期28卷 577-593页

作者： TARJAN, RE STANFORD UNIV STANFORDCA 94305

A general method is described for solving path problems on directed graphs. Such path problems include finding shortest paths, solving sparse systems of hnear equaUons, and carrying out global flow analysis of computer programs The method consists of two steps First, a collecUon of regular expressions representmg sets of paths m the graph Is constructed This can be done by using any standard algorithm, such as Gaussmn or Gauss-Jordan elimination. Next, a natural mapping from regular expressions into the gwen problem domain is applied. The mappmgs required to find shortest paths are exhibited, sparse systems of hnear equations are solved, and global flow analysis Is carned out. The results provide a general-purpose algonthm for solwng any path problem and show that the problem of constructing path expressions is in some sense the most general path problem. © 1981, ACM. All rights reserved.

关键词： code optimization compiling Ganss-Jordan ehmmatlon Gaussian elmamation global flow analysis graph algorithm linear algebra path problem regular expression semdattlce shortest path sparse matrix

来源：评论

学校读者我要写书评

暂无评论

VARIATIONS ON THE COMMON SUBEXPRESSION PROBLEM

引用

JOURNAL OF THE ACM 1980年第4期27卷 758-771页

作者： DOWNEY, PJ SETHI, R TARJAN, RE BELL TEL LABS INC MURRAY HILLNJ 07974 STANFORD UNIV STANFORDCA 94305

Let G be a directed graph such that for each vertex v in G, the successors of v are ordered Let C be any equivalence relation on the vertices of G. The congruence closure C* of C is the finest equivalence relation containing C and such that any two vertices having corresponding successors equivalent under C* are themselves equivalent under C* Efficient algorithms are described for computing congruence closures in the general case and in the following two special cases. 0) G under C* is acyclic, and (it) G is acychc and C identifies a single pair of vertices. The use of these algorithms to test expression eqmvalence (a problem central to program verification) and to test losslessness of joins in relational databases is described. © 1980, ACM. All rights reserved.

关键词： common subexpresslon congruence closure decision procedure expression equivalence graph algorithm lossless join relational database theory of equality unification uniform word problem

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：