Queries on spatial data commonly concern a certain range or area, for example, queries related to intersections, containment and nearest neighbors. The Continuous Nearest Neighbor (CNN) query is one kind of the nearest neighbor queries. For example, people may want to know where those gas stations are along the super highway from the starting position to the ending position. Due to that there is no total ordering of spatial proximity among spatial objects, the space filling curve (SFC) approach has proposed to preserve the spatial locality. Chen and Chang have proposed efficient algorithms based on SFC to answer nearest neighbor queries, so we may perform a sequence of individually nearest neighbor queries to answer such a CNN query in the centralized system by one of Chen and Chang's algorithms. However, each searched range of these nearest neighbor queries could be overlapped, and these queries may access several same pages on the disk, resulting in many redundant disk accesses. On the other hand, Zheng et al. have proposed an algorithm based on the Hilbert curve for the CNN query for the wireless broadcast environment, and it contains two phases. In the first phase, Zheng et al.'s algorithm designs a searched range to find candidate objects. In the second phase, it uses some heuristics to filter the candidate objects for the final answer. However, Zheng et al.'s algorithm may check some data blocks twice or some useless data blocks, resulting in some redundant disk accesses. Therefore, in this thesis, to avoid these disadvantages in the first phase of Zheng et al.'s algorithm, we propose a local expansion approach based on the Peano curve for the CNN query in the centralized system. In the first phase, we determine the searched range to obtain all candidate objects. Basically, we first calculate the route between the starting point and the ending point. Then, we move forward one block from the starting point to the ending point, and locally spread the searched range to find the candidate objects. In the second phase, we use heuristics mentioned in Zheng et al.'s algorithm to filter the candidate objects for the final answer. Based on such an approach, we proposed two algorithms: the forward moving (FM) algorithm and the forward moving* (FM*) algorithm. The FM algorithm assumes that each object is in the center of a block, and the FM* algorithm assumes that each object could be in any place of a block. Our local expansion approach can avoid the duplicated check in Zheng et al.'s algorithm, and determine a searched range with higher accuracy than that of Zhenget al.'s algorithm. From our simulation results, we show that the performance of the FM or FM* algorithm is better than that of Zheng et al.'s algorithm, in terms of the accuracy and the processing time.

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.

<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>

Thesis (Ph. D.)--University of Missouri-Columbia, 2000. / Typescript. Vita. Includes bibliographical references (leaf 104). Also available on the Internet.

Thesis (Ph. D.)--University of Missouri-Columbia, 2000. / Typescript. Vita. Includes bibliographical references (leaf 104). Also available on the Internet.

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.

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.

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

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

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.