课程文献中心 更多>>

关键词： Succinct data structure   Geometric data structure   Dynamic data structure   Orthogonal range counting   Dynamic orthogonal range counting  

摘要： We present a linear-space data structure that maintains a dynamic set of n points with coordinates of real numbers in the plane to support orthogonal range counting in O((lg n/lg lg n)(2))worst-case time, and insertions and deletions in O((lg n/lg lg n)(2)) amortized time. This provides faster support for updates than previous results with the same bounds on space cost and query time. We also consider the same problem for points on a U x U grid, and design the first succinct data structure for a dynamic integer sequence, S, to support range counting queries defined as follows: Given a range, [i(1)..i(2)] of indices and a range, [v(1)..v(2)], of values, count the number of entries of that store integers from [v(1)..v(2)]. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Computational geometry   Data structures   Closest pair   Diameter   Width  

摘要： A fundamental and well-studied problem in computational geometry is range searching, where the goal is to preprocess a set, S, of geometric objects (e.g., points in the plane) so that the subset S' c S that is contained in a query range (e.g., an axes-parallel rectangle) can be reported efficiently. However, in many situations, what is of interest is to generate a more informative "summary" of the output, obtained by applying a suitable aggregation function on S'. Examples of such aggregation functions include count, sum, min, max, mean, median, mode, and top-k that are usually computed on a set of weights defined suitably on the objects. Such range-aggregate query problems have been the subject of much recent research in both the database and the computational geometry communities. In this paper, we further generalize this line of work by considering aggregation functions on point-sets that measure the extent or "spread" of the objects in the retrieved set S'. The functions considered here include closest pair, diameter, and width. The challenge here is that these aggregation functions (unlike, say, count) are not efficiently decomposable in the sense that the answer to S' cannot be inferred easily from answers to subsets that induce a partition of S'. Nevertheless, we have been able to obtain space- and query-time-efficient solutions to several such problems including: closest pair queries with axes-parallel rectangles on point sets in the plane and on random point-sets in R-d (d >= 2), closest pair queries with disks on random point-sets in the plane, diameter queries on point-sets in the plane, and guaranteed-quality approximations for diameter and width queries in the plane. Our results are based on a combination of geometric techniques, including multilevel range trees, Voronoi Diagrams, Euclidean Minimum Spanning Trees, sparse representations of candidate outputs, and proofs of (expected) upper bounds on the sizes of such representations. (C) 2013 Elsevier B.

关键词： Dynamic programming   Geometric data structure   Gap dependency  

摘要： We are given integers 0 <= G(1) <= G(2) not equal 0 and a sequence S-n = (a(1), a(2), . . . , a(n)) of n integers. The goal is to compute the minimum number of insertions and deletions necessary to transform S-n into a valid sequence, where a sequence is valid if it is nonempty, all elements are integers, and all the differences between consecutive elements are between G(1) and G(2). For this problem from the database theory literature, previous dynamic programming algorithms have running times O(n(2)) and O(A . n log n), for a parameter A unrelated to n. We use a geometric data structure to obtain a O(n log n loglog n) running time. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Bookmark   Continuous Sequential Pattern   Discontinuous Sequential Pattern   Prefix Tree   Time Duration  

摘要： Perceiving the navigational performance of website visitors is an essential factor for the success in the emerging systems of electronic commerce and mobile commerce. In this paper, we propose a utility and frequency dependent algorithm for web path traversal using prefix tree structure. Here, we take the web log files and extract the details such as time duration that the user visited the web page and the bookmark information about the web page. The extracted data from the web log file of different users are considered as input to construct the prefix tree. Using this prefix tree we mine the continuous sequential pattern and discontinuous sequential pattern and we calculate the weight value for each pattern mined using the continuous and discontinuous sequential pattern. The prefix tree constructed using the existing users can be updated further with the details of new users. We compare the path traversal efficiency of our proposed technique with the existing frequency dependent prefix span technique. © 2005 - 2014 JATIT & LLS. All rights reserved.

关键词： 文档管理系统   版本控制   文档工作流   权限控制   数据结构   统一用户管理  

摘要： 互联网作为一种信息采集、传播、存储、交互、共享的有效工具，已经成为信息化社会必不可少的基础设施。而各种类型的电子文档作为信息传播的主要载体，已经渗透到我们工作生活的各个方面，如何从海量信息中迅速而准确地获取最需要的信息，有效管理各类文档已经成为一个重要的课题。\n 科学研究、企业运营大都是一个多人参与、协同工作的过程，能够管理好企业机构成员，合理地为参与协作的每一个成员分配角色任务、控制权限，使企业能够有组织、有纪律有条不紊的运行，使成员能且只能执行被授权的操作也十分重要。\n EAST正是一个多人协作的大科学工程，随着实验的进行产生了越来越多的项目文档，且这些文档大都分散存储，管理混乱、文档冗余、版本有效性和权威性普遍缺失，为了更有效的组织文档、管理用户、控制权限，需要设计一个兼具丰富文档管理功能、强大用户管理功能以及完善权限控制功能的集成文档管理系统EDM(EAST Document Management)。系统以文档作为操作对象，重点分析了如何采用LDAP实现统一用户管理，利用RBAC技术实现高级权限分配，同时根据用户角色信息实现文档版本控制和工作流管理等功能。系统采用强大而稳定的LAMP平台框架;后台通过PHP和MySQL设计控制逻辑和数据结构。前台采用现在流行的HTML4、CSS，jQuery与AJAX技术，设计丰富的界面元素满足个性化用户操作体验。最终满足EAST文档管理的需要。该系统的建立为所有拥有操作对象和用户的系统提供了用户权限管理的核心模型。

