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

7th International conference on database and Expert Systems Applications, DEXA 1996

作者： Tran, Nguyen Le, Dung Phu Srinivasan, Bala Sier, Bob Department of Computer Technology Monash University Australia

ISBN: (纸本)9783540616566

Tree-based spatial indexing techniques have been developed for advanced applications which require high dimensional data. However, studies on spatial access methods particularly focus on the data structures and algorithms, performances in the worst case may not be predicted. In this paper, we propose a methodology for evaluating the performance of tree-based indexing techniques in the worst case, and a new tree-based data structure for indexing. The methodology allows better selection of indexing techniques for applications without having to actually implementing and experimenting the techniques. The new tree-based structure allows more efficient storage space utilisation and better searching time in comparison to the R-tree and TV-tree.

关键词： data structures

来源：评论

学校读者我要写书评

暂无评论

Path-consistency:: When space misses time

Path-consistency:: When space misses time

引用

13th National conference on Artificial Intelligence (AAAI 96) / 8th conference on Innovative Applications of Artificial Intelligence (IAAI 96)

作者： Chmeiss, A Jégou, P Univ Aix Marseille 1 CMI LIM URA CNRS 1787 F-13453 Marseille 13 France

ISBN: (纸本)026251091X

Within the framework of constraint programming, particulary concerning the Constraint Satisfaction Problems (CSPs), the techniques of preprocessing based on filtering algorithms were shown to be very important for the search phase. In particular, two filtering methods have been studied, these methods exploit two properties of local consistency: arc-and path-consistency. Concerning the are-consistency methods, there is a linear time algorithm (in the size of the problem) which is efficientin practice (Bessikrel Freuder, & Regin 1995). But the limitations of the are-consistency algorithms requires often filtering methods with higher order like path-consistency filterings;The best path-consistency algorithm proposed is PC-6, a natural generalization of AC-6 (Bessiere 1994) to path-consistency (Chmeiss St Jegou 1995)(Chmeiss 1996). Its time complexity is O(n(3)d(3)) and its space complexity is O(n(3)d(2)), where n is the number of variables and cd is the size of domains. We have remarked that PC-6, though it is widely better than PC-4 (Han & Lee 1988), was not very efficient in practice, specialy for those classes of problems that require an important space to be run. Therefore, we propose here a new path-consistency algorithm called PC-7, its space complexity is O(n(2)d(2)) but its time complexity is O(n(3)d(4)) i.e. worse than that of PC-6. However, the simplicity of PC-7 as well as the data structures used for its implementation offer really a higher performance than PC-6. Furthermore, it turns out that when the size of domains is a constant of the problems, the time complexity of PC-7 becomes, like PC-6, optimal i.e. O(n(3)).

关键词： CSPs path-consistency PC-2 PC-4 PC-6 clp(FD)

来源：评论

学校读者我要写书评

暂无评论

Global rebuilding of OBDD's avoiding memory requirement maxima

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 1996年第1期15卷 131-134页

作者： Bern, J Meinel, C Slobodova, A University of Trier Trier Germany

It is wed-known that the size of an ordered binary decision diagram (OBDD) may depend crucially on the order in which the variables occur. In the paper, we describe an implementation of an output-efficient algorithm that transforms an OBDD P representing a Boolean function f with respect to one variable ordering pi into an OBDD Q that represents f with respect to another variable ordering sigma. The algorithm runs in average time O(\P parallel to Q\) and requires O(\P\ + \Q\) space. The importance of the algorithm gets demonstrated by means of experimental results on basically two different applications. In one of them, the algorithm is used merely once. Such transformations are needed to test equivalence or to perform synthesis on OBDD's in which variables appear in different orders. The other application shows a way how to decrease the size of intermediate OBDD representations of a given circuit in the course of its symbolic simulation. Here, the algorithm is used dynamically, whenever the size of the manipulated OBDD's becomes too large.

关键词： Boolean functions data structures Circuit testing Performance evaluation Circuit synthesis Circuit simulation Heuristic algorithms

