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

New method in information processing for maintaining an efficient dynamic ordered set

Science in China(Series F) 2009年第8期52卷 1292-1301页

作者： XIN ShiQing WANG GuoJin Institute of Computer Graphics and Image Processing Zhejiang University Hangzhou 310027 China State Key Laboratory of CAD & CG Zhejiang University Hangzhou 310027 China

This paper investigates how to maintain an efficient dynamic ordered set of bit strings, which is an important problem in the field of information search and information processing. Generally, a dynamic ordered set is required to support 5 essential operations including search, insertion, deletion, max-value retrieval and next-larger-value retrieval. Based on previous research fruits, we present an advanced data structure named rich binary tree （RBT）, which follows both the binary-search-tree property and the digital-search-tree property. Also, every key K keeps the most significant difference bit （MSDB） between itself and the next larger value among K＇s ancestors, as well as that between itself and the next smaller one among its ancestors. With the new data structure, we can maintain a dynamic ordered set in O（L） time. Since computers represent objects in binary mode, our method has a big potential in application. In fact, RBT can be viewed as a general-purpose data structure for problems concerning order, such as search, sorting and maintaining a priority queue. For example, when RBT is applied in sorting, we get a linear-time algorithm with regard to the key number and its performance is far better than quick-sort. What is more powerful than quick-sort is that RBT supports constant-time dynamic insertion/deletion.

关键词： information processing dynamic ordered set algorithms and data structures rich binary tree

来源：评论

学校读者我要写书评

暂无评论

Linear, bidirectional on-line construction of affix trees

引用

ALGORITHMICA 2003年第1期37卷 43-74页

作者： Maass, MG Tech Univ Munich Fak Informat D-85748 Garching Germany

Affix trees are a generalization of suffix trees that are based on the inherent duality of suffix trees induced by the suffix links. An algorithm is presented that constructs affix trees on-line by expanding the under... 详细信息

关键词： algorithms and data structures pattern matching affix tree suffix tree amortized analysis

来源：评论

学校读者我要写书评

暂无评论

Reachability on suffix tree graphs

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2008年第1期19卷 147-162页

作者： Higa, Yasuto Bannai, Hideo Inenaga, Shunsuke Takeda, Masayuki Kyushu Univ Dept Informat Nishi Ku Fukuoka 8190395 Japan Kyushu Univ Grad Sch Informat Sci & Elect Engn Nishi Ku Fukuoka 8190395 Japan

We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links. Using a simplified reachability labeling algorithm presented by Agrawal et al. (1989), we show that for a random string of length n, its ST-graph can be preprocessed in O(n log n) expected time and space to answer reachability queries in O(log n) time. Furthermore, we present a series of strings that require circle minus(n root n) time and space to answer reachability queries in O(log n) time for the same algorithm. Exhaustive computational calculations for strings of length n <= 33 have revealed that the same strings are also the worst case instances of the algorithm. We therefore conjecture that reachability queries can be answered in O(log n) time with a worst case time and space preprocessing complexity of circle minus(n root n).

关键词： algorithms and data structures suffix trees graph reachability

来源：评论

学校读者我要写书评

暂无评论

Comparing Cognitive Load Among Undergraduate Students Programming in Python and the Visual Language Algot 2024

Comparing Cognitive Load Among Undergraduate Students Progra...

引用

55th ACM Technical Symposium on Computer Science Education (SIGCSE)

作者： Thorgeirsson, Sverrir Weidmann, Theo B. Weidmann, Karl-Heinz Su, Zhendong Swiss Fed Inst Technol Zurich Switzerland Univ Appl Sci Vorarlberg Dornbirn Austria

ISBN: (纸本)9798400704239

This paper examines whether undergraduate students perform better and experience lower cognitive load when programming in Algot, a visual programming language that supports programming by demonstration, than in the textual programming language Python. We recruited 38 first-semester computer science university students who had received prior instruction in the programming language Python but were unfamiliar with Algot. Participants reviewed a 12-minute video tutorial about Algot and performed the same programming tasks in Python and Algot. We graded student submissions, estimated cognitive load through physiological measures and a validated post-test survey, and evaluated free-form feedback. Our results indicated that students experienced lower negative (extraneous and intrinsic) and higher positive (germane) cognitive load when programming in Algot. Additionally, students programming in Algot scored an average grade of 5.8 out of 10, compared to an average grade of 3.4 when using Python for the same tasks, and according to the free-form feedback, Algot is perceived as well-designed and easy to learn.

