Search adaptations and the challenges of the web

Search has become a hot topic in Internet computing, with rival search engines battling to become the de facto Web portal, harnessing search algorithms to wade through information on a scale undreamed of by early information retrieval (IR) pioneers. This article examines how search has matured from its roots in specialized IR systems to become a key foundation of the Web. The authors describe new challenges posed by the Web's scale, and show how search is changing the nature of the Web as much as the Web has changed the nature of search

Search space pruning and global optimisation of Multiple Gravity Assist spacecraft trajectories

We introduce and describe the Multiple Gravity Assist problem, a global optimisation problem that is of great interest in the design of spacecraft and their trajectories. We discuss its formalization and we show, in one particular problem instance, the performance of selected state of the art heuristic global optimisation algorithms. A deterministic search space pruning algorithm is then developed and its polynomial time and space complexity derived. The algorithm is shown to achieve search space reductions of greater than six orders of magnitude, thus reducing significantly the complexity of the subsequent optimisation.

Minimum stable convergence criteria for stochastic diffusion search

An analysis of Stochastic Diffusion Search (SDS), a novel and efficient optimisation and search algorithm, is presented, resulting in a derivation of the minimum acceptable match resulting in a stable convergence within a noisy search space. The applicability of SDS can therefore be assessed for a given problem.

Communicating neurons: a connectionist spiking neuron implementation of stochastic diffusion search

An information processing paradigm in the brain is proposed, instantiated in an artificial neural network using biologically motivated temporal encoding. The network will locate within the external world stimulus, the target memory, defined by a specific pattern of micro-features. The proposed network is robust and efficient. Akin in operation to the swarm intelligence paradigm, stochastic diffusion search, it will find the best-fit to the memory with linear time complexity. information multiplexing enables neurons to process knowledge as 'tokens' rather than 'types'. The network illustrates possible emergence of cognitive processing from low level interactions such as memory retrieval based on partial matching. (C) 2007 Elsevier B.V. All rights reserved.

Classification-based probabilistic modeling of texture transition for fast line search tracking and delineation

We introduce a classification-based approach to finding occluding texture boundaries. The classifier is composed of a set of weak learners, which operate on image intensity discriminative features that are defined on small patches and are fast to compute. A database that is designed to simulate digitized occluding contours of textured objects in natural images is used to train the weak learners. The trained classifier score is then used to obtain a probabilistic model for the presence of texture transitions, which can readily be used for line search texture boundary detection in the direction normal to an initial boundary estimate. This method is fast and therefore suitable for real-time and interactive applications. It works as a robust estimator, which requires a ribbon-like search region and can handle complex texture structures without requiring a large number of observations. We demonstrate results both in the context of interactive 2D delineation and of fast 3D tracking and compare its performance with other existing methods for line search boundary detection.

Linear predicted hexagonal search algorithm with moments

A novel Linear Hashtable Method Predicted Hexagonal Search (LHMPHS) method for block based motion compensation is proposed. Fast block matching algorithms use the origin as the initial search center, which often does not track motion very well. To improve the accuracy of the fast BMA's, we employ a predicted starting search point, which reflects the motion trend of the current block. The predicted search centre is found closer to the global minimum. Thus the center-biased BMA's can be used to find the motion vector more efficiently. The performance of the algorithm is evaluated by using standard video sequences, considers the three important metrics: The results show that the proposed algorithm enhances the accuracy of current hexagonal algorithms and is better than Full Search, Logarithmic Search etc.

Linear algorithm and hexagonal search based two-pass algorithm for motion estimation

This paper presents a novel two-pass algorithm constituted by Linear Hashtable Motion Estimation Algorithm (LHMEA) and Hexagonal Search (HEXBS) for block base motion compensation. On the basis of research from previous algorithms, especially an on-the-edge motion estimation algorithm called hexagonal search (HEXBS), we propose the LHMEA and the Two-Pass Algorithm (TPA). We introduced hashtable into video compression. In this paper we employ LHMEA for the first-pass search in all the Macroblocks (MB) in the picture. Motion Vectors (MV) are then generated from the first-pass and are used as predictors for second-pass HEXBS motion estimation, which only searches a small number of MBs. The evaluation of the algorithm considers the three important metrics being time, compression rate and PSNR. The performance of the algorithm is evaluated by using standard video sequences and the results are compared to current algorithms, Experimental results show that the proposed algorithm can offer the same compression rate as the Full Search. LHMEA with TPA has significant improvement on HEXBS and shows a direction for improving other fast motion estimation algorithms, for example Diamond Search.

