Time versus cost tradeoffs for deterministic rendezvous in networks

Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds. Each agent has a distinct integer label from the set \(\{1,\ldots ,L\}\). Two main efficiency measures of rendezvous are its time (the number of rounds until the meeting) and its cost (the total number of edge traversals). We investigate tradeoffs between these two measures. A natural benchmark for both time and cost of rendezvous in a network is the number of edge traversals needed for visiting all nodes of the network, called the exploration time. Hence we express the time and cost of rendezvous as functions of an upper bound E on the time of exploration (where E and a corresponding exploration procedure are known to both agents) and of the size L of the label space. We present two natural rendezvous algorithms. Algorithm Cheap has cost O(E) (and, in fact, a version of this algorithm for the model where the agents start simultaneously has cost exactly E) and time O(EL). Algorithm Fast has both time and cost \(O(E\log L)\). Our main contributions are lower bounds showing that, perhaps surprisingly, these two algorithms capture the tradeoffs between time and cost of rendezvous almost tightly. We show that any deterministic rendezvous algorithm of cost asymptotically E (i.e., of cost \(E+o(E)\)) must have time \(\varOmega (EL)\). On the other hand, we show that any deterministic rendezvous algorithm with time complexity \(O(E\log L)\) must have cost \(\varOmega (E\log L)\).     

Input space versus feature space in kernel-based methods

This paper collects some ideas targeted at advancing our understanding of the feature spaces associated with support vector (SV) kernel functions. We first discuss the geometry of feature space. In particular, we review what is known about the shape of the image of input space under the feature space map, and how this influences the capacity of SV methods. Following this, we describe how the metric governing the intrinsic geometry of the mapped surface can be computed in terms of the kernel, using the example of the class of inhomogeneous polynomial kernels, which are often used in SV pattern recognition. We then discuss the connection between feature space and input space by dealing with the question of how one can, given some vector in feature space, find a preimage (exact or approximate) in input space. We describe algorithms to tackle this issue, and show their utility in two applications of kernel methods. First, we use it to reduce the computational complexity of SV decision functions; second, we combine it with the kernel PCA algorithm, thereby constructing a nonlinear statistical denoising technique which is shown to perform well on real-world data     

Resilient k-d trees: k-means in space revisited

We propose a k-d tree variant that is resilient to a pre-described number of memory corruptions while still using only linear space. While the data structure is of independent interest, we demonstrate its use in the context of high-radiation environments. Our experimental evaluation demonstrates that the resulting approach leads to a significantly higher resiliency rate compared to previous results. This is especially the case for large-scale multi-spectral satellite data, which renders the proposed approach well-suited to operate aboard today??s satellites.     

Query costs in HB(1) trees versus 2–3 trees

Query costs in random AVL trees are compared to those in random 2–3 trees. Both data structures are assumed to reside in main storage. Costs are calculated in terms of the number of node visits and key comparisons required to find a match or no match for a given key. The comparison is based upon theoretical concepts and implementation dependent considerations; e.g., data and instruction fetch. It is shown that if the cost of a key comparison is greater than or equal to the cost of a node access, then AVL trees are more advantageous.     

On balanced versus unbalanced computation trees

A great number of complexity classes between P and PSPACE can be defined via leaf languages for computation trees of nondeterministic polynomial-time machines. Jenner, McKenzie, and Thérien (Proceedings of the 9th Conference on Structure in Complexity Theory, 1994) raised the issue of whether considering balanced or unbalanced trees makes any difference. For a number of leaf-language classes, coincidence of both models was shown, but for the very prominent example of leaf-language classes from the alternating logarithmic-time hierarchy the question was left open. It was only proved that in the balanced case these classes exactly characterize the classes from the polynomial-time hierarchy. Here, we show that balanced trees apparently make a difference: In the unbalanced case, a class from the logarithmic-time hierarchy characterizes the corresponding class from the polynomial-time hierarchy with a PP-oracle. Along the way, we get an interesting normal form for PP computations. The first and third authors were supported by Deutsche Forschungsgemeinschaft, Grant No. Wa 847/1-1, “k-wertige Schaltkreise.” The second author was supported in part by an Alexander von Humboldt fellowship.     

Reducing the space requirement of suffix trees

We show that suffix trees store various kinds of redundant information. We exploit these redundancies to obtain more space efficient representations. The most space efficient of our representations requires 20 bytes per input character in the worst case, and 10.1 bytes per input character on average for a collection of 42 files of different type. This is an advantage of more than 8 bytes per input character over previous work. Our representations can be constructed without extra space, and as fast as previous representations. The asymptotic running times of suffix tree applications are retained. Copyright © 1999 John Wiley & Sons, Ltd.     

Quasi-optimum control for minimum-time rendezvous

A quasi-optimum control law for minimum-time, bounded acceleration rendezvous in a plane is obtained. By ignoring the tangential velocity, a simplified problem is obtained for which there is a well-known solution. The tangential velocity is then accounted for, approximately, by use of the quasi-optimum control technique described by Friedland.1 Simulated trajectories show that the quasi-optimum control law gives excellent results.     

The efficiency of using k-d trees for finding nearest neighbors in discrete space

In this paper, we examine the efficiency of the k-d tree for retrieving from a file of fixed-length binary key records the best match to a given input word. We provide guidelines for determining if the search of the tree will provide any savings when compared with an exhaustive search.     

Time and space for segmenting personal photo sets

Multimedia Tools and Applications - A personal collection of photos shows large variability in the depicted items, making difficult a fully automated solution to cope with sensory and semantic...     

