Morris' tree traversal algorithm reconsidered

In 1968, Knuth posed the problem of designing a stack-free, tag-free, non-recursive algorithm that traversed the tree in in-order while leaving it unaltered in the end. Since then, numerous solutions have appeared in the literature. The 1979 algorithm by Morris is one of the most elegant of these solutions. The algorithm is clearly non-recursive, and appears, at first glance, to use neither a stack, nor tag fields. We present an insightful derivation of this algorithm. We also show that a stack is indeed present and ‘time-shares’ the right-link fields of the tree nodes. Our proof comes in two parts: (a) We start with a traversal algorithm that explicitly uses a stack, and show that it is computationally equivalent to another that uses a non-standard implementation of a stack; (b) We then show that the later algorithm can be transformed to Morris' algorithm using only control structure transformations.     

基于线性四叉树的快速邻域查询算法

邻域查询是位置服务系统的核心技术,它的实现取决于空间对象数据模型.根据空间对象分布构建的四叉树模型,以及线性四叉树中位置码的使用,提出了一种新的基于线性四叉树的快速邻域查询算法.该算法根据满四叉树结点编码思想对线性四叉树的Morton码进行了改进,并增加了表示四叉树所有结点状态的序列,通过网格模型的邻域查询算法实现了线性四叉树的快速邻域查询.     

Gout-ITS系统的深度优先语义遍历算法

该文分析了痛风临床诊治智能教学系统（Intelligent Tutoring System for the Instruction of Gout Clinical Diagnosis and Treatment，以下简称Gout-ITS系统）自动生成病例所需的领域知识及其特点，提出了语义树知识表示法和深度优先语义遍历算法。该算法可以有效地生成既符合学生的学习难度要求、又符合病理逻辑的、多样化不重复的病例。最后，将该算法与人工智能中的深度优先搜索算法进行了比较，阐述了其中的不同之处。     

基于改进四叉树的ORB特征均匀分布算法

针对ORB特征在图像上分布不均匀的问题,提出一种基于改进四叉树的特征均匀分布算法。通过计算图像灰度均值与方差选取FAST角点的初始提取阈值,采用改进的四叉树对特征点进行筛选,对不同金字塔层设置不同的四叉树深度以提高计算效率,减少特征冗余,采用均匀度函数对特征的均匀度进行量化。实验结果表明,改进算法提高了ORB特征的均匀度,特征提取时间相比传统算法减少10%以上,有效提高了特征提取的均匀度和效率。     

A strip-splitting-based optimal algorithm for decomposing a query window into maximal quadtree blocks

Decomposing a query window into maximal quadtree blocks is a fundamental problem in quadtree-based spatial database. Recently, Proietti presented the first optimal algorithm for solving this problem. Given a query window of size n/sub 1//spl times/n/sub 2/, Proietti's algorithm takes O(n/sub 1/) time, where n/sub 1/=max(n/sub 1/, n/sub 2/). Based on a strip-splitting approach, we present a new optimal algorithm for solving the same problem. Experimental results reveal that our proposed algorithm is quite competitive with Proietti's algorithm.     

A robust circle detection algorithm based on top-down least-square fitting analysis

In this paper, we propose a robust and efficient circle detector, which achieves accurate results with a controlled number of false detections and requires no parameter tuning. The proposed algorithm consists of three steps as follows. First, we propose a novel edge point chaining method to extract Canny edge segments (i.e., contiguous and sequential chains of Canny edge points). Second, we split each edge segment into several smooth sub-segments, and detect candidate circles within each obtained sub-segment based on top-down least-square fitting analysis. Third, we employ Desolneux et al.’s method to reject the false detections. Experimental results demonstrate that the proposed method is efficient and more robust than the state-of-the-art algorithm EDCircles.     

An optimal algorithm for decomposing a window into maximal quadtree blocks

Decomposing a two-dimensional window (i.e., the region specified by the cross product of two closed intervals over a given two-dimensional space) into its maximal quadtree blocks means to find the set of black quadrants that would be obtained by representing the region covered by the window using a quadtree. In this paper we propose an optimal O(n) time algorithm for decomposing a square window of size embedded in an image space of pixel elements, thus improving the O(n log log T) time algorithm of Aref and Samet [2]. As a direct consequence of this new faster algorithm, classical window operations on main memory quadtree based data structures can be solved more efficiently. In particular, we show that the exist and report queries on the incomplete pyramid [1] and on the up-down pyramid [8] can be solved in O(n) time, which is optimal. Received: 1 September 1997 / 28 October 1998     

A top-down algorithm for generating the Hasse tree of a fuzzy preorder closure

This paper describes a new top-down algorithm for the stepwise generation of the different levels or Hasse diagrams of the Hasse tree associated to the fuzzy preorder closure (min-transitive closure) of a given reflexive binary fuzzy relation. The algorithm is based upon a recently established weight-driven method for computing the min-transitive closure of a reflexive binary fuzzy relation. The way in which this method gradually establishes the fuzzy preorder closure implies that for the generation of a specific level of the Hasse tree, the newly proposed algorithm does not require the complete computation of this closure.     

Execution time analysis of a top-down R-tree construction algorithm

