In Mobile Ad Hoc Networks (MANETs), nodes depend on each other for routing and forwarding packets. However, to save power and other resources, nodes belonging to independent authorities may behave selfishly, and may not be willing to help other nodes. Such selfish behavior poses a real threat to the proper functioning of MANETs. One way to foster node cooperation is to introduce punishment for selfish nodes. Based on neighbor-monitoring techniques, a fully distributed solution to detect, punish, and re-admit selfish nodes, is proposed here. This solution provides nodes the same opportunity to serve/and be served by others. A light-weight solution regarding battery status is also proposed here. This solution requires neighbor monitoring only when necessary, thereby saving nodes battery power. Another effective way to solve the selfish-node problem is to reward nodes for their service according to their cost. To force nodes to show their true cost, truthful protocols are needed. A low overhead truthful routing protocol to find optimal routes is proposed in this thesis. The most prominent feature of this protocol is the reduction of overhead from existing solutions O(n3) to O(n2). A light-weight scalable truthful routing protocol (LSTOP) is further proposed, which finds near-least-cost paths in dense networks. LSTOP reduces overhead to O(n) on average, and O(n2) in worst case scenarios. Multiple path routing protocols are an effective alternative to single path routing protocols. A generic mechanism that can turn any table-driven multipath routing protocol into a truthful one, is outlined here. A truthful multipath routing protocol (TMRP), based on well-known AOMDV protocol, is presented as an example. TMRP incurs an only 2n message overhead for a route discovery, and can also achieve load balancing without compromising truthfulness. To cope with the selfish-node problem in the area of position-based routing, a truthful geographic forwarding (TGF) algorithm is presented. TGF utilizes three auction-based forwarding schemes to stimulate node cooperation. The truthfulness of these schemes is proven, and their performance is evaluated through statistical analysis and simulation studies.

Problems of population genetics are magnified by problems of big data. My dissertation spans the disciplines of computer science and population genetics, leveraging computational approaches to biological problems to address issues in genomics research. In this dissertation I develop more efficient metric search algorithms. I also show that vast majority of the genomes of great apes are impacted by the forces of natural selection. Finally, I introduce a heuristic to identify neutralomes—regions that are evolving with minimal selective pressures—and use these neutralomes for inferences on effective population size in great apes. We begin with a formal and far-reaching problem that impacts a broad array of disciplines including biology and computer science; the 𝑘-nearest neighbors problem in generalized metric spaces. The 𝑘-nearest neighbors (𝑘-NN) problem is deceptively simple. The problem is as follows: given a query q and dataset D of size 𝑛, find the 𝑘-closest points to q. This problem can be easily solved by algorithms that compute 𝑘th order statistics in O(𝑛) time and space. It follows that if D can be ordered, then it is perhaps possible to solve 𝑘-NN queries in sublinear time. While this is not possible for an arbitrary distance function on the points in D, I show that if the points are constrained by the triangle inequality (such as with metric spaces), then the dataset can be properly organized into a dispersion tree (Appendix A). Dispersion trees are a hierarchical data structure that is built around a large dispersed set of points. Dispersion trees have construction times that are sub-quadratic (O(𝑛¹·⁵ log⁡ 𝑛)) and use O(𝑛) space, and they use a provably optimal search strategy that minimizes the number of times the distance function is invoked. While all metric data structures have worst-case O(𝑛) search times, dispersion trees have average-case search times that are substantially faster than a large sampling of comparable data structures in the vast majority of spaces sampled. Exceptions to this include extremely high dimensional space (d>20) which devolve into near-linear scans of the dataset, and unstructured low-dimensional (d<6) Euclidean spaces. Dispersion trees have empirical search times that appear to scale as O(𝑛ᶜ) for 0<c<1. As solutions to the 𝑘-NN problem are in general too slow to be used effectively in the arena of big data in genomics, it is my hope that dispersion trees may help lift this barrier. With source-code that is freely available for academic use, dispersion trees may be useful for nearest neighbor classification problems in machine learning, fast read-mapping against a reference genome, and as a general computational tool for problems such clustering. Next, I turn to problems in population genomics. Genomic patterns of diversity are a complex function of the interplay between demographics, natural selection and mechanistic forces. A central tenet of population genetics is the neutral theory of molecular evolution which states the vast majority of changes at the molecular level are (relatively) selectively neutral; that is, they do not effect fitness. A corollary of the neutral theory is that the frequency of most alleles in populations are dictated by neutral processes and not selective processes. The forces of natural selection impact not just the site of selection, but linked neutral sites as well. I proposed an empirical assessment of the extents of linked selection in the human genome (Appendix B). Recombination decouples sites of selection from the genomic background, thus it serves to mitigate the effects of linked selection. I use two metrics on recombination, both the minimum genetic distance to genes and local rates of recombination, to parse the effects of linked selection into selection from genic and nongenic sources in the human genome. My empirical assessment shows profound linked selective effects from nongenic sources, with these effects being greater than that of genic sources on the autosomes, as well as generally greater effects on the X chromosome than on the autosomes. I quantify these trends using multiple linear regression, and then I model the effects of linked selection to conserved elements across the whole of the genome. Places predicted to be neutral by my model do not, unlike the vast majority of the genome, show these linked selective effects. This demonstrates that linkage to these regulatory elements, and not some other mechanistic force, accounts for our findings. Further, neutrally evolving regions are extremely rare (~1%) in the genome, and despite generally larger linked selective effects on the X chromosome, the size of this “neutralome” is proportionally larger on the X chromosome than on the autosomes. To account for this and to extend my findings to other great apes I improve on my procedure to find neutralomes, and apply this procedure to the genome of humans, Nigerian chimpanzees, bonobos, and western lowland gorillas (Appendix C). In doing so I show that like humans, these other apes are also enormously impacted by linked selection, with their neutralomes being substantially smaller than the neutralomes of humans. I then use my genomic predictions on neutrality to see how the landscape of linked selection changes across the X chromosome and the autosomes in regions close to, and far from, genes. While I had previously demonstrated the linked selective forces near genes are stronger on the X chromosome than on the autosomes in these taxa, I show that regions far from genes show the opposite; regions far from genes show more selection from noncoding targets on the autosomes than on the X chromosome. This finding is replicated across our great ape samples. Further, inferences on the relative effective population size of the X chromosome and the autosomes both near and far from genes can be biased as a result.