Directed search with real options

While search is normally modelled by economists purely in terms of decisions over making observations, this paper models it as a process in which information is gained through feedback from innovatory product launches. The information gained can then be used to decide whether to exercise real options. In the model the initial decisions involve a product design and the scale of production capacity. There are then real options to change these factors based on what is learned. The case of launching product variants in parallel is also considered. Under ‘true’ uncertainty, the model can be seen in terms of heuristic decision-making based on subjective beliefs with limited foresight. Search costs, the values of the real options, beliefs, and the cost of capital are all shown to be significant in determining the search path.

Studying reactive processes with classical dynamics: rebinding dynamics in MbNO

A new surface-crossing algorithm suitable for describing bond-breaking and bond-forming processes in molecular dynamics simulations is presented. The method is formulated for two intersecting potential energy manifolds which dissociate to different adiabatic states. During simulations, crossings are detected by monitoring an energy criterion. If fulfilled, the two manifolds are mixed over a finite number of time steps, after which the system is propagated on the second adiabat and the crossing is carried out with probability one. The algorithm is extensively tested (almost 0.5 mu s of total simulation time) for the rebinding of NO to myoglobin. The unbound surface ((FeNO)-N-...) is represented using a standard force field, whereas the bound surface (Fe-NO) is described by an ab initio potential energy surface. The rebinding is found to be nonexponential in time, in agreement with experimental studies, and can be described using two time constants. Depending on the asymptotic energy separation between the manifolds, the short rebinding timescale is between 1 and 9 ps, whereas the longer timescale is about an order of magnitude larger. NO molecules which do not rebind within 1 ns are typically found in the Xenon-4 pocket, indicating the high affinity of NO to this region in the protein.

Reactive Halogens in the Marine Boundary Layer (RHaMBLe): the tropical North Atlantic experiments

The NERC UK SOLAS-funded Reactive Halogens in the Marine Boundary Layer (RHaMBLe) programme comprised three field experiments. This manuscript presents an overview of the measurements made within the two simultaneous remote experiments conducted in the tropical North Atlantic in May and June 2007. Measurements were made from two mobile and one ground-based platforms. The heavily instrumented cruise D319 on the RRS Discovery from Lisbon, Portugal to São Vicente, Cape Verde and back to Falmouth, UK was used to characterise the spatial distribution of boundary layer components likely to play a role in reactive halogen chemistry. Measurements onboard the ARSF Dornier aircraft were used to allow the observations to be interpreted in the context of their vertical distribution and to confirm the interpretation of atmospheric structure in the vicinity of the Cape Verde islands. Long-term ground-based measurements at the Cape Verde Atmospheric Observatory (CVAO) on São Vicente were supplemented by long-term measurements of reactive halogen species and characterisation of additional trace gas and aerosol species during the intensive experimental period. This paper presents a summary of the measurements made within the RHaMBLe remote experiments and discusses them in their meteorological and chemical context as determined from these three platforms and from additional meteorological analyses. Air always arrived at the CVAO from the North East with a range of air mass origins (European, Atlantic and North American continental). Trace gases were present at stable and fairly low concentrations with the exception of a slight increase in some anthropogenic components in air of North American origin, though NOx mixing ratios during this period remained below 20 pptv (note the non-IUPAC adoption in this manuscript of pptv and ppbv, equivalent to pmol mol−1 and nmol mol−1 to reflect common practice). Consistency with these air mass classifications is observed in the time series of soluble gas and aerosol composition measurements, with additional identification of periods of slightly elevated dust concentrations consistent with the trajectories passing over the African continent. The CVAO is shown to be broadly representative of the wider North Atlantic marine boundary layer; measurements of NO, O3 and black carbon from the ship are consistent with a clean Northern Hemisphere marine background. Aerosol composition measurements do not indicate elevated organic material associated with clean marine air. Closer to the African coast, black carbon and NO levels start to increase, indicating greater anthropogenic influence. Lower ozone in this region is possibly associated with the increased levels of measured halocarbons, associated with the nutrient rich waters of the Mauritanian upwelling. Bromide and chloride deficits in coarse mode aerosol at both the CVAO and on D319 and the continuous abundance of inorganic gaseous halogen species at CVAO indicate significant reactive cycling of halogens. Aircraft measurements of O3 and CO show that surface measurements are representative of the entire boundary layer in the vicinity both in diurnal variability and absolute levels. Above the inversion layer similar diurnal behaviour in O3 and CO is observed at lower mixing ratios in the air that had originated from south of Cape Verde, possibly from within the ITCZ. ECMWF calculations on two days indicate very different boundary layer depths and aircraft flights over the ship replicate this, giving confidence in the calculated boundary layer depth.

