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

TWO algorithms FOR incremental CONSTRUCTION OF DIRECTED ACYCLIC WORD GRAPHS

International Journal on Artificial Intelligence Tools 1995年第3期4卷 369-381页

作者： KYRIAKOS N. SGARBAS NIKOS D. FAKOTAKIS GEORGE K. KOKKINAKIS Wire Communications Lab. Electrical Engineering Dept. University of Patras Patras GR-26500 Greece

In this paper we present two algorithms for building lexicons in Directed Acyclic Word-Graphs (DAWGs). The two algorithms, one for deterministic and the other for non-deterministic DAWGs, can be used instead of the traditional subset construction method. Although the proposed algorithms do not produce the optimal DAWG (i.e., the one with the minimum number of states), they are simple, fast and able to build the DAWG incrementally, as new words are added to the lexicon. Thus, building large lexicons in a DAWG structure becomes an easy task, even for a modest computer.

关键词： Search graphs data structures lexicon building incremental algorithms content-addressable search

来源：评论

学校读者我要写书评

暂无评论

incremental Detection of Inconsistencies in Distributed Data

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2014年第6期26卷 1367-1383页

作者： Fan, Wenfei Li, Jianzhong Tang, Nan Yu, Wenyuan Univ Edinburgh Sch Informat Lab Fdn Comp Sci LFCS Edinburgh EH8 9AB Midlothian Scotland Harbin Inst Technol Sch Comp Sci & Technol Dept Comp Sci & Engn Heilongjiang 150001 Peoples R China Qatar Fdn Qatar Comp Res Inst QCRI Doha Qatar

This paper investigates incremental detection of errors in distributed data. Given a distributed database D, a set Sigma of conditional functional dependencies (CFDs), the set V of violations of the CFDs in D, and updates Delta D to D, it is to find, with minimum data shipment, changes Delta V to V in response to Delta D. The need for the study is evident since real-life data is often dirty, distributed and frequently updated. It is often prohibitively expensive to recompute the entire set of violations when D is updated. We show that the incremental detection problem is NP-complete for database D that is partitioned either vertically or horizontally, even when Sigma and D are fixed. Nevertheless, we show that it is bounded: there exist algorithms to detect errors such that their computational cost and data shipment are both linear in the size of Delta D and Delta V, independent of the size of the database D. We provide such incremental algorithms for vertically partitioned data and horizontally partitioned data, and show that the algorithms are optimal. We further propose optimization techniques for the incremental algorithm over vertical partitions to reduce data shipment. We verify experimentally, using real-life data on Amazon Elastic Compute Cloud (EC2), that our algorithms substantially outperform their batch counterparts.

关键词： incremental algorithms distributed data conditional functional dependencies error detection

来源：评论

学校读者我要写书评

暂无评论

An evaluation of point-insertion sequences for incremental Delaunay tessellations

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2018年第1期37卷 641-674页

作者： Gonzaga de Oliveira, Sanderson L. Nogueira, Jessica Renata Univ Fed Lavras Lavras Brazil Inst Fed Educ Ciencia & Tecnol Sul Minas Gerais Campus Passos Passos Brazil

Currently, incremental algorithms may be seen as the lowest-cost computational methods to generate Delaunay tessellations in several point distributions. In this work, eight point-insertion sequences in incremental algorithms for generating Delaunay tessellations are evaluated. More specifically, four point-insertion sequences in incremental algorithms for generating Delaunay tessellations are proposed: with orders given by the red-black tree with in-order and level-order traversals, spiral ordering, and H-indexing. These four incremental algorithms with such sequences are compared with four incremental algorithms with point-insertion orders given by the following sequences: the Hilbert and Lebesgue curves, cut-longest-edge kd-tree, and random order. Six 2-D and seven 3-D point distributions are tested, with sets ranging from 25,000 to 8,000,000 points. The results of computational and storage costs of these eight algorithms are analyzed. It follows that the incremental algorithm with a point-insertion sequence in the order given by the cut-longest-edge kd-tree shows the lowest computational and storage costs of the sequences tested.

关键词： Mesh generation Delaunay tessellation incremental algorithms Computer-aided design, engineering and manufacturing Computational geometry and topology Insertion sequences Non-uniform point distributions

来源：评论

学校读者我要写书评

暂无评论

On solving the Lagrangian dual of integer programs via an incremental approach

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2009年第1期44卷 117-138页

作者： Gaudioso, Manlio Giallombardo, Giovanni Miglionico, Giovanna Univ Calabria Dipartimento Elettron Informat & Sistemist I-87036 Arcavacata Di Rende CS Italy

