Compact Labeling Scheme for XML Ancestor Queries

XML documents are often viewed as trees (basically the parse tree of the document), and queries over such documents typically test for ancestor relationships among tree nodes. Search engines process such queries using an index structure summarizing the ancestor relations. In the index, each document item (tree node) is identified using some logical id (node label), such that, given two labels, the engine can determine the ancestor relationship between the corresponding nodes. The length of the labels is a main factor of the index size. Therefore, reducing this length, even by a constant factor, is a critical issue. In this work we consider the following problem. Given a rooted XML tree T, label the nodes of T in the most compact way such that given the labels of two nodes, one can determine in constant time, by looking at the labels only, whether one node is an ancestor of the other. Labelings currently being used are all variants of the following interval scheme. Number the leaves say from left to right and label each node with a pair consisting of the numbers of its smallest and largest leaf descendants. An ancestor query then amounts to an interval containment test on the labels. The maximum label length using this scheme is 2 log n, where n is the number of nodes in the tree. (All logarithms in this paper are to base 2.) The focus of this work is finding a scheme that works best in practice on real XML data. We suggest an orthogonal prefix-based approach, where the labeling is such that an ancestor query roughly amounts to testing whether one label is a prefix of the other. We present several new labeling schemes based on this approach and analyze their performance both theoretically and empirically.     

交通道路网中任意两点之间最短路径的快速算法

寻找交通道路网中任意两点之间最短路径的算法已有许多 ,其中Dijkstra算法是最有效的算法之一 ,其时间复杂性为O(n2 )。本文提出的算法与Dijkstra算法不同 ,其主要思想是依据从始点至终点的直线段方向选择边产生二叉树 ,并采取有效方法降低二叉树的规模及缩短路径长度 ,然后由二叉树节点的标记计算出近似最短路径及其长度。反复执行常数次该算法可以求得最短路径及其长度。     

Ad hoc网络时延受限的Steiner树启发式算法

针对Ad hoc网络时延受限的Steiner树问题,设计一个分布式的快速启发式算法DCST,该算法通过对网络中节点进行标号,并根据标号修改节点间的关联关系,建立一棵时延受限的Steiner树。在网络节点保持时间同步的前提下,算法的时间复杂度为O(n)。与现有经典的Steiner树算法相比,该算法具有明显优势。     

Constructing Euclidean minimum spanning trees and all nearestneighbors on reconfigurable meshes

A reconfigurable mesh, R-mesh for short, is a two-dimensional array of processors connected by a grid-shaped reconfigurable bus system. Each processor has four I/O ports that can be locally connected during execution of algorithms. This paper considers the d-dimensional Euclidean minimum spanning tree (EMST) and the all nearest neighbors (ANN) problem. Two results are reported. First, we show that a minimum spanning tree of n points in a fixed d-dimensional space can be constructed in O(1) time on a √(n³)×√(n³) R-mesh. Second, all nearest neighbors of n points in a fixed d-dimensional space can be constructed in O(1) time on an n×n R-mesh. There is no previous O(1) time algorithm for the EMST problem; ours is the first such algorithm. A previous R-mesh algorithm exists for the two-dimensional ANN problem; we extend it to any d-dimensional space. Both of the proposed algorithms have a time complexity independent of n but growing with d. The time complexity is O(1) if d is a constant     

在动态树中寻找祖先

文章提出了有线性预处理时间,在恒定的查询时间内,通过加叶和加根操作对树的祖先进行查找的一种有效算法,这种算法能在O(m+n)时间内进行m次祖先查询及n次增叶操作。     

Maintaining order in a generalized linked list