关键词： visual programming programming by demonstration undergraduate education algorithms and data structures cognitive load

来源：评论

学校读者我要写书评

暂无评论

PARAMETERIZED COMPLEXITY OF DIRECTED STEINER TREE ON SPARSE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2017年第2期31卷 1294-1327页

作者： Jones, Mark Lokshtanov, Daniel Ramanujan, M. S. Saurabh, Saket Suchy, Ondrej Royal Holloway Univ London Dept Comp Sci Egham TW20 0EX Surrey England Univ Bergen N-5020 Bergen Norway Inst Math Sci Madras 600113 Tamil Nadu India Czech Tech Univ Fac Informat Technol Prague 16636 Czech Republic

We study the parameterized complexity of the directed variant of the classical STEINER TREE problem on various classes of directed sparse graphs. While the parameterized complexity of STEINER TREE parameterized by the number of terminals is well understood, not much is known about the parameterization by the number of nonterminals in the solution tree. All that is known for this parameterization is that both the directed and the undirected versions are W[2]-hard on general graphs and hence unlikely to be fixed parameter tractable (FPT). The undirected STEINER TREE problem becomes FPT when restricted to sparse classes of graphs such as planar graphs, but the techniques used to show this result break down on directed planar graphs. In this article we precisely chart the tractability border for DIRECTED STEINER TREE (DST) on sparse graphs parameterized by the number of nonterminals in the solution tree. Specifically, we show that the problem is FPT on graphs excluding a topological minor but becomes W[2]-hard on graphs of degeneracy 2. On the other hand we show that if the subgraph induced by the terminals is acyclic, then the problem becomes FPT on graphs of bounded degeneracy. We further show that our algorithm achieves the best possible asymptotic running time dependence on the solution size and degeneracy of the input graph, under standard complexity theoretic assumptions. Using the ideas developed for DST, we also obtain improved algorithms for DOMINATING SET on sparse undirected graphs. These algorithms are asymptotically optimal.

关键词： algorithms and data structures graph algorithms parameterized algorithms Steiner tree problem sparse graph classes

来源：评论

学校读者我要写书评

暂无评论

More efficient periodic traversal in anonymous undirected graphs

引用

THEORETICAL COMPUTER SCIENCE 2012年 444卷 60-76页

作者： Czyzowicz, Jurek Dobrev, Stefan Gasieniec, Leszek Ilcinkas, David Jansson, Jesper Klasing, Ralf Lignos, Ioannis Martin, Russell Sadakane, Kunihiko Sung, Wing-Kin CNRS LaBRI F-33405 Talence France Univ Bordeaux F-33405 Talence France Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada Slovak Acad Sci Inst Math Bratislava 84000 Slovakia Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Ochanomizu Univ Bunkyo Ku Tokyo 1128610 Japan Univ Durham Dept Comp Sci Durham DH1 3LE England Natl Inst Informat Principles Informat Res Div Chiyoda Ku Tokyo 1018430 Japan Natl Univ Singapore Dept Comp Sci Singapore 117543 Singapore

We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it;for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily;see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005)[4] described an algorithm for assigning port numbers and an oblivious agent (i.e., an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gasieniec et al. (2008) [7] to be no more than 3.75n - 2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most (4 + 1/3)n - 4 for oblivious agents and a period length of at most 3.5n - 2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2.8n - 2, on the period length for the oblivious case. (c) 2012 Elsevier B.V. All rights reserved.

关键词： algorithms and data structures Graph exploration Periodic graph traversal Oblivious agent Constant-memory agent Three-layer partition

来源：评论

学校读者我要写书评

暂无评论

Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs

引用

ALGORITHMICA 2014年第3期70卷 513-560页

作者： Hermelin, Danny Mnich, Matthias van Leeuwen, Erik Jan Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Cluster Excellence MMCI D-66123 Saarbrucken Germany Max Planck Inst Informat D-66123 Saarbrucken Germany

The Induced Graph Matching problem asks to find disjoint induced subgraphs isomorphic to a given graph in a given graph such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, among several other problems. We show that Induced Graph Matching is fixed-parameter tractable in on claw-free graphs when is a fixed connected graph, and even admits a polynomial kernel when is a complete graph. Both results rely on a new, strong, and generic algorithmic structure theorem for claw-free graphs. Complementing the above positive results, we prove -hardness of Induced Graph Matching on graphs excluding as an induced subgraph, for any fixed complete graph . In particular, we show that Independent Set is -hard on -free graphs. Finally, we consider the complexity of Induced Graph Matching on a large subclass of claw-free graphs, namely on proper circular-arc graphs. We show that the problem is either polynomial-time solvable or -complete, depending on the connectivity of and the structure of G.

关键词： algorithms and data structures Induced matchings Claw-free graphs Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

ReNeuIR: Reaching Efficiency in Neural Information Retrieval 22

ReNeuIR: Reaching Efficiency in Neural Information Retrieval

引用

45th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR)

