Search

The article discusses the correctness of nonblocking data structures. Topics covered include language and architecture memory models as considerations when programming nonblocking data structures, the unaligned word-sized memory accesses as a good example of a problem with nonblocking data-structure programming, and how reordering can be conducted at various levels for performance reasons. Also mentioned are the considerations of throughput and scalability tied to atomic accesses and memory barriers, the use of counterexamples to illustrate problems in nonblocking data-structure design and implementation, and execution-based model checking.

In the article, the author discusses the basic steps and processes in reading and writing data to and from a portable document format. Other topics include how to use a PDF Library in the process, PDFLibrary source codes and samples, iText 7 PDF libraries, iText7 NuGet package, as well as how to incorporate PDF functionality into an application.

Extendible hashing is a dynamic data structure which accommodates expansion and contraction of any stored data efficiently. In this article, an algorithm has been developed for managing concurrent operations on extendible hashing by achieving optimal memory utilization by supporting directory expansion and contraction, page split, and merge. The results of this study have been encouraging in the sense that it seems to provide a higher degree of concurrency compared to other algorithms on an extendible hash file. [ABSTRACT FROM AUTHOR]

The article discusses problems associated with data compression. Four methods of decoding prefix codes in limited space have been presented. The methods are partitioned into two categories based on the data structuring strategy employed. Tables comparing time and space requirements of the four methods expose the relevant parameters. The methods authors' describe define only the decoding phase of a data compression system. The choice of a fixed encoding dictionary is the most critical factor in determining the performance of a system based on their methods. While the representation of the code contributes to the compression ratio attained, most of the compression is achieved by selecting a dictionary that is well-suited to the data being compressed. With an advantageous choice of dictionary, the authors' methods can attain compression performance comparable to state-of-the-art techniques such as the Unix utility compress. Defining a dictionary that guarantees good compression is, however, a difficult task.

Several methods are presented for adaptive, invertible data compression in the style of Lempel's and Ziv's first textual substitution proposal. For the first two methods, the article describes modifications of McCreight's suffix tree data structure that support cyclic maintenance of a window on the most recent source characters. A percolating update is used to keep node positions within the window, and the updating process is shown to have constant amortized cost. Other methods explore the tradeoffs between compression time, expansion time, data structure size, and amount of compression achieved. The article includes a graph-theoretic analysis of the compression penalty incurred by our codeword selection policy in comparison with an optimal policy, and it includes empirical studies of the performance of various adaptive compressors from the literature. [ABSTRACT FROM AUTHOR]

Presents information about literate programming. Use of program codes segments in text; Benefits of literate programs; Features of a system for literate programming; Discussion on programming style and data structures.

A number of data structures for representing images by quadtrees without pointers are discussed. The image is treated as a collection of leaf nodes. Each leaf node is represented by use of a locational code corresponding to a sequence of directional codes that locate the leaf along a path from the root of the tree. Somewhat related is the concept of a forest which is a representation that consists of a collection of maximal blocks. It is reviewed and refined to enable the representation of a quadtree as a sequence of approximations. In essence, all BLACK and WHITE nodes are said to be of type GB and GW, respectively. GRAY nodes are of type GB if at least two of their sons are of type GB; otherwise, they are of type GW. Sequences of approximations using various combinations of locational codes of GB and GW nodes are proposed and shown to be superior to approximation methods based on truncation of nodes below a certain level m the tree. These approximations have two important properties. First, they are progressive in the sense that as more of the image is transmitted, the receiving device can construct a better approximation (contrast with facsimile methods which transmit the image one line at a time). Second, they are proved to lead to compression in the sense that they never require more than MIN(B. W) nodes where B and W correspond to the number of BLACK and WHITE nodes in the original quadtree. Algorithms are given for constructing the approximation sequences as well as decoding them to rebuild the original quadtree. [ABSTRACT FROM AUTHOR]

A perfect hash function PHF is an injection F from a set W of M objects into the set consisting of the first N nonnegative integers where N >= M. If N = M, then F is a minimal perfect hash function, MPHF. PHFs are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a programming language or commonly employed words in a natural language. The mincycle algorithm for finding PHFs executes with an expected time complexity that is polynomial in M and has been used successfully on sets of cardinality up to 512. Given three pseudorandom functions h0, h1, and h2, the mincycle algorithm searches for a function g such that F(w) = (h0(w) + g ∘ h2(w)) mod N is a PHF. [ABSTRACT FROM AUTHOR]

Two algorithms are developed for the optimal organization of B-trees (and variations) with variable-length items. The first algorithm solves a problem posed by McCreight, that of finding a pagination of n items that minimizes the sum of key lengths promoted to the next higher level of the tree. The algorithm requires O(n log n) time and O(n) space. The second algorithm constructs the minimum depth tree in O(n³ log n) time from the n items. Both methods rely on dynamic programming arguments and can be interpreted as shortest-path problems. Practical approaches for implementing the algorithms are discussed. [ABSTRACT FROM AUTHOR]

