一种新的多属性索引法——区域组合属性索引

数据库技术不仅在商业,企业管理,情报资科管理等方面获得了广泛的应用,而且在工程技术领域也有广阔的应用前景。本文针对工程数据库的二维数据及用户常提出的一类查询——区域查询提出了一种新的多属性索引法区域组合属性索引;并给出了矩形区域查询算法,分析了算法的复杂性;讨论了索引的最小存贮开销问题和最佳区域组合属性索引选择问题。这种索引方法具有较高的查询效率,并能实现各种形状的区域查询。     

多对象的最近邻查询

最近邻查询是地理信息系统等领域经常遇到的问题，该文在最近邻查询的基础上提出一种多个对象的最近邻查询，并利用已有的R-树最近邻查询方法实现多个对象的查询，该方法不同于普通的最近邻查询，是一种新的方法，在实际应用中也很有意义。     

一种数据流查询共享模型的设计

为了提高查询效率,从数据流查询过程中查询操作单元和查询存储结构的共享两个方面展开研究.设计一种基于共享的二级索引队列,用于存储数据流中间结果.该结构使得中间查询结果可以再利用的同时也为数据共享情况下的迁移提供了一定的灵活性.对于多查询共享,通过抽取相同数据流中的相同谓词进行查询共享,实现一处计算多处使用的目的.最后对相关模型和算法进行了分析.     

基于大规模智能电网网格结构的查询方法

由于智能电网输电线路监测系统的查询多数是针对无线传感器网络(WSN)的全局式查询,不能满足用户基于任意区域的灵活高效的查询需求,根据该系统的网络布局和查询特点,提出了一种基于大规模智能电网网格结构的查询方法MSQuery。MSQuery将不同网格内的查询节点的数据汇聚到一棵或多棵逻辑查询树上, 采用逻辑查询树的合并策略建立优化的回收路径。将MSQuery与采用路线型结构进行查询的RSA算法和采用簇型结构进行查询的SkySensor算法进行对比,结果显示MSQuery的平均传输消耗最小,平均剩余能量最大。实验结果表明,MSQuery可以快速地返回查询窗口内的查询结果,降低通信消耗,节省传感器节点能量。     

SWAPS一种基于Small World的文件搜索算法

资源发现是P2P应用所面临的最核心问题之一．无结构P2P方面的已有工作主要采用了查询消息泛洪和信息索引机制，这会造成严重的网络带宽负担以及巨大的索引维护开销．提出了一种无结构P2P环境下能够节约带宽、易维护的自适应搜索算法，即SWAPS．SWAPS根据用户的访问历史抽取用户的兴趣属性，并遵循用户的访问行为模式，以自发的方式组织基于用户兴趣属性的应用层Small world覆盖网络，然后基于覆盖网络实现了高效的文件定位．分析了影响搜索性能的关键因素，针对Small world网络特点分别设计了基于兴趣度、基于本体距离和基于兴趣宽度等有效的查询消息转发策略．最后实验显示，SWAPS以其高成功率、低带宽消耗和很小的响应时间能够显著的提高搜索性能，而且对用户的访问行为体现出良好适应性．     

Sweeping体的拓扑结构与精确B—Rep反算策略

本文根据五种造型法则:平行扫法则、回转扫法则、箱体法则、异形体法则和曲面立体法则的离散化原理,提出了Sweeping体的拓扑结构的生成方法。讨论了离散化多面体边界的几何属性码和CSG-索引方法,以及基于这种几何属性码和CSG-索引的精确B-Rep反算策略。     

MSCR树：一种移动终端电子地图索引结构

现有空间数据索引结构并未同时考虑移动终端电子地图的多比例尺特性及嵌入式设备性能的限制,造成对大区域进行空间查询操作时装载开销过大。深入分析了多种空间索引结构的特点,提出一种新的空间索引结构——MSCR树索引结构,该结构将多级地图中的空间元素线性化,同时以压缩的方式存储空间元素外包矩形数据以提高数据读写效率。实验表明,MSCR树算法有效地提高了查询性能与空间利用率。     

利用HB+树的复合索引问题的解决方案

B＋树是目前数据库管理系统在单属性上广泛使用的一种索引，但它在处理由多属性组成的复合索引时效率很低。为此，该文在B＋树的基础上提出了一种考虑属性逻辑层次关系的HB＋树及其操作算法。该树采用了分类串行解析各属性的方法，可以很好地解决复合索引问题；并具有层次分类清楚、结点小且结构简单等优点。文中还对HB＋树的时空性能进行了分析。     

移动对象数据库预测范围聚集查询技术研究

