An Oblivious Priority Queue (OPQ) is a cryptographic primitive that enables a client to outsource its data to a dishonest server, and also to securely manage the data according to a priority queue algorithm. Though the first OPQ achieves perfect security, it supports only two operations; Inserting an element and extracting the top-priority element, which are the minimal requirement for a priority queue. In addition, this OPQ allows an adversary to observe operations in progress, which leaks the exact number of elements in the data structure. On the other hand, there are many subsequent works for OPQs that implement additional operations of a priority queue, hide the running operations, and improve efficiency. Though the recent works realize optimal efficiency, all of them achieve only statistical or computational security. Aiming to reconcile perfect security of the first OPQ with all functions (including the operation hiding) supported by recent OPQs, we construct a novel perfectly secure OPQ that can simulate the following operations while hiding which one is in progress; Inserting an element, extracting the top-priority one, deleting an element, and modifying the priority of an element. The efficiency of our scheme is O(log2 N), which is larger than that of the best known statistically secure OPQ but is the same as the known perfectly secure scheme.

Buffer overflow is one of the main approaches to get control of vulnerable programs. This paper presents a protection technique called BFWindow for performance and resource sensitive embedded systems. By coloring data structure in memory with single associate property bit to each byte and extending the target memory block to a BFWindow(2), it validates each memory write by speculatively checking consistency of data properties within the extended buffer window. Property bits are generated by compiler statically and checked by hardware at runtime. They are transparent to users. Experimental results show that the proposed mechanism is effective to prevent sequential memory writes from crossing buffer boundaries which is the common scenario of buffer overflow exploitations. The performance overhead for practical protection mode across embedded system benchmarks is under 1%.

Recently, due to the development of design and manufacturing technologies for VLSI systems, an embedded system becomes more and more complex. Consequently, not only the performance of chips, but also the flexibility and dynamic adaptation of the implemented systems are required. To achieve these requirements, a partially reconfigurable device is promising. In this paper, we propose an efficient data structure to manage the reconfigurable units. And then, on the assumption that each task utilizes the rectangle shaped resources, a very simple MER enumeration algorithm based on this data structure is proposed. By utilizing the result of MER enumeration, the free space on the reconfigurable device can be used sufficiently. We analyze the complexity of the proposed algorithm and confirm its efficiency by experiments.

An Invertible Bloom Lookup Tables (IBLT) is a data structure which supports insertion, deletion, retrieval and listing operations for the key-value pair. An IBLT can be used to realize efficient set reconciliation for database synchronization. The most notable feature of the IBLT is the complete listing operation of key-value pairs based on the algorithm similar to the peeling algorithm for low-density parity check (LDPC) codes. In this paper, we will present a stopping set (SS) analysis for the IBLT that reveals finite length behaviors of the listing failure probability. The key of the analysis is enumeration of the number of stopping matrices of given size. We derived a novel recursive formula useful for computationally efficient enumeration. An upper bound on the listing failure probability based on the union bound accurately captures the error floor behaviors.

Discrete structures are foundational material for computer science and mathematics, which are related to set theory, symbolic logic, inductive proof, graph theory, combinatorics, probability theory, etc. Many problems solved by computers can be decomposed into discrete structures using simple primitive algebraic operations. It is very important to represent discrete structures compactly and to execute efficiently tasks such as equivalency/validity checking, analysis of models, and optimization. Recently, BDDs (Binary Decision Diagrams) and ZDDs (Zero-suppressed BDDs) have attracted a great deal of attention, because they efficiently represent and manipulate large-scale combinational logic data, which are the basic discrete structures in various fields of application. Although a quarter of a century has passed since Bryant's first idea, there are still a lot of interesting and exciting research topics related to BDD and ZDD. BDD/ZDD is based on in-memory data processing techniques, and it enjoys the advantage of using random access memory. Recent commodity PCs are equipped with gigabytes of main memory, and we can now solve large-scale problems which used to be impossible due to memory shortage. Thus, especially since 2000, the scope of BDD/ZDD methods has increased. This survey paper describes the history of, and recent research activity pertaining to, techniques related to BDD and ZDD.