Summary We give a representation for linked lists which allows to efficiently insert and delete objects in the list and to quickly determine the order of two list elements. The basic data structure, called an indexed BB []-tree, allows to do n insertions and deletions in O(n log n) steps and determine the order in constant time, assuming that the locations of the elements worked at are given. The improved algorithm does n insertions and deletions in O(n) steps and determines the order in constant time. An application of this provides an algorithm which determines the ancestor relationship of two given nodes in a dynamic tree structure of bounded degree in time O(1) and performs n arbitrary insertions and deletions at given positions in time O(n) using linear space.     

An Efficient Adaptive Algorithm for Constructing the Convex Differences Tree of a Simple Polygon

The convex differences tree (CDT) representation of a simple polygon is useful in computer graphics, computer vision, computer aided design and robotics. The root of the tree contains the convex hull of the polygon and there is a child node recursively representing every connectivity component of the set difference between the convex hull and the polygon. We give an O(n log K + K log² n) time algorithm for constructing the CDT, where n is the number of polygon vertices and K is the number of nodes in the CDT. The algorithm is adaptive to a complexity measure defined on its output while still being worst case efficient. For simply shaped polygons, where K is a constant, the algorithm is linear. In the worst case K = O(n) and the complexity is O(n log² n). We also give an O(n log n) algorithm which is an application of the recently introduced compact interval tree data structure.     

Computing geometric properties of images represented by linear quadtrees

The region quadtree is a hierarchical data structure that finds use in applications such as image processing, computer graphics, pattern recognition, robotics, and cartography. In order to save space, a number of pointerless quadtree representations (termed linear quadtrees) have been proposed. One representation maintains the nodes in a list ordered according to a preorder traversal of the quadtree. Using such an image representation and a graph definition of a quadtree, a general algorithm to compute geometric image properties such as the perimeter, the Euler number, and the connected components of an image is developed and analyzed. The algorithm differs from the conventional approaches to images represented by quadtrees in that it does not make use of neighbor finding methods that require the location of a nearest common ancestor. Instead, it makes use of a staircase-like data structure to represent the blocks that have been already processed. The worst-case execution time of the algorithm, when used to compute the perimeter, is proportional to the number of leaf nodes in the quadtree, which is optimal. For an image of size 2n × 2n, the perimeter algorithm requires only four arrays of 2n positions each for working storage. This makes it well suited to processing linear quadtrees residing in secondary storage. Implementation experience has confirmed its superiority to existing approaches to computing geometric properties for images represented by quadtrees.     

构造二叉树的两个改进算法

在数据结构中,已知一棵二叉树的先序序列和中序序列,可唯一确定此二叉树.本文在分析建立二叉树经典算法的时间复杂度的基础上,给出了两个改进算法:①利用哈希函数,使得改进后的算法在最差情况下,时间复杂度由O(n2)降为O(n);②利用栈和控制输入的结点序列构造二叉树,时间复杂度也由O(n2)降为O(n).     

Deterministic Communication in Radio Networks with Large Labels

We study deterministic gossiping in ad hoc radio networks with large node labels. The labels (identifiers) of the nodes come from a domain of size N which may be much larger than the size n of the network (the number of nodes). Most of the work on deterministic communication has been done for the model with small labels which assumes N = O(n). A notable exception is Peleg's paper, where the problem of deterministic communication in ad hoc radio networks with large labels is raised and a deterministic broadcasting algorithm is proposed, which runs in O(n²log n) time for N polynomially large in n. The O(nlog²n)-time deterministic broadcasting algorithm for networks with small labels given by Chrobak et al. implies deterministic O(n log N log n)-time broadcasting and O(n²log²N log n)-time gossiping in networks with large labels. We propose two new deterministic gossiping algorithms for ad hoc radio networks with large labels, which are the first such algorithms with subquadratic time for polynomially large N. More specifically, we propose: a deterministic O(n^3/2log²N log n)-time gossiping algorithm for directed networks; and a deterministic O(n log²N log²n)-time gossiping algorithm for undirected networks.     

Finding lowest common ancestors in arbitrarily directed trees

