Cited By
View all- Bavi KLian X(2023)Range-constrained probabilistic mutual furthest neighbor queries in uncertain databasesKnowledge and Information Systems10.1007/s10115-022-01807-065:6(2375-2402)Online publication date: 1-Jun-2023
Efficient multiple bichromatic mutual nearest neighbor query processing
Abstract
In this paper we propose, motivate and solve multiple bichromatic mutual nearest neighbor queries in the plane considering multiplicative weighted Euclidean distances. Given two sets of facilities of different types, a multiple bichromatic mutual ( k, k ' ) -nearest neighbor query finds pairs of points, one of each set, such that the point of the first set is a k-nearest neighbor of the point of the second set and, at the same time, the point of the second set is a k ' -nearest neighbor of the point of the first set. These queries find applications in collaborative marketing and prospective data analysis, where facilities of one type cooperate with facilities of the other type to obtain reciprocal benefits. We present a sequential and a parallel algorithm, to be run on the CPU and on a Graphics Processing Unit, respectively, for solving multiple bichromatic mutual nearest neighbor queries. We also present the time and space complexity analysis of both algorithms, together with their theoretical comparison. Finally, we provide and discuss experimental results obtained with the implementation of the proposed sequential and a parallel algorithm. HighlightsWe define and motivate multiple mutual bichromatic weighted nearest neighbor queries.We solve 2d multiple mutual nearest neighbor queries sequentially and parallelly.We theoretically analyze and compare the time and space complexity of both algorithms.We experimentally show the algorithms to be effective, robust and scalable.
References
[1]
E. Achtert, C. Böhm, P. Kroger, P. Kunath, A. Pryakhin, M. Renz, Efficient reverse k-nearest neighbor search in arbitrary metric spaces, in: SIGMOD, 2006.
[2]
R.J. Barrientos, J.I. Gómez, C. Tenllado, M.P. Matías, M. Marín, k-NN Query Processing in Metric Spaces using GPUs, in: Proceedings of the 17th International European Conference on Parallel and Distributed Computing (Euro-Par'11), 2011, pp. 380-392.
[3]
C. Böhm, S. Berchtold, D.A. Keim, Searching in high dimensional spaces, ACM Comput. Surv., 33 (2001) 322-373.
[4]
M.R. Brito, E.L. Chavez, A.J. Quiroz, J.E. Yukich, Connectivity of the mutual k-nearest neighbor graph in clustering and outlier detection, Stat. Probab. Lett., 35 (1997) 33-42.
[5]
B. Boots, R. South, Modeling retail trade areas using higher-order, multiplicatively weighted Voronoi diagrams, J. Retail., 73 (1997) 519-536.
[6]
S. Brown, J. Snoeyink, Gpu nearest neighbors using a minimal kd-tree, in: Second Workshop on Massive Data Algorithmics (MASSIVE), 2010.
[7]
L. Cayton, A nearest neighbor data structure for Graphics Hardware, in: VLDB-ADMS, 2010, pp. 1-6.
[8]
F.M. Choudhury, J.S. Culpepper, T. Sellis, X. Cao, Maximizing bichromatic reverse spatial and textual k nearest neighbor queries, in: Proceedings of the of the VLDB Endowment, vol. 9(6), 2016, pp. 456-467.
[9]
Y. Chen, J. Patel, Efficient evaluation of all-nearest-neighbor queries, in: ICDE, 2007, pp. 1056-1065.
[10]
K.L. Cheung, A.W.-C. Fu, Enhanced nearest neighbour search on the R-tree, SIGMOD, 27 (1998) 16-21.
[11]
T. Drezner, Optimal continuous location of a retail facility, facility attractiveness, and market share, J. Retail., 70 (1994) 49-64.
[12]
T. Drezner, Z. Drezner, Validating the gravity-based competitive location model using inferred attractiveness, Ann. Oper. Res., 111 (2002) 227-237.
[13]
M. Fort, J.A. Sellarès, Finding influential location regions based on reverse k-neighbor queries, Knowl. Based Syst., 47 (2013) 35-52.
[14]
M. Fort, J.A. Sellarès, Solving the k-influence region problem with the GPU, Inf. Sci., 269 (2014) 255-269.
[15]
M. Fort, J.A. Sellarès, Solving multiple bichromatic mutual nearest neighbor queries with the GPU, in: DASFAA 2014: SIM3, Database Systems for Advanced Applications, Lecture Notes in Computer Science, vol. 2014, 2014, pp. 308-316
[16]
M. Fort, J.A. Sellarès, Common influence region problems, Inf. Sci., 321 (2015) 116-135.
[17]
M. Fort, J.A. Sellarès, Solving multiple kth smallest dissimilarity queries for non metric dissimilarities with the GPU, Inf. Sci., 361-362 (2016) 66-83.
[18]
Y. Gao, G. Chen, Q. Li, B. Zheng, C. Li, Processing mutual nearest neighbor queries for moving object trajectories, in: Proceedings of the 9th International Conference on Mobile Data Management, 2008, pp. 116-123.
[19]
Y. Gao, B. Zheng, G. Chen, Q. Li, On efficient mutual nearest neighbor query processing in spatial databases, Data Knowl. Eng., 68 (2009) 705-727.
[20]
Y. Gao, B. Zheng, G. Chen, Q. Li, C. Chen, G. Chen, Efficient mutual nearest neighbor query processing for moving object trajectories, Inf. Sci. (2010) 2176-2195.
[21]
V. Garcia, E. Debreuve, F. Nielsen, M. Barlaud, k-nearest neighbor search: fast GPU-Based implementation and application to high-dimensional feature matching, in: Proceedings of the IEEE 17th International Conference on Image Processing (ICIP), 2010, pp. 3757-3760.
[22]
K.C. Gowda, G. Krishna, Agglomerative clustering using the concept of mutual nearest neighborhood, Pattern Recognit., 10 (1978) 105-112.
[23]
K.C. Gowda, G. Krishna, The condensed nearest neighbor rule using the concept of mutual nearest neighborhood, IEEE Trans. Inf. Theory, 25 (1979) 488-490.
[24]
G.R. Hjaltason, H. Samet, Distance browsing in spatial databases, ACM Trans. Database Syst., 24 (1999) 265-318.
[25]
W. Jin, A.K.H. Tung, J. Han, W. Wang, Ranking outliers using symmetric neighborhood relationship, in: Proceedings of the 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2006, pp. 577-593.
[26]
K. Kato, T. Hosino, Multi-GPU algorithm for k-nearest neighbor problem, Concurr. Comput.: Pract. Exp., 24 (2012) 45-53.
[27]
F. Korn, S. Muthukrishnan, Influence sets based on reverse nearest neighbor queries, in: SIGMOD, 2000.
[28]
Q. Kuang, L. Zhao, A practical GPU based k-NN algorithm, in: Proceedings of the 2nd International Symposium on Computer Science and Computational Technology (ISCSCT), 2009, pp. 151-155.
[29]
Y. Kumar, R. Janardan, P. Gupta, Efficient algorithms for reverse proximity query problems, in: Proceedings of the 16th ACM-GIS, vol. 39, 2008, pp. 1-10.
[30]
K.C.K. Lee, B. Zheng, W.C. Lee, Ranked reverse nearest neighbor search, IEEE Trans. Knowl. Data Eng., 20 (2008) 894-910.
[31]
P. Leite, J.M. Teixeira, T. Farias, V. Teichrieb, J. Kelner, Massively parallel nearest neigbhor queries for dynamic point clouds on the GPU, in: 21st International Symposium on Computer Architecture and High Performance Computing, 2009, pp. 19-25.
[32]
C.L. Li, E.T. Wang, G.J. Huang, A.L.P. Chen, Top-n query processing in spatial databases considering bi-chromatic reverse k-nearest neighbors, Inf. Syst., 42 (2014) 123-138.
[33]
S. Liang, Y. Liu, C. Wang, L. Jian, Design and evaluation of a parallel K-nearest neighbor algorithm on CUDA-enabled GPU, in: Proceedings of the 2nd IEEE Symposium of Web Society, 2010, pp. 53-60.
[34]
N. Miranda, E. Chávez, M.F. Piccoli, N. Reyes, (Very) fast (all) k-nearest neighbors in metric and non metric spaces without indexing, in: SISAP, Lecture Notes in Computer Science, vol. 8199, 2013, pp. 300-311.
[35]
B. Mendes, I.H. Themido, Multi-outlet retail site location assessment, Int. Trans. Oper. Res., 11 (2004) 1-18.
[36]
A. Papadopoulos, Y. Manolopoulos, Performance of nearest neighbor queries in R-trees, in: Proceedings of the Sixth International Conference on Database Theory (ICDT), 1997, pp. 394-408.
[37]
N. Roussopoulos, S. Kelley, F. Vincent, Nearest neighbor queries, in: Proceedings of the ACM International Conference on Management of Data (SIGMOD), 1995, pp. 71-79.
[38]
N. Sismanis, N. Pitsianis, X. Sun, Parallel search of k-nearest neighbors with synchronous operations, in: HPEC, 2012, pp. 1-6.
[39]
I. Stanoi, M. Riedewald, D. Agrawal, A.E. Abbadi, Discovery of influence sets in frequently updated databases, in: Proceedings of the 27th International Conference on Very Large Data Bases (VLDB), 2001, pp. 99-108.
[40]
Y. Sun, R. Zhang, A.Y. Xue, J. Qi, X. Du, Reverse nearest neighbor heat maps: a tool for influence exploration, in: Proceedings of the 31th IEEE International Conference on Data Engineering (ICDE), 2016.
[41]
R.C.-W. Wong, Y. Tao, A.W.C. Fu, X. Xiao, On efficient spatial matching, in: Proceedings of the 33rd International Conference on Very Large Data Base, 2007, pp. 579-590.
[42]
W. Wu, F. Yang, C.Y. Chan, K. Tan, FINCH: evaluating reverse k-Nearest-Neighbor queries on location data, in: Proceedings of the VLDB, vol. 1(1), 2008, pp. 1056-1067.
[43]
C. Xia, H. Lu, B.C. Ooi, J. Hu, Gorder: an efficient method for knn join processing, in: Proceedings of the VLDB 2004, 2004, pp. 756-767.
[44]
B. Yao, F. Li, P. Kumar, K-nearest neighbor queries and knn-joins in large relational databases (almost) for free, in: Proceedings of the ICDE 2010, 2010, pp. 4-15.
[45]
J. Zhang, N. Mamoulis, D. Papadias, Y. Tao, All-nearest-neighbors queries in spatial databases, in: Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM), 2004, pp. 297-306.
Recommendations
On efficient obstructed reverse nearest neighbor query processing
GIS '11: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsIn this paper, we study a new form of reverse nearest neighbor (RNN) queries, i.e., obstructed reverse nearest neighbor (ORNN) search. It considers the impact of obstacles on the distance between objects, which is ignored by the existing work on RNN ...
A new approach for maximizing bichromatic reverse nearest neighbor search
Maximizing bichromatic reverse nearest neighbor (MaxBRNN) is a variant of bichromatic reverse nearest neighbor (BRNN). The purpose of the MaxBRNN problem is to find an optimal region that maximizes the size of BRNNs. This problem has lots of real ...
On efficient mutual nearest neighbor query processing in spatial databases
This paper studies a new form of nearest neighbor queries in spatial databases, namely, mutual nearest neighbor (MNN) search. Given a set D of objects and a query object q, an MNN query returns from D, the set of objects that are among the k"1 (>=1) ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier Ltd.
Publisher
Elsevier Science Ltd.
United Kingdom
Publication History
Published: 01 December 2016
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
Cited By
View all- Bavi KLian X(2023)Range-constrained probabilistic mutual furthest neighbor queries in uncertain databasesKnowledge and Information Systems10.1007/s10115-022-01807-065:6(2375-2402)Online publication date: 1-Jun-2023
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in