Application of principal component analysis to multi-disk concurrent accessing

This paper is concerned with the allocation of multi-attribute records on several disks so as to achieve high degree of concurrency of disk access when responding to partial match queries.An algorithm to distribute a set of multi-attribute records onto different disks is presented. Since our allocation method will use the principal component analysis, this concept is first introduced. We then use it to generate a set of real numbers which are the projections on the first principal component direction and can be viewed as hashing addresses.Then we propose an algorithm based upon these hashing addresses to allocate multi-attribute records onto different disks. Some experimental results show that our method can indeed be used to solve the multi-disk data allocation problem for concurrent accessing.     

Optimality criteria of the disk modulo allocation method for Cartesian product files

Cartesian product (CP) files have been shown to be very effective for partial match retrieval. Further the Disk Modulo (DM) allocation method has been shown to be a simple and effective method for allocating CP files onto multiple independently accessible disks to further facilitate partial match retrieval. In this paper, a useful criterion for the DM method to be the best allocation method for a given CP file is presented. The presented criterion is much more general than that suggested previously which makes the DM allocation method much more applicable for real applications.     

A note on parallel depth first search

The subject of this note is the parallel algorithm for depth first searching of a directed acyclic graph by Ghosh and Bhattacharjee. It is pointed out that their algorithm does not always work. A counter example is given. This paper also states the necessary and sufficient condition for the algorithm to fail, or to work correctly.     

A heuristic file reorganization algorithm based on record clustering

The problem of file organization which we consider involves altering the placement of records on pages of a secondary storage device. In addition, we want this reorganization to be done in-place, i.e., using the file's original storage space for the newly reorganized file. The motivation for such a physical change is to improve the database system's performance. For example, by placing frequently and jointly accessed records on the same page or pages, we can try to minimize the number of page accesses made in answering a set of queeries. The optimal assignment (or reassignment) of records to clusters is exactly what record clustering algorithms attempt to do. However, record clustering algorithms usually do not solve the entire problem, i.e., they do not specify how to efficiently reorganize the file to reflect the clustering assignment which they determine. Our algorithm is a companion to general record clustering algorithms since it actually transforms the file. The problem of optimal file reorganization isNP-hard. Consequently, our reorganization algorithm is based on heuristics. The algorithm's time and space requirements are reasonable and its solution is near optimal. In addition, the reorganization problem which we consider in this paper is similar to the problem of join processing when indexes are used.The research of this author was partially supported by the National Science Foundation under grant IST-8696157.     

Optimal dynamic multi-attribute hashing for range queries

This paper examines a partial match retrieval scheme which supports range queries for highly dynamic databases. The scheme relies on order preserving multi-attribute hashing. In general, designing optimal indexes is NP-hard. Greedy algorithms used to determine the optimal indexes for simple partial match queries are not directly applicable because there are a larger number of queries to consider in determining the optimal indexes. In this paper we present heuristic algorithms which provide near-optimal solutions. The optimisation scheme we propose can be used to design other dynamic file structures such as the grid file, BANG file and multilevel grid file to further enhance their retrieval performance taking into consideration the query distribution.     

Minimal perfect hashing in polynomial time

We present a universally applicable algorithm for generating minimal perfect hashing functions. The method has (worst case) polynomial time complexity in units of bit operations. An adjunct algorithm for reducing parameter magnitudes in the generated hash functions is given. This probabilistic method makes hash function parameter magnitudes independent of argument (input key) magnitudes.     

Performance evaluation of shared and separate inverted files

In this paper, two different structures for inverted files are analyzed and compared, when the relational join operation is taken into account. The structures are called shared and separate inverted files. The results are given of some experiments which show that the shared inverted organization is always advantageous when the inverted files are not sorted and is almost always advantageous when the files are sorted.     

AVLSI partition algorithm

A VLSI sorter of sizeO(n) can sortn elements in linear time when the input and output time are taken into account. If the input contains more thann elements, some prepocessing has to be performed. A VLSI partition algorithm that provides a solution to this problem is presented. The algorithm partitions the input data into two smaller parts as the quicksort algorithm does. That is, the elements of the first part will be smaller than the elements of the second part. The partition is repeated until the parts are small enough to fit in the sorter. It is shown that the average number of times each element must go through the partitioner isO(logk) for a data file of sizekn wheren is the size of the sorter. In the worst case where the partitioner fails to divide the input evenly, the elements must goO(k) times through the partitioner like in the quicksort algorithm. The partitioner can also be used, with simple modifications, as a sorter, a stack, a queue, or as a priority queue. Other advantages of the VLSI algorithm are also discussed.     

Dynamic partition trees

In this paper we study dynamic variants of conjugation trees and related structures that have recently been introduced for performing various types of queries on sets of points and line segments, like half-planar range searching, shooting, intersection queries, etc. For most of these types of queries dynamic structures are obtained with an amortized update time ofO(log² n) (or less) with only minor increases in query times. As an application of the method we obtain an output-sensitive method for hidden surface removal in a set ofn triangles that runs in timeO(nlogn+n ^· k ) where=log₂((1+5)/2) 0.695 andk is the size of the visibility map obtained.Research of the second author was partially supported by the ESPRIT II Basic Research Actions Program of the EC, under contract No. 3075 (project ALCOM).     

Single access hashing with overflow separators for dynamic files

The dynamic external hashing proposed in this paper allocates records according to the spiral storage technique. Separators derived from the signature technique are used for distinguishing primary from overflow records and for subdividing overflow chains into segments allocated into the primary file. Single access retrieval is obtained by means of a main memory index with an entry per bucket and containing separators and pointers. While this method uses a larger index than other recent proposals, it is much more convenient regarding load factor and insertion cost. Furthermore, file expansion is directed by various control parameters, thus allowing the user to choose the most suitable policy for his application.     