Many methods for resolving collisions in hashing techniques have been proposed. They are classified into two main categories: open addressing and chaining. In this paper, other methods are presented that are intermediate between the two categories. The basic idea of our methods is the use of one or more predictors reserved per cell instead of a link field as in the chaining method. The predictors are used to maintain loose synonym chains. After describing the methods, the efficiencies are estimated theoretically and verified experimentally. In comparison with the chaining method, we prove that our methods significantly reduce the average number of probes necessary to retrieve a key without expending extra space. [ABSTRACT FROM AUTHOR]

A framework for describing specific algorithms and their data structures is introduced so that designs can be presented in a uniform style that is suitable for discovering new designs as well as documenting known ones. Data objects are described in terms of a formal grammar, and most data manipulation is characterized as composition of a few simple algorithms. Descriptions for several standard algorithms are included to illustrate the process, and a few newly designed structures are introduced. Such an approach is expected to be extremely useful in the construction of software libraries. [ABSTRACT FROM AUTHOR]

A technique is proposed for keeping a graphlike data structure near its optimum form; such global optimization is obtained as the cumulative result of simple local operations. Each operation involves only a small number of neighboring vertices and preserves the consistency of the data structure. The technique is demonstrated by means of two examples: the recording of equivalence classes and the construction of a binary search tree. In the examples the optimizing operations are executed "on the fly" while the data structure is being accessed. Hence optimization of the data structure is obtained as a side effect of its normal use. The derived solutions are comparable in efficiency to known solutions, but they allow concurrent access to the data structure. [ABSTRACT FROM AUTHOR]

The performance of most small computer systems is determined, to a large extent, by the characteristics of their mass storage devices. Data compression can expand the storage capacity of such devices and also slightly increase their speed. Here, a summary of one method of data compression using Huffman variable length coding is presented, along with statistics of effectiveness for various file types and practical techniques for integrating such methods into a small computer system. [ABSTRACT FROM AUTHOR]

A method is presented for building minimal perfect hash functions, i.e., functions which allow single probe retrieval from minimally sized tables of identifier sets. A proof of existence for minimal perfect hash functions of a special type (reciprocal type) is given. Two algorithms for determining hash functions of reciprocal type are presented and their practical limitations are discussed. Further some application results are given and compared with those of earlier approaches for perfect hashing. [ABSTRACT FROM AUTHOR]

Presents letters to the editor referencing articles and topics published in earlier issues of the journal "Communications of the ACM." Focuses on issues relating updating of master files; Information on algorithms used in updating process; Introduction on structured programming in everyday activities; Alternatives used in processing the different file records.

The steady increase in the power and complexity of modern computer systems has encouraged the implementation of automatic file migration systems which move files dynamically between mass storage devices and disk in response to user reference patterns. Using information describing 13 months of user disk data set file references, we develop and evaluate (replacement) algorithms for the selection of files to be moved from disk to mass storage. Our approach is general and demonstrates a general methodology for this type of problem. We find that algorithms based on both the file size and the time since the file was last used work well. The best realizable algorithms tested condition on the empirical distribution of the times between file references. Acceptable results are also obtained by selecting for replacement that file whose size times time to most recent reference is maximal. Comparisons are made with a number of standard algorithms developed for paging, such as Working Set, VMIN, and GOPT. Sufficient information (parameter values, fitted equations) is provided so that our algorithms may be easily implemented on other systems. [ABSTRACT FROM AUTHOR]

Most results in the field of algorithm design are single algorithms that solve single problems. In this paper we discuss multidimensional divide-anti-conquer, an algorithmic paradigm that can be instantiated in many different ways to yield a number of algorithms and data structures for multidimensional problems. We use this paradigm to give best-known solutions to such problems as the ECDF, maximal range searching, closest pair, and all nearest neighbor problems The contributions of the paper are on two levels. On the first level are the particular algorithms and data structures given by applying the paradigm. On the second level is the more novel contribution of this paper a detailed study of an algorithmic paradigm that is specific enough to be described precisely yet general enough to solve a wide variety of problems. [ABSTRACT FROM AUTHOR]

The article presents a data structure for manipulating priority queues. A variety of applications directly require using priority queues--job scheduling, discrete simulation languages where labels represent the time at which events are to occur, as well as various sorting problems. Priority queues also play a central role in several good algorithms, such as optimal code constructions. The author describes the underlying combinatorial structure, called binomial trees. Binomial trees and forests appear in various data manipulation problems. Although the discussion in the article is an adequate presentation of the priority queue primitives for a very abstract machine model, it does not indicate how to actually code these algorithms on a digital computer. One still has to solve some problems, the first of which concerns the machine representation of labeled binomial forests. The data structure seems to be interesting in itself because of its conceptual simplicity and of the connections it establishes among various data manipulation problems.