The Towers of Hanoi problem is a classical problem in puzzles, games, mathematics, data structures, and algorithms. In this letter, a least memory used algorithm is proposed by combining the source array and target array for comparing the sizes of disk and labeling the disks in the towers of Hanoi problem. As a result, the proposed algorithm reduces the space needed from 2n+2 to n+5, where n represents the disks number.

In terrain visualization, the quadtree is the most frequently used data structure for progressive mesh generation. The quadtree provides an efficient level of detail selection and view frustum culling. However, most applications using quadtrees are performed on the CPU, because the pointer and recursive operation in hierarchical data structure cannot be manipulated in a programmable rendering pipeline. We present a quadtree-based terrain rendering method for GPU (Graphics Processing Unit) execution that uses vertex splitting and triangle splitting. Vertex splitting supports a level of detail selection, and triangle splitting is used for crack removal. This method offers higher performance than previous CPU-based quadtree methods, without loss of image quality. We can then use the CPU for other computations while rendering the terrain using only the GPU.

In this paper, an idea for improvement of suffix array construction using lazy evaluation is presented. Evaluation of the suffix array is based on the searching queries; only the necessary part of the suffix array is built when unevaluated part of the suffix array is referred during the searching process. This is less time consuming than constructing complete suffix array. We propose lazy evaluation of Schürmann-Stoye algorithm. Experimental results show that lazy Schürmann-Stoye algorithm runs faster than Maniscalco, which is well-recognized as the fastest suffix sorting algorithm, under the constraint of small LCP (longest common prefix) and a limited number of searching queries.

Decision diagrams are often used for efficient representation of discrete functions in terms of needed storage space and processing time. In this paper, we propose an XML (Extensible Markup Language) based standard for the structural description of various types of decision diagrams. The proposed standard describes elements of the structure common to various types of decision diagrams. It also provides facilities for storing additional information, specific to particular types of decision diagrams. Properties of XML enable us to define a standard that is flexible enough to be applicable to various existing types of decision diagrams as well as new types that could be defined in the future. The existence of such a standard permits efficient storage and exchange of data in decision diagram form between various software systems. In this way, it supports benchmarking, testing and verification of various procedures using decision diagrams as a basic data structure.

Lin-Kernighan (LK) is the most powerful local search for the Traveling Salesman Problem (TSP). The choice of data structure for tour representation plays a vital role in LK's performance. Binary trees are asymptotically the best tour representation but they perform empirically best only for TSPs with one million or more cities due to a large overhead. Arrays and two-level trees are used for smaller TSPs. This paper proposes a new three-level tree data structure for tour representation. Although this structure is asymptotically not better than the binary tree structure, it performs empirically better than the conventional structures for TSPs having from a thousand to three million cities.

The construction of photo-realistic 3D scenes from video data is an active and competitive area of research in the fields of computer vision, image processing and computer graphics. In this paper we address our recent work in this area. Unlike most methods of 3D scene construction, we consider the generation of virtual environments from video sequence with a video-cam's forward motion. Each frame is decomposed into sub-images, which are registered correspondingly using the Levenberg-Marquardt iterative algorithm to estimate motion parameters. The registered sub-images are correspondingly pasted together to form a pseudo-3D space. By controlling the position and direction, the virtual camera can walk through this virtual space to generate novel 2D views to acquire an immersive impression. Even if the virtual camera goes deep into this virtual environment, it can still obtain a novel view while maintaining relatively high resolution.

In many applications, information retrieval is a very important research field. In several key strategies, the binary trie is famous as a fast access method able to retrieve keys in order. Especially, a Patricia trie gives the shallowest trie by eliminating all nodes which have only one arc, and it requires the smallest storage among the other trie structures. If trie structures are implemented, however, the greater the number of the registered keys, the larger storage is required. In order to solve this problem, Jonge et al. proposed a method to change the normal binary trie into a compact bit stream. This paper proposes the improved trie representation for the Patricia trie, as well as the methods for searching and inserting the key on it. The theoretical and experimental results, using 50,000 Japanese nouns and 50,000 English words, show that this method generates 25-39 percent shorter bit streams than the traditional method. This method, thus, enables us to provide more compact storage and faster access than the traditional method.