Storing line segments in partition trees

We design two variants of partition trees, calledsegment partition trees andinterval partition trees, that can be used for storing arbitrarily oriented line segments in the plane in an efficient way. The raw structures useO(n logn) andO(n) storage, respectively, and their construction time isO(n logn). In our applications we augment these structures by certain (simple) auxiliary structures, which may increase the storage and preprocessing time by a polylogarithmic factor. It is shown how to use these structures for solving line segment intersection queries, triangle stabbing queries and ray shooting queries in reasonably efficient ways. If we use the conjugation tree as the underlying partition tree, the query time for all problems isO(n ), where=log₂(1+5)–10.695. The techniques are fairly simple and easy to understand.Research of the first author was partially supported by the ESPRIT II Basic Research Action of the EC under contract No. 3075 (Project ALCOM).Work by the third author has been supported in part by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the Digital Equipment Corporation, the IBM Corporation, the U.S.-Israeli Binational Science Foundation, the NCRD — the Israeli National Council for Research and Development, and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.     

Searchability in merging and implicit data structures

We introduce the notion ofsearchability as a property of an in place merging algorithm. We show that a pair of sorted arrays can be merged in place in linear time, so that a search can be performed in logarithmic time at any point during the merging process. We apply this method to devise an implicit data structure which can support searches inO(log² n) time in the worst case, andO(logn) on the average, and insertions inO(logn) time, in the worst case.This research was partly supported by NSERC under grant A8237 and presented in preliminary form at the 10th International Colloquium on Automata, Languages and Programming.On leave from the University of Chile.     

Stable in situ sorting and minimum data movement

In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg^(k+1) n+kn) comparisons (lg^(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.Research supported by Natural Sciences and Engineering Research Council of Canada grant No.A-8237 and the Information Technology Research Centre of Ontario.Supported in part by a Research Initiation Grant from the Virginia Engineering Foundation.     

Signature files: An integrated access method for text and attributes,suitable for optical disk storage

We design and analyze integrated ways of applying the signature file approach for text and attributes simultaneously. In traditional signature file methods, the records are stored sequentially in the main file; for every record, a hash-coded abstraction of it (record signature) is created and stored in the signature file (usually, sequentially). To resolve a query, the signature file is scanned; the signatures retrieved correspond to all the qualifying records, plus some false drops.Here, we extend some signature file methods, namely superimposed coding and disjoint coding, to handle text and attributes. We develop a mathematical model and derive formulas for the optimal choice of parameters. The proposed methods achieve significant performance improvements, because they can take advantage of the skewed distribution of the queries. Depending on the query frequencies, the false drop probability can be reduced 40–45 times ( 97% savings), for the same overhead.Also with the University of Maryland Institute for Advanced Computer Studies (U.M.I.A.C.S.). This research was sponsored partially by the National Science Foundation under the grant DCR-86-16833.     

Multi-attribute hashing with multiple file copies for high performance partial-match retrieval

The average cost for answering partial-match queries can be dramatically reduced by storing multiple copies of the data, each with a different clustering. We analyse the cost benefits (in terms of page accesses) of this arrangement and present heuristic algorithms for determining a near-minimal-cost file organisation for a given probability distribution of queries. We also show how constraining the range of values for specific attributes affects the usefulness of maintaining multiple copies.     

An efficient implicit data structure for relation testing and searching in partially ordered sets

In this paper, we introduce an implicit data structure which represents a forest-structured partial order to efficiently perform, with respect to time and space, the following operations: 1) testing the relation among two elements (checking whether the two elements are related) and 2) given an elementu, searching for its father. The first operation can be performed in constant time, while the second one requires polylog time (logarithmic in the case of bounded degree). The data structure represents the order relation by referring only to internal nodes of the forest, thus achieving in many cases a significant saving in space occupation. Finally, the algorithm is shown to be optimal in a restricted computation model by deriving a lower bound on the space complexity within such a model.Work partially performed in the framework of Esprit BRA project 3075 Algorithms and Complexity and of Italian MURST 40% project Algoritmi e Strutture di Calcolo and partially supported by the National Research Council (CNR) Project Sistemi Informatici e Calcolo Parallelo.     

A linear time algorithm for the maximum matching problem on cographs

In this paper, we develop a sequential algorithm for the maximum matching problem on cographs. The input is a parse tree of some cograph. The time complexity of our algorithm is linear.Supported by National Science Council of Taiwan, R.O.C. under Grant NSC81-0415-E-005-03.     

An optimal time algorithm for finding a maximum weight independent set in a tree

The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.     

Optimal algorithms for total exchange without buffering on the hypercube

Two methods are given for constructing total exchange algorithms for hypercubic processor networks. This is done by means of bit sequences with special properties. The algorithms are optimal with respect to a given time model, need no intermediate message buffering and are local in the sense that every processor executes basically the same program.     

A note on the largest empty rectangle problem

We consider the following problem: given a rectangle containingn points, find the largest perimeter subrectangle whose sides are parallel to those of the original rectangle, whose aspect ratio is below a given bound, and which does not contain any of the given points. Chazelle, Drysdale and Lee have studied a variant of this problem with areas as the quantity to be maximized. They gave anO(nlog³ n) algorithm for that problem. We adopt a similar divide-and-conquer approach and are able to use the simpler properties of the perimeter measure to obtain anO(nlog² n) algorithm for our problem.The work of the first author was supported by the Academy of Finland and that of the second by the Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.