Efficient Flexible M-Tree Bulk Loading Using FastMap and Space-Filling Curves

Many database applications currently deal with objects in a metric space.Examples of such objects include unstructured multimedia objects and points of interest(POIs)in a road network.The M-tree is a dynamic index structure that facilitates an efficient search for objects in a metric space.Studies have been conducted on the bulk loading of large datasets in an M-tree.However,because previous algorithms involve excessive distance computations and disk accesses,they perform poorly in terms of their index construction and search capability.This study proposes two efficient M-tree bulk loading algorithms.Our algorithms minimize the number of distance computations and disk accesses using FastMap and a space-filling curve,thereby significantly improving the index construction and search performance.Our second algorithm is an extension of the first,and it incorporates a partitioning clustering technique and flexible node architecture to further improve the search performance.Through the use of various synthetic and real-world datasets,the experimental results demonstrated that our algorithms improved the index construction performance by up to three orders of magnitude and the search performance by up to 20.3 times over the previous algorithm.

Research on a toolpath generation method of NC milling based on space-filling curve

Tool path generated by space-filling curve always turns frequently causing trembling to machine,reducing toollife and affecting workpiece quality. Length and generation time of tool paths are both relatively long. In order to solve these problems,a toolpath generation method of NC milling based on space-filling curve is proposed. First,T-spline surface is regarded as the modeling surface,the grid,which is based on the limited scallop-height,can be got in the parameter space,and the influence value of grid node is determined. Second,a box is defined and planned,and the tool paths are got preliminarily,which is based on minimal spanning tree; Finally,based on an improved chamfering algorithm,the whole tool paths are got. A simulation system is developed for computer simulation,and an experiment is carried out to verify the method. The results of simulation and experiment show that the method is effective and feasible,and length and time of the tool paths are reduced.

An application of space-filling curves to improve results of turbulent aerodynamics modeling with convolutional neural networks

When carrying out calculations for turbulent flow simulation,one inevitably has to face the choice between accuracy and speed of calculations.In order to simultaneously obtain both a computationally efficient and more accurate model,a surrogate model can be built on the basis of some fast special model and knowledge of previous calculations obtained by more accurate base models from various test bases or some results of serial calculations.The objective of this work is to construct a surrogate model which allows to improve the accuracy of turbulent calculations obtained by a special model on unstructured meshes.For this purpose,we use 1D Convolutional Neural Network(CNN)of the encoder-decoder architecture and reduce the problem to a single dimension by applying space-filling curves.Such an approach would have the benefit of being applicable to solutions obtained on unstructured meshes.In this work,a non-local approach is applied where entire flow fields obtained by the special and base models are used as input and ground truth output respectively.Spalart-Allmaras(SA)model and Near-wall Domain Decomposition(NDD)method for SA are taken as the base and special models respectively.The efficiency and accuracy of the obtained surrogate model are demonstrated in a case of supersonic flow over a compression corner with different values for angleαand Reynolds number Re.We conducted an investigation into interpolation and extrapolation by Re and also into interpolation byα.

Spiralchord: a space-filling curve based location awareness, cross-layering P2P file sharing system in WMNs

The common characteristics of peer-to-peer （P2P） overlay networks and wireless multi-hop network, such as self-organization, decentralization, hop-by-hop message transmission mode and high degree of dynamicity, lead to research of operating wired P2P applications on wireless multi-hop networks. Wireless mesh network （WMN） as a relative static multi-hop wireless network which is extended from Ad-Hoc networks, has become one of the key technologies for providing increased network coverage of Internet infrastructures. This paper investigates the problem of enabling P2P file sharing in WMNs. A special chord algorithm--spiralchord is proposed to address the major problem in wireless file sharing system how to efficiently find resources currently available. Spiralchord put forward an identifier （ID） assignment technique based on spiral space-filling curve to integrate location-awareness with cross-layering. Location awareness aims at alleviating the mismatch of physical network topology and overlay network topology, and requires close-by IDs in logical ring of neighboring peers, while cross-layering aims at speeding up resource lookup operations, requires faraway IDs of neighboring peers. Spiralchord uses spiral curve to assign peers＇ IDs which meet the contradictory requirements of location-awareness and cross-layering. The simulation results show spiralchord is effective in reducing message overhead, and increasing lookup performance with respect to basic chord.

Novel Global Optimization Algorithm with a Space-Filling Curve and Integral Function

In this study,we consider the global optimization problem in a hypercube.We use a class of series to construct a curve in a hypercube,which can fill the hypercube,and we present an integral function on the curve.Based on the integral function,we propose an algorithm for solving the global optimization problem.Then,we perform a convergence analysis and numerical experiments to demonstrate the effectiveness of the proposed algorithm.