关键词： 多波束测深系统   XTF   ALL数据结构  

摘要： 通过对SeaBat系列多波束.XTF数据结构和EM系列多波束.ALL数据结构进行剖析,对两种数据结构编码特点、数据记录特点、数据存储方式等进行了比较,明确了这两种多波束系统原始数据的编码规则以及各参数的含义,并成功利用Visual C++编程平台实现了对这两种原始数据的提取。

关键词： 钣金加工   CAM系统   数控转塔冲床   数据结构  

摘要： 数控转塔冲床在钣金制造业中的应用非常广泛，智能化专用CAM系统是其核心支撑技术和重要模块之一。本文对数控转塔冲床CAM系统的若干关键技术及其实现进行了深入研究，主要工作如下:\n 1)针对数控转塔冲床加工需求和工艺特点对其专用CAM系统的总体架构进行了设计，定义了系统的数据结构，实现了零件的加工制造特征通过实体属性的承载机制;\n 2)建立了转塔模具库，实现了可视化的交互式转塔工位编辑功能;\n 3)对智能化模具适配技术进行了研究和系统实现。提出基于有向边属性邻接图的特征识别方法以及特征分解技术，通过二叉树的回溯机制和启发式因子实施工艺约束优化，得到符合生产实际的模具适配最优解;\n 4)对数控转塔冲床常用的钣金件排样优化技术进行了研究。深入分析了二维正交排样问题，将Best-fit(BF)算法的思想融入到Bottom-left-fill(BLF)算法中，提出一种新的启发式排样算法——Bottom-left Best-fit(BLBF)启发式算法;\n 5)在加工排序规则及加工路径的优化技术研究的基础上，基于加工工艺，建立了加工时间优化问题的数学模型，归纳了冲压次序的优化规则。将冲压加工路径优化问题转化为旅行商问题(Traveling Salemam Problem，TSP)进行求解，通过加工仿真模拟验证了路径优化的效果;\n 6)基于所研究的关键技术，研发拥有自主知识产权的SMD-Punch系统。通过典型实例的应用验证，系统在模具适配、多零件排样、加工路径优化等方面均取得了预期的结果。

关键词： 网络拓扑发现   软件开发   模块设计   数据结构  

摘要： 本文首先分析了随着网络规模的日益庞大，网络拓扑发现在网络管理中的重要性以及必要性。当前网络拓扑发现只能对网络层设备进行很好的发现，然而对于越来越重要的数据链路层物理设备的发现依然存在着困难和挑战。对本文进行网络拓扑发现所依赖的技术基础SNMP从概念和模型结构两个方面进行了简要的介绍。对网络设备发现和已经成熟的网络层拓扑发现的原理进行了介绍。本文对数据链路层拓扑发现进行了详细的分析与讨论，在此基础上总结出了数据链路层拓扑发现的算法模型和判定的理论依据。\n 其次对网络拓扑发现的需求进行了详细分析，根据分析得出将任务分解成为快速ping、设备发现和设备链路发现三个子模块，并对每个模块的功能以及模块之间的接口进行了分析与设计。依次对每个模块进行了概要设计和详细设计。在概要设计阶段依次按照概念结构、逻辑结构和物理结构的分析方式对本系统的数据结构进行了详细的设计。在详细设计阶段详细介绍每个模块功能的实现方法，并给出实现过程的关键代码。\n 最后，本文利用上述分析的系统在多个实际的大规模IP网络管理系统进行了测试。通过大量的测试，说明该系统能适用于异构的网络环境，并验证了该系统所发现结果的正确性以及本文所提出的各种算法的有效性。和同类软件相比，该系统具有较高的效率。

关键词： 独立学院   数据结构   教学方法  

摘要： 本文分析了独立学院《数据结构》课程的教学现状,针对存在的问题主要从课程的教学方法创新方面进行讨论,以期改善教学效果,提高教学质量。

关键词： 矢量图   描述规范   计算机图形学   内在特征   数据结构  

摘要： 一个成熟的科学领域，一般应有一个统一的、通用的理论描述模型。目前在计算机图形学中所使用的几种常见矢量图描述规范，都有各自的侧重点，且未有一种可以涵盖各类矢量图类型的统一矢量图描述格式被提出。\n 建立一个统一的矢量图描述模型，可以实现不同类型的描述格式之间的转换，对建立计算机图形的统一存储、分析、传输和播放数据结构，促进计算机矢量图形的进一步推广使用，研究矢量图的描述和本质有推动作用。因此，这一研究工作是有理论研究价值和现实应用意义的。\n 本文首先研究了目前计算机矢量图形已提出的一系列描述规范和定义标准，分析了常见描述规范的内容体系，抽取其内容分类，形成综合性的计算机矢量图形描述类型体系。然后，分析目前计算机矢量图形的内在特征，抽取共同点，设计能涵盖各种常见矢量图形的描述模型。最后将这一描述模型用于矢量图实例的描述，并通过分析表明该模型可以以一种统一形式描述各类不同特性的矢量图形内容，具有通用性、统一性。\n 但该模型仍有一定缺陷，如为了通用性而使简单矢量图形的描述中出现了较多的冗余字段，且尚不能描述矢量动画这一矢量图形应用中的一大类别，这是未来进一步工作的方向。