Resource allocation analysis of the stochastic diffusion search

The Stochastic Diffusion Search (SDS) was developed as a solution to the best-fit search problem. Thus, as a special case it is capable of solving the transform invariant pattern recognition problem. SDS is efficient and, although inherently probabilistic, produces very reliable solutions in widely ranging search conditions. However, to date a systematic formal investigation of its properties has not been carried out. This thesis addresses this problem. The thesis reports results pertaining to the global convergence of SDS as well as characterising its time complexity. However, the main emphasis of the work, reports on the resource allocation aspect of the Stochastic Diffusion Search operations. The thesis introduces a novel model of the algorithm, generalising an Ehrenfest Urn Model from statistical physics. This approach makes it possible to obtain a thorough characterisation of the response of the algorithm in terms of the parameters describing the search conditions in case of a unique best-fit pattern in the search space. This model is further generalised in order to account for different search conditions: two solutions in the search space and search for a unique solution in a noisy search space. Also an approximate solution in the case of two alternative solutions is proposed and compared with predictions of the extended Ehrenfest Urn model. The analysis performed enabled a quantitative characterisation of the Stochastic Diffusion Search in terms of exploration and exploitation of the search space. It appeared that SDS is biased towards the latter mode of operation. This novel perspective on the Stochastic Diffusion Search lead to an investigation of extensions of the standard SDS, which would strike a different balance between these two modes of search space processing. Thus, two novel algorithms were derived from the standard Stochastic Diffusion Search, ‘context-free’ and ‘context-sensitive’ SDS, and their properties were analysed with respect to resource allocation. It appeared that they shared some of the desired features of their predecessor but also possessed some properties not present in the classic SDS. The theory developed in the thesis was illustrated throughout with carefully chosen simulations of a best-fit search for a string pattern, a simple but representative domain, enabling careful control of search conditions.

Convergence analysis of stochastic diffusion search

In this paper we present a connectionist searching technique - the Stochastic Diffusion Search (SDS), capable of rapidly locating a specified pattern in a noisy search space. In operation SDS finds the position of the pre-specified pattern or if it does not exist - its best instantiation in the search space. This is achieved via parallel exploration of the whole search space by an ensemble of agents searching in a competitive cooperative manner. We prove mathematically the convergence of stochastic diffusion search. SDS converges to a statistical equilibrium when it locates the best instantiation of the object in the search space. Experiments presented in this paper indicate the high robustness of SDS and show good scalability with problem size. The convergence characteristic of SDS makes it a fully adaptive algorithm and suggests applications in dynamically changing environments.

Small-world effects in lattice stochastic diffusion search

Stochastic Diffusion Search is an efficient probabilistic bestfit search technique, capable of transformation invariant pattern matching. Although inherently parallel in operation it is difficult to implement efficiently in hardware as it requires full inter-agent connectivity. This paper describes a lattice implementation, which, while qualitatively retaining the properties of the original algorithm, restricts connectivity, enabling simpler implementation on parallel hardware. Diffusion times are examined for different network topologies, ranging from ordered lattices, over small-world networks to random graphs.