基于分布式哈希表的协作式Web服务组合

集中式的基于案例推理(CBR)应用于感知服务质量(QoS)的Web服务组合时,面临信息维护量大、节点负载高、中心失效等问题。为解决上述问题,提出了基于分布式哈希表(DHT)的协作式Web服务组合方法 COCO,利用哈希函数和空间填充曲线(SFC)将组合服务的工作流和服务质量映射为一维数据键,并利用底层DHT Overlay以Peer-to-Peer的方式查询满足用户请求的已知组合服务,一次成功查询可获得同时满足功能性要求和非功能性要求的组合服务。实验结果表明,COCO在查询时延和查询命中率方面均有较好性能,适用于大规模网络计算环境。

橡胶-钢纤维混凝土的劈裂应力-应变曲线特征及破坏机理研究

为探究橡胶掺量及其粒径对橡胶-钢纤维混凝土(R-SFC)应力-应变曲线特征和破坏机理的影响,利用电液伺服万能试验机对R-SFC试件进行静载劈裂抗拉试验。结果表明:随着橡胶掺量的增加,R-SFC的应力-应变曲线均位于钢纤维混凝土(SFC)的上方,且峰后延/韧性显著地增加。随着橡胶粒径的增大,R-SFC的弹性段先减小后增大,且各粒径下峰后曲线近似平行。劈裂抗拉强度和峰值应变随橡胶掺量的增加均逐渐降低。在SFC中加入橡胶颗粒可以明显地改善其低应力劈裂脆性并提高其峰后变形能力。根据材料特性和破坏形态建立了橡胶和钢纤维协同作用的桥接模型,并基于该模型推导了协同作用的力学简化计算表达式。最后,结合纤维间距理论和断裂力学推导了劈裂抗拉强度式。

静止变频器启动控制策略与限制曲线

采用静止变频器(SFC)拖动是目前大型同步机组柔性启动的最佳方式,可以将同步机组从静止或盘车状态平滑地拖入目标转速,不对电网产生冲击。从电机动力学方程和电磁关系方程入手,考虑了电机定、转子之间的相互耦合以及绕组压降的扰动,对各控制对象和执行机构设计了控制器。根据电机、SFC设备特性,给出了不同启动阶段的约束条件和边界曲线,使得在满足设备安全的条件下能够尽可能地缩短启机时间,提高成功率。最后给出了该控制策略在300 Mvar同步调相机组应用中的启动波形,验证了控制策略的正确性和合理性。

基于空间填充曲线排列码划分的并行缓冲区算法

缓冲区计算是地理信息系统空间分析的基本功能之一。在矢量缓冲区研究方面,以往大多聚焦缓冲区生成算法,这些优化方法在单机计算环境中针对大规模空间数量数据的计算效率提升是有限的,因而需要并行环境下的改进方法来进一步破解计算瓶颈。本文基于Map Reduce计算模型和分布式内存计算框架,提出了一种基于空间填充曲线排列码划分的并行缓冲区分析算法(SPBM),基于空间填充曲线编码进行数据排序和范围划分,对跨越网格的数据采用近似切分方法,在考虑负载均衡的前提下对任务并行分解,之后按照给定深度的"树状"方式进行结果合并。本文在单机和集群两种环境下利用实际道路网等数据进行了实验。同等环境下,相较于目前流行的GIS软件——QGIS和Post GIS计算性能提升明显,相较于现有其他并行优化方法效率提升超过50%。这样的优化分析方法对于GIS中其他矢量分析算法的并行算法也具有一定的借鉴意义。

L curve for spherical triangle region quadtrees

The sequence of facets and nodes has a direct influence on the efficiency of access to spherical triangle region quadtree. Based on the labeling schema by Lee, spatial curves both for facets and nodes are proposed and the main algorithms for coordinate translation, node Lsequence generation and visiting nodes are presented. In particular,constant time algorithms for generating node Lsequence are advanced by using bit manipulation operations,which can be easily implemented with hardware. In L curve the distance between three nodes of a facet is mostly limited in a range of small value, thus making fast access possible. Though codes of sibling facets are continuous, the difference between codes of some cousins may occasionally be very large and makes the distance of a few facets also very large, thus greatly increasing the mean node distance and the total traversing distance. Therefore an m cluster of nodes is proposed as a basic storage unit fo n cluster, which should store eery shared node in each,and the distance between three nodes of a facet is limited to a controllagle scope.

希尔平斯基曲线在物流路线问题中的应用

物流配送车辆路径问题(VRP)属于NP-Hard问题,对这类问题如何求解学术界提出了多种算法,但往往复杂性较高,易用性较差。以基于西尔平斯基曲线的空间填充方法来求解此类问题,具有快速、灵活、运算量少的特点。