This article focuses on problems related to classical list processing techniques. Using the method given in the article, a computer could have list processing primitives built in as machine instructions and the programmer would still be assured that each instruction would finish in a reasonable amount of time. A real-time list processing system has the property that the time required by each of the elementary operations is bounded by a constant independent of the number of cells in use. This property does not guarantee that the constant will be small enough for a particular application on a particular computer, and hence has been called "pseudo-real-time" by some. In all but the most demanding applications, the proper choice of hardware can reduce the constants to acceptable values. The model described in the article consists of a memory, that is, a one-dimensional array of words, each of which is large enough to hold the representation of a non-negative integer which is an index into that array; and a central processing unit, which has a small fixed number of registers the size of a word.

The Associative Processing of Line Drawings (APLD) System utilizes a hardware associative memory and creates, modifies, deletes, stores, and retrieves two-dimensional line drawings consisting of points, tines, rectangles, and triangles. The APLD functions were duplicated on the TX-2 computer at M.I.T.'s Lincoln Laboratory under the LEAP Language and Data Structure. A comparison of the hardware approach with the software simulation illustrates the advantages of the hardware associative memory in three areas: (1) processing speed, (2) storage requirements, and (3) flexibility. The major problem areas of hardware associative memory technology, namely input/output and cost effectiveness, are also addressed. [ABSTRACT FROM AUTHOR]

In most database organizations, the cost of accessing the database will increase due to structural changes caused by updates and insertions. By reorganizing the database, the access costs can be reduced. A basic problem is to establish the proper tradeoff between performance, storage costs, and reorganization costs. This paper considers the optimum points at which to reorganize a database. A disk file organization which allows for distributed free space is described. A cost function describing the excess costs due to physical disorganization is defined, and this function is minimized to obtain the optimum reorganization points. Numerical examples based on the characteristics of existing disk storage devices are given. [ABSTRACT FROM AUTHOR]

Using direct access computer files of bibliographic information, an attempt is made to overcome one of the problems often associated with information retrieval, namely, the maintenance and use of large dictionaries, the greater part of which is used only infrequently. A novel method is presented, which maps the hyperbolic frequency distribution of text characteristics onto a rectangular distribution. This is more suited to implementation on storage devices. This method treats text as a string of characters rather than words bounded by spaces, and chooses subsets of strings such that their frequencies of occurrence are more even than those of word types. The members of this subset are then used as index keys for retrieval. The rectangular distribution of key frequencies results in a much simplified file organization and promises considerable cost advantages. [ABSTRACT FROM AUTHOR]

The high cost of page accessing implies a need for for more careful data organization in a paged memory than is typical of most inverted file and similar approaches to multi-key retrieval. This article analyses that cost and proposes a method called multiple key hashing which attempts to minimize it, Since this approach is not always preferable to inversion, a combined method is described. The exact specifications of this combination for a file with given data and traffic characteristics is formulated as a mathematical program. The proposed heuristic solution to this program can often improve on a simple inversion technique by a factor of 2 or 3. [ABSTRACT FROM AUTHOR]

Presents a model and a programmed system to estimate total storage costs and average access time of various file organizations, given a specific database, query characterization and device-related specifications. Factors that affect the performance of file organization; Importance of proper file structure and evaluation.

The paper describes a scheme for symbolic manipulation of index expressions which arise as a by-product of the symbolic manipulation of expressions in the matrix calculi described by the authors in a previous paper. This scheme attempts program optimization by transforming the original algorithm rather than the machine code. The goal is to automatically generate code for handling the tedious address calculations necessitated by complicated data structures. The paper is therefore preoccupied with "indexing by position." The relationship of "indexing by name" and "indexing by position" is discussed. [ABSTRACT FROM AUTHOR]

List processing systems should be designed to facilitate production of large programs to manipulate large complex symbolic data stores. This paper presents an overview of a number of system features which the author feels are important to improve the productivity of programmers working in such domains. A systems view is taken, rather than focusing just on language features, since algorithms must be not only coded in a language form, but debugged, modified, made efficient, and run on data Because of this general framework, the requirements specified are applicable to the design of advanced programming systems for a wide range of applications Three aspects of programming systems are highlighted good interactive facilities, programmable control structures, and sophisticated data communication mechanisms Interactive features are described to facilitate program composition, entry, testing, debugging, editing, optimization, and packaging. Implementation of a generalized environment structure model specified would allow programming of various control regimes including multi processes, coroutines and backtracking. Alternative methods of procedure invocation required include invocation by pattern and by monitoring condition. The need for extended data forms, storage management, and extensibility are stressed, as is the duality of data retrieval and function evaluation. Syntax directed input and output of data would facilitate use of complex data stores. [ABSTRACT FROM AUTHOR]

