Using Rank Based KNN Queries Processing to Reduce Location Uncertainty in Wireless Sensor Networks - Term Paper Example

Abstract—imprecise or uncertain data are very common in a number of applications nowadays and this has contributed to the growth of several uncertain database frameworks. Since k-nearest neighbor (KNN) query is a very important issue in a number of applications, it has been broadly studied. The main aim of this paper is to study the issue of KNN query processing over uncertain data. To achieve this, I used the expected rank technique to work out KNN. Randomized and exact techniques integrating efficient IO accessing and object pruning techniques were formulated to process queries modelled by uncertain regions or query points. General experiments were carried out on both synthetic and real data to show the efficiency of randomized and exact approaches. Index Terms—exact technique, expected rank, k-nearest neighbor query, and randomized technique. I. INTRODUCTION Rapid improvements in positioning technologies, such as wireless communications and Global Positioning System (GPS), have made it possible to track continuously moving objects[YiK08]. A number of applications may benefit from the growth of such tracking technologies. The advancements of sensors and wireless technology have supported wide use of sensor systems or networks[Chi13][Tra11][Ail09]. Query processing and data collection in a sensor network are challenging research areas in sensor network database management. A number of applications that deals with such data have to come to terms with imprecise or uncertain data. In the vast majority of the evolving applications, the basic datasets are regularly imprecise or uncertain. There are variations in the sources of uncertainty data among different applications. Privacy preservation, limitations of the devices, delay on data updates, and data incompleteness and randomness are some of the causes of uncertainty data in some applications[XuC13][Sol07][RCh08]. Therefore, it is an essential thing for the database community to come up with ways of efficiently handling the uncertain data. As the number of applications that employ spatio-temporal data sets is increasing, it is very important to develop efficient query processing techniques for these applications[Nie14][Lia08]. In spatio-temporal databases, the K-Nearest Neighbor (KNN) query is a very important query[Bes08][Win05]. KNN query has been employed in a number of applications including facial pattern recognition, sensor network, traffic network analysis, and location based services[Chi13][Cab03]. On the other hand, the data uncertainty in these applications contributes to incorrect results. KNN query over imprecise data is very essential as it is employed in a number of real life applications. Processing of KNN queries in large spatio-temporal databases has been extensively examined preciously, but only a few studies have concentrated on uncertain data[Gen08]. To handle the growing needs of providing high-quality services and managing data uncertainty, researchers have suggested the use of “uncertain databases,” in which uncertainty is given priority[Che03][Ant07]. Specifically, the uncertain data is assessed through probabilistic queries, which provides solutions with statistical and probabilistic assurance. A data model that is widely used and adopted in databases with uncertainty is the attribute uncertainty[Ben06], in which the real attribute measure is situated in the uncertainty region or inside a closed region[Gen08]. The probabilistic database in the Attribute-level uncertainty model is an N tuples table. Every tuple has a single attribute with uncertain value. Each attribute with uncertainty has a discrete pdf defining its distribution. When representing this imprecise association to a given instance, all the tuples draw values for their uncertain attribute in accordance with the related discrete pdf and the selection is not dependent amongst the tuples. A number of studies have described the nearest neighbor (NN) query over data uncertainty as a Probabilistic Nearest Neighbor (PNN) based query, which positions objects with uncertainty according to their probabilities of being a query q nearest neighbor[Che03][Cor092][Dal04][Lia08]. In other studies, the ranking of uncertain data is based on the U-topk and expected score[Zha10][Bes08]. The effectiveness of the two semantics is evaluated using five important properties namely: stability, value invariance, unique ranking, containment, and exact-k[Zha10][LiG11]. The U-topk semantic does not satisfy the containment and exact-k properties, while the expected score ranking is responsive to the values and therefore it goes against the property of value invariance[Zha10].The expected rank suggested in [Cor092] meets all the properties that are mentioned above and this motivated me to apply it in this paper to rank objects with uncertainty for KNN queries. Though I am applying this technique, applying directly as it has been done in [Cor092] does not result to effective answers for the KNN queries over imprecise data. This paper will come up with CPU and IO time efficient algorithm that will be used to get the expected rank based KNN. The semantic of the KNN query used in this paper varies from the one used in [VLj07] and [Che09]. The techniques used in [VLj07] and [Che09] cannot apply in this paper as in [VLj07], the technique just considers the distance in L1 and in [Che09] the technique presume that there is a distribution of the distance between the object with uncertainty and a query point. The Monte-Carlo simulation has been used in some latest studies [Sol07] in an effort to handle the complex correlations amongst the imprecise data. Using the Markov Chain Monte-Carlo (MCMC) technique, this paper will develop an effective randomized algorithm to roughly work out k nearest neighbor. The randomized algorithm proposed in this paper can attain a substantial performance enhancement on the KNN query, even in applications that do not have data correlations, particularly when the query is uncertain or possible locations of an object are enormous. In the paper I am improving, the researchers developed an efficient method to quantify the moving objects uncertainty in the sensor network. This was done through the adoption of a minimum rectangle that enclosed the region with uncertainty and was used to estimate the region with uncertainty in query processing. The positive side of their solution is that it provided the approximate location of the moving object. This paper will employ the expected rank semantic to rank uncertain data for KNN queries. Expected rank is considered meet all the five properties described above. The expected ranks technique was adopted for two major reasons. The first reason is that a rank of tuple in a given database is a fixed number, whilst in a database that is uncertain, the fixed number changes to a random variable. Therefore, for ranking KNN queries, my major concern should be on the distribution of thos random variable. The second reason is that the expectation of rank of a tuple may function as the foundation for developing the concluding ranking of all the probabilistic tuples. Contributions: In general, my contributions in this paper may be summarized as follows: A rank based KNN query over location uncertainty information is introduced, where the expected rank is considered. Development of the exact and randomized algorithms for expected rank based KNN queries processing Comparing two techniques of measuring the uncertainty of moving objects in the sensor network Conducting an experiment on both synthetic and real data to show the effectiveness of expected rank technique Organization of the paper: This paper is organized as follows: Section II presents the related work. Section III presents the rank based KNN query and exact and randomized algorithms for rank based KNN query. Section IV presents the performance evaluation and Section V is the conclusion of the paper. II. Related Work The significance of the spatio-temporal queries was first identified by Sistla et al. [Sis97] and these authors defined query languages and modeling techniques for the expression of spatio-temporal queries. Additionally, these authors tried to construct a database of moving objects that they referred to as the DOMINO [Sis97], on top of already prevailing database management systems. The primary goal of their database, DOMINO, was to keep up with recent types of spatio-temporal query language and attributes for moving objects. Nonetheless, problems related to the processing of spatio-temporal queries have not been fully handled by the works named earlier. Over the years, a number of techniques have been developed to process these queries efficiently over moving or location-based objects. Tao and Papadias[Tao02] suggest a query processing technique that is repetitive with a TPR-tree for processing k nearest neighbor and range queries. Kalashnokov et al. [Kal02] suggest a technique operated with Quadtree and R-tree to effectively process range query. Benetis et al.[Ben02] designed a technique to find the NN by a TPR-tree depth-first traversal. In order to reduce the computational cost and adapt to moving objects, Raptopoulou, Papadopoulos and Manolopoulos [Rap03] suggest effective techniques that process the KNN query by mapping out the kth nearest neighbor (NN). Iwerks, Samet and Smith [Iwe03] processed a KNN query by using a technique that first processed the range query and then the k nearest neighbor query is computed from the objects that qualify the range query. Whenever the amount of objects that qualify the range query is bigger than K, then the solution to k nearest neighbor query may be determined from such objects. Song and Roussopoulos [Son01] suggest a technique whereby the snapshot k nearest neighbor query is re-assessed at every time moment. However, this technique can only process KNN query over static objects. The approach in [Son01] was improved by Nehme and Rundensteiner [Neh06] to process KNN query over moving object datasets. These researchers used the concepts of incremental evaluation and shared execution in order to process range query over moving objects. [Win05][XuC13][Zha10] [Han14] also adopted the technique of incremental evaluation in their work to process the KNN query. The KNN techniques described above are designed for the moving objects, whereby the GPS technique is used to obtain the locations of object s rather than using the sensor network technique. In addition, all the techniques cited above concentrate on processing the KNN query under the condition that the location of the moving objects is known. This is a clear indication that the above mentioned techniques cannot be applied to process the KNN query over moving objects with uncertain locations as suggested in this paper. Cheng et al.[Che09] suggest a PNN query technique for processing the KNN query over uncertain objects as discussed later in this section. The nature of uncertainty data in a number of applications has contributed to the growth of several uncertain database models, where most of them are formulated on basis of either attribute-level or tuple-level uncertainty[Ben06][Bes08]. This paper has modelled the uncertain data on basis of the attribute-level. A huge number of studies related to uncertain data has concentrated on top-k queries having a number of semantics like c-Typical-Topk, U-topk, expected rank topk U-kranks, Global-topk and PT-k[Zha081][Cab03]. The issue of processing KNN query over imprecise data has been evaluated in a number of latest studies as an extension of top-k query. This has been attributed to the natural data uncertainty in a number of applications including sensor network, traffic network analysis, and location based services[Dal04]. However, most of the recent studies have concentrated on the PNN query, which is considered a unique example of k nearest neighbor query with k = 1[Win05][Ail09][Zha11][Yue10][LiJ10]. Specifically, in Cormode, Li and Yi [Win05] worked out the qualification probabilities of moving objects fulfilling PNN by basically changing the uncertainty of every object to CDF and PDF subject to its distance from q. Another study by [Yue10] suggests a strategy to establish a mapping of objects by multiplex points analyzed from their PDF. Cabello and van Kreveld [Cab03] have handled the issue of effective recovery of data objects with least total distance from different forms of queries. In [Han14] and [Zha081] existential probability is applied to obtain lower and upper bounds for object pruning. Existential probability is used to indicate the possibility of an existing object in the database. Despite the fact that the studies mentioned above may yield the top-k subject to their likelihood of being the query nearest neighbor, the semantic is naturally not the same with the conventional k nearest neighbor query[LiG11]. Only two major studies that have concentrated on the KNN query over uncertain data,[VLj07] and [Che09]. Ljosa and Singh suggest an efficient index structure, referred to as the APLA-tree[VLj07]. They used this index structure to effectively rank objects in accordance with their anticipated distances to the query. Another study by [Sol07] concentrated on the T-k-PNN query. The T-k-PNN query gets several k objects sets fulfilling the query with probabilities that are greater than a certain threshold T. This study develops an indexing strategy referred to as the k-bound filtering, and the researchers also indicate that the working out of K-PNN may also be achieved through the use of distance based CDFs and PDFs[Sol07]. III. Ranked based knn query In this section, the paper will characterize the issue of rank based k nearest neighbor query and concentrate on the expected rank based KNN query. It will likewise discuss the randomized and exact algorithms for rank based k nearest neighbor query. A. Problem Definition An uncertain object is either described as discrete or continuous[Kri07][Han14]. In regard to continuous type, an uncertain object N is identified by uncertain region, denoted by Nr and its Probability Density Function (PDF), denoted by N.pdf. The appears with a probability of N.pdf(x) and In regard to discrete type, an object with uncertainty N, comprises of a group of instances {n1… nm} where ni appearance probability pni, and Basically, N.pdf. is often expressively inaccessible and estimated through a group of analyzed instances. This paper has mostly focused on the discrete uncertain object. The query described in this paper can be an uncertain object or a point. The term object is used in the paper present uncertain object if there is no uncertainty. Figure 1: Problem Definition Set of objects: N = {N1, N2, ………., Nn} N = {N1, N2, N3, N4} Possible World: W = {n1, n2, n3, ……., nn} W1 = {N1, N2} From the above equations, a rank of an object N in one possible world W can be represented as follows[Zha10]: Expected rank, erq (N), of a given group of objects Ŋ and a query q can be defined as follows[Zha10]: To simplify the presentation, if there is no uncertainty, the paper has used r (n) to represent the rank of an instance and er(N) to represent the expected rank of an object concerning a query q. This paper focuses on evaluating the problem of getting k nearest neighbors for a particular query q in accordance with the expected ranks of n objects. Devoid of losing the generality, I have assumed that n is bigger than k and their relation is broken by object ids. Using the expected ranks to process the KNN queries appears to be much easier than the design that was used in the paper I am improving because it was not easier to for the researchers to design an index structure because of the uncertainty on object locations[Zha10][Hua081][Hua081]. The researchers in that paper used a grids index to try to manage the uncertainty of objects’ location. In their model, the uncertainty of object’s location was presented as an estimate area using a rectangular outline. A grid index was used to effectively handle the approximate or estimate sections. Partitioning of the data space was first done, where they were partitioned into N*N grid cells, and then all the grid cells were used to store information about the objects and the sensor within it. Combining the grid index structure with an effective algorithm to process the k nearest neighbor query was not an easy task. This was much complicated compared to expected ranks, where a simpler algorithm can be used. Employing the well-established idea of the expected rank of every tuple over all possible worlds as the foundation of ranking, this paper develops an efficient algorithm for processing KNN queries over uncertain data. Table 1: Comparison between Expected Ranks Technique with the Grid Index Structure Technique Expected Ranks Grid Index Structure Rank-aware query processing can efficiently obtain the top-k objects Minimizes the number of comparison but can cause non-exact result if k is found outside the approximate region Easily locate the answer points during the Sweepline process It is not easy to combine the grid index structure with an effective algorithm to process KNN query A simpler algorithm may be used to process the KNN query based on the well-founded idea of expected rank Bound based and interval based technique cannot be applied in this method Bound based and interval based techniques can be employed for top-k query B. Finding Minimal Set for Kth Smallest Element The kth smallest component can be found amongst a set of n components, in which every component c is related to an interval Ic = [l(Ic), r(Ic)] to establish its maximum or minimum possible value. To get the exact value of c, a cost c(c) is needed. The most applied idea is to first get the smallest set of intervals which could have the kth smallest element. This is normally done using two common approaches namely the interval graph based technique and the bound based technique. The former technique finds the smallest set by dividing all the intervals into g categories in such a way that there are no intervals from the same category can overlap with one another. One advantage of the interval graph based technique is that the candidate set just comprises not more than 2 x g intervals. Despite the fact that a polynomial-time algorithm[Zha10] is available to divide intervals into small g categories, the time cost associated with this technique is huge particularly if intervals are dynamically refined. The bound based technique is described as follows: “Given a set of interval {I = [l(I), r(I)]}, the kth smallest component should belong to the interval Ic = [l, r], where l is the kth smallest l(I) and r is the (n − k + 1)th largest r(I). Then, any interval I with l(I) > r or r(I) < l may not have the kth smallest component[Zha10]”. As indicated in the figure below, only 4 intervals (I2 I3 I4 I5) may have the third smallest component. According to Zhang et al. [Zha10], the bound based technique performs better than the interval graph based technique in regards to candidate set size. As result, the bound based technique can be safely applied in this paper. Figure 2: Bound Based Technique[Zha10] When computing the KNN, the only thing that is required to be computed is the expected rank for the objects which may not be pruned or validated according to their probable minimal and maximal ranks. C. Exact Algorithm This sub-section will present an efficient algorithm to find k objects which has the greatest expected ranks for a particular query q. Algorithm 1[Zha10] below presents the main body of an efficient KNN algorithm. The Initialize procedure is used to calculate the candidate objects and the implementation is based on a min heap and R-tree. The candidate denoted by set Ί comprises of intervals generated for the objects which are candidates. The Sweepline process is called in order to effectively calculate the ranks of objects and modify r and l. The objects could be validated or pruned during the calculation, while the ProbeIntervals procedure is invoked to examine the intervals in a level-by-level manner. The Sweepline process is demonstrated in Algorithm 2[Zha10]. Algorithm 2 highlights the details of the sweepline procedure used in computing the expected rank. For every object, a flag is used to show whether the object active or not. In this algorithm, an object is considered active if and only if it is not validated or pruned by r and l. The only ranks that need to be computed are only those for the active objects. The sweep line paradigm is used to effectively work out the active objects ranks. As indicated in Lines four (4) and five (5) of the algorithm 2 below, the beginning and finish points of the intervals are being separated in Ί in which start (end) point got distance value d−(I) (d+(I)). For a given point p, its associated interval and object are represented by p.I and p.obj correspondingly. Subsequently, it is possible to accumulatively compute the rank of active objects and this information is shown in Line six (6) to twenty two (22). As indicated in Line thirteen (13) to seventeen (17), when the computation of the rank of an object is over, the r and l are updated and if the object is validated or pruned, its flag is set to inactive. The results of the sweepline procedure are as shown in the figure below: Figure 3: Sweepline Procedure Results[Zha10] D. Randomized Algorithm This sub-section presents the randomized algorithm for processing the rank based k nearest neighbor query. The primary intention of this algorithm is sampling the possible world in such a way that the expected rank may be roughly calculated in an efficient manner[Han14][LiJ10]. The randomized algorithm for expected rank computation is a shown below: Algorithm 3 presents an IO and CPU efficient algorithm which is based on the incremental nearest neighbor method[Zha10]. Similar to the exact algorithm, the candidate object is first found for the k nearest neighbor query using the global R-tree[Zha081][Yue10]. The maximal and minimal expected rank of all the objects may be computed using the Sweepline algorithm suggested in exact algorithm subsection (sub-section B). 1 and r in the above algorithm are values to validate or prune objects for the KNN query. As demonstrated in Algorithm 3 below, Nrmin and Nrmax of all the objects are first calculated on basis of their uncertain regions. Line 6 and 14 iteratively update the values of Nrmin and Nrmax of objects through getting the subsequent nearest neighbor in every sample. Figure 4: An Example of KNN[Zha10] The table below shows the notations in the algorithms Table 2 : The Summary of Notations in the Algorithms IV. performance evaluation This section discusses the results of the performance evaluation in terms of scalability and effectiveness of the suggested techniques in this paper. All the algorithms suggested in this paper are carried out using standard C++ programming language with Standard Template Library (STL) support and compiled with GNU Compiler Collection. From the results, the exact expected rank algorithm is very slow as compared to other algorithms as a result of its bigger number of Input/Output invoked. The randomized technique performed well than all the other techniques on various data sets. The amount of instances of every object (m) does not affect the performance of the randomized technique for a specific sample rate s, but the exact technique performance is affected by the amount of instances of every object as it drops with m. The uncertain region size affects both types of techniques and the larger it is the poorer the exact and randomized algorithms perform. However, randomized algorithm is less sensitive as to the increase of the uncertain region size as compared to the exact algorithm[Han14][Zha11]. The approximation quality of both techniques gets better when the sampling rate s, increases[LiJ10][Hua081]. The randomized algorithm is also less sensitive to the growth of k value in KNN query as shown in the following figure: Figure 5: Performance vs Different k[Zha10] Figure 6: Different n on USz[Zha10] As illustrated in Figure 6 above, the performance of both algorithms decreases gradually against the growth of the number of objects, n. Figure 7 below examine the effect of the amount of instances m on the two algorithms, in which m increases from 500 to 8000. As indicated in the figure, the increase of the amount of instances did not affect the performance of the randomized algorithms for a particular sample rate s. On the hand, the performance of the exact algorithm decreases with the number of instances. Figure 7: Different the Number of Instances of each Object m[Zha10] Figure 8 below evaluates the effect of uncertain region size ru, where it varies from 50 to 400. Both algorithms were affected by the size of the uncertain region because as the size increased all the algorithms performed poorly. However, as seen from the diagram, the randomized algorithm is less sensitive to the uncertain region growth. In other words, the performance of the randomized was not affected a lot by the uncertain region size as compared to the exact algorithm, which performed very poorly as the uncertain region size increases. Figure 8: Different Uncertain Region Size ru[Zha10] Figure 9 below evaluates the effect of sampling rate, s, on randomized algorithm on datasets LBZ and LBU. an increase in the sampling rate enhance the randomized algorithm approximation quality. The randomized algorithm managed to attain a recall and precision value of about 0.95 with only 200 rounds of trials. Figure 9: Different Sampling Rate, s[Zha10] Other experiments performed show that the accuracy of randomized algorithms increased with the increase of k value in KNN query. The randomized algorithm was also identified to perform much faster than the exact algorithm[Kri07][Stu101]. V. Conclusion This paper has focused on the rank based k nearest neighbor (KNN) query processing over uncertain data. It has specifically focused on expected rank ranking criteria as it satisfied all the top-k properties. Randomized and exact techniques integrating efficient IO accessing and object pruning techniques were developed to process queries modeled by uncertain regions or query points. General experiments were carried out on both synthetic and real data to show the efficiency of techniques used in this paper. References YiK08: , [1], Chi13: , [1], Tra11: , [3], Ail09: , [4], XuC13: , [3], Sol07: , [4], RCh08: , [5], Nie14: , [6], Lia08: , [7], Bes08: , [4], Win05: , [10], Chi13: , [2], Cab03: , [5], Gen08: , [6], Che03: , [7], Ant07: , [12], Ben06: , [13], Cor092: , [8], Dal04: , [9], Lia08: , [10], Zha10: , [11], LiG11: , [15], Cor092: , [17], VLj07: , [21], Che09: , [22], Sol07: , [6], Sis97: , [23], Tao02: , [23], Kal02: , [24], Ben02: , [25], Rap03: , [26], Iwe03: , [27], Son01: , [28], Neh06: , [29], Win05: , [11], XuC13: , [5], Zha10: , [19], Han14: , [30], Che09: , [22], Ben06: , [12], Bes08: , [8], Zha081: , [13], Cab03: , [9], Dal04: , [15], Win05: , [14], Ail09: , [15], Zha11: , [16], Yue10: , [17], LiJ10: , [24], Win05: , [14], Yue10: , [15], Han14: , [16], Zha081: , [20], LiG11: , [19], VLj07: , [17], Che09: , [18], Sol07: , [19], Sol07: , [19], Kri07: , [26], Han14: , [25], Hua081: , [27], Hua081: , [29], Zha10: , [19, p. 32], Zha10: , [19], Han14: , [23], LiJ10: , [28], Zha081: , [32], Yue10: , [34], Han14: , [31], Zha11: , [33], LiJ10: , [35], Hua081: , [37], Kri07: , [36], Stu101: , [38], [1] K. Yi, F. Li, G. Kollios and D. Srivastava, "Efficient processing of top-k queries in uncertain databases," in ICDE, 2008. [2] Y.-P. Chi and H.-P. Chang, "An energy-aware grid-based routing scheme for wireless sensor networks," Telecommunication Systems, vol. 54, no. 4, pp. 405-415, 2013. [3] G. Trajcevski, R. Tamassia, I. F. Cruz, P. Scheuermann, D. Hartglass and C. Zamierowski, "Ranking continuous nearest neighbors for uncertain trajectories," VLDB J, vol. 20, no. 5, pp. 767-791, 2011. [4] N. Ailon, "A simple linear ranking algorithm using query dependent intercept variables," Google Research, New York, 2009. [5] C. Xu, Y. Gu, L. Chen, J. Qiao and G. Yu, "Interval reverse nearest neighbor queries on uncertain data with markov correlations," in Proc. ICDE, 2013. [6] M. A. Soliman, I. F. IIyas and C. K. Chen-Chuan, "Top-k query processing in uncertain databases," in ICDE 2007, 23rd International Conference on Data Engineering, Istanbul, 2007. [7] C. R, J. Chen, M. M and C.-Y. Chow, "Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data," in ICDE 2008, IEEE 24th International Conference on Data Engineering, Cancun, 2008. [8] J. Niedermayer, A. Zufle, T. Emrich, M. Renz, N. Mamoulis, L. Chen and H.-P. Kriegel, "Probabilistic nearest neighbor queries on uncertain moving object trajectories," in Proceedings of the VLDB Endowment, Hangzhou, China, 2014. [9] X. Lian and L. Chen, "Probabilistic group nearest neighbor queries in uncertain databases," Knowledge and Data Engineering, vol. 20, no. 6, pp. 809-824, 2008. [10] G. Beskales, M. A. Soliman and I. F. IIyas, "Efficient search for the top-k probable nearest neighbors in uncertain databases," in Proceedings in VLDB Endowment, Auckland, New Zealand, 2008. [11] J. Winter, Y. Xu and W.-C. Lee, "Energy efficient processing of K nearest neighbor queries in location-aware sensor networks," in The Second International Conference on Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous'05), San Diego, 2005. [12] S. Cabello and M. J. van Kreveld, "Approximation algoritms for alignning points," in Symposium on compuational Geometry, 2003. [13] X. Geng, T.-Y. Liu, T. Qin, A. Arnold, H. Li and H.-Y. Shum, "Query dependent ranking using k-nearest neighbor," in Microsoft Research, 2008. [14] R. Cheng, D. V. Kalashnikov and S. Prabhakar, "Evaluating probabilistic queries over imprecise data," in SIGMOD Conference, 2003. [15] L. Antova, C. Koch and D. Olteanu, "Querylanguage support for incomplete information in the maybms system," in VLDB, 2007. [16] O. Benjelloun, A. D. Sarma, A. Y. Halevy and J. Widom, "Uldbs: Databases with uncertainty and lineage," in VLDB, 2006. [17] G. Cormode, F. Li and K. Yi, "Semantics of ranking queries for probabilistic data and expected ranks," in ICDE, 2009. [18] N. N. Dalvi and D. Suciu, "Efficiency query evaluation on probabilistic databases," in VLDB, 2004. [19] Y. Zhang, X. Lin, G. Zhu, W. Zhang and Q. Lin, "Efficient rank based KNN query processing over uncertain data," in 2010 IEEE 26th International Conference on Data Engineering (ICDE), Long Beach, CA, 2010. [20] G. Li, Y. Li, L. Shu and P. Fan, "Cknn query processing over moving objects with uncertain speeds in road networks," in APWeb, 2011. [21] V. Ljosa and A. K. Singh, "APLA: Inbdexing arbitrary probability distributions," in 2007 ICDE, IEEE 23rd International Conference on Data Engineering, Istanbul, 2007. [22] R. Cheng, L. Chen, J. Chen and X. Xie , "Evaluating probability threshhold k-nearest-neighbor queries over uncertain data," in EDBT, 2009. [23] A. P. Sistla, O. Wolfson, S. Chamberlain and S. Dao, "Modeling and quering moving objects," in Proceeding of the International Conference on Data Engineering, Birmingham, UK, 1997. [24] Y. Tao and D. Papadias, "Time parametrized queries in spatio-temporal databases," in Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, WI, USA, 2002. [25] D. V. Kalashnikov, S. Prabhakar, S. Hambrusch and W. Aref, "Efficient evaluation of continuous range queries on moving objects," in Proceedings of the International Conference on Database and Expert Systems Applications, Aix en, France, 2002. [26] R. Benetis, C. S. Jensen, G. Karciauskas and S. Saltenis, "Nearest neighbor and reverse nearest neighbor queries for moving objects," in Proceedings of the International Database Engineering and Applications Symposium, Edmonton, Canada, 2002. [27] K. Raptopoulou, A. N. Papadopoulos and Y. Manolopoulos, "Fast nearest-neighbor query processing in moving object databases," GeoInformatica, vol. 7, no. 1, pp. 113-137, 2003. [28] G. Iwerks, H. Samet and K. Smith, "Continuous K-nearest neighbor queries for continuously moving points with updates," in Proceedings of the International Conference on Very Large Databases, Berlin, Germany, 2003. [29] Z. Song and N. Roussopoulos, "K-nearest neighbor search for moving query point," in Proceedings of the 7th International Symposium on advances in spatial and temporal databases, Redondo Beach, CA, USA, 2001. [30] R. V. Nehme and E. A. Rundensteiner, "SCUBA: Scalable Cluster-Based Algorithm for evaluating continuous spatio-temporal queries on moving objects," in Proceedings of the 10th International Conference on Extending Database Technology, Munich, Germany, 2006. [31] Y. Han, J. Tang, Z. Zhou, M. Xiao, L. Sun and Q. Wang, "Novel itinerary-based KNN query algorithm leveraging grid division routing in wireless sensor networks of skewness distribution," Personal and Ubiquitous Computing , vol. 18, no. 8, pp. 1989-2001, 2014. [32] X. Zhang and J. Chomicki, "On thesemantics and evaluation of top-k queries in probabilistic databases," in DBRank, 2008. [33] W. Zhang, "Nearest neighbor searching under uncertainty," in RIP Proposal, 2011. [34] S. M. Yuen, Y. Tao, X. Xiao, J. Pei and D. Zhang, "Superseding nearest neighbor search on uncertain spatial databases," IEEE Transactions on Knowledge and Data Engineering, vol. 22, no. 7, pp. 1041-1055, 2010. [35] J. Li and A. Deshpande, "Ranking continuous probabilistic datasets," in Proceedings of the VLDB Endowment, Singapore, 2010. [36] H.-P. Kriegel, P. Kunath and M. Renz, "Probabilistic nearest-neighbor query on uncertain objects," in 12th International Conference on Database systems of Advanced Applications (DASFAA 2007), Munich, 2007. [37] M. Hua, J. Pei, W. Zhang and X. Lin, "Ranking queries on uncertain data: A probabilistic threshold approach," in Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD'08, New York, NY, USA, 2008. [38] A. Stupar, S. Michel and R. Schenkel, "RankReduce - Processing k-nearest neighbor queries on top of MapReduce," in LSDS-IR, Geneva, Switzerland, 2010. Read More