This paper presents a pivot-set generation algorithm for accelerating exact similarity search in a large-scale data set. To deal with the large-scale data set, it is important to efficiently construct a search index offline as well as to perform fast exact similarity search online. Our proposed algorithm efficiently generates competent pivots with two novel techniques: hierarchical data partitioning and fast pivot optimization techniques. To make effective use of a small number of pivots, the former recursively partitions a data set into two subsets with the same size depending on the rank order from each of two assigned pivots, resulting in a complete binary tree. The latter calculates a defined objective function for pivot optimization with a low computational cost by skillfully operating data objects mapped into a pivot space. Since the generated pivots provide the tight lower bounds on distances between a query object and the data objects, an exact similarity search algorithm effectively avoids unnecessary distance calculations. We demonstrate that the search algorithm using the pivots generated by the proposed algorithm reduces distance calculations with an extremely high rate regarding a range query problem for real large-scale image data sets.

A source code for N symbols can be represented by a codeword length sequence (1,2,,N). A binary code is compact if it satisfies = 1. Also we may assume that 1 1 2 N. In this paper, we show that these two constraints can be replaced by max i for 1 i N - 1. Using the latter characterization, we construct a tree T N representing all binary compact codes. In fact every leaf of T N represents a compact code and vice versa. This technique can also be used to generate all compact codes for a given (1,2,,k), k < N.

It is a fundamental problem to construct a virtual path layout minimizing the hop number as a function of the congestion for a communication network. It is known that we can construct a virtual path layout with asymptotically optimal hop number for a mesh of trees network, butterfly network, cube-connected-cycles network, de Bruijn network, shuffle-exchange network, and complete binary tree network. The paper shows a virtual path layout with minimum hop number for a complete binary tree network. A generalization to complete k-ary tree networks is also mentioned.

We consider the problem of embedding complete binary trees into 2-dimensional tori with minimum (edge) congestion. It is known that for a positive integer n, a 2n-1-vertex complete binary tree can be embedded in a (2n/2+1)(2n/2+1)-grid and a 2n/2 2n/2-grid with congestion 1 and 2, respectively. However, it is not known if 2n-1-vertex complete binary tree is embeddable in a 2n/2 2n/2-grid with unit congestion. In this paper, we show that a positive answer can be obtained by adding wrap-around edges to grids, i.e., a 2n-1-vertex complete binary tree can be embedded with unit congestion in a 2n/2 2n/2-torus. The embedding proposed here achieves the minimum congestion and an almost minimum size of a torus (up to the constant term of 1). In particular, the embedding is optimal for the problem of embedding a 2n-1-vertex complete binary tree with an even integer n into a square torus with unit congestion.