VLSI algorithms and architecture for relational operations

The use of a special purpose VLSI chip for relational operations is proposed The chip is structured like a tree with processors at the nodes, called TOP (Tree of Processors). Each node is capable of storing a data element and of performing elementary operations on elements. A table ofn tuples ofk elements each (e. g., a relation defined as in data base theory) is stored inn subtrees of at leastk nodes each, at the lowest levels of TOP. The upper portion of TOP is used for routing and bookkeeping purposes. A number of elementary operations are defined for the nodes, and high level operations on tables are performed as combinations of the former ones. In particular, some operations for data input/output and update are discussed, and the basic operations of UNION, DIFFERENCE, PROJECTION, PRODUCT, SELECTION, and JOIN, defined in relational algebra, are studied for TOP realization. Even the most complex operations are executed inO (kn) steps, that is the size of data. This result is optimal in our system, where we assume that data are transmitted to TOP's through channels of constan bandwidth. Dedicated to Professor S. Faedo on his 70th birthday This research has been partially supported by Ministero della Pubblica Istruzione of Italy.     

New primal and dual matching heuristics

We describe a new heuristic for constructing a minimum-cost perfect matching designed for problems on complete graphs whose cost functions satisfy the triangle inequality (e.g., Euclidean problems). The running time for ann node problem is O(n logn) after a minimum-cost spanning tree is constructed. We also describe a procedure which, added to Kruskal's algorithm, produces a lower bound on the size of any perfect matching. This bound is based on a dual problem which has the following geometric interpretation for Euclidean problems: Pack nonoverlapping disks centered at the nodes and moats surrounding odd sets of nodes so as to maximize the sum of the disk radii and moat widths.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada.     

Write-Optimized B+ Tree Index Technology for Persistent Memory

Due to its low latency,byte-addressable,non-volatile,and high density,persistent memory (PM) is expected to be used to design a high-performance storage system.However,PM also has disadvantages such as limited endurance,thereby proposing challenges to traditional index technologies such as B+ tree.B+ tree is originally designed for dynamic random access memory (DRAM)-based or disk-based systems and has a large write amplification problem.The high write amplification is detrimental to a PM-based system.This paper proposes WO-tree,a write-optimized B+ tree for PM.WO-tree adopts an unordered write mechanism for the leaf nodes,and the unordered write mechanism can reduce a large number of write operations caused by maintaining the entry order in the leaf nodes.When the leaf node is split,WO-tree performs the cache line flushing operation after all write operations are completed,which can reduce frequent data flushing operations.WO-tree adopts a partial logging mechanism and it only writes the log for the leaf node.The inner node recognizes the data inconsistency by the read operation and the data can be recovered using the leaf node information,thereby significantly reducing the logging overhead.Furthermore,WO-tree adopts a lock-free search for inner nodes,which reduces the locking overhead for concurrency operation.We evaluate WO-tree using the Yahoo!Cloud Serving Benchmark(YCSB) workloads.Compared with traditional B+ tree,wB-tree,and Fast-Fair,the number of cache line flushes caused by WO-tree insertion operations is reduced by 84.7％,22.2％,and 30.8％,respectively,and the execution time is reduced by 84.3％,27.3％,and 44.7％,respectively.     

Parallel processing of graph reachability in databases

In this paper we consider parallel processing of a graph represented by a database relation, and we achieved two objectives. First, we propose a methodology for analyzing the speedup of a parallel processing strategy with the purpose of selecting at runtime one of several candidate strategies, depending on the hardware architecture and the input graph. Second, we study the single-source reachability problem, namely the problem of computing the set of nodes reachable from a given node in a directed graph. We propose several parallel strategies for solving this problem, and we analyze their performance using our new methodology. The analysis is confirmed experimentally in a UNIX-Ethernet environment. We also extend the results to the transitive closure problem.A preliminary shortened version of this paper has appeared inPDIS. See Ref. 1.This author's work was supported in part by NSF Grant 90-03341.This author's work was supported in part by the Natural Sciences and Engineering Research Council of Canada.This author's work was supported in part by NSF Grant 90-03341.     

Insertion-safeness in balanced trees

