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

Proceedings of the Annual International conference on Computational Molecular Biology, RECOMB 1999年 226-237页

作者： Kleinberg, Jon M. Cornell Univ Ithaca NY United States

Protein sequence design is a natural inverse problem to protein structure prudish: given a target structure in three dimensions, we wish to design an amino acid sequence that is likely fold to it. A model of Sun, Brem, Chan, and Dill casts this problem as an optimization on a space of sequences of hydrophobic (H) and polar (P) monomers;the goal is to find a sequence which achieves a dense hydrophobic core with few solvent-exposed hydrophobic residues. Sun et al. developed a heuristic method to search the space of sequences, without a guarantee of optimality or near-optimality;Hart subsequently raised the computational tractability of constructing an optimal sequence in this model as an open question. Here we resolve this question by providing an efficient algorithm to construct optimal sequences;our algorithm has a polynomial running time, and performs very efficiently in practice. We illustrate the implementation of our method on structures drawn from the Protein data Bank. We also consider extensions of the model to larger amino acid alphabets, as a way to overcome the limitations of the binary H/P alphabet. We show that for a natural class of arbitrarily large alphabets, it remains possible to design optimal sequences efficiently. Finally, we analyze some of the consequences of this sequence design model for the study of evolutionary fitness landscapes. A given target structure may have many sequences that are optimal in the model of Sun et al.;following a notion raised by the work of J. Maynard Smith, we can ask whether these optimal sequences are `connected' by successive point mutations. We provide a polynomial-time algorithm to decide this connectedness property, relative to a given target structure. We develop the algorithm by first solving an analogous problem expressed in terms of submodular functions, a fundamental object of study in combinatorial optimization.

关键词： DNA sequences

来源：评论

学校读者我要写书评

暂无评论

efficient search for approximate nearest neighbor in high dimensional spaces 98

Efficient search for approximate nearest neighbor in high di...

引用

Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing

作者： Kushilevitz, Eyal Ostrovsky, Rafail Rabani, Yuval Technion - IIT Haifa Israel

ISBN: (纸本)9780897919623

We address the problem of designing data structures that allow efficient search for approximate nearest neighbors. More specifically, given a database consisting of a set of vectors in some high dimensional Euclidean space, we want to construct a space-efficient data structure that would allow us to search, given a query vector, for the closest or nearly closest vector in the database. We also address this problem when distances are measured by the L1 norm, and in the Hamming cube. Significantly improving and extending recent results of Kleinberg, we construct data structures whose size is polynomial in the size of the database, and search algorithms that run in time nearly linear or nearly quadratic in the dimension (depending on the case;the extra factors are polylogarithmic in the size of the database).

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

An efficient balanced hierarchical data structure for multiversion accesses to spatio-temporal data 9

An efficient balanced hierarchical data structure for multiv...

引用

9th European Signal Processing conference, EUSIPCO 1998

作者： Dekihara, Hiroyuki Nakamura, Yasuaki Department of Computer Science Hiroshima City University 3-4-1 Otsuka-higashi Asa-minami-ku Hiroshima731-3194 Japan

In the management of spatio-temporal data, a data structure must manage multiple versions of a data structure efficiently, and provide quick and flexible search methods not only for temporal or spatial queries, but also for the combined queries of spatial and temporal intervals. The persistent MD-tree, called the PMD-tree is developed by extending a hierarchical data structure to support accesses to multiple versions. The PMD-tree has the novel properties that the tree representing any time aspect of a data structure is always balanced, and that the storage utilization rate is more than 66.6%. The algorithms of the PMD-tree, space and time analyses, and search performances compared to the MD-tree are described in the paper.

关键词： data structures

来源：评论

学校读者我要写书评

暂无评论

Interactive out-of-core isosurface extraction

Interactive out-of-core isosurface extraction

引用

IEEE conference on Visualization

作者： Y.-J. Chiang C.T. Silva W.J. Schroeder Polytechnic University USA IBM Thomas J. Watson Research Center USA Kitware Inc.orporate

We present a novel out-of-core technique for the interactive computation of isosurfaces from volume data. Our algorithm minimizes the main memory and disk space requirements on the visualization workstation, while speeding up isosurface extraction queries. Our overall approach is a two-level indexing scheme. First, by our meta-cell technique, we partition the original dataset into clusters of cells, called meta-cells. Secondly, we produce meta-intervals associated with the meta-cells, and build an indexing data structure on the meta-intervals. We separate the cell information, kept only in meta-cells on disk, from the indexing structure, which is also on disk and only contains pointers to meta-cells. Our meta-cell technique is an I/O-efficient approach for computing a k-d-tree-like partition of the dataset. Our indexing data structure, the binary blocked I/O interval tree, is a new I/O-optimal data structure to perform stabbing queries that report from a set of meta-intervals (or intervals) those containing a query value q. Our tree is simpler to implement, and is also more space-efficient in practice than existing structures. To perform an isosurface query, we first query the indexing structure, and then use the reported meta-cell pointers to read from disk the active meta-cells intersected by the isosurface. The isosurface itself can then be generated from active meta-cells. Rather than being a single cost indexing approach, our technique exhibits a smooth trade-off between query time and disk space.

关键词： Isosurfaces Indexing data mining Tree data structures Clustering algorithms Partitioning algorithms data visualization Workstations data structures Costs

来源：评论

学校读者我要写书评

暂无评论

efficient approach to symbolic state exploration of complex parallel controllers

Efficient approach to symbolic state exploration of complex ...

引用

International conference on Application of Concurrency to System Design

作者： K. Bilinski E.L. Dagless Department of Computer Engineering Technical University of Zielona Gora Gora Poland Advanced Computing Research Center University of Bristol Bristol UK

In this paper a method based on the use of zero-suppressed BDDs (0-Sup-BDDs) to symbolic state space exploration of parallel controllers is presented. Unlike traditional methods, the new approach is based on the implicit manipulation of sets of states instead of the manipulation of their characteristic functions. A formal specification of the parallel controller is given in the form of an interpreted Petri net. Experimental results demonstrate that the proposed approach can successfully compete against the state of the art methods of state space exploration.

关键词： data structures Boolean functions State-space methods Petri nets space exploration Concurrent computing Clustering algorithms Circuit synthesis Computational efficiency Costs

来源：评论

学校读者我要写书评

暂无评论

Binary space partitioning trees: A multiresolution approach

Binary space partitioning trees: A multiresolution approach

引用

1997 IEEE conference on Information Visualization (IV 97)

作者： Huerta, J Chover, M Quiros, R Vivo, R Ribelles, J Jaume I Univ Castellon Spain

ISBN: (纸本)0818680768

space partitioning techniques are a useful means of organizing geometric models into data structures. Such data structures provide easy and efficient access to a wide range of computer graphics and visualization applications like real-time rendering of large data bases, collision detection, point classification, etc. Binary space Partitioning (BSP) trees are one of the most successful space partitioning techniques, since they allow both object modeling and classification in one single structure. However, with the advent of networked graphics applications there is an increasing need for multiresolution geometric representations. This paper presents a novel method that extends BSP trees to provide such a representation. The models we present have the advantages of both BSP trees and multiresolution representations. Nodes near the room of the BSP tree store coarser versions of the geometry, while leaf nodes provide the finest details of the representation. We present in this paper different algorithms to construct multiresolution BSP trees in 2D. Then we propose extensions of our methods to 3D space.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

An object-oriented data cache architecture for programmable parallel digital signal processors 3

An object-oriented data cache architecture for programmable ...

引用

3rd International conference on algorithms and Architectures for Parallel Processing (ICA(3)PP)

作者： Kneip, J Univ Hannover Informat Technol Lab D-30167 Hannover Germany

ISBN: (纸本)0780342291

The paper describes concept and implementation of a data cache architecture with concurrent conflict free access to shared data for DSPs with parallel, synchronized processing units. It utilizes techniques known from object-oriented software design to achieve efficient and programmer friendly on-chip storage of data. The cache internally uses virtual 1D or 2D address spaces directly assigned to data structures instead of a conventional, linear address space. data within the cache are distributed to a number of memory banks. Virtual local addresses are used for data location and hit/miss detection to minimize cost and memory latency. The object-oriented cache is fully transparent to programmer and compiler, reduces the amount of address calculations to be performed, exploits the 2D spatial locality typical for image processing algorithms and can be integrated into a standard RISC processor pipeline.

关键词： Digital signal processors

来源：评论

学校读者我要写书评

暂无评论

efficient indexing for constraint and temporal databases 6th

引用

6th International conference on database Theory

作者： Ramaswamy, S AT&T Bell Labs Murray Hill NJ 07974 USA

ISBN: (纸本)3540622225

We examine new I/O-efficient techniques for indexing problems in constraint and temporal data models. We present algorithms for these problems that are considerably simpler than previous solutions. Our solutions are unique in the sense that they only use B+-trees rather than special-purpose data structures. Indexing for many general constraint data models can be reduced to interval intersection. We present a new algorithm for this problem using a query-time/space tradeoff, which achieves the optimal query time O(log(B)n + t/B) I/O's in linear space O(n/B) using B+-trees. (Here, n is the number of intervals, t the number of intervals in the output of a query, and B the disk block size.) It is easy to update this data structure, but small worst-case bounds do not seem possible. Previous approaches have achieved these bounds but are fairly complex and rely mostly on reducing the interval intersection problem to special cases of two-dimensional search. Some of them can also handle updates in O(log(B)n) I/O's amortized. Indexing in many temporal models becomes a generalization of interval management, where each temporal object is characterized by an interval and a key. There are many different ways of querying these objects, and we achieve optimal bounds for many of these queries. These bounds are achieved using a modification of the technique used for the constraint indexing problem. Our technique is much simpler than other techniques that have been used for achieving similar bounds.

关键词： data structures

来源：评论

学校读者我要写书评

暂无评论

Scheduling for interactive operations in parallel video servers

Scheduling for interactive operations in parallel video serv...

引用

IEEE International conference on Multimedia Computing and Systems (ICMCS)

作者： Min-You Wu Wei Shu Department of Computer Science State University of New York University at Buffalo USA

ISBN: (纸本)0818678194

Providing efficient support for interactive operations such as fast-forward and fast-backward is essential in video-on-demand and other multimedia server systems. The authors present two basic approaches for scheduling interactive operations, the prefetching approach and the grouping approach. Scheduling algorithms are presented for both fine-grain and coarse-grain data blocks. These algorithms can precisely schedule video streams for both normal playout and interactive operations.

关键词： Bandwidth Streaming media Video sharing Prefetching Network servers Processor scheduling Scheduling algorithm space technology Displays Computer architecture

来源：评论

学校读者我要写书评

暂无评论

An object-oriented data cache architecture for programmable parallel digital signal processors

An object-oriented data cache architecture for programmable ...

引用

IEEE International conference on algorithms and Architectures for Parallel Processing (ICAP)

作者： J. Kneip Laboratorium fir Informationstechnologie Universitat Hannover Hanover Germany

关键词： Computer architecture Programming profession Digital signal processing Software design data structures Costs Delay Program processors Image processing Reduced instruction set computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：