Searching in metric spaces by spatial approximation

We propose a new data structure to search in metric spaces. A metric space is formed by a collection of objects and a distance function defined among them which satisfies the triangle inequality. The goal is, given a set of objects and a query, retrieve those objects close enough to the query. The complexity measure is the number of distances computed to achieve this goal. Our data structure, called sa-tree (“spatial approximation tree”), is based on approaching the searched objects spatially, that is, getting closer and closer to them, rather than the classic divide-and-conquer approach of other data structures. We analyze our method and show that the number of distance evaluations to search among n objects is sublinear. We show experimentally that the sa-tree is the best existing technique when the metric space is hard to search or the query has low selectivity. These are the most important unsolved cases in real applications. As a practical advantage, our data structure is one of the few that does not need to tune parameters, which makes it appealing for use by non-experts. Edited by R. Sacks-Davis Received: 17 April 2001 / Accepted: 24 January 2002 / Published online: 14 May 2002     

Effective bandwidth estimation and testing for Markov sources

This work addresses the resource sharing problem in broadband communication networks that can guarantee some quality of service (QoS), and develops some results about data source and traffic modelling, especially in aspects of model testing and parameter estimation. The multiplexing of variable bit rate (VBR) sources poses a mathematical and statistical problem: the estimation of the resource requirements of a source or set of sources. The estimation method shall be simple enough to be practically implemented in the connection acceptance control (CAC) function.

In this paper, the VBR video sources are taken as a typical case of variable rate, with real-time constraints. This association of requirements makes the case especially interesting. A Markov model is assumed for the VBR sources. The validity of such models is under research; they seem to be appropriate at least in certain time scales. The model is tested against real video traces. In order to estimate the resource allocation or “channel occupation” of each source, the concept of equivalent bandwidth proposed by Kelly [Notes on effective bandwidth, in: F.P. Kelly, S. Zachary, I.B. Ziedins (Eds.), Stochastic Networks: Theory and Applications, Oxford University Press, Oxford, 1996, pp. 141] is used; it is based on a consistent mathematical theory, and has proven to be robust and useful for technical applications.

A calculation of the equivalent bandwidth of a Markov source, given its parameters, can be found in the literature [IEEE ACM Trans. Networking 1 (4) (1993) 424]. But in fact, one can only estimate model and parameters. In this work, an estimation of the equivalent bandwidth is given, which can be obtained from real data. The convergence and the consistency of the estimation are studied, and practical bounds are found. Illustrative calculations are performed from real video traces that were obtained using a software MPEG coder, developed by the authors. The mathematical and statistical results are valid for whatever phenomenon that can be modelled as a Markov process.     

Detection and Discrimination of Conspecific Scents by the Anguid Slow-Worm Anguis fragilis

We tested the ability of male slow-worms, Anguis fragilis, a limbless anguid lizard with secretive, semifossorial habits, to detect chemical associated with conspecifics by using a T-maze in the laboratory. Male slow-worms discriminated conspecific male and female scent deposits. Males selected the arm with female scent, suggesting that scent deposits may be used to locate potential mates. Also, male slow-worms did not avoid the chemicals of other males, suggesting that they are not territorial. However, males discriminated their own scent from those of other males, and spent more time exploring the arm with other male scent, which suggests that scent marks may bear information that could be used in future intrasexual social contexts. We conclude that discrimination of conspecifics based on scents may be more widespread than previously expected among lizards inhabiting visually restricted environments.     

Comparison of linear and rotationally shearing interferometric layouts for extrasolar planet detection from space

We use the point spread function and the modulation transfer function (MTF) as two figures-of-merit to evaluate the performance of the multiaperture interferometric configurations for the detection of a faint planet in the vicinity of its bright star. We design nonredundant interferometric layouts that provide satisfactory coverage of the spatial frequencies of interest. We propose a design incorporating a rotating, rotationally shearing interferometer in a gravity-free environment and compare its performance with the Earth-based, fixed, linear configurations. The side peak of its MTF may be centered on the coordinate associated with a likely planet spatial frequency, resulting in planet signal enhancement and isolation.     

