Abstract

Ray Tracing is one of the most important rendering techniques used in computer graphics. Ray traced images are more accurate and photo-realistic as compared to direct rendering. Ray Tracing was earlier considered impractical for rendering scenes at interactive rates because of its high computational cost. However, with the advancements in modern Graphics Processing Units (GPU) and CPUs, ray tracing at interactive rates has now become possible. Parametric patches have been widely used in many fields to describe a model accurately. They provide a compact and effective way of representing an object and also possess the ability to remain curved on zooming. Ray Tracing of parametric surfaces was considered to be a static process because of the high complexity of intersection algorithms. With advancements in ray tracing techniques and high compute power devices, recent works on ray tracing parametric surfaces have reported near interactive results. We present a scheme for interactive ray tracing of Bezier bicubic patches using Newton iteration in this dissertation. We use a mixed hierarchy representation as the acceleration structure. This has a bounding volume hierarchy above the patches and a fixed depth subpatch tree below it. This helps reduce the number of ray-patch intersections that needs to be evaluated and provides good initialization for the iterative step, keeping the memory requirements low. We use Newton iteration on the generated list of ray patch intersections in parallel. Our method can exploit the cores of the CPU and the GPU with OpenMP on the CPU and CUDA on the GPU by sharing work between them according to their relative speeds. A data parallel framework is used throughout starting with a list of rays, which is transformed to a list of ray-patch intersections by traversal and then to intersections and a list of secondary rays by root finding. We are able to significantly outperform multi-core CPU implementation and previous GPU implementation using the mixed hierarchy model. Shadow and reflection rays can be handled exactly in the same manner as a result. The secondary ray list is again sent to the starting of the algorithm to perform mixed hierarchy traversal and intersection tests. We perform fixed depth multiple bounce ray tracing. We also show how our method extends easily to generate soft shadows using area light sources. These effects provide higher realism to the ray traced images. We render a million pixel image of the Teapot model at 125 fps on a system with an Intel i7 920 and a Nvidia GTX580 for primary rays only and at about 65 fps with one pass of shadow and refection rays. We are able to ray trace bigguy in a box scene with multi-bounce at near interactive rates. We get a speed up of about 5-30x for our hybrid Newton's method implementation over our optimized CPU implementation and about 20-50x over previous GPU implementation of Kajiya's method to ray trace Bezier surfaces. Traversing the mixed hierarchy is the most time consuming step of the algorithm. We expect to see better performance with greater cache size. The hybrid model would be optimal for systems with equal compute power of CPU and GPU. The proposed model is suitable for parallel architecture, hybrid systems and multi-GPU systems. Global illumination effects have recently started gaining popularity with the progress in parallel architecture. We extend our algorithm to global illumination effects to demonstrate its capabilities. Global illumination effects have not been reported for parametric surfaces. We perform path tracing by tracing a large number of rays per pixel for a fixed depth. Number of samples greatly increase the quality of the image generated. We also perform more advanced effects like ambient occlusion, depth of field, motion blur and glossy surface. We are able to path trace a $512 imes 512$ image with 1000 samples per pixel in about 165 seconds. We report timings for other advanced effects. We find that ray coherence is essential for optimal performance when ray tracing Bezier surfaces on the GPU. Size of the dataset also plays a small part in the overall rendering times. The work done in this dissertation should serve as the starting point to optimally render Bezier surfaces with advanced global illumination techniques.

Abstract

