An adaptation of a root finding method to searching ordered disk files

Three methods for locating a record in an ordered file are considered. The keys in the files are chosen from three different statistical distributions and the methods, two of which are taken from the literature and an adapted root finding method, are compared by tabulating information relating to standard statistics for the number of probes.     

An adaptation of a root finding method to searching ordered disk files revisited

In the present report, Interpolation search, Fast search and Pegasus method are compared with respect to their performance in searching ordered disk files for several key distributions. The aim is to study the effect of the page capacity on searching performance. Cost metric is the number of page accesses and not key comparisons. Numerical results are illustrated and a new approximate formula is derived giving an estimate of the number of page accesses for the case of the Interpolation algorithm under uniform distributions.     

Estimating searching cost of regular path queries on large graphs by exploiting unit-subqueries

Journal of Heuristics - Regular path queries (RPQs) are widely used on a graph whose answer is a set of tuples of nodes connected by paths corresponding to a given regular expression. Traditional...     

Ideals in the disk algebra

In this article, we determine a necessary and sufficient condition for a sum of closed ideals in the disk algebra to be closed. Essentially, the condition is that the generating inner functions must not simultaneously vanish in the sense used in the corona theorem. The proof uses interpolation properties of the disk algebra and Detraz' generalization of the corona theorem.     

Accounting for boundary effects in nearest-neighbor searching

Givenn data points ind-dimensional space, nearest-neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest-neighbor searching algorithms are made under the simplifying assumption thatd is fixed and thatn is so large relative tod thatboundary effects can be ignored. This means that for any query point the statistical distribution of the data points surrounding it is independent of the location of the query point. However, in many applications of nearest-neighbor searching (such as data compression by vector quantization) this assumption is not met, since the number of data pointsn grows roughly as 2 ^d .Largely for this reason, the actual performances of many nearest-neighbor algorithms tend to be much better than their theoretical analyses would suggest. We present evidence of why this is the case. We provide an accurate analysis of the number of cells visited in nearest-neighbor searching by the bucketing andk-d tree algorithms. We assumem ^dpoints uniformly distributed in dimensiond, wherem is a fixed integer ≥2. Further, we assume that distances are measured in theL _∞ metric. Our analysis is tight in the limit asd approaches infinity. Empirical evidence is presented showing that the analysis applies even in low dimensions. A preliminary version of this paper appeared in theProceedings of the 11th Annual ACM Symposium on Computational Geometry, 1995, pp. 336–344. Part of this research was conducted while the first author was visiting the Max-Planck-Institut für Informatik, Saarbrücken, Germany. The first author was supported by the ESPRIT Basic Research Actions Program, under Contract No. 7141 (project ALCOM II). The support of the National Science Foundation under Grant CCR-9310705 is gratefully acknowledged by the second author. The third author was supported in part by AT&T Bell Laboratories and the Society of Fellows at Harvard University.     

Edge ranking and searching in partial orders

We consider a problem of searching an element in a partially ordered set (poset). The goal is to find a search strategy which minimizes the number of comparisons. Ben-Asher, Farchi and Newman considered a special case where the partial order has the maximum element and the Hasse diagram is a tree (tree-like posets) and they gave an O(n⁴log³n)-time algorithm for finding an optimal search strategy for such a partial order. We show that this problem is equivalent to finding edge ranking of a simple tree corresponding to the Hasse diagram, which implies the existence of a linear-time algorithm for this problem.Then we study a more general problem, namely searching in any partial order with maximum element. We prove that such a generalization is hard, and we give an -approximate polynomial-time algorithm for this problem.     

Quasi-optimal range searching in spaces of finite VC-dimension

The range-searching problems that allow efficient partition trees are characterized as those defined by range spaces of finite Vapnik-Chervonenkis dimension. More generally, these problems are shown to be the only ones that admit linear-size solutions with sublinear query time in the arithmetic model. The proof rests on a characterization of spanning trees with a low stabbing number. We use probabilistic arguments to treat the general case, but we are able to use geometric techniques to handle the most common range-searching problems, such as simplex and spherical range search. We prove that any set ofn points inE ^d admits a spanning tree which cannot be cut by any hyperplane (or hypersphere) through more than roughlyn ^1–1/d edges. This result yields quasi-optimal solutions to simplex range searching in the arithmetic model of computation. We also look at polygon, disk, and tetrahedron range searching on a random access machine. Givenn points inE ², we derive a data structure of sizeO(n logn) for counting how many points fall inside a query convexk-gon (for arbitrary values ofk). The query time isO(kn logn). Ifk is fixed once and for all (as in triangular range searching), then the storage requirement drops toO(n). We also describe anO(n logn)-size data structure for counting how many points fall inside a query circle inO(n log² n) query time. Finally, we present anO(n logn)-size data structure for counting how many points fall inside a query tetrahedron in 3-space inO(n ^2/3 log² n) query time. All the algorithms are optimal within polylogarithmic factors. In all cases, the preprocessing can be done in polynomial time. Furthermore, the algorithms can also handle reporting within the same complexity (adding the size of the output as a linear term to the query time).Portions of this work have appeared in preliminary form in Partition trees for triangle counting and other range searching problems (E. Welzl),Proc. 4th Ann. ACM Symp. Comput. Geom. (1988), 23–33, and Tight Bounds on the Stabbing Number of Spanning Trees in Euclidean Space (B. Chazelle), Comput. Sci. Techn. Rep. No. CS-TR-155-88, Princeton University, 1988. Bernard Chazelle acknowledges the National Science Foundation for supporting this research in part under Grant CCR-8700917. Emo Welzl acknowledges the Deutsche Forschungsgemeinschaft for supporting this research in part under Grant We 1265/1-1.     

