The Chemical Space Project

One of the simplest questions that can be asked about molecular diversity is how many organic molecules are possible in total? To answer this question, my research group has computationally enumerated all possible organic molecules up to a certain size to gain an unbiased insight into the entire chemical space. Our latest database, GDB-17, contains 166.4 billion molecules of up to 17 atoms of C, N, O, S, and halogens, by far the largest small molecule database reported to date. Molecules allowed by valency rules but unstable or nonsynthesizable due to strained topologies or reactive functional groups were not considered, which reduced the enumeration by at least 10 orders of magnitude and was essential to arrive at a manageable database size. Despite these restrictions, GDB-17 is highly relevant with respect to known molecules. Beyond enumeration, understanding and exploiting GDBs (generated databases) led us to develop methods for virtual screening and visualization of very large databases in the form of a “periodic system of molecules” comprising six different fingerprint spaces, with web-browsers for nearest neighbor searches, and the MQN- and SMIfp-Mapplet application for exploring color-coded principal component maps of GDB and other large databases. Proof-of-concept applications of GDB for drug discovery were realized by combining virtual screening with chemical synthesis and activity testing for neurotransmitter receptor and transporter ligands. One surprising lesson from using GDB for drug analog searches is the incredible depth of chemical space, that is, the fact that millions of very close analogs of any molecule can be readily identified by nearest-neighbor searches in the MQN-space of the various GDBs. The chemical space project has opened an unprecedented door on chemical diversity. Ongoing and yet unmet challenges concern enumerating molecules beyond 17 atoms and synthesizing GDB molecules with innovative scaffolds and pharmacophores.

Stereoselective virtual screening of the ZINC database using atom pair 3D-fingerprints

Background Tools to explore large compound databases in search for analogs of query molecules provide a strategically important support in drug discovery to help identify available analogs of any given reference or hit compound by ligand based virtual screening (LBVS). We recently showed that large databases can be formatted for very fast searching with various 2D-fingerprints using the city-block distance as similarity measure, in particular a 2D-atom pair fingerprint (APfp) and the related category extended atom pair fingerprint (Xfp) which efficiently encode molecular shape and pharmacophores, but do not perceive stereochemistry. Here we investigated related 3D-atom pair fingerprints to enable rapid stereoselective searches in the ZINC database (23.2 million 3D structures). Results Molecular fingerprints counting atom pairs at increasing through-space distance intervals were designed using either all atoms (16-bit 3DAPfp) or different atom categories (80-bit 3DXfp). These 3D-fingerprints retrieved molecular shape and pharmacophore analogs (defined by OpenEye ROCS scoring functions) of 110,000 compounds from the Cambridge Structural Database with equal or better accuracy than the 2D-fingerprints APfp and Xfp, and showed comparable performance in recovering actives from decoys in the DUD database. LBVS by 3DXfp or 3DAPfp similarity was stereoselective and gave very different analogs when starting from different diastereomers of the same chiral drug. Results were also different from LBVS with the parent 2D-fingerprints Xfp or APfp. 3D- and 2D-fingerprints also gave very different results in LBVS of folded molecules where through-space distances between atom pairs are much shorter than topological distances. Conclusions 3DAPfp and 3DXfp are suitable for stereoselective searches for shape and pharmacophore analogs of query molecules in large databases. Web-browsers for searching ZINC by 3DAPfp and 3DXfp similarity are accessible at www.gdb.unibe.ch webcite and should provide useful assistance to drug discovery projects.

Time and space partition platform for safe and secure flight software.

There are a number of research and development activities that are exploring Time and Space Partition (TSP) to implement safe and secure flight software. This approach allows to execute different real-time applications with different levels of criticality in the same computer board. In order to do that, flight applications must be isolated from each other in the temporal and spatial domains. This paper presents the first results of a partitioning platform based on the Open Ravenscar Kernel (ORK+) and the XtratuM hypervisor. ORK+ is a small, reliable real-time kernel supporting the Ada Ravenscar Computational model that is central to the ASSERT development process. XtratuM supports multiple virtual machines, i.e. partitions, on a single computer and is being used in the Integrated Modular Avionics for Space study. ORK+ executes in an XtratuM partition enabling Ada applications to share the computer board with other applications.