针对预测范围聚集查询处理技术，提出了一种面向移动对象的聚集TPR树索引。聚集TPR树索引在TPR树中间节点中加入移动对象聚集信息以减少预测范围聚集查询所需要的节点访问代价。并增加了一个建于移动对象标识上的哈希辅助索引结构以支持自底向上的删除搜索算法，具有很好的动态更新性能和并发性。提出了一种EPRA查询算法，采用更精确的剪枝搜索准则，大大减少了查询所需要访问的磁盘节点，具有良好的查询性能。     

基于多序的空间数据索引结构——MOIS-树

以提高查询效率为目标,运用数据空间分割技术、结合B-树和R-树思想,提出了一种空间数据索引结构——MOIS-树,给出了全新的区域查询处理方法和空间对象按其MBR进行排序的4种序关系定义,并以此为基础给出了MOIS-树的定义,规定MOIS-树中的中间节点的所有孩子节点按其几何位置满足某种序的关系,从而使得在中间节点中进行查询时可以进行快速定位,明显地加快了查询的速度.此外,在查询算法中引入查询窗口包含中间节点MBR的检测,对于较大查询窗口的查询,有效地减少了常规查询算法中大量无效的相交性判断,从另一方面加快了查询速度.给出了MOIS-树的建立算法、节点插入算法及算法的正确性、可终止性证明及时间复杂度分析,并给出区域查询算法及算法的性能分析.实验表明,索引结构区域查询速度有很大的提高.     

Grid k-d tree approach for point location in polyhedral data sets – application to explicit MPC

ABSTRACT

Explicit model predictive control (EMPC) moves the online computational burden of linear model predictive control (MPC) to offline computation by using multi-parametric programming which produces control laws defined over a set of polyhedral regions in the state space. The online computation of EMPC is to find the corresponding control law according to a given state, this is called the point location problem. This paper deals with efficient point location in larger polyhedral data sets. The authors propose a hybrid data structure, grid k-d tree (GKDT), which is constructed by the k-dimensional tree (k-d tree), hash table and binary search tree (BST). The main part of GKDT is a multiple branch tree which constructs subtrees by splitting the polyhedral region into several equal grids based on the k-d tree and is traversed by the hash function on each level. GKDT has a high search efficiency, even though it needs much more storage memory. A complexity analysis of the approach in the runtime and storage requirements is provided. Advantages of the method are supported by two examples in the paper.     

Registration and interactive planar segmentation for stereo images of polyhedral scenes

We introduce a two-step iterative segmentation and registration method to find coplanar surfaces among stereo images of a polyhedral environment. The novelties of this paper are: (i) to propose a user-defined initialization easing the image matching and segmentation, (ii) to incorporate color appearance and planar projection information into a Bayesian segmentation scheme, and (iii) to add consistency to the projective transformations related to the polyhedral structure of the scenes. The method utilizes an assisted Bayesian color segmentation scheme. The initial user-assisted segmentation is used to define search regions for planar homography image registration. The two reliable methods cooperate to obtain probabilities for coplanar regions with similar color information that are used to get a new segmentation by means of quadratic Markov measure fields (QMMF). We search for the best regions by iterating both steps: registration and segmentation.     

Geometrical algorithms for automated design of side actions in injection moulding of complex parts

This paper describes algorithms for generating shapes of side actions to minimize a customizable injection moulding cost function. Given a set of undercut facets on a polyhedral part and the main mold opening directions, our approach works in the following manner: first, we compute candidate retraction space for every undercut facet. This space represents the set of candidate translation vectors that can be used by the side action to completely disengage from the undercut facet. As the next step, we generate a discrete set of feasible, nondominated retractions. Then we group the undercut facets into undercut regions by performing state space search over such retractions. This search step is performed by minimizing the given moulding cost function. After identifying the undercut regions, we generate the shapes of individual side actions. We believe that the results presented in this paper will provide the foundations for developing fully automated software for designing side actions.     

Evaluation of piecewise affine control via binary search tree

We present an algorithm for generating a binary search tree that allows efficient computation of piecewise affine (PWA) functions defined on a polyhedral partition. This is useful for PWA control approaches, such as explicit model predictive control, as it allows the controller to be implemented online with small computational effort. The computation time is logarithmic in the number of regions in the PWA partition.     

Approximate explicit constrained linear model predictive control via orthogonal search tree

