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

Generating frequent itemsets incrementally: two novel approaches based on Galois lattice theory

JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE 2002年第2期14卷 115-142页

作者： Valtchev, P Missaoui, R Godin, R Meridji, M Univ Montreal DIRO Montreal PQ H3C 3J7 Canada Univ Quebec Montreal Dept Informat Montreal PQ H3C 3P8 Canada

Galois (concept) lattice theory has been successfully applied in data mining for the resolution of the association rule problem. In particular, structural results about lattices have been used in the design of efficient procedures for mining the frequent patterns (itemsets) in transaction databases. Since such databases are often dynamic, we propose a detailed study of the incremental aspects in lattice construction to support effective procedures for incremental mining of frequent closed itemsets (FCIs). Based on a set of descriptive results about lattice substructures involved in incremental updates, the paper presents a novel algorithm for lattice construction that explores only limited parts of a lattice for updating. Two new methods for incremental FCI mining are studied: the first inherits its extensive search strategy from a classical lattice method, whereas the second applies the new lattice construction strategy to the itemset mining context. Unlike batch techniques based on FCIs, both methods avoid rebuilding the FCI family from scratch whenever new transactions are added to the database and/or when the minimal support is changed.

关键词： market basket analysis association rule mining closed itemset extraction Galois lattices incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

An incremental algorithm for simultaneous construction of 2D Voronoi diagram and Delaunay triangulation based on a face-based data structure

引用

ADVANCES IN ENGINEERING SOFTWARE 2022年 169卷

作者： Shivanasab, Pooya Abbaspour, Rahim Ali Univ Tehran Coll Engn Sch Surveying & Geospatial Engn Tehran Iran

In this paper, a new incremental algorithm with an overall complexity of O(nlogn) for constructing both the 2D Voronoi diagram (VD) and Delaunay triangulation (DT) is proposed. Moreover, a new face-based data structure is proposed which is more cost-effective in terms of memory than the previous edge-based data structures. The proposed data structure maintains the VD and DT in separate matrices, while establishing a connection between these two, allowing extracting neighborhoods and geometric information without the need for further processing in many applications. Moreover, the proposed data structure can be easily converted to the other edge-based data structures such as the Doubly Connected Edge List. The proposed algorithm for finding the nearest neighbor to the added point, in this incremental algorithm, has O(logn) complexity. Evaluations performed by points with different numbers and distributions confirm the high robustness of the proposed algorithm against different point distributions and its O(nlogn) overall complexity.

关键词： Delaunay triangulation Voronoi diagram Computational geometry incremental algorithms Data structures Point Insertion

来源：评论

学校读者我要写书评

暂无评论

String-averaging incremental subgradients for constrained convex optimization with applications to reconstruction of tomographic images

引用

INVERSE PROBLEMS 2016年第11期32卷 115014-115014页

作者： de Oliveira, Rafael Massambone Helou, Elias Salomao Costa, Eduardo Fontoura Univ Sao Paulo Inst Math & Comp Sci Dept Appl Math & Stat BR-13566590 Sao Carlos SP Brazil

We present a method for non-smooth convex minimization which is based on subgradient directions and string-averaging techniques. In this approach, the set of available data is split into sequences (strings) and a given iterate is processed independently along each string, possibly in parallel, by an incremental subgradient method. (ISM). The end-points of all strings are averaged to form the next iterate. The method is useful to solve sparse and large-scale non-smooth convex optimization problems, such as those arising in tomographic imaging. A convergence analysis is provided under realistic, standard conditions. Numerical tests are performed in a tomographic image reconstruction application, showing good performance for the convergence speed when measured as the decrease ratio of the objective function, in comparison to classical ISM.

关键词： convex optimization incremental algorithms subgradient methods projection methods string-averaging algorithms

来源：评论

学校读者我要写书评

暂无评论

ECO Cost Measurement and incremental Gate Sizing for Late Process Changes

引用

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS 2013年第1期18卷 16-16页

作者： Lee, John Gupta, Puneet Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90024 USA

Changes in the manufacturing process parameters may create timing violations in a design, making it necessary to perform an engineering change order (ECO) to correct these problems. We present a framework for performing incremental gate sizing for process changes late in the design cycle, and a method for creating initial designs that are robust to late process changes. This includes a method for measuring and estimating ECO cost and for transforming these costs into linear programming optimization problems. In the case of ECOs, the method reduces ECO costs on average, by 89% in changed area compared to a leading commercial tool. Furthermore, the robust initial designs are, on average, 55% less likely to need redesign in the future.