Tecnología de registro y reproducción sonora para entornos de realidad virtual

Este proyecto de fin de carrera tiene como objetivo obtener una visión detallada de los sistemas y tecnologías de grabación y reproducción utilizadas para aplicaciones de audio 3D y entornos de realidad virtual, analizando las diferentes alternativas existentes, su funcionamiento, características, detalles técnicos y sus ámbitos de aplicación. Como punto de partida se estudiará la teoría psicoacústica y la localización de fuentes sonoras en el espacio, base para el estudio de los sistemas de audio 3D. Se estudiará tanto la espacialización sonora en un espacio real y la espacialización virtual (simulación mediante procesado de información de la localización de fuentes sonoras), en los que intervienen algunos fenómenos acústicos y psicoacústicos como ITD, o diferencia de tiempo que existe entre una señal acústica que llega a los pabellones auditivos, la ILD, o diferencia de intensidad o amplitud que hay entre la señal que llega a los pabellones auditivos y la localización espacial mediante otra serie de mecanismos biaurales. Tras una visión general de la teoría psicoacústica y la espacialización sonora, se analizarán con detalle los elementos de grabación y reproducción existentes para audio 3D. Concretamente, a lo largo del proyecto se profundizará en el funcionamiento del sistema estéreo, caracterizado por el posicionamiento sonoro mediante la utilización de dos canales; del sistema biaural, caracterizado por reconstruir campos sonoros mediante el uso de las HRTF; de los sistemas multicanal, detallando gran parte de las alternativas y configuraciones existentes; del sistema Ambiophonics, caracterizado por implementar filtros de cruce; del sistema Ambisonics, y sus diferentes formatos y técnicas de codificación y decodificación; y del sistema Wavefield Synthesis, caracterizado por recrear ambientes sonoros en grandes espacios. ABSTRACT This project aims to get a detailed view of recording and reproducing systems and technologies used to 3D audio applications and virtual reality environments, analyzing the different alternatives available, their functioning, features, technical details and their different scopes of applications. As a starting point, will be studied the psychoacoustic theory and the localization of sound sources in space, basis for the 3D audio study. Will be studied both the spacialization of sound sources in real space as virtual spatialization of sound sources (simulation by information processing of localization of sound sources), in which involves some acoustic and psychoacoustic phenomena like ITD (or the Interaural time difference), the ILD, (or the Interaural Level Difference) and spatial localization by another set of binaural mechanisms. After a general overview of the psychoacoustics theory and the sound spatialization, will be analyzed in detail existing methods of recording and reproducing for 3D audio. Specifically, during the project will analyze the characteristics of the stereo systems, characterized by sound positioning using two channels; the binaural systems, characterized by reconstructing sound fields by using the HRTF; the multichannel systems, detailing many of the existing alternatives and configurations; the Ambiophonics system, which is characterized by implementing crosstalk elimination techniques; the Ambiosonics system, and its various formats and encoding and decoding techniques; and the Wavefield Synthesis system, characterized by recreate soundscapes in large spaces.

En un intervalo del límite : una nueva lectura del movimiento moderno desde la realidad virtual de lo ambiguo