A node in a 2-3-tree or B-tree is safe (with respect to insertion) if it has less than the maximally allowable number of keys. It is a deepest safe node if it is the deepest among all safe nodes on an access path. In this paper we analyze the probabilities for a random insertion to have its deepest safe node above the leaf level and the father-of-leaves level of its access path, using the well-known average case results of Yao (1978) for random 2-3- and B-trees. The implications of these results on various solutions proposed to support concurrent operations in 2-3-trees and B-trees are also discussed.     

Purely top-down updating algorithms for stratified search trees

Summary The existence of purely top-down updating algorithms for balanced search trees is of importance when maintaining such trees in a concurrent environment, where purely top-down means a single sweep from the root to frontier along a search path. We present algorithms for internal- and external-search trees in the general framework of stratified trees. This enables us to demonstrate that many classes of balanced search trees have such updating schemes, although, for example, weight-balanced trees do not fit into this framework.Work carried out partially under NATO Grant No. RG 155.81 and the work of the third author was partially supported by Natural Sciences and Engineering Research Council of Canada Grant No. A-5692     

Solving Connected Dominating Set Faster than 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In the connected dominating set problem we are given an n-node undirected graph, and we are asked to find a minimum cardinality connected subset S of nodes such that each node not in S is adjacent to some node in S. This problem is also equivalent to finding a spanning tree with maximum number of leaves. Despite its relevance in applications, the best known exact algorithm for the problem is the trivial Ω(2 ⁿ ) algorithm that enumerates all the subsets of nodes. This is not the case for the general (unconnected) version of the problem, for which much faster algorithms are available. Such a difference is not surprising, since connectivity is a global property, and non-local problems are typically much harder to solve exactly. In this paper we break the 2 ⁿ barrier, by presenting a simple O(1.9407 ⁿ ) algorithm for the connected dominating set problem. The algorithm makes use of new domination rules, and its analysis is based on the Measure and Conquer technique. An extended abstract of this paper appeared in the proceedings of FSTTCS’06. Fedor V. Fomin was additionally supported by the Research Council of Norway.     

Concurrent processing of linearly ordered data structures onhypercube multicomputers

The paper presents a simple and effective method for the concurrent manipulation of linearly ordered data structures on hypercube systems. The method Is based on the existence of an augmented binomial search tree, called the pruned binomial tree, rooted at any arbitrary processor node of the hypercube such that; every edge of the tree corresponds to a direct link between a pair of hypercube nodes; and the tree spans any arbitrary sequence of n consecutive nodes containing the root, using a fanout of at most [log₂ n] and a depth of at most [log₂ n]+1. Search trees spanning nonoverlapping processor lists are formed using only local information, and can be used concurrently without contention problems. Thus, they can be used for performing operations such as broadcast and merge simultaneously on sets with nonuniform sizes. Extensions of the tree to k-ary n-cubes and faulty hypercubes are presented. Applications of this concurrent data structure to low- and intermediate-level image processing algorithms, and for dictionary operations involving multiple keys, are also outlined     

A Highly Concurrent Priority Queue

We present a highly concurrent priority queue algorithm based on the B-link tree, which is a B⁺-tree in which every node has a pointer to its right sibling. The algorithm is built on the concurrent B-link tree algorithms. Since the priority queue is based on highly concurrent search structure algorithms, a large number of insert operations can execute concurrently with little or no interference. We first present an algorithm that executes deletemin operations serially. We extend the serialized-deletemin algorithm to allow both parallel and concurrent deletemin operations. We discuss a decisive operation serializable algorithm that permits concurrent deletemin operations, and an algorithm in which p processors cooperate to perform p deletemin operations in O(log p) time.     

基于GSCCT的族性化学结构筛选方案

以处理族性结构信息的计算机表达式一族性结构紧缩关联表(Generic Structure Compact Connection Table，GSCCT)为基础，拟定了一套检索族性结构的筛选策略，即从GSCCT表中提取出主干环节点的预筛选方案。GSCCT表包含主干结构节点和叶结构节点，主干节点又分为环节点和非环节点两部分。叶结构节点中含有环节点时，将其提升为主干环节点。该结构匹配方法与传统的在原子节点层次上的算法不同，是在紧缩节点的层次上提取关键信息，即提取族性结构中的主要信息一环结构信息(或称指纹信息)进行预筛选，先不考虑非环节点和叶节点，以避免大量枚举。文中详细介绍了筛选思路和筛选功能的实现过程。     