关键词： Design algorithms Performance Gate sizing incremental algorithms ECO linear programming

来源：评论

学校读者我要写书评

暂无评论

A CONVEX HULL ALGORITHM FOR POINTS WITH APPROXIMATELY KNOWN POSITIONS

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1994年第2期4卷 153-163页

作者： Franciosa, Paolo Giulio Gaibisso, Carlo Gambosi, Giorgio Talamo, Maurizio Univ Rome La Sapienza Dipartimento Infomat & Sistemist I-00198 Rome Italy CNR Ist Anal Sistemi & Informat I-00185 Rome Italy Univ Aquila Dipartimento Matemat Pura & Applicata I-67010 Laquila Italy

We consider the problem of deriving good approximations of the convex hull of a set of points in the plane in the realistic case that only arbitrary finite approximations of the real valued coordinates can be known. In particular, the algorithm we introduce derives sequences of improved certified approximations converging to the exact solution, at the same time allowing the insertion of new points to the problem instance. The complexity analysis of the algorithm is performed by referring to a suitable computation model, based on a RAM with logarithmic costs, and the derived space and time bounds are shown to be competitive with respect to current off-line algorithms.

关键词： Computational geometry convex hull incremental algorithms approximated algorithms scaling spatial data

来源：评论

学校读者我要写书评

暂无评论

Efficient grid-based spatial representations for robot navigation in dynamic environments

引用

ROBOTICS AND AUTONOMOUS SYSTEMS 2013年第10期61卷 1116-1130页

作者： Lau, Boris Sprunk, Christoph Burgard, Wolfram Univ Freiburg D-79110 Freiburg Germany

In robotics, grid maps are often used for solving tasks like collision checking, path planning, and localization. Many approaches to these problems use Euclidean distance maps (DMs), generalized Voronoi diagrams (GVDs), or configuration space (c-space) maps. A key challenge for their application in dynamic environments is the efficient update after potential changes due to moving obstacles or when mapping a previously unknown area. To this end, this paper presents novel algorithms that perform incremental updates that only visit cells affected by changes. Furthermore, we propose incremental update algorithms for DMs and GVDs in the configuration space of non-circular robots. These approaches can be used to implement highly efficient collision checking and holonomic path planning for these platforms. Our c-space representations benefit from parallelization on multi-core CPUs and can also be integrated with other state-of-the-art path planners such as rapidly-exploring random trees. In various experiments using real-world data we show that our update strategies for DMs and GVDs require substantially less cell visits and computation time compared to previous approaches. Furthermore, we demonstrate that our GVD algorithm deals better with non-convex structures, such as indoor areas. All our algorithms consider actual Euclidean distances rather than grid steps and are easy to implement. An open source implementation is available online. (C) 2013 Published by Elsevier B.V.

关键词： incremental algorithms Voronoi diagrams Distance maps Configuration space Collision checking Robot navigation

来源：评论

学校读者我要写书评

暂无评论

A subspace type incremental two-dimensional principal component analysis algorithm

引用

JOURNAL OF algorithms & COMPUTATIONAL TECHNOLOGY 2020年第14期14卷 -页

作者： Zhang, Xiaowei Teng, Zhongming Fujian Agr & Forestry Univ Coll Comp & Informat Sci Fuzhou Peoples R China Key Lab Ecol & Resources Stat Fujian Prov Fuzhou Peoples R China

Principal component analysis (PCA) has been a powerful tool for high-dimensional data analysis. It is usually redesigned to the incremental PCA algorithm for processing streaming data. In this paper, we propose a subspace type incremental two-dimensional PCA algorithm (SI2DPCA) derived from an incremental updating of the eigenspace to compute several principal eigenvectors at the same time for the online feature extraction. The algorithm overcomes the problem that the approximate eigenvectors extracted from the traditional incremental two-dimensional PCA algorithm (I2DPCA) are not mutually orthogonal, and it presents more efficiently. In numerical experiments, we compare the proposed SI2DPCA with the traditional I2DPCA in terms of the accuracy of computed approximations, orthogonality errors, and execution time based on widely used datasets, such as FERET, Yale, ORL, and so on, to confirm the superiority of SI2DPCA.