Esta tesis doctoral busca estudiar el espacio desde la premisa de que el espacio es, fundamentalmente, lo intermedio. El entre, lo que hay entre las cosas mismas y que les da, precisamente, su definición como cosas en un constante proceso de delimitación. Este entre, lo que hay entre las cosas, no es sin embargo un resto que queda, sino bien al contrario el principio activo que hace que las cosas, desde lo que hay alrededor, se configuren en su ser sensible y puedan percibirse. El entre, lo intermedio, no es así una línea, un corte puro, sino un intervalo, un espacio en sí mismo, un ámbito en que se desarrolla un proceso. Es por tanto un espacio de formación, en el que las cosas aún no son y ya están siendo, un intervalo ambiguo pleno de virtualidades, unas desplegadas otras que permanecen en espera, siempre en movimiento. Es la hipótesis principal de esta tesis que en el llamado Movimiento Moderno en la arquitectura del siglo veinte esta condición ambigua del límite se pone de manifiesto como la raíz articuladora de los cambios espaciales y formales que definen su ser y su estética. Para desarrollar esta hipótesis, se parte de una doble premisa: por una parte, como un entre que es en sí misma, la arquitectura se encuentra delimitada por las disciplinas artísticas contemporáneas, especialmente pintura y escultura y a la vez las delimita. Por tanto, se explorarán una serie de momentos claves en las vanguardias de comienzos del siglo veinte en paralelo a una serie de arquitecturas contemporáneas para estudiar esta doble dialéctica entre límites. Por otra parte, y entendiendo que lo propio de la arquitectura es el espacio, se estudiarán en profundidad las concepciones espaciales que en la física y la estética del finales del siglo diecinueve y principios del veinte se desarrollan, para comprender cómo estas nuevas concepciones, centradas en las ideas de relatividad y de espacio-tiempo como magnitudes interlimitadas, determinan a su vez las concepciones espaciales que se desarrollan simultáneamente en las artes plásticas y en la arquitectura. La tríada espacio/tiempo/luz regirá este recorrido, en un doble camino: a través de la física y la teoría del arte, y a través de la arquitectura y las artes plásticas. Se trata por tanto de incardinar la arquitectura en su contexto artístico y científico, y comprobar cómo la comprensión del espacio como un entre, como un intervalo del límite y no como un absoluto trascendente, se generaliza en dichos ámbitos en una exploración paralela que condiciona los resultados en todos ellos y que define, por tanto, la arquitectura de la modernidad como una arquitectura del entre. El encuadre enmarca como motivo principal el Movimiento Moderno a través de la figura de Le Corbusier. Se muestra el modo en que los recursos y mecanismos empleados provocan el encuentro del espacio indecible a través de la polifonía de las artes. Desde el espaciamiento del límite, su borradura, su ambigüedad, producidos mediante el entrelazamiento de los recursos artísticos, la continuidad de lo lineal, el encabalgamiento, el maridaje, la ambivalencia, la relatividad del color y la luz, el intersticio. Ello se analiza a través de la obra de le Corbusier, destacando la dialéctica entre Le Cheminée y Nature morte aux nombreux objets; Ma maison y el pabellón del Zurichhorn; Unité y L’espace indicible. Aclaradas las premisas fundamentales y las consecuencias inmediatas para la arquitectura del Movimiento Moderno, la cuarta parte y final de la tesis, mucho más breve que las anteriores, expone una primera aproximación a las consecuencias que todo esto ha tenido en un momento liminal también: el comienzo de la postmodernidad. En realidad se trata de una apertura a lo que ha de venir, pues establecida la operatividad de la hipóteisi inicial, se trata aquí solamente de abrir el camino a una interpretación que en realidad escapa del alcance de esta tesis. Así se deja apuntado cómo, a través de la obra de tres arquitectos, teóricos y artistas trabajando en los años setenta y comienzos de los ochenta del pasado siglo, una comprensión más clara de la revolución moderna precipitada por esta nueva comprensión del espacio como límite-entre queda patente. Chamberworks de Daniel Libeskind, Wexner Center for the Visual Arts de Peter Eisenman y Manhattan Transcripts de Bernard Tschumi servirían de privilegiados ejemplo. Como queda patente que las consecuencias de todo ello aún las estamos sintiendo en nuestra contemporaneidad. ABSTRACT This thesis aims to study the space from the premise that space is mainly the in-between. The in-between, what is in-between the things themselves and gives them precisely its definition as things in a constant process of delimitation. This in-between, what is in between things, is not a remnant that remains, but on the contrary it is the active ingredient that produces things from what is around, that configures them in a sensitive to be perceived. The in-between, the intermediate, is not a line, a pure cut, but an interval, a space in itself, an area in which a process is developed. It is therefore a space in development, where things are still not and already been, delimiting an ambiguous range full of potentialities, some present and others that remain only as virtualities. It is the main hypothesis of this thesis that in the so-called Modern Movement in the architecture of the twentieth century this ambiguous boundary condition is revealed as the result of the articulatation of spatial and formal changes. To develop this hypothesis, I posit this double premise: On the one hand, as an in-between which is in itself, architecture is defined by contemporary artistic disciplines, especially painting and sculpture and simultaneously defines them. Therefore, a number of key moments in the avantgarde of the early twentieth century in parallel with a number of contemporary architecture to study this double dialectic between boundaries will be explored. On the other hand, and considering that the “essence” of the architecture is space, I will study in depth the spatial concepts in physics and aesthetics of late-nineteenth century and early twentieth century to understand how these new concepts centered on the ideas of relativity and space-time as interlimited magnitudes in turn determine the spatial conceptions that take place simultaneously in the visual arts and architecture. The space / time / light triad governs this journey in a double way: through physics and theory of art, and through architecture and the arts. The aim is to anchor architecture in its artistic and scientific context, and to see how the understanding of space as an in-between interval and not as an absolute transcendent determines the results in all of them, defining, therefore, the architecture of modernity as an architecture of the in-between. The frame of the study is centered in the modern movement through the figure of Le Corbusier and how rthe different resources and mechanisms employed provoke an unspeakable space of encounter through the polyphony of the arts. From the spacing of the limit, its erasure, its ambiguity, produced by the intertwining of artistic resources to continuity of the linear, the marriage, the ambivalence, the relativity of color and light, the gap. All this is analyzed through the work of Le Corbusier, highlighting the dialectic between Le Cheminée and Nature morte aux nombreux objets, Ma maison and Zürichhorn pavilion, Unité and L’espace indicible. Once the basic premises and immediate consequences for the architecture of the Modern Movement are set, the fourth and final part of the thesis aims to explore the impact that all this has had in another liminal time: the beginning of postmodernism. Of course, this part is shorter, in fact it is more a prospective survey and an opening of possibilities than a truly articulated body of theory, since the conceptual core of this thesis has been developed in the central part. Hence, through the work of three architects, theorists and artists working in the seventies and early eighties of last century, a clearer understanding of the modern revolution precipitated by this new understanding of space as a boundary- between is proposed. Chamberworks by Daniel Libeskind, Wexner Center for the Visual Arts by Peter Eisenman and Manhattan Transcripts by Bernard Tschumi will exemplify this approach. The consequences of all this are still haunting our contemporaneity.