Solutions to constrained linear model predictive control problems can be precomputed off-line in an explicit form as a piecewise linear state feedback on a polyhedral partition of the state-space, avoiding real-time optimization. We suggest an algorithm that can determine an approximate explicit piecewise linear state feedback by imposing an orthogonal search tree structure on the partition. This leads to a real-time computational complexity that is logarithmic in the number of regions in the partition, and the algorithm yields guarantees on the suboptimality, asymptotic stability and constraint fulfillment.     

An Algorithm for Geometric Set Operations Using Cellular Subdivision Techniques

Geometric set operations play an integral role in systems for CAD/CAM, for robot planning, and for modeling objects such as underground formations from empirical data. Two major issues in the implementation of geometric set operations are efficiency in the search for geometric intersections and effectiveness in the treatment of singular intersection cases. This article presents an algorithm for geometric set operations on planar polyhedral nonmanifold objects that addresses both these issues. First, an efficient search for geometric intersections is obtained by localizing the search to small regions of object space through a cellular subdivision scheme using the polytree data structure. Second, an effective treatment of singular intersection cases is obtained by mapping each singular intersection occurring in a region into one of a small set of cases.     

Linear cone-invariant control systems and their equivalence

In this paper, we study invariant control systems that generalise positive systems. A characterisation of linear control systems invariant on polyhedral cones (corner regions) in the state-space, called cone-invariant linear control systems, is established both for the inputs taking values in a polyhedral cone in the control space and for the inputs taking values in an affine polyhedral cone. The problem of equivalence between control systems invariant on corner regions is introduced. For cone-invariant linear control systems, we study invariance-preserving state-equivalence and invariance-preserving feedback-equivalence and present characterisations of both notions of equivalence.     

Semi-Automatic Composition of Loop Transformations for Deep Parallelism and Memory Hierarchies

Modern compilers are responsible for translating the idealistic operational semantics of the source program into a form that makes efficient use of a highly complex heterogeneous machine. Since optimization problems are associated with huge and unstructured search spaces, this combinational task is poorly achieved in general, resulting in weak scalability and disappointing sustained performance. We address this challenge by working on the program representation itself, using a semi-automatic optimization approach to demonstrate that current compilers offen suffer from unnecessary constraints and intricacies that can be avoided in a semantically richer transformation framework. Technically, the purpose of this paper is threefold: (1) to show that syntactic code representations close to the operational semantics lead to rigid phase ordering and cumbersome expression of architecture-aware loop transformations, (2) to illustrate how complex transformation sequences may be needed to achieve significant performance benefits, (3) to facilitate the automatic search for program transformation sequences, improving on classical polyhedral representations to better support operation research strategies in a simpler, structured search space. The proposed framework relies on a unified polyhedral representation of loops and statements, using normalization rules to allow flexible and expressive transformation sequencing. Thisrepresentation allows to extend the scalability of polyhedral dependence analysis, and to delay the (automatic) legality checks until the end of a transformation sequence. Our work leverages on algorithmic advances in polyhedral code generation and has been implemented in a modern research compiler.     

Optimal complexity reduction of polyhedral piecewise affine systems

This paper focuses on the NP-hard problem of reducing the complexity of piecewise polyhedral systems (e.g. polyhedral piecewise affine (PWA) systems). The results are fourfold. Firstly, the paper presents two computationally attractive algorithms for optimal complexity reduction that, under the assumption that the system is defined over the cells of a hyperplane arrangement, derive an equivalent polyhedral piecewise system that is minimal in the number of polyhedra. The algorithms are based on the cells and the markings of the hyperplane arrangement. In particular, the first algorithm yields a set of disjoint (non overlapping) merged polyhedra by executing a branch and bound search on the markings of the cells. The second approach leads to non-disjoint (overlapping) polyhedra by formulating and solving an equivalent (and well-studied) logic minimization problem. Secondly, the results are extended to systems defined on general polyhedral partitions (and not on cells of hyperplane arrangements). Thirdly, the paper proposes a technique to further reduce the complexity of piecewise polyhedral systems if the introduction of an adjustable degree of error is acceptable. Fourthly, the paper shows that based on the notion of the hyperplane arrangement PWA state feedback control laws can be implemented efficiently. Three examples, including a challenging industrial problem, illustrate the algorithms and show their computational effectiveness in reducing the complexity by up to one order of magnitude.     

多面体表示技术及在程序性能优化中的应用

多面体表示技术提供一种统一化的方式来表示程序变换和程序变换组合,有利于最优程序变换的搜索。论文首先介绍并评价了几种典型的多面体表示方法,并详细介绍了Cohen提出的多面体表示模型;同时,对多面体表示在程序性能优化尤其是迭代编译中的应用进行了介绍和评价;最后,对多面体表示技术在迭代编译领域今后的发展方向做出了展望。