A detailed CPU execution-time analysis and implementation are given for a bulk loading algorithm to construct R-trees due to García et al. [Y.J. García, M.A. López, S.T. Leutenegger, A greedy algorithm for bulk loading R-trees, in: GIS'98: Proc. of the 6th ACM Intl. Symp. on Advances in Geographic Information Systems, Washington, DC, 1998, pp. 163-164] which is known as the top-down greedy split (TGS) bulk loading algorithm. The TGS algorithm makes use of a classical bottom-up packing approach. In addition, an alternative packing approach termed top-down packing is introduced which may lead to improved query performance, and it is shown how to incorporate it into the TGS algorithm. A discussion is also presented of the tradeoffs of using the bottom-up and top-down packing approaches.     

一种SIP穿透NAT的解决方案

基于IP的语音、数据、视频等业务在NGN网络中所面临的一个实际困难就是如何有效地穿透各种NAT的问题。现有的解决方案有ALG、Media Proxy、STUN、Middlebox等。本文提出了一种综合应用STUN和Media Proxy方案解决SIP穿透NAT的方案。对于非对称NAT采用STUN穿透,对于对称NAT采用Media Proxy方案穿透。实验结果表明,该方案可以让SIP终端穿透几乎所有类型的NAT。     

Secure 3D data hiding technique based on a mesh traversal algorithm

Multimedia Tools and Applications - Due to its powerful ability to conceal secret data inside an unsuspicious cover object, image steganography has emerged as an active field of research. Recently,...     

Can: A context-aware NAT traversal scheme

Network Address Translation (NAT) is a technique commonly used to share one public IPv4 address among several hosts located behind a NAT device. NAT devices typically block session requests originating from outside, causing NAT traversal problem that prevents the establishment of peer-to-peer (P2P) sessions. There have been many proposals for the NAT traversal problem. However, existing methods induce high connectivity check delay and resource demand when finding a communicating path, calling for a routine that determines the path best suited for a given pair of communicating peers. This study proposes CAN, a Context-Aware NAT traversal scheme which gathers and exchanges network-context information to find the most appropriate path for two communicating peers behind NAT devices. We have implemented CAN and conducted extensive experiments with off-the-shelf NAT devices to compare the performance of CAN with Interactivity Connectivity Establishment (ICE), the most acknowledged approach to creating a session across NATs. Experimental results show that CAN outperforms ICE in terms of direct communication ratio, connectivity check delay and message overload when checking connectivity.     

A quadtree normalization scheme based on cyclic translations

An image can be represented by a compact and hierarchical structure, i.e. a quadtree. The storage requirements of an image constructed by a quadtree is highly sensitive to its position. Ang and Samet [Pattern Recognition Lett. 15(1), 57–63 (1994)] proposed an algorithm capable of normalizing a quadtree in O(s²log₂s) time and O(s²) space, where s is the length of the image grid, such that the number of nodes of the quadtree after normalization can be minimal. However, s is twice as long as the length of one side of the image to be normalized. In this study, we propose a normalization scheme based on cyclic translations. The time complexity and the space requirements of this scheme have four times less than those in Ang and Samet's case. In addition, no translation is necessary to fit the image into the northwest quadrant of the grid before the process of normalization. Also, this scheme can normalize a quadtree to obtain less node numbers than that of Ang and Samet. Furthermore, if the image's four corners have the same color, the amount of reduction for node number becomes larger after cyclic translations; it can occasionally reach to 75%. The analytical and empirical results demonstrate the advantages of this scheme.     

P-Teredo服务穿越Symmetric NAT的解决方案

介绍了Teredo服务的运行原理和NAT设备类型。重点描述了P-Teredo服务的架构和应用端口预测算法在该服务中获取客户端IPv6地址的方法。为了提高网络连接成功率,提出了几个提高端口预测命中率的方法,分析了网络连接成功率和系统性能。     

FTP文件遍历方法研究与应用

分析了FTP协议和图的遍历算法,对比了遍历算法的适用性,叙述了采用广度优先算法进行FTP文件遍历的方法,并基于此建立了FTP文件搜索引擎,给出了应用实例。     

A top-down methodology for microprocessor validation

A major challenge in today's functional verification is the lack of a formal specification with which to compare the RTL model. We propose a novel top-down verification approach that allows specification of a design above the RTL. From this specification, it is possible to automatically generate assertion models and RTL reference models. We also demonstrate that symbolic simulation and equivalence checking can be applied to verify an RTL design against its specification.     

A software tool for top-down programming

Top-down design and programming methods have become well established in both commercial and academic environments. However, a programmer using such methods faces a number of organizational difficulties. This paper describes a software tool, written in Pascal, which eliminates these difficulties. It allows a programmer to interactively develop programs in a top-down fashion.     

Motion estimation with quadtree splines

This paper presents a motion estimation algorithm based on a new multiresolution representation, the quadtree spline. This representation describes the motion field as a collection of smoothly connected patches of varying size, where the patch size is automatically adapted to the complexity of the underlying motion. The topology of the patches is determined by a quadtree data structure, and both split and merge techniques are developed for estimating this spatial subdivision. The quadtree spline is implemented using another novel representation, the adaptive hierarchical basis spline, and combines the advantages of adaptively-sized correlation windows with the speedups obtained with hierarchical basis preconditioners. Results are presented on some standard motion sequences     

An efficient top-down search algorithm for learning Boolean networks of gene expression

Boolean networks provide a simple and intuitive model for gene regulatory networks, but a critical defect is the time required to learn the networks. In recent years, efficient network search algorithms have been developed for a noise-free case and for a limited function class. In general, the conventional algorithm has the high time complexity of O(2^{2k mn k+1}) where m is the number of measurements, n is the number of nodes (genes), and k is the number of input parents. Here, we suggest a simple and new approach to Boolean networks, and provide a randomized network search algorithm with average time complexity O ^{(mn k+1}/ (log m)^(k−1)). We show the efficiency of our algorithm via computational experiments, and present optimal parameters. Additionally, we provide tests for yeast expression data. Editor: David Page