COMUNICAÇÃO & ASTRONOMIA: UMA UNIÃO VIRTUAL Estudos para uma teoria de comunicação organizacional on-line a partir do caso Rede de Astronomia Observacional REA/Brasil

A tese Comunicação & Astronomia, uma união virtual aborda o universo da comunicação virtual, das organizações virtuais, da ciência virtual. Um universo novo e emocionante onde a relação assíncrona espaço-temporal é o fator comum a todos os atores sociais envolvidos. O universo do virtual, das ferramentas de comunicação relacionadas às novas tecnologias, do ciberespaço, da existência concreta de uma organização imaterial. Estes elementos abrem novos horizontes para o conhecimento e compreensão dos processos de comunicação humana e organizacional na era da revolução informacional, proporcionando a oportunidade de estabelecer uma teoria de comunicação organizacional on line. A pesquisa bibliográfica apoiou-se em três bases teóricas de referência: a comunicação mediada por computador, comunicação virtual e comunicação organizacional, estas bases tiveram ainda o suporte de um estudo de caso que constituiu o corpus da pesquisa. Pudemos então compreender como ocorre a comunicação em uma organização virtual, seus processos, ferramentas e pontos cruciais que podem ser resumidos no fator motivacional necessário ao estímulo à interação virtual cooperativa, necessidade de construção e manutenção de imagem institucional forte que delimite a organização no ciberespaço e definição clara dos códigos de conduta da organização virtual.(AU)

