Graph Traversal and Top-Down Evaluation of Logic Queries

In this paper,an optimal method to handle cyclic and acyclic data relations in the linear recursive queries is proposed.High efficiency is achieved by integrating graph traversal mechanisms into a top-down evaluation.In such a way,the subsumption checks and the identification of cyclic data can be done very efficiently.First,based on the subsumption checks,the search space can be reduced drastically by avoiding any redundant expansion operation.In fact,in the case of non-cyclic data,the proposed algorithm requires only linear time for evaluating a linear recursive query.On the other hand,in the case of cyclic data,by using the technique for isolaiting strongly connected components a lot of answers can be generatded directly in terms of the intermediate results and the relevant path information instead of evaluating them by performing algebraic operations.Since the cost of generating an answer in much less than that of evaluating an answer by algebraic operations,the bime consumption for cyclic data can be reduced by an order of magnitude or more.     

一种改进的四叉树RFID防碰撞算法

针对随机ALOHA算法效率较低,确定性树型方法要求区域内标签数量不变的问题,提出一种改进的四叉树RFID防碰撞算法。在阅读器阅读范围内的标签根据不同的问询命令修改自身应答概率进行分组。阅读器采用比较碰撞位的四叉树算法识别应答概率为1的标签。通过公式推导证明了算法采用四叉树识别的合理性。实例说明和仿真结果显示,该算法能减少阅读器和标签之间的查询次数和通信量,有效提高阅读器的识别效率。     

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.     

用户访问兴趣路径挖掘方法

针对当前挖掘用户访问模式算法仅将频繁访问路径作为用户浏览兴趣路径的问题,依据使用Web日志挖掘用户兴趣页面时,通过引入页面信息量参数,综合考虑页面访问次数、浏览时间和页面信息量大小来定义用户兴趣度,提出了基于兴趣度的用户访问模式挖掘算法。实验证明该算法是有效的,在用户浏览兴趣度量方面比当前的频繁访问路径挖掘算法更准确。     

Dilation algorithm for a linear quadtree

A dilation algorithm for a linear quadtree is presented. This can be used to expand the black regions of a region quadtree by a user-specified amount. The algorithm requires two traversals through the ordered quadtree leaf set, the second traversal being in the opposite direction to the first. No explicit neighbour finding is required. Timings are compared with those obtained using an existing one-pass algorithm. The two-pass algorithm is faster than the one-pass for expansions of typical real images, and this speed increase becomes more pronounced as the expansion and the complexity of the image increase.     

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

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

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

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

一种基于四叉树的TIN的LOD算法

通过在不规则采样点集上构建一个四叉树结构，并联合基于四叉树的LOD算法和基于TIN的三角网简化算法，提出并实现了一种TIN的LOD算法。意在把适用于格网数据的高效方法应用于不规则采样点集，得到地形的一个高效的多分辨率表达。     

基于分类遍历的碰撞检测优化算法

针对现有层次树遍历方法的低效率问题,提出了一种基于分类遍历的碰撞检测算法.首先根据两个物体树中节点的平衡因子差值来将所有的物体对进行分类:结构相似的,采用同步下降遍历方法;结构不相似的,采用交换下降遍历方法,这减少了相交测试的次数.然后加入时空相关性和优先级策略优化遍历过程.最后通过实验结果表明,相比基于统一遍历的碰撞检测算法,该算法缩短了相交测试的时间,物体数目越多,快速性优势越显著,大约可以缩减所需时间的1/5.     

基于改进四叉树的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.     

IM-FTS:一种快速增量式频繁访问序列挖掘算法

由于Web数据增长迅速,先前的频繁序列随着序列库的更新而改变。若重新挖掘频繁序列会增加处理时间和数据存储量。提出一种改进的扩展格结构IE-LATTICE,存储先前的挖掘结果,并在其基础上提出一种基于双向约束的增量挖掘算法IM-FTS,在利用先前结果和约束策略前提下,算法仅从插入和删除序列中发现新的频繁序列。分析和实验表明算法能有效缩减数据处理时间和存储空间。     

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 fast graph traversal algorithm for the computer enumeration of P-V paths of benzenoid graphs

A computer program with O(p.n) time complexity is developed for the combinatorial enumeration of peak to valley augmenting paths of any n-vertex benzenoid graph with p number of peaks, using sets as its primary data structure. Peaks and valleys are recognized by using a breadth-first labeling procedure. The code computes the P-V matrix whose determinant is the number of Kekule structures of the given graph G. this program can handle very large graphs and takes only a few seconds to compute the P-V matrix of the typical graph even on a personal computer. As the code is very efficient and compact it can be used in any program that calculates the Kekule structure count (KSC) as an intermediate result.     

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。