Background. Pathfinding plays a big role in both digital games and robotics, and is used in many different ways. One of them is multi-goal pathfinding (MGPF) which is used to calculate paths from a start position to a destination with the condition that the resulting path goes though a series of goals on the way to the destination. For the most part research on this topic is sparse, and when the complexity is increased through obstacles that are introduced to the scenario, there are only a few articles in the field that relate to the problem.Objectives. The objective in this thesis is to conduct an experiment to compare four algorithms for solving the MGPF problem on six different maps with obstacles, and then analyze and draw conclusions on which of the algorithms is best suited to use for the MGPF problem. The first is the traditional Nearest Neighbor algorithm, the second is a variation on the Greedy Search algorithm, and the third and fourth are variations on the Nearest Neighbor algorithm. Methods. To reach the Objectives all the four algorithms are tested fifty times on six different maps of varying sizes and obstacle layout. Results. The data from the experiment is compiled in graphs for all the different maps, with the time to calculate a path and the path lengths as the metrics. The averages of all the metrics are put in tables to visualize the difference between the results for the four algorithms.Conclusions. The conclusions were that the dynamic version of the Nearest Neighbor algorithm has the best result if both the metrics are taken into account. Otherwise the common Nearest Neighbor algorithm gives the best results in respect to the time taken to calculate the paths and the Greedy Search algorithm creates the shortest paths of all the tested algorithms.

Thesis advisor: Roberto Goizueta / The injunction to `love our neighbor' is a constitutive element of any Christian ethic. It is frequently found embedded within the triadic formulation of `love of God, love of neighbor, and love of self.' Because this injunction must always be contextualized within each historical period it was important to explore how one should love the neighbor in our contemporary context. The dissertation begins by exploring the contemporary conditions of pluralism and interdependence. In this context we realize that love of neighbor must manifest in an encounter with the other. The project shows some current models of encountering the other. In showing the inadequacies of each model I also introduce the work of Johann B. Metz and Enrique Dussel. I then construct a process entitled Agapic Solidarity which seeks to use some aspects of the political theology of Metz and the liberation philosophy of Dussel to formulate an authentic encounter with the other. This process honors both elements; the condition of pluralism and the acknowledgement of interdependence. In doing this we begin the process of loving the neighbor which is so central to any Christian ethic. In the conclusion of the dissertation I show some possible applications of the process. The final component is a case study of the undocumented migrant in the United States of America as a demonstration of the process in action. In this way, it shows how the ethical demand can be enacted and embodied within a particular, concrete ethical issue. / Thesis (PhD) — Boston College, 2013. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Theology.