Generating and AnalyzingN-di mensional Hilbert Cell

In this paper, two algorithms are presented for generating two code scan lists of an N dimensional Hilbert cell, and a formal proof of the backward encoding algorithm is given. On the basis of the self similarity properties of a Hilbert curve, this paper gives a novel algorithm for generating a static evolvement rule table through analyzing a Hilbert cell. By looking up the static evolvement rule table, the N dimensional Hilbert mappings are efficiently implemented.

A Solution of a Problem of I. P. Natanson Concerning the Decomposition of an Interval into Disjoint Perfect Sets

In a previous paper published in this journal, it was demonstrated that any bounded, closed interval of the real line can, except for a set of Lebesgue measure 0, be expressed as a union of c pairwise disjoint perfect sets, where c is the cardinality of the continuum. It turns out that the methodology presented there cannot be used to show that such an interval is actually decomposable into c nonoverlapping perfect sets without the exception of a set of Lebesgue measure 0. We shall show, utilizing a Hilbert-type space-filling curve, that such a decomposition is possible. Furthermore, we prove that, in fact, any interval, bounded or not, can be so expressed.

An improved parallel contrast-aware halftoning

Digital image halftoning is a widely used technique. However, achieving high fidelity tone reproduction and structural preservation with low computational time cost remains a challenging problem. This paper presents a highly parallel algorithm to boost real-time application of serial structure-preserving error diffusion. The contrast-aware halftoning approach is one such technique with superior structure preservation, but it offers only a limited opportunity for graphics processing unit(GPU) acceleration. Our method integrates contrast-aware halftoning into a new parallelizable error-diffusion halftoning framework. To eliminate visually disturbing artifacts resulting from parallelization, we propose a novel multiple quantization model and space-filling curve to maintain tone consistency, blue-noise property, and structure consistency. Our GPU implementation on a commodity personal computer achieves a real-time performance for a moderately sized image. We demonstrate the high quality and performance of the proposed approach with a variety of examples, and provide comparisons with state-of-the-art methods.

SwiftArray: Accelerating Queries on Multidimensional Arrays

Scientific instruments and simulation programs are generating large amounts of multidimensional array data. Queries with value and dimension subsetting conditions are commonly used by scientists to find useful information from big array data, and data storage and indexing methods play an important role in supporting queries on multidimensional array data efficiently. In this paper, we propose SwiftArray, a new storage layout with indexing techniques to accelerate queries with value and dimension subsetting conditions. In SwiftArray, the multidimensional array is divided into blocks and each block stores sorted values. Blocks are placed in the order of a Hilbert space-filling curve to improve data locality for dimension subsetting queries. We propose a 2-D-Bin method to build an index for the blocks＇ value ranges, which is an efficient way to avoid accessing unnecessary blocks for value subsetting queries. Our evaluations show that SwiftArray surpasses the NetCDF-4 format and FastBit indexing technique for queries on multidimensional arrays.

An Efficient Representation of Quadtrees and Bintrees for Multiresolution Terrain Models

A space-filling curve in 2,3,or higher dimensions can be thought as a path of a continuously moving point.As its main goal is to preserve spatial proximity,this type of curves has been widely used in the design and implementation of spatial data structures and nearest neighbor-finding techniques.This paper is essentially focused on the efficient representation of Digital Ele-vation Models(DEM) that entirely fit into the main memory.We propose a new hierarchical quadtree-like data structure to be built over domains of unrestricted size,and a representation of a quadtree and a binary triangles tree by means of the Hilbert and the Sierpinski space-filling curves,respectively,taking into account the hierarchical nature and the clustering properties of this kind of curves.Some triangulation schemes are described for the space-filling-curves-based approaches to efficiently visualize multiresolu-tion surfaces.

A discussion of objective function representation methods in global optimization

Non-convex optimization can be found in several smart manufacturing systems. This paper presents a short review on global optimization(GO) methods. We examine decomposition techniques and classify GO problems on the basis of objective function representation and decomposition techniques. We then explain Kolmogorov's superposition and its application in GO. Finally,we conclude the paper by exploring the importance of objective function representation in integrated artificial intelligence, optimization, and decision support systems in smart manufacturing and Industry 4.0.

PLC在快速压滤机系统中的应用

介绍可编程控制器（ＰＬＣ）在ＸＫＺＧ快速压滤机系统中的应用。运用状态转移图（ＳＦＣ）进行编程，解决了按工序步进动作的机械设备编程复杂且他人阅读不易理解的问题。工序之间的连锁或双重输出，ＰＬＣ均能自动进行处理，并采用国际上均能理解的表达方式，既ＩＥＣ标准。