关键词： PCA 2DPCA incremental algorithms subspace method feature extraction

来源：评论

学校读者我要写书评

暂无评论

An incremental Algorithm to Check Satisfiability for Bounded Model Checking

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2005年第2期119卷 51-65页

作者： Jin, HoonSang Somenzi, Fabio Univ Colorado Boulder CO USA

In Bounded Model Checking (BMC), the search for counterexamples of increasing lengths is translated into a sequence of satisfiability (SAT) checks. It is natural to try to exploit the similarity of these SAT instances by forwarding clauses learned during conflict analysis from one instance to the next. The methods proposed to identify clauses that remain valid fall into two categories: Those that are oblivious to the mechanism that generates the sequence of SAT instances and those that rely on it. In the case of a BMC run, it was observed by Strichman [20] that those clauses learned during one SAT check that only depend on the structure of the model remain valid when checking for longer counterexamples. E'en and Sorensson [9] pointed out that all learned clauses can be forwarded if the translation into SAT obeys commonly followed rules. Many clauses that are forwarded this way, however, are of little usefulness and may degrade performance. This paper presents an extension to Strichman's approach in the form of a more general criterion to filter conflict clauses that can be profitably forwarded to successive instances. This criterion, in particular, is still syntactic and quite efficient, but accounts for the presence of both primary and auxiliary objectives in the SAT instance. This paper also introduces a technique to distill clauses to be forwarded even though they fail the syntactic check. Distillation is a semantic approach that can be applied in general to incremental SAT, and often produces clauses that are independent of the primary objective, and hence remain valid for the remainder of the sequence of instances. In addition, distillation often improves the quality of the clauses, that is, their ability to prevent the examination of large regions of the search space. Experimental results obtained with the CirCUs SAT solver confirm the efficacy of the proposed techniques, especially for large, hard problems.

关键词： bounded model checking propositional satisfiability conflict-learned clauses incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

On-line Solution of System Constraints in Generalized Predictive Control Design Convenient Way to Cope with Constraints 20

On-line Solution of System Constraints in Generalized Predic...

引用

20th International Conference on Process Control (PC)

作者： Belda, Kvetoslav Acad Sci Czech Republic Inst Informat Theory & Automat Dept Adapt Syst Pod Vodarenskou Vezi 4 Prague 8 Czech Republic

ISBN: (纸本)9781467366274

A specific efficient solution of constrained system outputs is presented. The solution is based on on-line weighting of individual system outputs or output components representing in fact a specific on-line tuning/applification of the components of weighting control parameters. Thus, the predictive control design retains flexibility without any increase of time-computational demands. The proposed solution represents only soft solution of the constraints, i.e. a compliance with the constraints is not fully guaranteed, but the result is satisfactory and not so far from results of hard-constraint solution computed e.g. by a quadratic programming. The solution predetermines the area of the use to the systems with fast dynamics requiring very high sampling rates as electric drives and the like. The solution is presented in the paper as a generalized solution for common use. It is demonstrated by simple simulative examples and one illustration from a real control of 3-phase electric drive.

关键词： Predictive control incremental algorithms system constraints component tuning of control parameters quadratic cost function quadratic programming problem

来源：评论

学校读者我要写书评

暂无评论

Efficient Maintenance of All-Pairs Shortest Distances 16

Efficient Maintenance of All-Pairs Shortest Distances

引用

28th International Conference on Scientific and Statistical Database Management (SSDBM)

作者： Greco, Sergio Molinaro, Cristian Pulice, Chiara Univ Calabria DIMES I-87036 Arcavacata Di Rende CS Italy

ISBN: (纸本)9781450342155

Computing shortest distances is a central task in many graph applications. Since it is impractical to recompute shortest distances from scratch every time the graph changes, many algorithms have been proposed to incrementally maintain shortest distances after edge deletions or insertions. In this paper, we address the problem of maintaining all-pairs shortest distances in dynamic graphs and propose novel efficient incremental algorithms, working both in main memory and on disk. We prove their correctness and provide complexity analyses. Experimental results on real-world datasets show that current main-memory algorithms become soon impractical, disk-based ones are needed for larger graphs, and our approach significantly outperforms state-of-the-art algorithms.

关键词： Shortest distances incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：