SAW COM-parameter extraction in AlN/diamond layered structures

Highly c-axis oriented aluminum nitride (AlN) thin piezoelectric films have been grown on polycrystalline diamond substrates by pulsed direct current (DC) magnetron reactive sputter-deposition. The films were deposited at a substrate temperature below 50/spl deg/C (room temperature) and had a typical full width half maximum (FWHM) value of the rocking curve of the AlN-002-peak of 2.1 degrees. A variety of one-port surface acoustic wave (SAW) resonators have been designed and fabricated on top of the AlN films. The measurements indicate that various SAW modes are excited. The SAW phase velocities of up to 11.800 m/s have been measured. These results are in agreement with calculated dispersion curves of the AlN/diamond structure. Finally, the coupling of modes parameters have been extracted from S/sub 11/ measurements using curve fitting for the first SAW mode, which indicate an effective coupling K/sup 2/ of 0.91% and a Q factor of about 600 at a frequency of 1050 MHz.     

Flow Intensity Parameter in Pier Scour Experiments

Technical note discusses a detailed approach to dimensional analysis for the bridge pier scour phenomenon and the introduction of flow intensity. It demonstrates the dependence of critical upstream velocity on the rest of the parameters describing the process and its implications on dimensional analysis. Assuming that the viscous effects are negligible in the local scour phenomenon, it is concluded that the flow intensity of the approaching undisturbed flow is not an adequate parameter to describe the process in usual laboratory conditions. A new proposal is established.     

Modeling and Analysis of Composite Antenna Superstrates Consisting on Grids of Loaded Wires

We study the characteristics and radiation mechanism of antenna superstrates based on closely located periodical grids of loaded wires. An explicit analytical method based on the local field approach is used to study the reflection and transmission properties of such superstrates. It is shown that as a result of proper impedance loading there exists a rather wide frequency band over which currents induced to the grids cancel each other, leading to a wide transmission maximum. In this regime radiation is produced by the magnetic dipole moments created by circulating out-of-phase currents flowing in the grids. An impedance matrix representation is derived for the superstrates, and the analytical results are validated using full-wave simulations. As a practical application example we study numerically the radiation characteristics of dipole antennas illuminating finite-size superstrates.     

Ultrasound image segmentation with shape priors: application to automatic cattle rib-eye area estimation.

Automatic ultrasound (US) image segmentation is a difficult task due to the quantity of noise present in the images and the lack of information in several zones produced by the acquisition conditions. In this paper, we propose a method that combines shape priors and image information to achieve this task. In particular, we introduce knowledge about the rib-eye shape using a set of images manually segmented by experts. A method is proposed for the automatic segmentation of new samples in which a closed curve is fitted taking into account both the US image information and the geodesic distance between the evolving curve and the estimated mean rib-eye shape in a shape space. This method can be used to solve similar problems that arise when dealing with US images in other fields. The method was successfully tested over a database composed of 610 US images, for which we have the manual segmentations of two experts.     

Fixed Queries Array: A Fast and Economical Data Structure for Proximity Searching

Pivot-based algorithms are effective tools for proximity searching in metric spaces. They allow trading space overhead for number of distance evaluations performed at query time. With additional search structures (that pose extra space overhead) they can also reduce the amount of side computations. We introduce a new data structure, the Fixed Queries Array (FQA), whose novelties are (1) it permits sublinear extra CPU time without any extra data structure; (2) it permits trading number of pivots for their precision so as to make better use of the available memory. We show experimentally that the FQA is an efficient tool to search in metric spaces and that it compares favorably against other state of the art approaches. Its simplicity converts it into a simple yet effective tool for practitioners seeking for a black-box method to plug in their applications.