来源：评论

学校读者我要写书评

暂无评论

Exploiting partitioned transition relations for efficient symbolic model checking in CTL 96

Exploiting partitioned transition relations for efficient sy...

引用

European Design and Test (ED&TC) conference

作者： A. Casar Z. Brezocnik T. Kapus University of Maribor Slovenia

We present an efficient tool for symbolic state space traversal of finite state machines. Both algorithms for searching reachable states and for model checking in CTL owe their efficiency primarily to the use of parti... 详细信息

ISBN: (纸本)9780818674235

关键词： Binary decision diagrams State-space methods Partitioning algorithms Boolean functions data structures Central Processing Unit Circuit testing Automata Heuristic algorithms Software packages

来源：评论

学校读者我要写书评

暂无评论

Two new constraint propagation algorithms requiring small space complexity

Two new constraint propagation algorithms requiring small sp...

引用

International conference on Tools for Artificial Intelligence (ICTAI)

作者： A. Chmeiss P. Jegou LIM-URA CNRS 1787 CMI Université de Provence Marseilles France

Recently, efficient algorithms have been proposed to achieve arc- and path-consistency in constraint networks. The best path-consistency algorithm proposed is PE-{5|6} which is a natural generalization of AC-6 to path-consistency independently proposed by M. Singh (1995) for PC-5 and A. Chmeiss and P. Jegou (1995) for PC-6. Unfortunately, we have remarked that PC-{5|6}, though it is widely better than PC-4 (Chmeiss and P. Jegou, 1996) was not very efficient in practice, especially for those classes of problems that require an important space to be run. So, we propose a new path-consistency algorithm called PC-8, the space complexity of which is O(n/sup 2/d) but its time complexity is O(n/sup 3/d/sup 4/), i.e. worse than that of PC-{5|6}. However, the simplicity of PC-8 as well as the data structures used for its implementation offer a higher performance than PC-{5|6}. The principle of PC-8 is also used to propose a new algorithm to achieve arc-consistency called AC-8.

关键词： data structures Filtering algorithms Time factors

来源：评论

学校读者我要写书评

暂无评论

Programming fuzzy logic in assembly language

Programming fuzzy logic in assembly language

引用

Northcon

作者： J.M. Sibigtroth Motorola Inc. Austin TX USA

This paper outlines the subjects covered in a half-day class an programming fuzzy logic algorithms in assembly language. The short course covers assembly language examples that are not shown in this paper, and goes into much greater detail. Assembly language allows more efficient fuzzy logic programs in terms of code space and execution time compared to C programs. After attending this class, a participant should be able to estimate the code size and execution time requirements for various fuzzy logic programs and data structures. These skills can then be applied to embedded control applications.

关键词： Logic programming Fuzzy logic Assembly Fuzzy systems data structures Software performance Read-write memory Hardware Fuzzy control Software algorithms

来源：评论

学校读者我要写书评

暂无评论

Grid-clustering: an efficient hierarchical clustering method for very large data sets

Grid-clustering: an efficient hierarchical clustering method...

引用

International conference on Pattern Recognition

作者： E. Schikuta Institute of Applied Computer Science and Information Systems University of Technology Vienna Austria

Clustering is a common technique for the analysis of large images. In this paper a new approach to hierarchical clustering of very large data sets is presented. The GRIDCLUS algorithm uses a multidimensional grid data structure to organize the value space surrounding the pattern values, rather than to organize the patterns themselves. The patterns are grouped into blocks and clustered with respect to the blocks by a topological neighbor search algorithm. The runtime behavior of the algorithm outperforms all conventional hierarchical methods. A comparison of execution times to those of other commonly used clustering algorithms, and a heuristic runtime analysis are presented.

关键词： Clustering methods Clustering algorithms Partitioning algorithms Multidimensional systems data structures Runtime Computer science Information systems Heuristic algorithms Algorithm design and analysis

来源：评论

学校读者我要写书评

暂无评论

