Learning Boxes in High Dimension

We present exact learning algorithms that learn several classes of (discrete) boxes in {0,...,l-1} ⁿ . In particular we learn: (1) The class of unions of O(log n) boxes in time poly(n,log l) (solving an open problem of [16] and [12]; in [3] this class is shown to be learnable in time poly(n,l) ). (2) The class of unions of disjoint boxes in time poly(n,t,log l) , where t is the number of boxes. (Previously this was known only in the case where all boxes are disjoint in one of the dimensions; in [3] this class is shown to be learnable in time poly(n,t,l) .) In particular our algorithm learns the class of decision trees over n variables, that take values in {0,...,l-1} , with comparison nodes in time poly(n,t,log l) , where t is the number of leaves (this was an open problem in [9] which was shown in [4] to be learnable in time poly(n,t,l) ). (3) The class of unions of O(1) -degenerate boxes (that is, boxes that depend only on O(1) variables) in time poly(n,t, log l) (generalizing the learnability of O(1) -DNF and of boxes in O(1) dimensions). The algorithm for this class uses only equivalence queries and it can also be used to learn the class of unions of O(1) boxes (from equivalence queries only). Received January 19, 1997; revised June 4, 1997.     

Succinct Representation of Labeled Graphs

In many applications, the properties of an object being modeled are stored as labels on vertices or edges of a graph. In this paper, we consider succinct representation of labeled graphs. Our main results are the succinct representations of labeled and multi-labeled graphs (we consider planar triangulations, planar graphs and k-page graphs) to support various label queries efficiently. The additional space cost to store the labels is essentially the information-theoretic minimum. As far as we know, our representations are the first succinct representations of labeled graphs. We also have two preliminary results to achieve the main contribution. First, we design a succinct representation of unlabeled planar triangulations to support the rank/select of edges in ccw (counter clockwise) order in addition to the other operations supported in previous work. Second, we design a succinct representation for a k-page graph when k is large to support various navigational operations more efficiently. In particular, we can test the adjacency of two vertices in O(lg?k) time, while previous work uses O(k) time.     

图形变换的几何化表示 --论图形变换和投影的若干问题之一

对已有文献中一般采用分离的齐次坐标矩阵的图形变换叙述方法做了比较大的改进．根据仿射变换理论,从几何计算的理论和算法出发,探索了图形变换的几何化表示机制．将图形变换与基本几何有机地联系在一起,用有向直线求解系列函数构筑图形变换齐次矩阵,统一了平移、旋转、错切、对称和比例等坐标变换．     

几何变换的误差表示

针对几何变换中的误差传播问题，通过基本几何量——点的两种误差域表示(矩形域表示和圆域表示)，分别给出了在这两种定义下进一步计算直线、圆的误差域，以及对称旋转变换下误差传播的算法描述。     

Using Parallel Bloom Filters for Multiattribute Representation on Network Services

One widely used mechanism for representing membership of a set of items is the simple space-efficient randomized data structure known as Bloom filters. Yet, Bloom filters are not entirely suitable for many new network applications that support network services like the representation and querying of items that have multiple attributes as opposed to a single attribute. In this paper, we present an approach to the accurate and efficient representation and querying of multiattribute items using Bloom filters. The approach proposes three variant structures of Bloom filters: Parallel Bloom Filter (referred as PBF) structure, PBF with a hash table (PBF-HT), and PBF with a Bloom filter (PBF-BF). PBF stores multiple attributes of an item in parallel Bloom filters. The auxiliary HT and BF provide functions to capture the inherent dependency of all attributes of an item. Compared to standard Bloom filters to represent items with multiple attributes, the proposed PBF facilitates much faster query service and both PBF-HT and PBF-BF structures achieve much lower false positive probability with a result to save storage space. Simulation and experimental results demonstrate that the new space-efficient Bloom filter structures can efficiently and accurately represent multiattribute items and quickly respond queries at the cost of a relatively small false positive probability.     

Optimal Polygonal Representation of Planar Graphs

In this paper, we consider the problem of representing planar graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear-time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges having at most three slopes and with all vertices lying on an O(n)×O(n) grid.     

Orthogonally Drawing Cubic Graphs in Parallel

In this paper we describe a parallel algorithm that, given annvertex cubic graphGas input, outputs an orthogonal drawing ofGwithO(n) bends,O(n) maximum edge length, andO(n²) area inO(log n) time using a CRCW PRAM withnprocessors. We give two slight variants of the algorithm. The first generates a drawing in which each edge has at most 2 bends; the total number of bends and the area are bounded byn+3 and [formula], respectively. The second optimizes the number of bends per edge (at most one) even if the values of the other functions are slightly worst. Despite its nonoptimality, this parallel algorithm is the first dealing with nonplanar, nonbiconnected graphs. Moreover, no embedding of the graph is requested as input nor is anst-numbering (orlmc-numbering) computed.     

Face Recognition Using A Low Rank Representation Based Projections Method

In this paper, a low rank representation based projections (LRRP) method is presented for face recognition. In LRRP, low rank representation is used to construct a nuclear graph to characterize the local compactness information by designing the local scatter matrix like SPP; the total separability information is characterized by the total scatter like PCA. LRRP seeks the projection matrix simultaneously maximizing the total separability and the local compactness. Experimental results on FERET, AR, Yale face databases and the PolyU finger-knuckle-print database demonstrate that LRRP works well for face recognition.     