ZigBee网络中孤岛节点快速处理算法研究

研究ZigBee网络孤岛节点的搜索和处理,快速减免孤岛节点提高网络资源利用率。针对节点间因配置或接口协议不统一而造成孤岛节点的出现,传统的基于广度搜索的处理方法需要逐一遍历所有节点从而搜索出孤岛节点,造成搜索效率不高、网络资源利用率较低的问题。为解决上述问题,提出了基于节点帧的孤岛节点处理方法。利用ZigBee网络树型结构的特点,只有父节点中可能存在孤岛节点,因此通过判断网络节点是否为父节点并将结果保存在节点帧中,根据节点帧找到网络中有限的父节点并从中监测出孤岛节点,避免了遍历所有网络节点而造成的搜索效率不高的问题。仿真结果表明,节点帧方法能够快速搜索出ZigBee网络中的孤岛节点并作减免处理,有效提高了网络资源的利用率。     

基于分布式内存数据库的移动对象全时态索引

针对现有移动索引仅对内存/磁盘两层结构进行优化,忽略了索引节点在内存中的缓存敏感性,提出一种基于分布式内存数据库的全时态索引结构DFTB^x树。该索引结构针对存储器Cache、内存和磁盘3层结构进行优化,根据Cache行、指令数量和TLB失配数等多个条件设计内存索引节点的大小。同时,根据磁盘数据页的大小设计历史数据迁移链节点的大小,使得Cache和内存能够一次读取索引节点和迁移链节点数据,避免多次读取数据带来的延迟。此外,构建历史数据迁移链,实现历史数据持久化,从而支持移动对象全时态索引。实验结果表明:与B^x树、B^dual树、TPR*树和STRIPES算法相比,DFTB^x树具有较高的查询和更新效率。     

An Ordered Upwind Method with Precomputed Stencil and Monotone Node Acceptance for Solving Static Convex Hamilton-Jacobi Equations

We define a δ-causal discretization of static convex Hamilton-Jacobi Partial Differential Equations (HJ PDEs) such that the solution value at a grid node is dependent only on solution values that are smaller by at least δ. We develop a Monotone Acceptance Ordered Upwind Method (MAOUM) that first determines a consistent, δ-causal stencil for each grid node and then solves the discrete equation in a single-pass through the nodes. MAOUM is suited to solving HJ PDEs efficiently on highly-nonuniform grids, since the stencil size adjusts to the level of grid refinement. MAOUM is a Dijkstra-like algorithm that computes the solution in increasing value order by using a heap to sort proposed node values. If δ>0, MAOUM can be converted to a Dial-like algorithm that sorts and accepts values using buckets of width δ. We present three hierarchical criteria for δ-causality of a node value update from a simplex of nodes in the stencil.     

Log-Based Rollback Recovery without Checkpoints of Shared Memory in Software DSM

A common approach to fault-tolerant software DSM is to take checkpoints with message logging. Our remote logging has low overhead because each node saves the coherence-related data into the memory of a remote node through a high-speed system area network. For more lightweight fault-tolerant DSM, in this paper, we mainly focused on eliminating shared memory checkpointing during failure-free execution. Each node independently takes the checkpoints of execution states and non-shared data only. When a node fails, it regenerates its pages from the remote copies in live nodes. In order to efficiently reconstruct pages, we also introduced a XOR-diffing technique. The diff logs, which have been created by XOR operations during failure-free execution, can be applicable to any version of remote copies either backward or forward for recovery. Our scheme reduces the checkpointing overhead and also alleviates the imbalance in execution times among nodes due to independent checkpointing. This research is supported by KISTEP under the National Research Laboratory program.     

Fast k-nearest neighbors search using modified principal axis search tree

The problem of k-nearest neighbors (kNN) is to find the nearest k neighbors for a query point from a given data set. Among available methods, the principal axis search tree (PAT) algorithm always has good performance on finding nearest k neighbors using the PAT structure and a node elimination criterion. In this paper, a novel kNN search algorithm is proposed. The proposed algorithm stores projection values for all data points in leaf nodes. If a leaf node in the PAT cannot be rejected by the node elimination criterion, data points in the leaf node are further checked using their pre-stored projection values to reject more impossible data points. Experimental results show that the proposed method can effectively reduce the number of distance calculations and computation time for the PAT algorithm, especially for the data set with a large dimension or for a search tree with large number of data points in a leaf node.     