作者： Bruch, Sebastian Lucchese, Claudio Nardini, Franco Maria Pinecone New York NY 10012 USA Ca Foscary Univ Venice Venice Italy ISTI CNR Pisa Italy

ISBN: (纸本)9781450387323

Perhaps the applied nature of information retrieval research goes some way to explain the community's rich history of evaluating machine learning models holistically, understanding that efficacy matters but so does the computational cost incurred to achieve it. This is evidenced, for example, by more than a decade of research on efficient training and inference of large decision forest models in learning-to-rank. As the community adopts even more complex, neural network-based models in a wide range of applications, questions on efficiency have once again become relevant. We propose this workshop as a forum for a critical discussion of efficiency in the era of neural information retrieval, to encourage debate on the current state and future directions of research in this space, and to promote more sustainable research by identifying best practices in the development and evaluation of neural models for information retrieval.

关键词： efficiency neural IR sustainable IR retrieval ranking algorithms and data structures

来源：评论

学校读者我要写书评

暂无评论

Measure and Conquer: A Simple O(2^0.288n) Independent Set Algorithm

Measure and Conquer: A Simple O(2<SUP>0.288n</SUP>) Independ...

引用

17th ACM-SIAM Symposium on Discrete algorithms

作者： Fomin, Fedor V. Grandoni, Fabrizio Kratsch, Dieter Univ Bergen Dept Informat N-5020 Bergen Norway Univ Roma La Sapienza Dipartimento Informat I-00198 Rome Italy Univ Metz LITA F-57045 Metz 01 France

ISBN: (纸本)9780898716054

For more than 30 years Davis-Putnam-style exponential-time backtracking algorithms have been the most common tools used for finding exact solutions of NP-hard problems. Despite of that, the way to analyze such recursive algorithms is still far from producing tight worst case running time bounds. The "Measure and Conquer" approach is one of the recent attempts to step beyond such limitations. The approach is based on the choice of the measure of the subproblems recursively generated by the algorithm considered;this measure is used to lower bound the progress made by the algorithm at each branching step. A good choice of the measure can lead to a significantly better worst case time analysis. In this paper we apply "Measure and Conquer" to the analysis of a very simple backtracking algorithm solving the well-studied maximum independent set problem. The result of the analysis is striking: the running time of the algorithm is O(2(0.288n)), which is competitive with the current best time bounds obtained with far more complicated algorithms (and naive analysis). Our example shows that a good choice of the measure, made in the very first stages of exact algorithms design, can have a tremendous impact on the running time bounds achievable.

关键词： algorithms and data structures exponential-time exact algorithms NP-hard problems independent set problem

来源：评论

学校读者我要写书评

暂无评论

klcluster: Center-based Clustering of Trajectories 19

klcluster: Center-based Clustering of Trajectories

引用

27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS)

作者： Buchin, Kevin Driemel, Anne van de L'Isle, Natasja Nusser, Andre Eindhoven Tech Univ Eindhoven Netherlands Univ Bonn Hausdorff Ctr Math Bonn Germany Max Planck Inst Informat Grad Sch Comp Sci Saarbrucken Germany

ISBN: (纸本)9781450369091

Center-based clustering, in particular k-means clustering, is frequently used for point data. Its advantages include that the resulting clustering is often easy to interpret and that the cluster centers provide a compact representation of the data. Recent theoretical advances have been made in generalizing center-based clustering to trajectory data. Building upon these theoretical results, we present practical algorithms for center-based trajectory clustering.

关键词： Computational Geometry algorithms and data structures Trajectories Clustering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：