正螺面和悬链面的表示与构造

利用三角和双曲多项式几何样条,给出了正螺面和悬链面的参数样条张量积表示形式．因而可以利用细分算法生成正螺面和悬链面．通过对正螺面和悬链面控制多边形网格的几何性质的分析,给出了它们的控制多边形网格的一种几何构造规则．     

关联维数的并行求解算法

关联维数的求解是分形理论中的一个重要问题,标准算法由于其巨大的计算量,不能满足实时任务的需要,过去的改造算法集中在串行地减少求解多个关联维数时的重复计算量,并未从根本上降低O(N^2)次的向量距离计算、距离比较和求和次数,其应用范围和性能改善程度是有限的。本文给出了两个并行算法：基于PRAM模型的花费O(N^2／p logp)时间p个处理机的算法,和基于LARPBS模型的花费O(N^2p)时间p个处理机的算法。相对纯理论的PRAM算法,LARPBS算法是实际可行的,它是目前时间复杂度最低的算法,并且是最优可扩展和成长最优的。     

Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions

A random geometric graph (RGG) is defined by placing n points uniformly at random in [0,n ^1/d ] ^d , and joining two points by an edge whenever their Euclidean distance is at most some fixed r. We assume that r is larger than the critical value for the emergence of a connected component with Ω(n) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of $\omega (\frac{\log n}{r^{d-1}} )$ , their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is Θ(n ^1/d /r) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within Θ(n ^1/d /r+logn) rounds.     

基于弱能量并行训练序列的OFDM信道估计

研究获得OFDM信道的信道状态信息,提高信道的传输性能,针对快速信道传输中提高传输率,提出了一种基于弱能量并行训练序列的信道估计算法,算法中训练序列直接叠加到发送的信息数据上,在接收端利用并行训练序列来进行信道估计.仿真结果显示,所提算法的性能与基于导频的LS、MMSE算法性能相当,且在低信噪比时稍优于LS算法.采用m序列、ZCZ序列和最优周期训练序列时都能达到很好的BER信道估计性能,可选择的训练序列的范围更广,并进行仿真.结果表明,算法提高了信道传输性能,计算复杂度低,并具有很好的灵活性,对无线通信系统有效,为系统设计提供了依据.     

无向图同构判定的并行算法

提出了一种判别无向图同构的方法，该方法根据无向图的邻接矩阵的特征值来判别出图的同构关系，而不需要其它附加信息。同时给出用Jacobi方法求出无向图的邻接矩阵的特征值的一种并行算法，它可以在分布式存储的多处理的多处理机上实现。实验结果表明，此方法是快速有效的，能在较短的运算时间内给出判断结果。     

用互感器校验仪测试负载箱的方法

介绍一种利用互感器校验仪测试负载箱阻抗或导纳值的方法.从分析测试原理入手,详细图解如何具体利用广州羊城(或海纳)YC-52互感器校验装置实现对自身所带负载箱的测试.     

协同模板中几何约束关系的表示与解释

模板设计标记语言TDML是协同模板中描述设计信息的标记语言，主要用于表示设计对象的部件信息、部件属性信息、部件位置装配关系信息、操作和连接信息等。设计对象是由一系列部件按照一定的约束关系装配而成的，所以约束信息是设计对象重要的结构信息。文章分析并总结了设计对象之间的几何约束及装配位置关系，采用TDML语言加以描述和解释，并用三维建模器ACIS实现了设计部件间位置关系的可视化。     

一种有效的并行高维聚类算法

针对CLQUE算法聚类结果精确性不高的缺点,提出利用小波变换来生成自适应网格的方法对CLIQUE算法进行改进,将改进算法并行化以增强聚类维数升高时算法的可伸缩性,并将其应用于药品的销售预测。实验表明本算法聚类结果的精确性高,可伸缩性好,并且有效地降低了计算复杂度。     

图形处理器维度层并行粒子群优化算法

笔者提出基于GPU维度层面并行的局部PSO算法,换言之,基于GPU的局部粒子群优化算法求解高维优化函数,即在求解目标函数时对每一个维度进行并行处理。将粒子与线程块对应,线程块中的线程与目标函数的维度对应。实验表明,此算法在优化高维度目标函数中优势明显,概念简单,易编程实现,能有效果解决串行粒子群优化算法性能急剧下降的问题。     

A Parallel Algorithm for Finding Minimum Cutsets in Reducible Graphs

We present a parallel algorithm for finding minimum cutsets in reducible graphs. For a reducible graph that has N nodes our algorithm runs in O(log³N) time using O(N³/log N) PEs on the EREW P-RAM model of computation. We also present a parallel heuristic for finding minimal cutsets in general graphs.     

Trajectory Tracking with Parallel Robots Using Low Chattering,Fuzzy Sliding Mode Controller

This paper proposes a trajectory tracking scheme which belongs to the sliding mode control (SMC) for the 4-degree-of-freedom (DOF) parallel robots. Two fuzzy logic systems (FLS) are first put forward to replace the constant switching control gain and the width of the boundary layer. The fuzzy adaptive supervisory controller (FASC) is combined with the fuzzy sliding mode control (FSMC) to further reduce the chattering. The design is simple and less fuzzy rules are required. The simulation results demonstrate that the chattering of the SMC is reduced greatly and the parallel robot realizes the trajectory tracking with very good robustness to the parameter uncertainties and external disturbances.