Cache coherence requirements for interprocess rendezvous

Multiprocessors in which a shared bus is used by the processor to communicate with common memory are an emerging class of machines where there is a need to support parallel programming languages. A language construct that is found in a number of parallel programming languages to support synchronization and communication in the interprocess rendezvous. Shared-bus multiprocessor require a protocol to keep the date in their caches coherent. There are two major categories of these protocols: invalidation and write-boadcast. This paper examines the requirements for cache coherence protocols to support efficient interprocessor rendezvous. The approach taken is to examine the memory referencing patterns to the run-time data structures during rendezvous execution. The appropriate coherence protocol is shown to be a function of the processor scheduling strategy used by the run-time system at synchronzation points during the rendezvous. When processes migrate freely as a result of the scheduling strategy, invalidation protocols are found to be more efficient. When migration is restricted by the scheduler, write-broadcast protocols are more efficient.     

Searching minimax game trees under memory space constraint

Games such as CHESS, GO and OTHELLO can be represented by minimax game trees. Among various search procedures to solve such game trees,- and SSS^* are perhaps most well known. Although it is proved that SSS^* explores only a subset of the nodes explored by-, - is commonly believed to be faster in real applications, since it requires very little memory space and hence its storage management cost is low. Contrary to this folklore, however, this paper reports, using the OTHELLO game as an example, that SSS^* is much faster than-. It is also demonstrated that SSS^* can be modified to make the required memory space controllable to some extent, while retaining the high efficiency of the original SSS^*.This research was partially supported by the Ministry of Education, Science and Culture of Japan, under a Scientific Grant-in-Aid.     

Improving time and space efficiency in generalized binary search trees

Summary This paper deals with main memory data structures for which time and space performance are simultaneously considered. The main contribution is a new data structure called Generalised Binary Search Tree (GBS-tree) together with searching and updating algorithms on this structure. GBS-trees generalise different data structures based on binary trees that have appeared in the literature. A k-t GBS-tree allows up to t keys per node and subtrees in the tree's fringe of exactly 2k-1 full nodes are kept balanced. Their time and space performances are analysed in depth. The time performance is expressed in terms of the average and the variance of the number of binary comparisons between a given key and keys already in the structure. The space performance measures both the space used to space generated ratio (space utilization factor) and the pointers to keys ratio of these trees. The analysis shows that the time performance always improves when GBS-trees of higher order are considered. In the absence of balancing techniques, larger values of t, which produces smaller pointers to key ratios, induce unacceptably poor space utilizations factors. We show that both pointers to keys ratio and space utilization factor improve when larger values of k are used. Thus, local balancing techniques are adequate, not only for time performance improvement, but also, for space performance improvement.     

Time lag versus stability

By employing Lyapunov functions and the theory of differential inequalities in the context of a suitable minimal class of functions, sufficient conditions are given for stability of functional differential systems. It is shown that the dominant diagonal property of a matrix provides a suitable mechanism to resolve "time-lag vs. stability" problem.     

On time versus space III

Paul and Reischuk devised space efficient simulations of logarithmic cost random access machines and multidimensional Turing machines. We simplify their general space reduction technique and extend it to other computational models, including pointer machines, which model computations on graphs and data structures. Every pointer machine of time complexityT(n) can be simulated by a pointer machine of space complexityO(T(n)/logT(n)).     

On time versus space II

Every t(n)-time bounded RAM (assuming the logarithmic cost measure) can be simulated by a t(n)/log t(n)-space bounded Turing machine and every t(n)-time bounded Turing machine with d-dimensional tapes by a bounded machine, where n is the length of the input. A class $\text{E}$ of storage structures which generalizes multidimensional tapes is defined. Every t(n)-time bounded Turing machine whose storage structures are in $\text{E}$ can be simulated by a t(n) loglog t(n)/log t(n)-space bounded Turing machine.     

Consolidated trees versus bagging when explanation is required

In some real-world problems solved by machine learning it is compulsory for the solution provided to be comprehensible so that the correct decision can be made. It is in this context that this paper compares bagging (one of the most widely used multiple classifier systems) with the consolidated trees construction (CTC) algorithm, when the learning problem to be solved requires the classification made to be provided with an explanation. Bearing in mind the comprehensibility shortcomings of bagging, the Domingos’ proposal, called combining multiple models, has been used to address this problem. The two algorithms have been compared from three main points of view: accuracy, quality of the explanation the classification is provided with, and computational cost. The results obtained show that it is beneficial to use CTC in situations where an explanation is required, because: CTC has a greater discriminating capacity than the explanation extraction algorithm added to bagging; the explanation provided is of a greater quality; it is simpler and more reliable; and CTC is computationally more efficient.     

Feature space versus empirical kernel map and row kernel space in SVMs

In machine-learning technologies, the support vector machine (SV machine, SVM) is a brilliant invention with many merits, such as freedom from local minima, the widest possible margins separating different clusters, and a solid theoretical foundation. In this paper, we first explore the linear separability relationships between the high-dimensional feature space H and the empirical kernel map U as well as between H and the space of kernel outputs K. Second, we investigate the relations of the distances between separating hyperplanes and SVs in H and U, and derive an upper bound for the margin width in K. Third, as an application, we show experimentally that the separating hyperplane in H can be slightly adjusted through U. The experiments reveal that existing SVM training can linearly separate the data in H with considerable success. The results in this paper allow us to visualize the geometry of H by studying U and K.