The Lagrangian dual of an integer program can be formulated as a min-max problem where the objective function is convex, piecewise affine and, hence, nonsmooth. It is usually tackled by means of subgradient algorithms, or multiplier adjustment techniques, or even more sophisticated nonsmooth optimization methods such as bundle-type algorithms. Recently a new approach to solving unconstrained convex finite min-max problems has been proposed, which has the nice property of working almost independently of the exact evaluation of the objective function at every iterate-point. In the paper we adapt the method, which is of the descent type, to the solution of the Lagrangian dual. Since the Lagrangian relaxation need not be solved exactly, the approach appears suitable whenever the Lagrangian dual must be solved many times (e.g., to improve the bound at each node of a branch-and-bound tree), and effective heuristic algorithms at low computational cost are available for solving the Lagrangian relaxation. We present an application to the Generalized Assignment Problem (GAP) and discuss the results of our numerical experimentation on a set of standard test problems.

关键词： incremental algorithms Convex minimization Finite min-max Lagrangian relaxation Nonsmooth optimization Bundle methods

来源：评论

学校读者我要写书评

暂无评论

An incremental algorithm for concept lattice based on structural similarity index

引用

SOFT COMPUTING 2022年第21期26卷 11409-11423页

作者： Hu, Yu Hu, Yan Zhu Su, Zhong Li, Xiao Li Meng, Zhen Tian, Wen Jia Yang, Yan Ying Chai, Jia Feng Beijing Informat Sci & Technol Univ Sch Automat 12 Qinghe Xiao Ying East Rd Beijing 100196 Peoples R China Beijing Univ Posts & Telecommun Sch Modern Post 10 Xi Tu Cheng Rd Beijing 100876 Peoples R China Beijing Univ Technol Informat Dept 100 Ping Le Yuan Beijing 100124 Peoples R China Beijing Acad Sci & Technol 27West 3rd Ring Rd NorthBeike Bldg Beijing 100089 Peoples R China Beijing Gas Grp Co 22 XiZhiMen NanXiao St Beijing 100035 Peoples R China

As an effective tool for data analysis, formal concept analysis (FCA) is widely used in software engineering and machine learning. The construction of concept lattice is a key step of the FCA. How to effectively to update the concept lattice is still an open, interesting and important issue. To resolve this problem, an incremental algorithm for concept lattice on image structure similarity (SsimAddExten) was presented. The proposed method mapped each knowledge class on the conceptlattice into a graphic, when a new object was added or deleted in a knowledge class, the boundary profile of graphic will be changed, the graphic edge structure similarity was introduced as the calculation index of the change degree before and after the knowledge, and the concept lattice will be updated on the basis of the index. We performed experiments to test SsimAddExtent, whose computational efficiency obtains obvious advantages over mainstream methods on almost all test points, especially on the data set with a large number of attributes. But, its complexity is not reduced compared with mainstream methods. Both theoretical analysis and performance test show SsimAddExtent algorithm is better choice when we apply the FCA to large scale data or non-sparse data.

关键词： Concept lattice incremental algorithms Structural similarity index Edge detection Fourier Descriptor

来源：评论

学校读者我要写书评

暂无评论

Speeding up incremental wrapper feature subset selection with Naive Bayes classifier

引用

KNOWLEDGE-BASED SYSTEMS 2014年第Jan.期55卷 140-147页

作者： Bermejo, Pablo Gamez, Jose A. Puerta, Jose M. Univ Castilla La Mancha Intelligent Syst & Data Min Lab 13A Dept Comp Syst Albacete 02071 Spain

This paper deals with the problem of wrapper feature subset selection (FSS) in classification-oriented datasets with a (very) large number of attributes. In high-dimensional datasets with thousands of variables, wrapper FSS becomes a laborious computational process because of the amount of CPU time it requires. In this paper we study how under certain circumstances the wrapper FSS process can be speeded up by embedding the classifier into the wrapper algorithm, instead of dealing with it as a black-box. Our proposal is based on the combination of the NB classifier (which is known to be largely beneficial for FSS) with incremental wrapper FSS algorithms. The merit of this approach is analyzed both theoretically and experimentally, and the results show an impressive speed-up for the embedded FSS process. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Wrapper feature subset selection incremental algorithms Naive Bayes High-dimensional data

来源：评论

学校读者我要写书评

暂无评论

On the effectiveness of the incremental approach to minimal chordal edge modification

引用

THEORETICAL COMPUTER SCIENCE 2021年 888卷 1-12页

作者： Blair, Jean R. S. Crespelle, Christophe US Mil Acad Dept Elect Engn & Comp Sci West Point NY USA Univ Bergen Dept Informat N-5020 Bergen Norway

Because edge modification problems are computationally difficult for most target graph classes, considerable attention has been devoted to inclusion-minimal edge modifications, which are usually polynomial-time computable and which can serve as an approximation of minimum cardinality edge modifications, albeit with no guarantee on the cardinality of the resulting modification set. Over the past fifteen years, the primary design approach used for inclusion-minimal edge modification algorithms is based on a specific incremental scheme. Unfortunately, nothing guarantees that the set epsilon of edge modifications of a graph Gthat can be obtained in this specific way spans all the inclusion-minimal edge modifications of G. Here, we focus on edge modification problems into the class of chordal graphs and we show that for this the set epsilon may not even contain any solution of minimum size and may not even contain a solution close to the minimum;in fact, we show that it may not contain a solution better than within an Omega(n) factor of the minimum. These results show strong limitations on theuse of the current favored algorithmic approach to inclusion-minimal edge modification in heuristics for computing a minimum cardinality edge modification. They suggest that further developments might be better using other approaches. (C) 2021 The Authors. Published by Elsevier B.V.

