{X,Y}-Cyclacene Graphs with Next Nearest Neighbor Interactions

Eigensolutions of {X( = C,B,N),Y( = C,B,N)}-cyclacene graphs with next nearest neighbor (nnn) interactions have been obtained in analytical forms by adapting n-fold rotational symmetry followed by two-fold rotational symmetry (or a plane of symmetry). Expressions of eigensolution indicate the subspectral relationship among such cyclacenes with an even number of hexagonal rings e.g., eigenvalues of {X,Y}-di-cyclacene are found in the eigenspectra of all such even cyclacenes. Total π-electron energies and highest occupied molecular orbital and lowest unoccupied molecular orbital (HOMO–LUMO) gaps are calculated using the analytical expressions obtained and are found to vary negligibly with the variation of nnn interactions in such cyclacenes. Total π-electron energy is found to increase due to increase in restriction intensity of nnn interactions, whereas the HOMO–LUMO gap of polyacenecs having the even number of hexagonal rings and with one electron at each site (atom) decreases with increase in the restriction intensity since such systems contain degenerate half-filled HOMO (bonding or nonbonding) that are much more vulnerable for perturbations imposed through nnn interactions.     

High training set size reduction by space partitioning and prototype abstraction

Instance-based learning methods like the nearest neighbour classifier generally suffer from the indiscriminate storage of all training instances, resulting in large memory requirements and slow execution speed. In this paper, new training set size reduction methods based on prototype generation and space partitioning are proposed. Experimental results show that the new algorithms achieve a very high reduction rate with still an important classification accuracy.     

Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

DKNNS:面向延迟敏感型应用的可扩展精确分布式K近邻搜索算法研究

为了降低用户访问延迟,延迟敏感型网络应用需要选择合适的邻近服务节点响应用户访问请求.分布式K近邻搜索通过可扩展的选择距任意用户节点邻近的K个服务节点,可以有效满足网络应用延迟优化的目的.已有工作在精确度以及可扩展性等方面存在不足.针对可扩展精确的K近邻搜索问题,文中提出了分布式K近邻搜索方法DKNNS(distributed K nearest neighbor search).DKNNS将大量的服务节点组织为邻近性感知的多级环,通过最远节点搜索机制选择优化的K近邻搜索初始化节点,然后基于回退方式快速的在目标节点邻近区域发现K个近邻.基于理论分析,模拟测试以及真实环境下的部署实验发现,在不同规模的节点集合下,DKNNS算法能够确定近似最优的K个服务节点.且DKNNS的查询延迟,查询开销均显著低于Meridian算法.最后,DKNNS的返回结果相对于Meridian具有较高的稳定性.     

Peer-to-peer bichromatic reverse nearest neighbours in mobile ad-hoc networks

The increasing use of mobile communications has raised many issues of decision support and resource allocation. A crucial problem is how to solve queries of Reverse Nearest Neighbour (RNN). An RNN query returns all objects that consider the query object as their nearest neighbour. Existing methods mostly rely on a centralised base station. However, mobile P2P systems offer many benefits, including self-organisation, fault-tolerance and load-balancing. In this study, we propose and evaluate 3 distinct P2P algorithms focusing on bichromatic RNN queries, in which mobile query peers and static objects of interest are of two different categories, based on a time-out mechanism and a boundary polygon around the mobile query peers. The Brute-Force Search Algorithm provides a naive approach to exploit shared information among peers whereas two other Boundary Search Algorithms filter a number of peers involved in query processing. The algorithms are evaluated in the MiXiM simulation framework with both real and synthetic datasets. The results show the practical feasibility of the P2P approach for solving bichromatic RNN queries for mobile networks.     

基于DXF格式的优化数控代码自动生成方法

DXF是AutoCAD与其他软件进行数据交换的CAD通用图形文件格式。实现了一种DXF读取方式并自动生成数控加工代码。传统算法的读取结果无序,不适用于实际加工,针对这一问题根据提取结果及位置关系生成图元轮廓树,并利用最近邻插入算法对图元轮廓优化排序,得到全局优化的最短切割路径,并通过实例证实了算法的有效性,能满足实际自动编程数控系统的工作需要。     

LDE融合光谱回归分类的光照变化人脸识别

针对光照变化人脸识别问题中传统的光谱回归算法不能很好地进行特征提取而严重影响识别性能的问题,提出了局部判别嵌入优化光谱回归分类的人脸识别算法。计算出训练样本的特征向量;借助于数据的近邻和分类关系,利用局部判别嵌入算法构建分类问题所需的嵌入,同时学习每种分类的子流形所需的嵌入;利用光谱回归分类算法计算投影矩阵,并利用最近邻分类器完成人脸的识别。在两大人脸数据库扩展YaleB及CMU PIE上的实验验证了该算法的有效性,实验结果表明,相比其他光谱回归算法,该算法取得了更高的识别率、更好的工作特性,并且降低了计算复杂度。     

一种基于稀疏表示的WLAN室内定位算法

随着科技进步和人民生活水平的提高,越来越多的用户对定位技术需求变得日益迫切。基于WLAN的室内定位技术研究在此背景下应运而生,但是该技术容易受非视距离以及多径影响。而位置指纹算法有效地克服了上述缺点,并得到了广泛应用。提出一种基于稀疏表示的WLAN室内定位算法,以解决位置指纹算法K近邻方法中参数选择问题、不能综合利用全局参考点信息问题,并对其进行了实验仿真。     

基于Voronoi图的连续反向最近邻查询

为解决动态环境中移动点的连续反向最近邻查询问题,将连续反向最近邻查询分为单色和双色2种情况进行研究。利用移动点Voronoi图,分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理,对算法正确性和可终止性进行证明,分析算法时间复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况,分析每种情况下候选所在区域的变化,在变化区域内进行Voronoi图的重构,得到对应的解决方法。在多数情况下,该算法只需生成局部移动点的Voronoi图即可找到结果,减小了连续反向最近邻查询的代价。     

一种基于自然最近邻的离群检测算法

任何涉及k近邻求解问题的算法被应用于处理不同特征的数据集时,参数k值的选择都会明显影响算法的性能和结果。因而,如何选择k近邻算法中敏感参数k值一直是一个研究难点。提出了一种新的近邻关系———自然最近邻,它不需要设置参数k,每个节点的邻居是由算法自适应计算而形成的。针对离群点检测的特殊性,通过确定自然最近邻居搜索算法的终止条件,提出一种基于自然最近邻的新的离群检测算法ODb3N。实验表明,该算法不仅避免了k近邻中参数的选择问题,而且能够更有效地发现离群簇。