Made available in DSpace on 2017-07-10T17:11:50Z (GMT). No. of bitstreams: 1 JORGE AIKES JUNIOR.PDF: 2050278 bytes, checksum: f5bae18bbcb7465240488c45b2c813e7 (MD5) Previous issue date: 2012-04-11 / Time series can be understood as any set of observations which are time ordered. Among the many possible tasks appliable to temporal data, one that has attracted increasing interest, due to its various applications, is the time series forecasting. The k-Nearest Neighbor - Time Series Prediction (kNN-TSP) algorithm is a non-parametric method for forecasting time series. One of its advantages, is its easiness application when compared to parametric methods. Even though its easier to define kNN-TSP s parameters, some issues remain opened. This research is focused on the study of one of these parameters: the similarity measure. This parameter was empirically evaluated using various similarity measures in a large set of time series, including artificial series with seasonal and chaotic characteristics, and several real world time series. It was also carried out a case study comparing the predictive accuracy of the kNN-TSP algorithm with the Moving Average (MA), univariate Seasonal Auto-Regressive Integrated Moving Average (SARIMA) and multivariate SARIMA methods in a time series of a Korean s hospital daily patients flow in the Emergency Department. This work also proposes an approach to the development of a hybrid similarity measure which combines characteristics from several measures. The research s result demonstrated that the Lp Norm s measures have an advantage over other measures evaluated, due to its lower computational cost and for providing, in general, greater accuracy in temporal data forecasting using the kNN-TSP algorithm. Although the literature in general adopts the Euclidean similarity measure to calculate de similarity between time series, the Manhattan s distance can be considered an interesting candidate for defining similarity, due to the absence of statistical significant difference and to its lower computational cost when compared to the Euclidian measure. The measure proposed in this work does not show significant results, but it is promising for further research. Regarding the case study, the kNN-TSP algorithm with only the similarity measure parameter optimized achieves a considerably lower error than the MA s best configuration, and a slightly greater error than the univariate e multivariate SARIMA s optimal settings presenting less than one percent of difference. / Séries temporais podem ser entendidas como qualquer conjunto de observações que se encontram ordenadas no tempo. Dentre as várias tarefas possíveis com dados temporais, uma que tem atraído crescente interesse, devido a suas várias aplicações, é a previsão de séries temporais. O algoritmo k-Nearest Neighbor - Time Series Prediction (kNN-TSP) é um método não-paramétrico de previsão de séries temporais que apresenta como uma de suas vantagens a facilidade de aplicação, quando comparado aos métodos paramétricos. Apesar da maior facilidade na determinação de seus parâmetros, algumas questões relacionadas continuam em aberto. Este trabalho está focado no estudo de um desses parâmetros: a medida de similaridade. Esse parâmetro foi avaliado empiricamente utilizando diversas medidas de similaridade em um grande conjunto de séries temporais que incluem séries artificiais, com características sazonais e caóticas, e várias séries reais. Foi realizado também um estudo de caso comparativo entre a precisão da previsão do algoritmo kNN-TSP e a dos métodos de Médias Móveis (MA), Auto-regressivos de Médias Móveis Integrados Sazonais (SARIMA) univariado e SARIMA multivariado, em uma série de fluxo diário de pacientes na Área de Emergência de um hospital coreano. Neste trabalho é ainda proposta uma abordagem para o desenvolvimento de uma medida de similaridade híbrida, que combine características de várias medidas. Os resultados obtidos neste trabalho demonstram que as medidas da Norma Lp apresentam vantagem sobre as demais medidas avaliadas, devido ao seu menor custo computacional e por apresentar, em geral, maior precisão na previsão de dados temporais utilizando o algoritmo kNN-TSP. Apesar de na literatura, em geral, a medida Euclidiana ser adotada como medida de similaridade, a medida Manhattan pode ser considerada candidata interessante para definir a similaridade entre séries temporais, devido a não apresentar diferença estatisticamente significativa com a medida Euclidiana e possuir menor custo computacional. A medida proposta neste trabalho, não apresenta resultados significantes, mas apresenta-se promissora para novas pesquisas. Com relação ao estudo de caso, o algoritmo kNN-TSP, com apenas o parâmetro de medida de similaridade otimizado, alcança um erro consideravelmente inferior a melhor configuração com MA, e pouco maior que as melhores configurações dos métodos SARIMA univariado e SARIMA multivariado, sendo essa diferença inferior a um por cento.