An encoding scheme based on fractional number for querying and updating XML data

In order to facilitate the XML query processing, several labeling schemes have been proposed to directly determine the structural relationships between two arbitrary XML nodes without accessing the original XML documents. However, the existing XML labeling schemes have to re-label the pre-existing nodes or re-calculate the label values when a new node is inserted into the XML document during an update process. In this paper, we devise a novel encoding scheme based on the fractional number to encode the labels of the XML nodes. Moreover, we propose a mapping method to convert our proposed fractional number based encoding scheme to bit string based encoding scheme with the intention to minimize the label size and save the storage space. By applying our proposed bit string encoding scheme to the range-based labeling scheme and the prefix labeling scheme, the process of re-labeling the pre-existing nodes can be avoided when nodes are inserted as leaf nodes and sibling nodes without affecting the order of XML nodes. In addition, we propose an algorithm to control the increment of label size when new nodes are inserted frequently at a fix place of an XML tree. Experimental results show that our proposed bit string encoding scheme provides efficient support to the process of XML updating without sacrificing the query performance when it is applied to the range-based labeling schemes.     

一种实现网络入侵检测的高效算法及其实现架构

为了实现网络入侵检测系统中的精确字符串匹配,本文提出了一种基于叶子-附加和二叉搜索树的字符串匹配算法及其实现架构;首先采用叶子-追加算法来对给定的模式集进行处理,以消除模式之间的重叠。然后采用二叉搜索树算法提取叶子模式及其匹配向量来构建二叉搜索树,并根据每个节点的比较结果,通过左遍历或右遍历来实现字符串的精确匹配;为了进一步提高字符串匹配算法的内存效率,提出了级联二叉搜索树;最后給出了实现精确字符串匹配的总体架构和各个功能模块的架构;实验结果表明,本文提出的设计不仅在内存效率和吞吐量方面优于目前先进的设计技术,而且具有灵活的可扩展性。     

A comparison of iterative and defined classes of search trees

We initiate the study of iteratively defined classes of search trees, that is the classes of trees obtained by carrying out all possible iterative insertions into the initially empty tree, with respect to some given insertion scheme. For the well-known classes of search trees we compare their iteratively defined classes with their corresponding (statically) defined classes. Such a study sheds light on the properties of average trees in both classes.The work of the first author was partially supported by the Deutsche Forschungsgemeinschaft and that of the second by a Natural Sciences and Engineering Research Council of Canada Grant A-7700.     

A B-Tree index extension to enhance response time and the life cycle of flash memory

Flash memory has critical drawbacks such as long latency of its write operation and a short life cycle. In order to overcome these limitations, the number of write operations to flash memory devices needs to be minimized. The B-Tree index structure, which is a popular hard disk based index structure, requires an excessive number of write operations when updating it to flash memory. To address this, it was proposed that another layer that emulates a B-Tree be placed between the flash memory and B-Tree indexes. This approach succeeded in reducing the write operation count, but it greatly increased search time and main memory usage. This paper proposes a B-Tree index extension that reduces both the write count and search time with limited main memory usage. First, we designed a buffer that accumulates update requests per leaf node and then simultaneously processes the update requests of the leaf node carrying the largest number of requests. Second, a type of header information was written on each leaf node. Finally, we made the index automatically control each leaf node size. Through experiments, the proposed index structure resulted in a significantly lower write count and a greatly decreased search time with less main memory usage, than placing a layer that emulates a B-Tree.     

It is decidable whether a monadic thue system is canonical over a regular set

A restricted confluence problem is investigated for string-rewriting systems (Thue systems). It is shown that it is decidable whether a monadic Thue system is canonical over a regular set; i.e., there is an algorithm to determine whether every string in a regular set has a unique normal form modulo a monadic Thue system.This work was supported by the Natural Sciences and Engineering Research Council of Canada. It was done while the author was visiting the Department of Computer Science, University of Calgary, Alberta, Canada T2N 1N4.