efficient lossless compression of trees and graphs

Efficient lossless compression of trees and graphs

引用

data Compression conference (DCC)

作者： Shenfeng Chen J.H. Reif Department of Computer Science Duke University Durham NC USA

Summary form only given, as follows. data compression algorithms have been widely used in many areas to meet the demand of storage and transfer of large size data. Most of the data compression algorithms regard the input as a sequence of binary numbers and represent the compressed data also as a binary sequence. However, in many areas such as programming languages (e.g. LISP and C) and compiler design, it is more desirable to have a compression algorithm which compresses a data structure while keeping a similar structure of the original data in the compressed form. In addition to reducing storage space, such compression also has the benefit of efficiently executing various operations (e.g. searching) in the compressed form. We study the problem of compressing a non-binary data structure (e.g. tree, undirected and directed graphs) in an efficient way while keeping a similar structure in the compressed form. To date, there has been no proven optimal algorithm for this problem. We use the idea of building LZW tree in LZW compression to compress a binary tree generated by a stationary ergodic source. The tree is parsed into subtrees using breadth first search and an optimal dictionary is constructed with each index pointing to a distinct subtree. We replace the parsed subtrees by dictionary indices to formed the compressed tree. We also extend our tree compression algorithm to compress undirected and directed acyclic graphs.

关键词： Tree graphs data compression Compression algorithms Dictionaries Binary sequences Computer languages Algorithm design and analysis data structures Tree data structures Buildings

来源：评论

学校读者我要写书评

暂无评论

Optimal dynamic interval management in external memory

Optimal dynamic interval management in external memory

引用

Annual IEEE Symposium on Foundations of Computer Science

作者： L. Arge J.S. Vitter Department of Computer Science Duke University Durham NC USA

The authors present a space- and I/O-optimal external-memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The data structure settles an open problem in databases and I/O algorithms by providing the first optimal external-memory solution to the dynamic interval management problem, which is a special case of 2-dimensional range searching and a central problem for object-oriented and temporal databases and for constraint logic programming. The data structure simultaneously uses optimal linear space (that is, O(N/B) blocks of disk space) and achieves the optimal O(log/sub B/ N+T/B) I/O query bound and O(log/sub B/ N) I/O update bound, where B is the I/O block size and T the number of elements in the answer to a query. The structure is also the first optimal external data structure for a 2-dimensional range searching problem that has worst-case as opposed to amortized update bounds. Part of the data structure uses a novel balancing technique for efficient worst-case manipulation of balanced trees, which is of independent interest.

关键词： Memory management data structures Object oriented databases Logic programming Computer science Dynamic programming Object oriented modeling Tree data structures Indexing Earth Observing System

来源：评论

学校读者我要写书评

暂无评论

A compact and fast structure for trie retrieval algorithms

A compact and fast structure for trie retrieval algorithms

引用

IEEE International conference on Systems, Man and Cybernetics

作者： H. Mochizuki Y. Hayashi M. Shishibori J.-I. Aoe Department of Information Science & Intelligent Systems University of Tokushima Tokushima Japan

A trie structure is frequently used for various applications, such as natural language dictionaries, database systems and compilers. However, the total number of states (and transitions between them) of a trie becomes large so that space cost may not be acceptable for a huge key set. In order to resolve this disadvantage, this paper presents a new scheme, called "trio-trie", that enables us to perform efficient retrievals, insertions and deletions for the key sets. The essential idea is to construct two tries for both front and rear compressions of keys which is similar to a DAWG (Directed Acyclic Word-Graph). The approach differs from a DAWG in that the two-trie approach presented can determine uniquely information corresponding to keys while a DAWG cannot. For an efficient implementation of the two-trie, two types of data structures are introduced. The theoretical and experimental observations show that the method presented is more practical than existing ones considering the use of dynamic key sets, storing information of keys and compression of transitions.

关键词： Information retrieval Tail Natural languages Dictionaries data structures Information science Intelligent systems Deductive databases Intelligent structures database systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：