<p>It is important to detect faults in bus details at an early stage. Because the driving style affects the breakdown of different details in the bus, identification of the driving style is important to minimize the number of failures in buses.</p><p>The identification of the driving style of the driver was based on the input data which contained examples of the driving runs of each class. K-nearest neighbor and neural networks algorithms were used. Different models were tested.</p><p>It was shown that the results depend on the selected driving runs. A hypothesis was suggested that the examples from different driving runs have different parameters which affect the results of the classification.</p><p>The best results were achieved by using a subset of variables chosen with help of the forward feature selection procedure. The percent of correct classifications is about 89-90 % for the k-nearest neighbor algorithm and 88-93 % for the neural networks.</p><p>Feature selection allowed a significant improvement in the results of the k-nearest neighbor algorithm and in the results of the neural networks algorithm received for the case when the training and testing data sets were selected from the different driving runs. On the other hand, feature selection did not affect the results received with the neural networks for the case when the training and testing data sets were selected from the same driving runs.</p><p>Another way to improve the results is to use smoothing. Computing the average class among a number of consequent examples allowed achieving a decrease in the error.</p>

Example-based methods are effective for parameter estimation problems when the underlying system is simple or the dimensionality of the input is low. For complex and high-dimensional problems such as pose estimation, the number of required examples and the computational complexity rapidly becme prohibitively high. We introduce a new algorithm that learns a set of hashing functions that efficiently index examples relevant to a particular estimation task. Our algorithm extends a recently developed method for locality-sensitive hashing, which finds approximate neighbors in time sublinear in the number of examples. This method depends critically on the choice of hash functions; we show how to find the set of hash functions that are optimally relevant to a particular estimation problem. Experiments demonstrate that the resulting algorithm, which we call Parameter-Sensitive Hashing, can rapidly and accurately estimate the articulated pose of human figures from a large database of example images.

Thesis (Ph. D.)--University of Hong Kong, 2006. / Title proper from title frame. Also available in printed format.

It is important to detect faults in bus details at an early stage. Because the driving style affects the breakdown of different details in the bus, identification of the driving style is important to minimize the number of failures in buses. The identification of the driving style of the driver was based on the input data which contained examples of the driving runs of each class. K-nearest neighbor and neural networks algorithms were used. Different models were tested. It was shown that the results depend on the selected driving runs. A hypothesis was suggested that the examples from different driving runs have different parameters which affect the results of the classification. The best results were achieved by using a subset of variables chosen with help of the forward feature selection procedure. The percent of correct classifications is about 89-90 % for the k-nearest neighbor algorithm and 88-93 % for the neural networks. Feature selection allowed a significant improvement in the results of the k-nearest neighbor algorithm and in the results of the neural networks algorithm received for the case when the training and testing data sets were selected from the different driving runs. On the other hand, feature selection did not affect the results received with the neural networks for the case when the training and testing data sets were selected from the same driving runs. Another way to improve the results is to use smoothing. Computing the average class among a number of consequent examples allowed achieving a decrease in the error.

As provision of social services is increasingly handled by the non-profit sector, specifically through faith-based organizations (FBO's), current scholarship has suggests that FBOs have the possibility to either reinforce neoliberal ideology or progress social justice. This study provides an examination of the shift in conceptions of justice for participants in the Mission Year program, an FBO program naming justice as a goal. For the participants, this experience creates a new understanding of the causes of poverty, injustice and American culture which I name 'justice as knowing.' This understanding culminated within participants a desire to “live out justice” as ‘intentional neighbors’ by relocating to a high-poverty neighborhood, reconciling racial relations by building relationships, and contributing to a redistribution of wealth by investing resources in a high-poverty neighborhood. I call this action ‘justice as doing.’ Participants shift from liberal-based notions justice, rooted in liberalism, toward more equity-based conceptions of justice as fairness.