In this paper trade-offs among certain computational factors in hash coding are analyzed. The paradigm problem considered is that of testing a series of messages one-by-one for membership in a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency. The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods. in such applications, it is envisaged that overall performance could be improved by using a smaller core resident hash area in conjunction with the new methods and, when necessary, by using some secondary and perhaps time-consuming test to "catch" the small fraction of errors associated with the new methods. An example is discussed which illustrates possible areas of application for the new methods. Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time. [ABSTRACT FROM AUTHOR]

GEDAN KEN is an experimental programming language with the following characteristics. (1) Any value which is permitted in some context of the language is permissible in any other meaningful context. In particular, functions and labels are permissible results of functions and values of variables. (2) Assignment and indirect addressing are formalized by introducing values, called references, which in turn possess other values. The assignment operation always affects the relation between some reference and its value. (3) All compound data structures are treated as functions. (4) Type declarations are not permitted. The functional approach to data structures and the use of references insure that any process which accepts some data structure will accept any logically equivalent structure, regards less of its internal representation. More generally, any data structure may be implicit; i.e. it may be specified by giving an arbitrary algorithm for computing or accessing its components. The existence of label variables permits the construction of co-routines, quasi-parallel processes, and other unorthodox control mechanisms. A variety of programming examples illustrates the generality of the language. Limitations and possible extensions are discussed briefly. [ABSTRACT FROM AUTHOR]

ASP is a general purpose Associative Data Structure Package in which an arbitrary number of data items and an arbitrary number of the relationships between these data items may be represented. A special picture language is described which has proved very useful for drawing ASP structures on paper. ASP structures are built and manipulated by means of a series of macro coils, which are outlined in the Appendix. Emphasis is on the philosophy of the system rather than a particular implementation, though sufficient information is included to enable the reader to produce his own implementation of ASP. [ABSTRACT FROM AUTHOR]

Reduction in the size of decision tables can be accomplished by several techniques. The techniques considered in this paper are on the parsing of decision tables with regard to horizontal and vertical data structures, job identity, hardware and job priorities, and context relationships. Such parsing rests upon some conventions for the linkage of decision tables. [ABSTRACT FROM AUTHOR]

The internal organization of string processing systems is discussed. Six techniques for data structures are presented and evaluated on the basis of; (1) creation of strings; (2) examination of strings; and (3) alteration of strings. Speed of operation, storage requirements, effect on paging, and programmer convenience are also considered. One of the techniques, single-word linked blocks, is used in an example demonstrating an implementation of a SNOBOL string processing language on an IBM System 360. [ABSTRACT FROM AUTHOR]

A mapping from block diagrams of digital circuits to list structures is described, together with a list processing program written for the Control Data 3600 which uses this mopping to automatically carry out circuit analysis. [ABSTRACT FROM AUTHOR]

Some basic facts about certain data structures are reviewed and an efficient algorithm is presented for constructing storage mapping function for n structure from the structure's definition. [ABSTRACT FROM AUTHOR]

This article presents several abstracts related to computer programming. The first one is "Analysis of the Search Performance of Coalesced Hashing," by Jeffrey Scott Vitter. An analysis is presented of the coalesced hashing method, in which a portion of memory (called the address region) serves as the range of the hash function while the rest of memory (called the cellar) is devoted solely to storing records that collide when inserted. The main result of this paper expresses the average search times as a function of the number of records and the cellar size, solving a long-standing open problem. Another abstract is "Computable Error Bounds for Aggregated Markov Chains," by G.W. Stewart. In this paper, a method is described for computing the steady-state probability vector of a nearly completely decomposable Markov chain. It does not require the determination of a completely decomposable stochastic approximation to the transition matrix, and hence it is applicable to non stochastic matrices. An error analysis of the procedure which results in effectively computable error bounds is given.

The article presents 15 useful tips to make the Windows 10 operating system from technology company Microsfot work faster. Topics covered include the fast way of accessing specific files and folders, tips on how to disable notification sounds when the user sleeps, and how to instantly zoom hard-to-read text. It also discusses how to open programs faster, how to launch Windows tools that are used often, and how to read important notifications before they disappear.

The article offers tips when searching in the Finder, the default file manager and graphical user interface shell used on Macintosh operating systems. It discusses the steps to follow when starting a Finder search, honing one's search, and adding criteria. It also explains how to combine multiple queries and save searches for later.