COMUNICAÇÃO & ASTRONOMIA: UMA UNIÃO VIRTUAL Estudos para uma teoria de comunicação organizacional on-line a partir do caso Rede de Astronomia Observacional REA/Brasil

A tese Comunicação & Astronomia, uma união virtual aborda o universo da comunicação virtual, das organizações virtuais, da ciência virtual. Um universo novo e emocionante onde a relação assíncrona espaço-temporal é o fator comum a todos os atores sociais envolvidos. O universo do virtual, das ferramentas de comunicação relacionadas às novas tecnologias, do ciberespaço, da existência concreta de uma organização imaterial. Estes elementos abrem novos horizontes para o conhecimento e compreensão dos processos de comunicação humana e organizacional na era da revolução informacional, proporcionando a oportunidade de estabelecer uma teoria de comunicação organizacional on line. A pesquisa bibliográfica apoiou-se em três bases teóricas de referência: a comunicação mediada por computador, comunicação virtual e comunicação organizacional, estas bases tiveram ainda o suporte de um estudo de caso que constituiu o corpus da pesquisa. Pudemos então compreender como ocorre a comunicação em uma organização virtual, seus processos, ferramentas e pontos cruciais que podem ser resumidos no fator motivacional necessário ao estímulo à interação virtual cooperativa, necessidade de construção e manutenção de imagem institucional forte que delimite a organização no ciberespaço e definição clara dos códigos de conduta da organização virtual.(AU)

El salto virtual del debate colectivo: potencialidades y limitaciones de las nuevas plataformas para la deliberación y la toma de decisiones ciudadanas

Las nuevas Tecnologías de la Información y la Comunicación han emergido en los últimos años como el principal cambio en la conformación de redes de acción colectiva y en la mutación de los canales que sustentan el debate público. En este ámbito, la reciente aparición de plataformas virtuales para la deliberación ha contribuido a transformar profundamente la naturaleza de la acción participativa, tanto en su concepción expresiva como instrumental. Dichas nuevas herramientas se caracterizan esencialmente por proporcionar un soporte que aúna la posibilidad del debate plural en torno a asuntos políticos y cambio social, y a la vez integra en él (en grados muy diversos como se comprobará) la toma de decisiones como fruto de la deliberación colectiva. Estas propiedades les dotan de una naturaleza que no es asimilable a aplicaciones virtuales de comunicación política netamente discursivas, y perfilan un objetivo expreso de simular las características propias de un ágora presencial, ofreciendo un incentivo participativo a través de su intento por solventar las limitaciones y condicionantes espacio-temporales o de amplitud poblacional propios de la interacción comunicativa tradicional. La integración del componente expresivo e instrumental de la participación ciudadana que abordan este tipo de plataformas y aplicaciones, plantea sin duda un reto en el ya amplio debate académico en torno al alcance real de Internet como esfera significativa para conformación de voluntad colectiva y cambio político, que hasta ahora quedaba escindido entre escépticos y partidarios. La propuesta se articula a partir de la exploración y análisis comparativo de las principales plataformas y aplicaciones virtuales en español para la deliberación y la toma de decisiones colectivas. A efectos de análisis se establecen criterios evaluativos combinando las propuestas dimensionales desarrolladas por Coleman y Gøtze (2001) y Dahlgren (2005) para cuestiones relativas a Internet, comunicación y deliberación política, con especial énfasis en el análisis diferencial de las capacidades estructurales e interactivas de cada una de las herramientas.

A probabilistic switch model of information flow in social networks: Application for virtual circuits to organizational design

