E.3. Analysis of Algorithms and Problem Complexity
A. Mesrikhani; M. Davoodi
Abstract
Nearest Neighbor (NN) searching is a challenging problem in data management and has been widely studied in data mining, pattern recognition and computational geometry. The goal of NN searching is efficiently reporting the nearest data to a given object as a query. In most of the studies both the data ...
Read More
Nearest Neighbor (NN) searching is a challenging problem in data management and has been widely studied in data mining, pattern recognition and computational geometry. The goal of NN searching is efficiently reporting the nearest data to a given object as a query. In most of the studies both the data and query are assumed to be precise, however, due to the real applications of NN searching, such as tracking and locating services, GIS and data mining, it is possible both of them are imprecise. So, in this situation, a natural way to handle the issue is to report the data have a nonzero probability —called nonzero nearest neighbor— to be the nearest neighbor of a given query. Formally, let P be a set of n uncertain points modeled by some regions. We first consider the following variation of NN searching problem under uncertainty. If both the query and the data are uncertain points modeled by distinct unit segments parallel to the x-axis, we propose an efficient algorithm that reports nonzero nearest neighbors under Manhattan metric in O(n^2 α(n^2 )) preprocessing and O(logn+k) query time, where α(.) is the extremely slowly growing functional inverse of Ackermann’s function. Finally, for the arbitrarily length segments parallel to the x-axis, we propose an approximation algorithm that reports nonzero nearest neighbor with maximum error L in O(n^2 α(n^2 )) preprocessing and O(logn+k) query time, where L is the length of the query.
E.3. Analysis of Algorithms and Problem Complexity
M. Asghari; H. Nematzadeh
Abstract
Suspended particles have deleterious effects on human health and one of the reasons why Tehran is effected is its geographically location of air pollution. One of the most important ways to reduce air pollution is to predict the concentration of pollutants. This paper proposed a hybrid method to predict ...
Read More
Suspended particles have deleterious effects on human health and one of the reasons why Tehran is effected is its geographically location of air pollution. One of the most important ways to reduce air pollution is to predict the concentration of pollutants. This paper proposed a hybrid method to predict the air pollution in Tehran based on particulate matter less than 10 microns (PM10), and the information and data of Aghdasiyeh Weather Quality Control Station and Mehrabad Weather Station from 2007 to 2013. Generally, 11 inputs have been inserted to the model, to predict the daily concentration of PM10. For this purpose, Artificial Neural Network with Back Propagation (BP) with a middle layer and sigmoid activation function and its hybrid with Genetic Algorithm (BP-GA) were used and ultimately the performance of the proposed method was compared with basic Artificial Neural Networks along with (BP) Based on the criteria of - R2-, RMSE and MAE. The finding shows that BP-GA has higher accuracy and performance. In addition, it was also found that the results are more accurate for shorter time periods and this is because the large fluctuation of data in long-term returns negative effect on network performance. Also, unregistered data have negative effect on predictions. Microsoft Excel and Matlab 2013 conducted the simulations.