It is well known how to preprocess a rooted tree in linear time to yield the lowest common ancestor of any given pair of nodes in constant time. We generalize these algorithms for graphs called Arbitrarily Directed Trees, or ADTs. Such trees are obtained by reversing the directions of some edges in trees with the customary “root-to-leaf” orientation of edges.     

二叉树演绎于结点序号内蕴性质的快速算法

通过研究二叉树结点顺序存储序号的性质,演绎出了二叉树非递归无堆栈的一些新算法,包括完全二叉树两结点最近共同祖先（LCA）的查询算法、中序遍历算法、顺序序列与中序序列的互转算法以及从中序序列恢复层次结构的算法。新的算法都具有很好的时间复杂度,其中LCA查询算法可在常数时间内实现且不需要任何预处理过程,其他算法均为线性时间复杂度。所有算法均为常数空间复杂度,仅涉及到简单的加减运算与位运算,既可用于常规程序设计也可用于嵌入式等专业开发。     

All nearest smaller values on the hypercube

Given a sequence of n elements, the All Nearest Smaller Values (ANSV) problem is to find, for each element in the sequence, the nearest element to the left (right) that is smaller, or to report that no such element exists. Time and work optimal algorithms for this problem are known on all the PRAM models but the running time of the best previous hypercube algorithm is optimal only when the number of processors p satisfies 1⩽p⩽n/((lg³ n)(lg lg n)²). In this paper, we prove that any normal hypercube algorithm requires Ω(M) processors to solve the ANSV problem in O(lg n) time, and we present the first normal hypercube ANSV algorithm that is optimal for all values of n and p. We use our ANSV algorithm to give the first O(lg n)-time n-processor normal hypercube algorithms for triangulating a monotone polygon and for constructing a Cartesian tree     

A new parallel and distributed shortest path algorithm forhierarchically clustered data networks

This paper presents new efficient shortest path algorithms to solve single origin shortest path problems (SOSP problems) and multiple origins shortest path problems (MOSP problems) for hierarchically clustered data networks. To solve an SOSP problem for a network with n nodes, the distributed version of our algorithm reaches the time complexity of O(log(n)), which is less than the time complexity of O(log ² (n)) achieved by the best existing algorithm. To solve an MOSP problem, our algorithm minimizes the needed computation resources, including computation processors and communication links for the computation of each shortest path so that we can achieve massive parallelization. The time complexity of our algorithm for an MOSP problem is O(m log(n)), which is much less than the time complexity of O(M log² (0)) of the best previous algorithm. Here, M is the number of the shortest paths to be computed and m is a positive number related to the network topology and the distribution of the nodes incurring communications, m is usually much smaller than M. Our experiment shows that m is almost a constant when the network size increases. Accordingly, our algorithm is significantly faster than the best previous algorithms to solve MOSP problems for large data networks     

On computing all north-east nearest neighbors in the L1 metric

Given a collection of n points in the plane, we exhibit an algorithm that computes the nearest neighbor in the north-east (first quadrant) of each point, in the L₁ metric. By applying a suitable transformation to the input points, the same procedure can be used to compute the L₁ nearest neighbor in any given octant of each point. This is the basis of an algorithm for computing the minimum spanning tree of the n points in the L₁ metric. All three algorithms run in O(n lg n) total time and O(n) space.     

A Tree Projection Algorithm for Generation of Frequent Item Sets

In this paper we propose algorithms for generation of frequent item sets by successive construction of the nodes of a lexicographic tree of item sets. We discuss different strategies in generation and traversal of the lexicographic tree such as breadth-first search, depth-first search, or a combination of the two. These techniques provide different trade-offs in terms of the I/O, memory, and computational time requirements. We use the hierarchical structure of the lexicographic tree to successively project transactions at each node of the lexicographic tree and use matrix counting on this reduced set of transactions for finding frequent item sets. We tested our algorithm on both real and synthetic data. We provide an implementation of the tree projection method which is up to one order of magnitude faster than other recent techniques in the literature. The algorithm has a well-structured data access pattern which provides data locality and reuse of data for multiple levels of the cache. We also discuss methods for parallelization of the TreeProjection algorithm.     