Network building and exchange of information by people within networks is crucial to the innovation process. Contrary to older models, in social networks the flow of information is noncontinuous and nonlinear. There are critical barriers to information flow that operate in a problematic manner. New models and new analytic tools are needed for these systems. This paper introduces the concept of virtual circuits and draws on recent concepts of network modelling and design to introduce a probabilistic switch theory that can be described using matrices. It can be used to model multistep information flow between people within organisational networks, to provide formal definitions of efficient and balanced networks and to describe distortion of information as it passes along human communication channels. The concept of multi-dimensional information space arises naturally from the use of matrices. The theory and the use of serial diagonal matrices have applications to organisational design and to the modelling of other systems. It is hypothesised that opinion leaders or creative individuals are more likely to emerge at information-rich nodes in networks. A mathematical definition of such nodes is developed and it does not invariably correspond with centrality as defined by early work on networks.

COMUNIDADE VIRTUAL E COMUNICAÇÃO: O site da Igreja Adventista do Sétimo Dia

O desenvolvimento das novas tecnologias de comunicação e informação não representa apenas uma nova forma de transmitir conteúdos informacionais às pessoas. Ao se refletir nas novas possibilidades de atuação à distância, permitida pela mídia interativa on-line, percebese uma mudança significativa na postura comportamental das pessoas em suas interações nas relações sociais básicas. Há uma transformação ocorrendo no conceito de comunidade, visto que as novas e emergentes formas de comunicação, próprias do atual cenário tecnológico, passam a coabitar com as formas tradicionais de comunidade. Esta metamorfose seria produto de uma tentativa de agregação das práticas sociais realizadas nas comunidades reais dentro de um espaço virtual. Surgem assim as chamadas comunidades virtuais, que carregam consigo uma nova dinâmica de atuação a distância disjunta de contextos sociais imediatos. Através da metodologia de estudo de caso, buscou-se conhecer como as coabitações de formas tradicionais e emergent es de comunidades estão convivendo e interagindo. Além disso, procurou-se conhecer quais são os resultados obtidos das trocas informacionais e relacionais ocorridas no ciberespaço. A investigação se deu a partir do estudo de caso de um site da Igreja Adventista do Sétimo Dia, no qual foram utilizadas entrevistas, observação direta e observação participativa como fontes de evidência. Os resultados obtidos da investigação sugerem que o indivíduo corpóreo deseja viver dentro de uma nova ambiência regida pela fluidez digital, pois esta se apresenta como um meio no qual as trocas informacionais se dão de forma efetiva e responsiva, ao mesmo tempo em que relacionamentos sociais podem ser engendrados, confirmados e mantidos.(AU)

COMUNICAÇÃO & ASTRONOMIA: UMA UNIÃO VIRTUAL Estudos para uma teoria de comunicação organizacional on-line a partir do caso Rede de Astronomia Observacional REA/Brasil

A tese Comunicação & Astronomia, uma união virtual aborda o universo da comunicação virtual, das organizações virtuais, da ciência virtual. Um universo novo e emocionante onde a relação assíncrona espaço-temporal é o fator comum a todos os atores sociais envolvidos. O universo do virtual, das ferramentas de comunicação relacionadas às novas tecnologias, do ciberespaço, da existência concreta de uma organização imaterial. Estes elementos abrem novos horizontes para o conhecimento e compreensão dos processos de comunicação humana e organizacional na era da revolução informacional, proporcionando a oportunidade de estabelecer uma teoria de comunicação organizacional on line. A pesquisa bibliográfica apoiou-se em três bases teóricas de referência: a comunicação mediada por computador, comunicação virtual e comunicação organizacional, estas bases tiveram ainda o suporte de um estudo de caso que constituiu o corpus da pesquisa. Pudemos então compreender como ocorre a comunicação em uma organização virtual, seus processos, ferramentas e pontos cruciais que podem ser resumidos no fator motivacional necessário ao estímulo à interação virtual cooperativa, necessidade de construção e manutenção de imagem institucional forte que delimite a organização no ciberespaço e definição clara dos códigos de conduta da organização virtual.(AU)