Computational advertising, popularly known as online advertising or web advertising, refers to nding the most relevant ads matching a particular context on the web. It is a scienti c sub-discipline at the intersection of information retrieval, statistical modeling, machine learning, optimization, large scale search and text analysis. The core problem addressed in Computational Advertising (CA) is of match making between the ads, context and user. Depending upon the context, ads are shown based on two kinds of targeting { content targeting and user targeting. Content targeting involves displaying ads relevant to the content being targeted. Retrieving ads for a query on a search page (known as Sponsored Search) or for a third party web-page content (known as Contextual Advertising) are instances of content level targeting. User level targeting involves modeling user's recent interests based on their activities and showing ads relevant to user's interest. Recent outburst in the usage of social networks and recommender systems has made targeting of ads based on user's prole a popular method. Within user modeling, ads can usually be targeted based on user's recent activity or based on user's social contacts. Net ix, Amazon, StumbleUpon are some examples that recommend ads/sponsored content based on user's recent activities. Facebook is a common example of targeting ads based on user's social contacts and reach in a social network. This thesis aims at analyzing the problems and contributing towards solutions to these two types of targeting. Specically, the thesis work plans on leveraging various user interactions, advertiser related and contextual information for dierent types of targeted advertising. The research work deals with identication of various factors that contribute in retrieval and ranking the most relevant set of ads that match best with the context. For this purpose, information associated with the user, publisher and advertiser is leveraged. Given the proprietary nature of datasets on ad targeting, there is a scarcity of public datasets. Experiments involved in this thesis provide substantial amount of labeled data that can also be used to tune future ad targeting systems. The research work in this thesis primarily focuses on the problem of retrieving relevant ads for dierent content types. This thesis proposes a couple of semantic solutions to the problem of retrieving ads for a given content. As ads that are being retrieved are short, often there is a vocabulary mismatch between the query and the ads. This problem renders traditional information retrieval techniques insucient for the task of ad retrieval. We propose two techniques based on modeling the latent topics/concepts from the ads and the content for retrieving relevant ads. The idea is to transform the ads and the content into lower topical/conceptual dimension and retrieve ads in that lower dimensional space. This lower dimensional transformation helps reduce vocabulary mismatch to some extent. The thesis begins with simplistic topic modeling approach and then builds on top of it with the conceptual modeling approach. These techniques are studied extensively for a variety of dierent content types like user search query, third party web pages and microblogs such as tweets. The proposed semantic techniques are compared with various state-of-the-art retrieval techniques for the problem of ad retrieval. The proposed techniques perform better than all the baseline state-of-the-art approaches. The performance improvement for the proposed best performing semantic method over the best performing baseline ranges from around 10% to as much as 28%. This performance improvement of the proposed techniques is consistent over dierent content types like search query, web pages and microblog. Considering the hardness of the ad retrieval problem, the percentage improvement shown by the proposed method over dierent content types is impressive. In addition, we also study the combination of various techniques on this problem of retrieving ads. It turns out that various combinations of semantic techniques proposed in this thesis also perform better than combinations of dierent baseline approaches. This performance improvement was consistently observed for several metrics like precision @ n, precision-recall etc. All the performance improvements were found to be statistically signicant at very good signicance levels (96% to 99%). The thesis also studies matching of ads from user targeting perspective. We look at the targeting of users based on their actions and their prole. The idea here is to model the user in order to facilitate better matching of relevant ads with the user context. We study following dierent user contexts { user and their prole, user's social contacts, user's action. The user targeting study aims at exploring various factors pertaining to a user that aect the targeting of ads. To the best of our knowledge,

Abstract

Technology has enabled the rapid creation and easy storage of vast amounts of digital spoken content. In this context, a reliable and fast way to search through spoken content has become a hot topic of research in speech technology. Query-by-Example Spoken Term Detection (QbE-STD) is a framework for searching a speech database using spoken queries. The aim of this work is to develop an improved dynamic time warping (DTW) based QbE-STD by exploiting syllable boundary information. Within this scope, novel contributions are made within two research themes, i.e., locating the syllable nuclei and thus subsequently locating the syllable boundaries and, using these syllable boundaries to improve the accuracy of the DTW based QbE-STD system. Speech can be segmented into syllables by identifying the syllable nuclei, which are points of high sonority. The excitation peaks in the linear prediction (LP) residual and the formant peaks can be interpreted as perceptually significant point features which contribute to the loudness of speech. In this paper, the use of these two point features is described for the use of detecting syllable nuclei. Each of these evidences contain information about different aspects of speech production, namely the glottal vibrations and the time varying vocal tract system. Thus it is possible that they contain complementary information about the syllable nuclei. Performance of the proposed syllable nuclei detection algorithm is evaluated for the TIMIT, Switchboard and the NTIMIT corpus. The proposed method performs comparably against two other state of the art syllable nuclei detection methods, and it is very fast requiring no training. Important acoustic events in speech occur at the transition boundaries between two sounds. These acoustic events carry sufficient information so as to be useful for QbE-STD. The syllable boundaries and the transition boundaries within the syllable are anchor points where major acoustic events occur. In this work, the use of these two types of anchor points are explored for feature selection. This initial feature selection method serves as a way to prune the search space for QbE-STD for later re-ranking. Results are demonstrated for the MediaEval2012 Spoken Web Search database. The performance after re-ranking the pruned results are on par or better than the standard results returned by the DTW technique.

Abstract

In recent years, the microblogging services like Twitter has become a major tool for sharing events, expressing opinions and communicating with friends. Several thousand of microblogs are posted each second describing the ongoing events around the world. Because of this recent rise in the popularity and size of social media, there is a growing need for system that can extract useful information from social media. The use of limited words (140 characters), special vocabulary with incomplete sentences and emoticons, heavy use of abbreviations and misspellings make traditional text analysis methods less effective on Twitter. Entity Linking is the task of extracting semantics from text by linking the entities present within the text to the knowledge base. For example, given a text “India is my country”, we need to extract important mentions like ‘India’ and link them to their corresponding Wikipedia pages. Entity Linking is an important task as it not only provides important meta-information about the linked entities but also helps us in extracting the relations among various entities present within the text. Meta-information and relations are really helpful in extracting other important information like documents’ topics etc. Since this also removes the problem of synonymy and polysemy, therefore it is more easy for computers to analyse the text. So, entity linking is really helpful in making computers understand the text usually meant for human consumption. In this thesis, we device a method for efficient entity linking. We have devised various features that helps in detecting and linking entities present within the tweet. Firstly, the mentions present within the tweets are identified. We experimented various approaches like heuristics based approach, probabilistic approach and sequence labelling based approach for detecting mentions in the tweet. Finally, we proposed a classification approach for mention detection. Along with identification, the detected mentions are also ranked based on their predicted informativeness content. The user can select the mentions by setting the threshold on the ranks based on application. All the approaches are evaluated using various datasets like NEEL Challenge Dataset, User Dataset, TagMe Dataset and IITB dataset. Classification based methods performs best on all the datasets with performance of 0.59 F-measure on NEEL Dataset. The detected mentions are then disambiguated on the basis of context. Disambiguation means selecting the best entity from the set of candidate entities for the given mention. Due to limited characters, context is usually not sufficient to disambiguate all the entities present within the tweet. So, we have also explored users’ interests and recent tweet information to improve the disambiguation on the short and noisy tweets. The information provided by users’ previous tweets is modeled to build users’ topic of interests. These interests along with the context is then used to disambiguate the entities in the users’ new tweet. We also explored trending topics information (at a particular time on Twitter) to improve entity disambiguation in the tweets. The user based approach is tested using user dataset collected from around 200 tweets of 20 users with two context modeling systems. Recent tweet information based approach is tested using the standard NEEL Dataset and tweets from recent events collected in June 2014. Experiments show that extra information based on users’ previous history and recent tweets helps in improving the performance of entity disambiguation systems. Hashtags are semantico-syntactic constructs used across various social networking and microblogging platforms to enable users to start a topic specific discussion or classify a post into a desired category. Segmenting and linking the entities present within the hashtags could therefore help in better understanding and extraction of information shared across the social media. However, due to lack in space delimiter, extracting semantics from hashtags is a non-trivial task. Most of the current state-ofthe- art social media analytics systems like Sentiment Analysis and Entity Linking tend to either ignore hashtags, or treat them as a single word. We present a context aware approach to segment and link entities in the hashtags to a knowledge base (KB) entry, based on the context within the tweet. Our approach segments and links the entities in hashtags, such that the coherence between hashtag semantics and the tweet is maximized. As the segmentation and linking is jointly modeled, the system chooses the segment that maximizes the relatedness between tweet and the hashtag. So, the best segmentation is picked based on the context, if multiple segments are possible. The approach is tested on two different datasets, one is synthetically created using NEEL Dataset and the other is manually created. We have achieved the P@1 score of 0.914 on NEEL Dataset and

Abstract

Statistical machine translation (SMT) depends heavily on parallel training data available for a language pair. This thesis addresses problems of data-sparsity and translation quality of a SMT system for English-Hindi and Indo-Aryan language pairs. We also show use of machine translation (MT) in improving speech recognition output in the scenario of a computer assisted translation (CAT) system. SMT depends heavily on parallel training data available for a language pair. We describe a MT system for English to Hindi in which we use a pre-processing module to transform English data into Hindi-Order to get better phrase alignments. Morphologically rich languages require large amounts of parallel data to adequately estimate parameters in a statistical MT system. We explore alternate strategies, given that the collection of large parallel corpora is expensive. Firstly, we explore the use of distributed representations in a language model in a Recurrent neural network based Language Model (RNNLM) framework with different linguistic features and secondly, we explore the use of lexical resources such as WordNet to overcome sparsity. The techniques used above rely on large mono-lingual data for the target language and also requires WordNet of the source language. WordNet is not available for Indo-Aryan languages except Hindi and there are not many sources available for extracting clean mono-lingual data. So we improved the translation quality of Indo-Aryan MT systems by exploring popular available techniques called ``Triangulation'' and ``System Combination'' to reduce problem of data sparsity and improve quality of the system. MT systems for other Indo-Aryan language pairs which are trained on small parallel corpora are improved using various recently developed techniques in the field of SMTs. Triangulation is a technique which has been found to be very useful in improving the translations when multilingual parallel corpora are present. Triangulation is the process of using an intermediate language as a pivot to translate a source language to a target language. We have used phrase table triangulation instead of sentence based triangulation as it gives better translations. As triangulation technique explores additional multi parallel data, it provides us with separately estimated phrase-tables which could be further smoothed using smoothing methods. The subsequent approach explores the various system combination techniques through which these triangulated systems can be combined to improve the translations. In concluding chapter of the thesis, we show the application of MT in improving the Automatic Speech Recognition (ASR) output in the scenario of ocite{*}a CAT system where a human translator translates a source language string into a target language string using different input methods such as speech and typing. In this work, we have improved the performance of speech recognition of a translator speaking in the target language, taking the advantage of source language string and synset information from WordNet. We used MT system to translate the source language string to target language. We use the semantic information we get for the words in the translated string from WordNet to bias the speech recognizer towards the gained knowledge. We perform different experiments including variation of number of hypothesis of MT and also different techniques of incorporating the semantic information. Overall we outperformed the baseline system having no semantic information by the increase in word accuracy of 1.6% for the Hindi ASR in English-Hindi system.

Abstract

Binding of gold clusters (Au3 and Au4 ) with DNA bases and extended DNA bases (x-bases) has been studied in this work. An attempt to locate the energetically low-lying minimum structures in case of Aun clusters (n=3-8) was carried out using density functional theory. Both the studies have been performed by employing high quality basis set. A number of geometrical isomers, in case of Aun clusters, was studied. The relative stabilities were then compared to determine the minima. Electronic properties such as HOMO-LUMO gaps, polarizability and dipole moments,etc., were also investigated. In gold-nucleobase complexes, all possible orientations of Au clusters with respect to the titratable sites of bases were examined. The geometric and electronic features of these complexes provided evidence for existence of non-conventional hydrogen bonds. This was further substantiated via normal mode and NBO analysis. The nucleobases, both canonical and extended forms, form stable complexes with the gold clusters considered here. Upon complexation, a marked decrease in the HOMO-LUMO gaps and ionization potentials was observed, which was more profound in case of x-bases. This study attempts to provide an insight into the stability of different-sized gold clusters and demonstrates that combining structural modifications to DNA bases and subsequent binding to gold nano particles provides an opportunity to modulate and achieve desired optico-electronic properties.

Abstract

Arithmetic and Logic Unit (ALU) is a critical component of any CPU. In ALU, adders play a major role not only in addition but also in performing many other basic arithmetic operations like subtraction, multiplication, etc. Thus realizing an efficient adder is required for better performance of an ALU and therefore the processor. Research started in late 1950s on designing efficient adder algorithms and their hardware implementation. Many designs based on serial and parallel structures have been proposed to optimize different parameters from time to time. The first contribution of this thesis is the development of an efficient adder architecture that addresses the problems for higher bit operand lengths like fan-out, wiring complexity, etc. Another important element in an ALU after adder is a multiplier. In multipliers, for reducing partial products and computing final result, multi-operand adders and fast adders are required. A special structure known as counters/compressors are typically used for designing multi-operand adders. Counters are multi-input, multi-output combinational logic circuits, which determine the number of logic 1’s in their input vectors, and generate a binary coded output vector that corresponds to this number. Large parallel counters like (15, 4), (32, 5), etc. can be constructed using this small counter and similar approach can be adopted in the case of compressors. The second contribution of the thesis is development of efficient counters and compressors for better performance of multiplier. Apart from adders and multipliers in arithmetic units, elements like, incrementer/decrementer (INC/DEC) also play a major role in an ALU and also in address generation unit. A loop algorithm, for example, often needs a increment/decrement. These operations can be realized using adders but with a cost in terms of power and area. Therefore, standalone designs or unified designs for INC/DEC are required for low power applications. The third contribution of this thesis is the design of a multi-functional INC/DEC/2's complement/Priority encoder circuit. A design for binary INC/DECs is presented that is efficient in terms of speed without compromising on power. The need to have hardware support for decimal arithmetic is increasing in recent years because of the growth in decimal data processing in commercial, financial and internet-based applications. To facilitate binary computations on the same hardware, a reconfigurable approach needs to be adopted. The fourth contribution of this thesis is the design of a new architecture for efficient Binary Coded Decimal (BCD) addition/subtraction that can be configured to perform binary addition/subtraction also. The architecture has been designed keeping in view the signed magnitude format where the adder logic itself detects the larger operand and carries out corresponding operations. Finally, novel versions of two widely used arithmetic blocks i.e., multiplier and floating point adder, are designed. Efficient and proven basic functional units described above are used to implement these blocks. Simulations of these blocks have been carried out and comparisons made with existing designs that clearly demonstrate the efficiency of proposed units. Finally, a segment of a core of a processor is designed with incorporating all the above elements resulting in an efficient architecture.

Abstract

One of the main goals of modern biotechnology and biophysics is to understand the structure and interactions of biomolecules such as nucleic acids and proteins. The complexity in understanding the living systems and the processes occurring in them primarily revolves around these biomolecules. Understanding the molecular level details of such processes is difficult and is not always possible using experimental methods. Computational methods prove to be efficient alternative tools in studying the atomistic details of molecular processes. Molecular dynamics (MD) simulation is one such method that is extremely used to study structure-function relationships of biomolecules. The present thesis has two parts: heterogeneous nucleic acids and homogeneous nucleic acids. The heterogeneous nucleic acids include DNA-RNA hybrids, locked nucleic acids and 2’-O-methyl modified duplexes that have a wide range of applications in nucleic acid-based therapies. Extensive analyses of MD trajectories suggest that the structural and energetic properties of DNA-RNA hybrids depend on the extent of mixing of base composition in their DNA strand. However, such variations were not seen in their RNA strand. The MD simulation results also showed that the decreasing deoxypyrimidine composition in DNA strand leads to transformation of the DNA-RNA hybrid conformation from A-type to A/B-type. The possible factors responsible for the inactivity of ribonuclease H (RNase H) enzyme towards hybrids with high deoxypyrimidine composition have also been proposed. Thermodynamic stabilities of the duplexes were explained by using binding free energies. Next, investigations have been carried out to understand the interactions between rnase H enzyme with the DNA-RNA hybrid and the energy cost accompanying the complex formation. The binding of enzyme to the nucleic acid induces conformational transitions towards N-type or S-type in deoxyribose sugars that are important for efficient binding. Since this enzyme exhibit close structural and functional similarity with RNase H of the HIV-I reverse transcriptase and several other nucleic acid processing enzymes, the present study is helpful in understanding the molecular level details of their dynamics and stability. A comprehensive study has been performed on DNA-RNA hybrid duplexes by systematically modifying the deoxyribose sugars to isomeric locked nucleic acid (α/β-LNA) modifications; which leads to increase in duplex stability and change in conformation to A-type. The differential effects of these two modifications were studied extensively. The results indicate that the α-LNA modification induces conformational changes in the duplex backbone in order to adjust in the duplex. However, such changes are not necessary for β-LNA modification. The structure and thermodynamic stabilities of the full LNA duplexes have also been explored. Free energy calculations suggest that hydrophobicity of 2'-O-Methyl groups is primarily responsible for the reversal thermodynamic stabilities of DNA-RNA hybrids. RNA molecules have been shown to fold to form complex three-dimensional structures that are important for catalytic cellular processes. Investigation of RNA folding is crucial for understanding its diverse functions. RNA folding dynamics has been studied by taking a 12 nucleotide GNRA RNA hairpin in water, urea and MgCl 2 solutions using replica exchange molecular dynamics simulations. Urea decreases the melting temperature of the RNA hairpin while Mg 2+ increases melting temperature that agree well with the experimental data. Urea reduces the hydrogen bonding interactions of base pairs and stacking interactions among nucleobases that results in faster unfolding of RNA hairpin. Urea prevents refolding of hairpin by forming strong hydrogen bond and stacking interactions with the nucleobases when the nucleobases separate from hairpin during unfolding process. The components of calculated interaction energies suggest that dispersion interactions play key role in RNA denaturation and unfolding processes.

Abstract

Advances in cloud computing have redefined the landscape of modern information technology as seen by the popularity of cloud service providers such as Amazon, Microsoft Azure and Google App Engine. Data storage outsourcing is a prime application in cloud computing, which allows organizations to provide reliable data services to users without concerning with the data management overheads. But, there are several practical apprehensions regarding the privacy of the outsourced data and these concerns are a major hindrance towards the uninhibited adoption of cloud storage services. Generally, the cloud service provider does not attempt to violate data privacy, there are internal factors like malicious employees who will abuse the client data at the first available opportunity. Thus, the data needs to be encrypted prior to outsourcing. However, the encryption is a major hindrance to perform regular data access operations, such as searching for documents containing specific keywords or patterns. Therefore, there is a crucial need for techniques to support a rich set of querying functionality on the encrypted data without violating the privacy of the users. While there have been many works on efficiently solving the problem of privacy preserving single keyword and multi-keyword search on outsourced data in cloud computing, both in public key and symmetric key domains, the problem of privacy preserving string pattern search has only been solved in public key domain and that too is not efficient enough for adopting to practical scenarios like cloud. We note that the solution to this problem is unexplored in symmetric key domain. In this work, we present the first ever symmetric key based approach to support privacy preserving string pattern matching on outsourced data in cloud computing. String pattern matching functionality can find occurrence of a string pattern anywhere within a keyword. We describe an efficient and accurate indexing structure, the PASStree, which can execute a string pattern query in logarithmic time complexity over a set of data items. The PASStree provides strong privacy guarantees against attacks from a semi-honest adversary. We have comprehensively evaluated our scheme over large real-life data, such as Wikipedia and Enron documents, containing up to 100000 keywords, and show that our algorithms achieve pattern search in less than a few milliseconds with 100% accuracy. We have performed prefix and sub-string pattern search on Wikipedia dataset, and performed multi-keyword phrase search of sender/receiver queries on Enron dataset. Furthermore, we also describe a relevance ranking algorithm to return the most relevant documents to the user based on the query pattern. Our ranking algorithm achieves 90%+ above precision in ranking the returned documents.

Abstract

An overlay network is a logical network built on top of some underlying network (the underlay) with an objective to provide some service to the underlying network. The internet, for instance, was initially an overlay network built on top of the Public Switched Telephone Network and has today become the underlying substrate for overlay networks of numerous types - peer-to-peer file sharing (BitTorrent), multimedia (Skype), security (VPNs), experimental test beds (PlanetLab), etc. Pioneered by Napster in 1999 and strongly purported by further advances like Gnutella, Kaaza, Freenet, shortly thereafter, peer-to-peer content sharing became quite popular across a wide range of internet audience during the early 2000s and has been growing ever since. As a result, peer-to-peer systems (not just file sharing), in general, are today some of the most popular overlay applications across the internet. Peer-to-peer overlay networks can be classified into two broad categories - structured and unstructured. In the unstructured category, any peer may host any content which means that in order to find a specific content, only a blind search can be carried out in the overlay. In the structured category, on the other hand, a tight relation is defined between the content and its host, such that any peer in the overlay, given the content to be searched, can compute the identity of the peer hosting the content. Therefore, while in an unstructured P2P overlay, data storage is random and data search is blind or at best heuristic, in a structured P2P overlay, data storage is controlled and, as a result, data search is structured. The way we see it, the structured category can be characterized by a couple of components - the mapping component that maps the data items to one or more overlay nodes and the overlay nodes to the underlay peers, i.e., one that takes care of distribution/re-distribution of the data to be hosted on the overlay among the overlay nodes and the routing component that creates the overlay routing topology in a way that every peer in the overlay can deterministically figure out which outgoing link must be chosen to reach a given destination peer in the overlay. So, for any data search, while the mapping component tells us where - on which overlay node - the data resides, the routing component tells us how to get there. In this work, we formalize the routing component of structured P2P overlay networks and mathematically analyze the overlay properties determined/affected by it. Unless explicitly qualified, throughout thiswork, by structured overlay networks (short hand SONs), or structured overlays or simply overlays, we shall mean structured P2P overlay networks.