关键词： Chordal graphs Edge modification incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

incremental DISTRIBUTED ASYNCHRONOUS ALGORITHM FOR MINIMUM SPANNING-TREES

COMPUTER NETWORKS AND ISDN SYSTEMS

引用

COMPUTER NETWORKS AND ISDN SYSTEMS 1993年第2期26卷 227-232页

作者： TSIN, YH UNIV WINDSOR SCH COMP SCIWINDSOR N9B 3P4ONTARIOCANADA

A distributed algorithm for updating a minimum spanning tree when a new vertex is added to the underlying network connected, undirected, weighted graph) is presented. The algorithm runs asynchronously and the processor at each vertex of the network is required to know only information concerning its adjacent edges. The number of messages transmitted is bounded by 6N and the time complexity is O(H) where N and H(less-than-or-equal-to N) are the number of vertices and the height of the original minimum spanning tree, respectively. Each message contains at most an edge weight and a few bits. This result is superior to the previously known result as well as that of using the best known distributed minimum spanning tree algorithm to construct a minimum spanning tree for the new network from scratch. The algorithm is extended to handle k(greater-than-or-equal-to 1) vertex insertions. The resulting time and message complexities are O(k * max(H, H-1, . . . , H(k - 1))) and O(kN + k2) respectively, where H(i) is the height of the MST after i new vertices have been handled. The algorithm can be modified to handle edge insertions within same time and message bounds.

关键词： DISTRIBUTED algorithms COMMUNICATION NETWORKS MINIMUM SPANNING TREES GRAPH THEORY incremental algorithms VERTEX INSERTION

来源：评论

学校读者我要写书评

暂无评论

incremental convex minimization for computing collision translations of convex polyhedra

引用

IEEE TRANSACTIONS ON ROBOTICS 2007年第3期23卷 403-415页

作者： Mirolo, Claudio Carpin, Stefano Pagello, Enrico Univ Udine Dept Math & Comp Sci I-33100 Udine Italy Univ Calif Sch Engn Merced CA 95344 USA Univ Padua Dept Informat Engn I-35131 Padua Italy

The subject of this paper is an asymptotically fast and incremental algorithm for computing collision translations of convex polyhedra, where the problem at hand is reduced to determining collision translations of pairs of planar sections and minimizing a bivariate convex function. There are two main reasons, in our view, why the algorithm is worth consideration. On the one hand, the addressed proximity measure, namely collision translation, is not as widely studied as distance. On the other, its peculiar computation strategy may be interesting in itself, being well suited to work without initialization and also endowed with an inherently embedded mechanism to exploit spatial coherence. After outlining the main ideas of this novel approach and providing an estimation of the computational costs, we summarize a broad set of numerical experiments meant to explore extensively the behavior of the algorithm, both without and with initialization. Finally, in order to assess the efficacy and the potential of the approach under analysis, the attained performances are contrasted with those of other popular algorithms designed to compute distances between polyhedra. A thorough comparison of the reported query times an, more significantly of the corresponding trends shows that the behavior of the collision translation algorithm is quite interesting, especially when used without initialization or under variable coherence, which should encourage further work on this approach.

关键词： collision detection convex minimization convex polyhedra incremental algorithms proximity problems

来源：评论

学校读者我要写书评

暂无评论

An incremental least squares algorithm for large scale linear classification

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2013年第3期224卷 560-565页

作者： Cassioli, A. Chiavaioli, A. Manes, C. Sciandrone, M. Univ Florence Dipartimento Sistemi & Informat I-50139 Florence Italy Univ Aquila Dip Ingn & Sci Informaz & Matemat I-67100 Coppito AQ Italy Radiat Oncol Massachusetts Gen Hosp Boston MA 02114 USA Harvard Univ Sch Med Boston MA 02114 USA

In this work we consider the problem of training a linear classifier by assuming that the number of data is huge (in particular, data may be larger than the memory capacity). We propose to adopt a linear least-squares formulation of the problem and an incremental recursive algorithm which requires to store a square matrix (whose dimension is equal to the number of features of the data). The algorithm (very simple to implement) converges to the solution using each training data once, so that it effectively handles possible memory issues and is a viable method for linear large scale classification and for real time applications, provided that the number of features of the data is not too large (say of the order of thousands). The extensive computational experiments show that the proposed algorithm is at least competitive with the state-of-the-art algorithms for large scale linear classification. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Large scale optimization Machine learning Linear classification incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：