On a Virtual Learning Environment

Education in the Information Society is based on asynchronism in time and space, interactivity and virtual restructuring of the educational space. One way to implement such a model of training is web-based - use of the WWW as a virtual environment to access educational materials or to organize the learning process. This work presents a virtual learning environment (VLE) developed for students and made up of modules of dynamically changing content implemented by authorized users. The aim is, through advanced technology for e-learning, testing and self-testing to stimulate students’ activity to focus their potential on the acquisition of the necessary knowledge, skills and competences. The VLE was developed under the Human Resources Development Operational Programme.

Self-adaptive probabilistic roadmap generation for intelligent virtual agents

Agents inhabiting large scale environments are faced with the problem of generating maps by which they can navigate. One solution to this problem is to use probabilistic roadmaps which rely on selecting and connecting a set of points that describe the interconnectivity of free space. However, the time required to generate these maps can be prohibitive, and agents do not typically know the environment in advance. In this paper we show that the optimal combination of different point selection methods used to create the map is dependent on the environment, no point selection method dominates. This motivates a novel self-adaptive approach for an agent to combine several point selection methods. The success rate of our approach is comparable to the state of the art and the generation cost is substantially reduced. Self-adaptation therefore enables a more efficient use of the agent's resources. Results are presented for both a set of archetypal scenarios and large scale virtual environments based in Second Life, representing real locations in London.

Regrouping metric-space search index for search engine size adaptation

This work contributes to the development of search engines that self-adapt their size in response to fluctuations in workload. Deploying a search engine in an Infrastructure as a Service (IaaS) cloud facilitates allocating or deallocating computational resources to or from the engine. In this paper, we focus on the problem of regrouping the metric-space search index when the number of virtual machines used to run the search engine is modified to reflect changes in workload. We propose an algorithm for incrementally adjusting the index to fit the varying number of virtual machines. We tested its performance using a custom-build prototype search engine deployed in the Amazon EC2 cloud, while calibrating the results to compensate for the performance fluctuations of the platform. Our experiments show that, when compared with computing the index from scratch, the incremental algorithm speeds up the index computation 2–10 times while maintaining a similar search performance.

Self-adapting parallel metric-space search engine for variable query loads

This research focuses on automatically adapting a search engine size in response to fluctuations in query workload. Deploying a search engine in an Infrastructure as a Service (IaaS) cloud facilitates allocating or deallocating computer resources to or from the engine. Our solution is to contribute an adaptive search engine that will repeatedly re-evaluate its load and, when appropriate, switch over to a dierent number of active processors. We focus on three aspects and break them out into three sub-problems as follows: Continually determining the Number of Processors (CNP), New Grouping Problem (NGP) and Regrouping Order Problem (ROP). CNP means that (in the light of the changes in the query workload in the search engine) there is a problem of determining the ideal number of processors p active at any given time to use in the search engine and we call this problem CNP. NGP happens when changes in the number of processors are determined and it must also be determined which groups of search data will be distributed across the processors. ROP is how to redistribute this data onto processors while keeping the engine responsive and while also minimising the switchover time and the incurred network load. We propose solutions for these sub-problems. For NGP we propose an algorithm for incrementally adjusting the index to t the varying number of virtual machines. For ROP we present an ecient method for redistributing data among processors while keeping the search engine responsive. Regarding the solution for CNP, we propose an algorithm determining the new size of the search engine by re-evaluating its load. We tested the solution performance using a custom-build prototype search engine deployed in the Amazon EC2 cloud. Our experiments show that when we compare our NGP solution with computing the index from scratch, the incremental algorithm speeds up the index computation 2{10 times while maintaining a similar search performance. The chosen redistribution method is 25% to 50% faster than other methods and reduces the network load around by 30%. For CNP we present a deterministic algorithm that shows a good ability to determine a new size of search engine. When combined, these algorithms give an adapting algorithm that is able to adjust the search engine size with a variable workload.