Spectral factorization in the disk algebra

Every strictly positive function f, given on the unit circle of the complex plane, defines an outer function. This article investigates the behavior of these outer functions on the boundary of the unit disk. It is shown that even if the given function f on the boundary is continuous, the corresponding outer function is generally not continuous on the closure of the unit disk. Moreover, any subset E∈ [-π ,π) of Lebesgue measure zero is a valid divergence set for outer functions of some continuous functions f. These results are applied to study the solutions of non-linear boundary-value problems and the factorization of spectral density functions.     

Stress relaxation in a polymer disk

The stress relaxation in a polymer disk with a central hole, into which a rigid metal rod is press-fitted, is considered. The progressive redistribution of the stresses in the disk has been observed by a photoelastic method. In the theoretical solution of the problem the relaxation properties of the polymer are taken into account by means of a generalized nonlinear Maxwell equation with two terms of the relaxation spectrum. It is shown that the linear, as distinct from the nonlinear, theory is not capable of conveying the characteristics of the stress relaxation process in a rigid polymer disk.Institute of Chemical Physics, Academy of Sciences of the USSR, Moscow. Translated from Mekhanika Polimerov, No. 6, pp. 1064–1070, November–December, 1971.     

Complemented ideals in the disk algebra

The complemented ideals in the disk algebra are characterized. The projection operators onto the ideals and the complements of the ideals are identified. Research partially supported by a National Academy of Sciences Fellowship to the USSR during the 1977–78 academic year. This author wishes to thank S. Khrushchev, V. Peller, S. Kisljakov, I. Vasoonin, and B. Mitiagin for their many helpful comments and suggestions.     

Thin interpolating sequences in the disk

Using a kind of summability procedure we give, within this survey, a new proof of a result by Sundberg and Wolff on large perturbations of thin interpolating sequences and present a detailed proof of the statement of Dyakonov and Nicolau that asymptotic interpolation problems in H^∞ can be solved by thin Blaschke products. Dedicated to Professor Heinz K?nig on the occasion of his 80^th birthday     

Harmonic measure of curves in the disk

A powerful tool for studying the growth of analytic and harmonic functions is Hall's Lemma, which states that there is a constantC>0 so that the harmonic measure of a subsetE of the closed unit disk evaluated at 0 satisfies whereE _rad is the radial projection ofE onto . FitzGerald, Rodin and Warschawski proved that ifE is a continuum in whose radial projection has length at most π then (*) is true withC=1, and they asked how large the length, |E _rad|, can be in order for their result to be valid. We prove that (*) holds withC=1 for every continuum satisfying and θc cannot be replaced by a larger number. Fuchs asked for the largest constantC so that (*) holds for allE. We show that for every continuum , (*) holds withC=C _2π≅.977126698498665669…, whereC _2π is the harmonic measure of the two long sides of a 3∶1 rectangle evaluated at the center. There are Jordan curves for which equality holds in (*) withC=C _2π. The authors are supported in part by NSF grants DMS-9302823 and DMS-9401027, and while at MSRI by NSF grant DMS-9022140.     

Optimal data placement in two-headed disk systems

A problem inherent to the performance of disk systems is the data placement in cyinders in such a way that the seek time is minimized. If successive searchers are independent, then the optimal placement for conventional one-headed disk systems is the organ-pipe arrangement. According to this arrangement the most frequent cylinder is placed in the central location, while the less frequent cylinders are placed right and left alternatively. This paper proves that the optimal placement for two-headed disk systems is the camel arrangement, which may be viewed as two consecutive organ-pipe arrangements. It is also proved that, for a two-headed disk system withN=2(2n+1) cylinders, the total number of these optimal camel arrangements is exp₂ (N/2+1).Professor J. G. Kollias died untimely December 1989.     

On random points in the unit disk

Let n be a positive integer and λ > 0 a real number. Let V_n be a set of n points in the unit disk selected uniformly and independently at random. Define G(λ, n) to be the graph with vertex set V_n, in which two vertices are adjacent if and only if their Euclidean distance is at most λ. We call this graph a unit disk random graph. Let and let X be the number of isolated points in G(λ, n). We prove that almost always X ～ n when 0 ≤ c < 1. It is known that if where ?(n) → ∞, then G(λ, n) is connected. By extending a method of Penrose, we show that under the same condition on λ, there exists a constant K such that the diameter of G(λ, n) is bounded above by K · 2/λ. Furthermore, with a new geometric construction, we show that when and c > 2.26164 …, the diameter of G(λ, n) is bounded by (4 + o(1))/λ; and we modify this construction to yield a function c(δ) > 0 such that the diameter is at most 2(1 + δ + o(1))/λ when c > c(δ). © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006