In high performance compilers to process pointer-handling programs, precise pointer alias analysis is useful for the compilers to generate efficient object code. It is well known that most compiler techniques such as data flow analysis, dependence analysis, side effect analysis and optimizations are related to the alias problem. However, without data structure information, there is a limit on the precision of the alias analysis. Even though the automatic data structure detection problem is complex, when pointer manipulation satisfies some restrictions, some data structures can be detected automatically by compilers with some knowledge of aliases. In this paper, we propose an automatic data structure detection method for Pascal and Fortran 90. Linear list, tree and dag data structures are detected. Detected data structure information can be used not only for raising the precision of alias analysis but also for some optimizing techniques for pointer handling programs directly.

The concept of a basis matrix is introduced to investigate the trade-off between complexity and storage for multiplication in a finite field. The effect on the storage requirements of using polynomial and normal bases for element representation is also considered.

In logic programming or functional programming languages, data objects, such as terms and lists, are immutable. In a basic implementation of such language, updating one element of an aggregate (contiguous data structure, such as an array) involves making a new copy of the whole aggregate. However, such copying can be expensive, and can be avoided by using a destructive update. We introduce the concept of a wrapper which enables destructive operation on an immutable object. Based on this concept, we designed the reversible functor as a solution to the aggregate update problem. We implemented the reversible functor in the existing SB-Prolog system and carried out several benchmarks. These benchmark results show its effectiveness. When using a large functor and updating it many times, the performance is improved dramatically by implementing the reversible functor. It incurs some overhead at runtime, but the amount is small and acceptable.

Exploring enormous state graphs represented implicitly by ordered binary decision diagrams (OBDDs) is one of the most successful applications of OBDDs. However, our worst-case analysis of implicit graph representations by OBDDs shows that there are cases where OBDD representations are not optimal and require more space than adjacency lists. As an improvement, we propose a new type of BDDs, called Patricia BDDs, which are capable of implicit representation of graphs while their worst-case sizes are kept equal or less than adjacency lists and OBDDs.

This paper proposes a functional video handling technique based on structured video. The video handling architecture, which includes a video data structure, file management structure, and visual interface structure, is introduced as the core concept of this technique. One of the key features of this architecture is that the newly proposed video indexing method is performed automatically based on image processing. The video data structure, which plays an important role in the architecture, has two kinds of data structures: content and node. The central idea behind these structures is to separate the video contents from the processing operations and to create links between them. Video indexes work as a backend mechanism in structuring video content. A prototype video handling system called the MediaBENCH, a hypermedia basic environment for computer and human interactions, which demonstrates the actual implementation of the proposed concept and technique, is described. Basic functions such as browsing and editing, which are achieved based on the architecture, exhibit the advantages of structured video handling. The concept and the methods proposed in this paper assure various video-computer applications, which will play major roles in the multimedia field.

Two new algorithms for performing modular exponentiation are suggested. Nonstandard number systems are used. The first algorithm is based on the representing the exponent as a sum of generalized Fibonacci numbers. This representation is known as Zeckendorf representation. When precomputing is allowed the resulting algorithm is more efficient than the classical binary algorithm, but requires more memory. The second algorithm is based on a new number system, which is called hybrid binary-ternary number system (HBTNS). The properties of the HBTNS are investigated. With or without precomputing the resulting algorithm for modular exponentiation is superior to the classical binary algorithm. A conjecture is made that if more bases are used asymptotically optimal algorithm can be obtained. Comparisons are made and directions for future research are given.

Data of system parameters of real systems have some uncertainty and they should be given by sets (or intervals) rather than fixed values. To analyze and design systems contaning such uncertain parameters, it is required to represent and treat uncertainty in data of parameters, and to compute value sets of characteristic polynomials and transfer functions. Interval arithmetic is one of the most powerful tools to perform such subjects. In this paper, Polygon Interval Arithmetic (PIA) on the set of polygons in the complex plane is considered, and the data structure and algorithms to execute PIA efficiently is proposed. Moreover, practical examples are shown to demonstrate how PIA is useful to compute the evaluation of value sets.

The planar point location problem is one of the most fundamental problems in computational geometry and stated as follows： Given a straight line planar graph (subdivision) with n vertices and an arbitary query point Q, determine the region containing Q. Many algorithms have been proposed, and some of them are known to be theoretically optimal (O(log n) search time, O(n) space and O(n log n) preprocessing time). In this paper, we implement several representative algorithms in C, and investigate their practical efficiencies by computational experiments on Voronoi diagrams with 210 - 217 vertices.