Search
Join ACM

Kurt Maly

Research and Advances May 1 2001

Buckets: Smart Objects For Digital Libraries

Information content is more important than the systems used for its storage and retrieval. While this seems obvious enough, digital library discussions often mire on the merits of specific databases, search engines, and other implementation details. This is because digital library services (for example, searching, browsing, document access) are often vertically integrated with the content […]
Computing Applications

Advertisement

Author Archives

Research and Advances Apr 1 1995

Wide Area Technical Report Service: technical reports online

Wide Area Technical Report Service (WATERS) is a distributed database of computer science technical reports. Contributors are departments of computer science that make their reports, stored locally at their sites, available through World-Wide Web and a WAIS search engine. By using WATERS, anyone with access to the Internet can, using a client such as Mosaic browse, search, obtain abstract and bibliographic information, and retrieve technical reports online. The latter assumes that the user's WWW client is set up to launch viewers such as ghostview for Postscript files, xdvi for dvi files, and xtiff for TIFF page images.
Artificial Intelligence and Machine Learning
Research and Advances Oct 1 1978

A comparison of heaps and the TL structure for the simulation event set

Following publication of our paper [2], questions arose with respect to the superiority of the TL structure over heaps,1 particularly in the face of the remarks of Gonnet [3], concerning the use of heaps for the physical realization of the simulation event set. Gonnet's communication was in response to the Vaucher and Duval paper [5], and suggested the heap to be a more efficient structure than any proposed in [5]. As regards a comparison of heaps and the TL structure we can make the following remarks:
Artificial Intelligence and Machine Learning
Research and Advances Sep 1 1978

A note on virtual memory indexes

In [4] Maruyama and Smith analyzed design alternatives for virtual memory indexes. The indexes investigated were those modeled on the structure of VSAM [5] which are closely related to B-trees [1]. Maruyama and Smith presented alternatives for search strategies, page format, and whether or not to compress keys. They made a comparative analysis based on the average cost of processing the index for retrieval of a key with its associated data pointer (or a sequence of keys and data pointers). The analysis showed that the optimal solution depends on machine and file characteristics and they provided formulas for selecting the best alternative. In this brief note1 we propose that another alternative for the page format be considered. The basic idea is to replace the sequential representation within a page by a linked representation. The main advantage of this method is realized in the construction (and maintenance) phase of the index. Although this phase is difficult to analyze quantitatively—as alluded to in [4]—we provide data to substantiate our claim of a net saving in construction cost without any corresponding loss in the average retrieval cost. In the ensuing discussion we assume that the reader is familiar both with B-trees and the paper of Maruyama and Smith [4].
Computing Applications
Research and Advances Aug 1 1977

An efficient data structure for the simulation event set

Recently algorithms have been presented for the realization of event scheduling routines suitable for general purpose discrete event simulation systems. Several exhibited a performance superior to that of commonly used simple linked list algorithms. In this paper a new event scheduling algorithm is presented which improves on two aspects of the best of the previously published algorithms. First, the new algorithm's performance is quite insensitive to skewed distributions, and second, its worst-case complexity is O(√n), where n is the number of events in the set. Furthermore, tests conducted to estimate the average complexity showed it to be nearly independent of n.
Research and Advances Jul 1 1976

Compressed tries

This paper presents a new data structure, called a compressed trie or C-trie, to be used in information retrieval systems. It has the same underlying m-ary tree structure as a trie, where m is a parameter of the trie, but whereas the fields of the nodes in a trie have to be large enough to hold a key or at least a pointer, the fields in a C-trie are only one bit long. In the analysis part of the paper it will be shown that for a collection of n keys the retrieval time, measured in terms of bit inspections of one key, is of the order logmn and the storage requirement of the order n·(m + log2n) bits. This improvement in storage requirements and retrieval time is achieved at the cost of decreasing the flexibility of the structure, and therefore updating costs are increased. First the C-trie is analyzed as a data structure, and then several methods of its use for relatively static databases are discussed.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved