Spelling suggestions: "subject:"neighbor"" "subject:"weighbor""
81 |
AKDB-Tree: An Adjustable KDB-tree for Efficiently Supporting Nearest Neighbor Queries in P2P SystemsLiu, Hung-ze 06 July 2008 (has links)
In the future, more data intensive applications, such as P2P auction networks, P2P job--search networks, P2P multi--player games, will require the capability to respond to more complex queries such as the nearest neighbor queries involving numerous data types. For the problem of answering nearest neighbor queries (NN query) for spatial region data in the P2P environment, a quadtree-based structure probably is a good choice. However, the quadtree stores the data in the leaf nodes, resulting in the load unbalance and expensive cost of any query. The MX--CIF quadtree can solve this problem. The MX--CIF quadtree has three properties: controlling efficiently the height of the tree, reducing load unbalance, and reducing the NNquery scope with controlling the value of the radius. Although the P2P MX--CIF quadtree can do the NN query efficiently, it still has some problems as follows: low accuracy of the nearest neighbor query, the expensive cost of the tree construction, the high search cost of the NN query, and load unbalance. In fact, the index structures for the region data can also work for the point data which can be considered as the degenerated case of the region data. Therefore, the KDB--tree which is a well-known algorithm for the point data can be used to reduce load unbalance, but it has the same problem as the quadtree. The data is stored only in the leaf nodes of the KDB--tree. In this thesis, we propose an Adjustable KDB--tree (AKDB--tree) to improve this situation for the P2P system. The AKDB--tree has five properties: reducing load unbalance, low cost of the tree construction, storing the data in the internal nodes and leaf nodes, high accuracy and low search cost of the NN query. The Chord system is a well--known structured P2P system in which the data search is performed by a hash function, instead of flooding used in most of the unstructured P2P system. Since the Chord system is a hash approach, it is easy to deal with peers joining/exiting. Besides, in order to combine AKDB--tree with the Chord system, we design the IDs of the nodes in the AKDB--tree. Each node is hashed to the Chord system by the ID. The IDs can be used to differentiate the edge node in the AKDB-tree is a vertical edge or a horizontal edge and the relative position of two nodes in the 2D space. And, we can calculate the related edge of a region in the 2D space according to the ID of the region. As discussed above, we make use of the property of IDs to reduce the search cost of the NN query by a wide margin. In our simulation study, we compare our method with the P2P MX--CIF quadtree by considering five performance measures under four different situations of the P2P MX--CIF quadtree. From our simulation results, for the NN query, our AKDB-tree can provide the higher accuracy and lower search cost than the P2P MX--CIF quadtree. For the problem of load, our AKDB-tree is more balance than the P2P MX--CIF quadtree. For the time of the tree construction, our AKDB-tree needs shorter time than the P2P MX--CIF quadtree.
|
82 |
Méthodes de distance pour l'inférence phylogénomiqueCriscuolo, Alexis 05 December 2006 (has links) (PDF)
L'inférence phylogénomique cherche à combiner le signal évolutif induit par un ensemble de gènes dans le but de construire un unique arbre phylogénétique.<br />Elle peut être décomposée en trois grandes familles méthodologiques: la combinaison basse, qui s'appuie sur la concaténation des différents gènes, la combinaison haute, qui considère l'ensemble des arbres inférés à partir de chaque gène, et la combinaison moyenne, qui encode les différents signaux phylogénétiques puis combine ces différents encodages.<br />Une méthode d'inférence d'arbre est ensuite appliquée sur le résultat de la combinaison.<br /><br />Cette thèse développe de nouveaux scénarios d'inférence phylogénomique, principalement basés sur l'estimation de distances évolutives entre chaque paire de taxons.<br />Elle propose une nouvelle méthode de combinaison moyenne, nommée SDM, qui considère les matrices de distance estimées à partir de chaque gène et qui les combine en une unique supermatrice de distance.<br />Cette dernière pouvant parfois contenir des distances manquantes, cette thèse décrit également de nouveaux algorithmes, nommés NJ*, UNJ*, BioNJ* et MVR*, permettant d'inférer très rapidement un arbre à partir d'une matrice de distance complète ou incomplète.<br />De nombreuses simulations ont permis d'observer les bonnes performances de ces nouvelles méthodes de distance.<br />Initialement développées pour la combinaison moyenne, elles permettent toutefois d'améliorer significativement les résultats de certaines approches standards en combinaison basse, et représentent une alternative efficace à MRP, la plus utilisée des techniques de combinaison haute, en termes de fiabilité et de rapidité.<br />La taille des jeux de données phylogénomiques étant de plus en plus importante, les méthodes développées dans cette thèse constituent ainsi des outils de choix pour construire l'Arbre de la Vie.
|
83 |
Improving WiFi positioning through the use of successive in-sequence signal strength samplesHallström, Per, Dellrup, Per January 2006 (has links)
<p>As portable computers and wireless networks are becoming ubiquitous, it is natural to consider the user’s position as yet another aspect to take into account when providing services that are tailored to meet the needs of the consumers. Location aware systems could guide persons through buildings, to a particular bookshelf in a library or assist in a vast variety of other applications that can benefit from knowing the user’s position.</p><p>In indoor positioning systems, the most commonly used method for determining the location is to collect samples of the strength of the received signal from each base station that is audible at the client’s position and then pass the signal strength data on to a positioning server that has been previously fed with example signal strength data from a set of reference points where the position is known. From this set of reference points, the positioning server can interpolate the client’s current location by comparing the signal strength data it has collected with the signal strength data associated with every reference point.</p><p>Our work proposes the use of multiple successive received signal strength samples in order to capture periodic signal strength variations that are the result of effects such as multi-path propagation, reflections and other types of radio interference. We believe that, by capturing these variations, it is possible to more easily identify a particular point; this is due to the fact that the signal strength fluctuations should be rather constant at every position, since they are the result of for example reflections on the fixed surfaces of the building’s interior.</p><p>For the purpose of investigating our assumptions, we conducted measurements at a site at Växjö university, where we collected signal strength samples at known points. With the data collected, we performed two different experiments: one with a neural network and one where the k-nearest-neighbor method was used for position approximation. For each of the methods, we performed the same set of tests with single signal strength samples and with multiple successive signal strength samples, to evaluate their respective performances.</p><p>We concluded that the k-nearest-neighbor method does not seem to benefit from multiple successive signal strength samples, at least not in our setup, compared to when using single signal strength samples. However, the neural network performed about 17% better when multiple successive signal strength samples were used.</p>
|
84 |
Time series discrimination, signal comparison testing, and model selection in the state-space framework /Bengtsson, Thomas January 2000 (has links)
Thesis (Ph. D.)--University of Missouri-Columbia, 2000. / Typescript. Vita. Includes bibliographical references (leaf 104). Also available on the Internet.
|
85 |
Time series discrimination, signal comparison testing, and model selection in the state-space frameworkBengtsson, Thomas January 2000 (has links)
Thesis (Ph. D.)--University of Missouri-Columbia, 2000. / Typescript. Vita. Includes bibliographical references (leaf 104). Also available on the Internet.
|
86 |
Nearest neighbor queries in spatial and spatio-temporal databases /Zhang, Jun. January 2003 (has links)
Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2003. / Includes bibliographical references (leaves 125-131). Also available in electronic version. Access restricted to campus users.
|
87 |
Small Scale Distribution of the Sand Dollars Mellita tenuis and Encope spp. (Echinodermata)Swigart, James P. 01 January 2006 (has links)
Small scale distributions of Mellita tenuis and Encope spp. were quantified at Fort De Soto Park on Mullet Key, off Egmont Key and off Captiva Island, Florida during 2005. Off Captiva Island, Encope spp. were aggregated in 33.3% of plots in March. Off Egmont Key, M. tenuis were aggregated in 100% of plots in March but in no plots in September. At Fort De Soto Park, M. tenuis were aggregated in 37.5% of plots in May 12.5% in July and 50.0% in September. Sand dollars in 6.3% of the plots in September at Fort De Soto had a uniform distribution. Individuals in all other plots at all sites had random distributions. At Fort De Soto, each plot was revisited a few hours after the initial observation; 37.5% of plots had a different distribution at the second observation.
Percent organic content of the smallest sediment grains (<105 μm) was not correlated with sand dollar distribution, except off Egmont Key. There was a significant negative correlation between nearest neighbor index and percent organic content. Mellita tenuis do aggregate on occasion. The cause of aggregation is not known. If localized differences in percent organic content of the sediment influence distribution, then homogeneity in the percent organic content of the sediment, as found in the majority of plots, would suggest random distribution of sand dollars.
|
88 |
Existence and persistence of invariant objects in dynamical systems and mathematical physicsCalleja, Renato Carlos 06 August 2012 (has links)
In this dissertation we present four papers as chapters. In Chapter 2, we extended the techniques used for the Klein-Gordon Chain by Iooss, Kirchgässner, James, and Sire, to chains with non-nearest neighbor interactions. We look for travelling waves by reducing the Klein-Gordon chain with second nearest neighbor interaction to an advance-delay equation. Then we reduce the equation to a finite dimensional center manifold for some parameter regimes. By using the normal form expansion on the center manifold we were able to prove the existence of three different types of travelling solutions for the Klein Gordon Chain: periodic, quasi-periodic and homoclinic to periodic orbits with exponentially small amplitude. In Chapter 3 we include numerical methods for computing quasi-periodic solutions. We developed very efficient algorithms to compute smooth quasiperiodic equilibrium states of models in 1-D statistical mechanics models allowing non-nearest neighbor interactions. If we discretize a hull function using N Fourier coefficients, the algorithms require O(N) storage and a Newton step for the equilibrium equation requires only O(N log(N)) arithmetic operations. This numerical methods give rise to a criterion for the breakdown of quasi-periodic solutions. This criterion is presented in Chapter 4. In Chapter 5, we justify rigorously the criterion in Chapter 4. The justification of the criterion uses both Numerical KAM algorithms and rigorous results. The hypotheses of the theorem concern bounds on the Sobolev norms of a hull function and can be verified rigorously by the computer. The argument works with small modifications in all cases where there is an a posteriori KAM theorem. / text
|
89 |
A scalable metric learning based voting method for expression recognitionWan, Shaohua 09 October 2013 (has links)
In this research work, we propose a facial expression classification method using metric learning-based k-nearest neighbor voting. To achieve accurate classification of a facial expression from frontal face images, we first learn a distance metric structure from training data that characterizes the feature space pattern, then use this metric to retrieve the nearest neighbors from the training dataset, and finally output the classification decision accordingly. An expression is represented as a fusion of face shape and texture. This representation is based on registering a face image with a landmarking shape model and extracting Gabor features from local patches around landmarks. This type of representation achieves robustness and effectiveness by using an ensemble of local patch feature detectors at a global shape level. A naive implementation of the metric learning-based k-nearest neighbor would incur a time complexity proportional to the size of the training dataset, which precludes this method being used with enormous datasets. To scale to potential larger databases, a similar approach to that in [24] is used to achieve an approximate yet efficient ML-based kNN voting based on Locality Sensitive Hashing (LSH). A query example is directly hashed to the bucket of a pre-computed hash table where candidate nearest neighbors can be found, and there is no need to search the entire database for nearest neighbors. Experimental results on the Cohn-Kanade database and the Moving Faces and People database show that both ML-based kNN voting and its LSH approximation outperform the state-of-the-art, demonstrating the superiority and scalability of our method. / text
|
90 |
ENABLING HYDROLOGICAL INTERPRETATION OF MONTHLY TO SEASONAL PRECIPITATION FORECASTS IN THE CORE NORTH AMERICAN MONSOON REGIONMaitaria, Kazungu January 2009 (has links)
The aim of the research undertaken in this dissertation was to use medium-range to seasonal precipitation forecasts for hydrologic applications for catchments in the core North American Monsoon (NAM) region. To this end, it was necessary to develop a better understanding of the physical and statistical relationships between runoff processes and the temporal statistics of rainfall. To achieve this goal, development of statistically downscaled estimates of warm season precipitation over the core region of the North American Monsoon Experiment (NAME) were developed. Currently, NAM precipitation is poorly predicted on local and regional scales by Global Circulation Models (GCMs). The downscaling technique used here, the K-Nearest Neighbor (KNN) model, combines information from retrospective GCM forecasts with simultaneous historical observations to infer statistical relationships between the low-resolution GCM fields and the locally-observed precipitation records. The stochastic nature of monsoon rainfall presents significant challenges for downscaling efforts and, therefore, necessitate a regionalization and an ensemble or probabilistic-based approach to quantitative precipitation forecasting. It was found that regionalization of the precipitation climatology prior to downscaling using KNN offered significant advantages in terms of improved skill scores.Selected output variables from retrospective ensemble runs of the National Centers for Environmental Predictions medium-range forecast (MRF) model were fed into the KNN downscaling model. The quality of the downscaled precipitation forecasts was evaluated in terms of a standard suite of ensemble verification metrics. This study represents the first time the KNN model has been successfully applied within a warm season convective climate regime and shown to produce skillful and reliable ensemble forecasts of daily precipitation out to a lead time of four to six days, depending on the forecast month.Knowledge of the behavior of the regional hydrologic systems in NAM was transferred into a modeling framework aimed at improving intra-seasonal hydrologic predictions. To this end, a robust lumped-parameter computational model of intermediate conceptual complexity was calibrated and applied to generate streamflow in three unregulated test basins in the core region of the NAM. The modeled response to different time-accumulated KNN-generated precipitation forcing was investigated. Although the model had some difficulty in accurately simulating hydrologic fluxes on the basis of Hortonian runoff principles only, the preliminary results achieved from this study are encouraging. The primary and most novel finding from this study is an improved predictability of the NAM system using state-of-the-art ensemble forecasting systems. Additionally, this research significantly enhanced the utility of the MRF ensemble forecasts and made them reliable for regional hydrologic applications. Finally, monthly streamflow simulations (from an ensemble-based approach) have been demonstrated. Estimated ensemble forecasts provide quantitative estimates of uncertainty associated with our model forecasts.
|
Page generated in 0.0192 seconds