A parallel algorithm for constructing a labeled tree

A tree T is labeled when the n vertices are distinguished from one another by names such as v₁, v₂…v_n . Two labeled trees are considered to be distinct if they have different vertex labels even though they might be isomorphic. According to Cayley's tree formula, there are n^n-2 labeled trees on n vertices. Prufer used a simple way to prove this formula and demonstrated that there exists a mapping between a labeled tree and a number sequence. From his proof, we can find a naive sequential algorithm which transfers a labeled tree to a number sequence and vice versa. However, it is hard to parallelize. In this paper, we shall propose an O(log n) time parallel algorithm for constructing a labeled tree by using O(n) processors and O(n log n) space on the EREW PRAM computational model     

Efficient algorithms for the all nearest neighbor and closest pair problems on the linear array with a reconfigurable pipelined bus system

We present two O(1)-time algorithms for solving the 2D all nearest neighbor (2D/spl I.bar/ANN) problem, the 2D closest pair (2D/spl I.bar/CP) problem, the 3D all nearest neighbor (3D/spl I.bar/ANN) problem and the 3D-closest pair (3D/spl I.bar/CP) problem of n points on the linear array with a reconfigurable pipelined bus system (LARPBS) from the computational geometry perspective. The first O(1) time algorithm, which invokes the ANN properties (introduced in this paper) only once, can solve the 2D/spl I.bar/ANN and 2D/spl I.bar/CP problems of n points on an LARPBS of size 1/2n/sup 5/3+c/, and the 3D/spl I.bar/ANN and 3D/spl I.bar/CP problems pf n points on an LARPBS of size 1/2n/sup 7/4+c/, where 0 < /spl epsi/ = 1/2/sup c+1/-1 /spl Lt/ 1, c is a constant and positive integer. The second O(1) time algorithm, which recursively invokes the ANN properties k times, can solve the kD/spl I.bar/ANN, and kD/spl I.bar/CP problems of n points on an LARPBS of size 1/2n/sup 3/2+c/, where k = 2 or 3, 0 < /spl epsi/ = 1/2/sup n+1/-1 /spl Lt/ 1, and c is a constant and positive integer. To the best of our knowledge, all results derived above are the best O(1) time ANN algorithms known.     

Representing Trees of Higher Degree

This paper focuses on space efficient representations of rooted trees that permit basic navigation in constant time. While most of the previous work has focused on binary trees, we turn our attention to trees of higher degree. We consider both cardinal trees (or k-ary tries), where each node has k slots, labelled {1,...,k}, each of which may have a reference to a child, and ordinal trees, where the children of each node are simply ordered. Our representations use a number of bits close to the information theoretic lower bound and support operations in constant time. For ordinal trees we support the operations of finding the degree, parent, ith child, and subtree size. For cardinal trees the structure also supports finding the child labelled i of a given node apart from the ordinal tree operations. These representations also provide a mapping from the n nodes of the tree onto the integers {1, ..., n}, giving unique labels to the nodes of the tree. This labelling can be used to store satellite information with the nodes efficiently.     

Compressed Suffix Trees with Full Functionality

We introduce new data structures for compressed suffix trees whose size are linear in the text size. The size is measured in bits; thus they occupy only O(n log|A|) bits for a text of length n on an alphabet A. This is a remarkable improvement on current suffix trees which require O(n log n) bits. Though some components of suffix trees have been compressed, there is no linear-size data structure for suffix trees with full functionality such as computing suffix links, string-depths and lowest common ancestors. The data structure proposed in this paper is the first one that has linear size and supports all operations efficiently. Any algorithm running on a suffix tree can also be executed on our compressed suffix trees with a slight slowdown of a factor of polylog(n).