• Database and Knowledge-Based Systems • Previous Articles     Next Articles

Continually Answering Constraint $\pmb k$-{\it\bfseries NN} Queries in Unstructured P2P Systems

Bin Wang1, Xiao-Chun Yang1, Guo-Ren Wang1, Ge Yu1, Lei Chen2, X. Sean Wang3, and Xue-Min Lin4   

  1. 1College of Information Science and Engineering, Northeastern University, Shenyang 110004, China 2Department of Computer Science, The Hong Kong University of Science and Technology, Hong Kong S.A.R., China 3Department of Computer Science, University of Vermont, Vermont, U.S.A. 4Department of Computer Science, The University of New South Wales, Australia
  • Received:2007-05-07 Revised:2008-02-09 Online:2008-07-10 Published:2008-07-10

We consider the problem of efficiently computing distributed geographical $k$-{\it NN} queries in an unstructured peer-to-peer (P2P) system, in which each peer is managed by an individual organization and can only communicate with its logical neighboring peers. Such queries are based on local filter query statistics, and require as less communication cost as possible, which makes it more difficult than the existing distributed $k$-{\it NN} queries. Especially, we hope to reduce candidate peers and degrade communication cost. In this paper, we propose an efficient pruning technique to minimize the number of candidate peers to be processed to answer the $k$-{\it NN} queries. Our approach is especially suitable for continuous $k$-{\it NN} queries when updating peers, including changing ranges of peers, dynamically leaving or joining peers, and updating data in a peer. In addition, simulation results show that the proposed approach outperforms the existing Minimum Bounding Rectangle (MBR)-based query approaches, especially for continuous queries.

Key words: testability; genetic algorithm; forecasting; test generation;

[1] Hjaltason G R, Samet H. Distance browsing in spatial da\-ta\-bases. {\it ACM Trans. Database Syst.}, 1999, 24(2):~265--318.
[2]} Korn F, Sidiropoulos N, Faloutsos C \it et al. \rm Fast nearest neighbor search in medical image databases. In {\it Proc. 22nd Int. Conf. Very Large Data Bases}, Mumbai (Bombay), India, 1996, pp.215--226.
[3]} Mouratidis K, Yiu M L, Papadias D \it et al. \rm Continuous nearest neighbor monitoring in road networks. In {\it Proc. 32nd Int. Conf. Very Large Data Bases}, Seoul, Korea, 2006, pp.43--54.
[4]} Seidl T, Kriegel H. Optimal multi-step $k$-nearest neighbor search. In {\it Proc. ACM SIGMOD Int. Conf. Management of Data}, Seattle, Washington, USA, 1998, pp.154--165.
[5]} Wang Y F, Hori Y, Sakurai K. Characterizing economic and social properties of trust and reputation systems in P2P environment. {\it Journal of Computer Science and Technology}, 2008, 23(1): 129--140.
[6]} V T de Almeida, R H G\"uting. Using dijkstra's algorithm to incrementally find the $k$-nearest neighbors in spatial network databases. In {\it Proc. the 2006 ACM Symposium on Applied Computing $($SAC$)$}, Dijon, France, 2006, pp.58--62.
[7]} Hu H, Lee D L, Xu J. Fast nearest neighbor search on road networks. In {\it Proc. 10th International Conference on Extending Database Technology $($EDBT$)$}, Munich, Germany, {\it Lecture Notes in Computer Science}, 3896, 2006, pp.186--203.
[8]} Kolahdouzan M R, Shahabi C. Voronoi-based $k$ nearest neighbor search for spatial network databases. In {\it Proc. 30th Int. Conf. Very Large Data Bases}, Toronto, Canada, 2004, pp.840--851.
[9]} Yiu M L, Papadias D, Mamoulis N, Tao Y. Reverse nearest neighbors in large graphs. {\it IEEE Trans. Knowl. Data Eng.}, 2006, 18(4): 540--553.
[10]} Jagadish H V, Ooi B C, Vu Q \it et al. \rm Vbi-tree: A peer-to-peer framework for supporting multi-dimensional indexing schemes. In {\it Proc. 22th Int. Conf. Data Engineering}, Atlanta, GA, USA, 2006, p.34.
[11]} Jagadish H V, Ooi B C, Vu Q H. Baton: A balanced tree structure for peer-to-peer networks. In {\it Proc. 23rd Int. Conf. Very Large Data Bases}, Trondheim, Norway, 2005, pp.661--672.
[12]} Tanenbaum A S. Computer Networks. Third edition, Prentice Hall PTR, ISBN 0-13-349945-6, 1996, pp.355--359.
[13]} Silberstein A, Braynard R, Ellis C \it et al. \rm A sampling-based approach to optimizing top-$k$ queries in sensor networks. In {\it Proc. 22nd Int. Conf. Data Engineering}, Atlanta, GA, USA, 2006, p.68.
[14]} Robinsy G, Zelikovskyz A. \rm Improved Steiner tree approximation in graphs. In {\it Proc. the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms $($SODA$)$}, San Francisco, CA, USA, 2000, pp.770--779.
[15]} Saltenis S, Jensen C S, Leutenegger S T \it et al. \rm Indexing the positions of continuously moving objects. In {\it Proc. ACM SIGMOD Int. Conf. Management of Data}, Dallas, Texas, USA, 2000, pp.331--342.
[16]} Tao Y, Papadias D. MV3R-tree: A spatio-temporal access method for timestamp and interval queries. In {\it Proc. 27th Int. Conf. Very Large Data Bases}, Rome, Italy, 2001, pp.431--440.
[17]} Ratnasamy S, Francis P, Handley M \it et al. \rm A scalable content addressable network. In {\it Proc. the 2001 ACM SIGCOMM Conference}, Santa Barbara, CA, USA, 2001, pp.161--172.
[18]} Stoica I, Morris R, Karger D \it et al. \rm Chord: A scalable peer-to-peer lookup service for Internet applications. In {\it Proc. the 2001 ACM SIGCOMM Conference}, Santa Barbara, CA, USA, 2001, pp.149--160.
[19]} Rowstron A, Druschel P. \rm Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In {\it Proc. the 18th IFIP/ACM International Conf. Distributed Systems Platforms}, Heidelberg, Germany, {\it Lecture Notes in Computer Science}, 2218, 2001, pp.329--350.
[20]} Zhao B Y, Kubiatowicz K, Joseph A D. \rm Tapestry: An infrastructure for fault-tolerant wide-area location and routing. {\it Technical Report}, University of California, Berkeley, 2001.
[21]} Aberer K, Mauroux P C, Datta A, Despotovic Z, Hauswirth M, Punceva M, Schmidt R. P-grid: A self-organizing structured p2p system. {\it SIGMOD Record}, 2003, 32(3): 29--33.
[22]} Crainiceanu A, Linga P, Machanavajjhala A \it et al. \rm P-ring: An index structure for peer-to-peer systems. {\it Technical Report}, TR2004-1946, Cornell University, 2004.
[23]} Bharambe A, Agrawal M, Seshan S. \rm Mercury: Supporting scalable multi-attribute range queries. In {\it Proc. the 2004 ACM SIGCOMM Conference}, Portland, Oregon, USA, 2004, pp.329--350.
[24]} Gnutella. http://www.gnutella.com/.
[25]} Guttman A. \rm R-trees: A dynamic index structure for spatial searching. In {\it Proc. ACM SIGMOD Int. Conf. Management of Data}, Boston, Massachusetts, USA, 1984, pp.47--57.
[26]} Bentley J. Multidimensional binary search trees used for associative searching. {\it Commun. ACM}, 1975, 18(9): 509--517.
[27]} Lin K I, Jagadish H V, Faloutsos C. The tv-tree: An index structure for high-dimensional data. {\it The VLDB Journal}, 1994, 3(4): 517--542.
[28]} Katayama N, Satoh S. \rm The sr-tree: An index structure for high-dimensional nearest neighbor queries. In {\it Proc. ACM SIGMOD Int. Conf. Management of Data}, Tucson, Arizona, USA, 1997, pp.369--380.
[29]} Berchtold S, Keim D A, Kriegel H P. \rm The x-tree: An index structure for high-dimensional data. In {\it Proc. 22nd Int. Conf. Very Large Data Bases}, Bombay, India, 1996, pp.28--39.
[30]} Uhlmann J K. Satisfying general proximity/similarity queries with metric trees. {\it Information Processing Letter}, 1991, 40(4): 175--179.
[31]} Brin S. Near neighbor search in large metric spaces. In {\it Proc. 21st Int. Conf. Very Large Data Bases}, Zurich, Switzerland, 1995, pp.574--584.
[32]} Navarro G. Searching in metric spaces by spatial approximation. {\it The VLDB Journal}, 2002, 11: 28--46.
[33]} Ciaccia P, Patella M, Zezula P. M-tree: An efficient access method for similarity search in metric spaces. In {\it Proc. 23rd Int. Conf. Very Large Data Bases}, Athens, Greece, 1997, pp.426--435.
[34]} Bozkaya T, Ozsoyoglu M. Indexing large metric spaces for similarity search queries. {\it ACM Trans. Database Syst.}, 1999, 24(3): 361--404.
[35]} Fagin R, Lotem A, Naor M. \rm Optimal aggregation algorithms for middleware. In {\it Proc. ACM SIGACT-SIGMOD Symp. Principles of Database Systems}, Santa Barbara, California, USA, 2001, pp.102--113.
[1] Yong-Hao Long, Yan-Cheng Chen, Xiang-Ping Chen, Xiao-Hong Shi, and Fan Zhou. Test-Driven Feature Extraction of Web Components [J]. Journal of Computer Science and Technology, 2022, 37(2): 389-404.
[2] Chun-Hui Wang, Zhi Jin, Wei Zhang, Didar Zowghi, Hai-Yan Zhao, Wen-Pin Jiao. Activity Diagram Synthesis Using Labelled Graphs and the Genetic Algorithm [J]. Journal of Computer Science and Technology, 2021, 36(6): 1388-1406.
[3] Jie Xiao, Zhan-Hui Shi, Jian-Hui Jiang, Xu-Hua Yang, Yu-Jiao Huang, Hai-Gen Hu. A Locating Method for Reliability-Critical Gates with a Parallel-Structured Genetic Algorithm [J]. Journal of Computer Science and Technology, 2019, 34(5): 1136-1151.
[4] Rong-Zhi Qi, Zhi-Jian Wang, Shui-Yan Li. A Parallel Genetic Algorithm Based on Spark for Pairwise Test Suite Generation [J]. , 2016, 31(2): 417-427.
[5] Concha Bielza, Juan A. Fernández del Pozo, and Pedro Larrañaga. Parameter Control of Genetic Algorithms by Learning and Simulation of Bayesian Networks —— A Case Study for the Optimal Ordering of Tables [J]. , 2013, 28(4): 720-731.
[6] Antonio M. Mora, Antonio Fernández-Ares, Juan J. Merelo, Pablo García-Sánchez, and Carlos M. Fernandes. Effect of Noisy Fitness in Real-Time Strategy Games Player Behaviour Optimisation Using Evolutionary Algorithms [J]. , 2012, 27(5): 1007-1023.
[7] Zhu-Fei Chu (储著飞), Student Member, IEEE, Yin-Shui Xia (夏银水), and Lun-Yao Wang (王伦耀). Cell Mapping for Nanohybrid Circuit Architecture Using Genetic Algorithm [J]. , 2012, 27(1): 113-120.
[8] Zi-Chu Qi (齐子初), Hui Liu (刘慧), Xiang-Ku Li (李向库), and Wei-Wu Hu (胡伟武). Design for Testability Features of Godson-3 Multicore Microprocessor [J]. , 2011, 26(2): 302-313.
[9] Xiao-Chen Li, Wen-Ji Mao, Senior Member, CCF, Member, ACM, Daniel Zeng, Senior Member, IEEE, Peng Su, and Fei-Yue Wang, Senior Member CCF, Fellow, IEEE. Performance Evaluation of Machine Learning Methods in Cultural Modeling [J]. , 2009, 24(6): 1010-1017.
[10] Feng Zeng, Student Member, CCF, and Zhi-Gang Chen, Member, CCF. Cost-Sensitive and Load-Balancing Gateway Placement in Wireless Mesh Networks with QoS Constraints [J]. , 2009, 24(4): 775-785.
[11] Sriparna Saha, Student Member, IEEE, and Sanghamitra Bandyopadhyay, Senior Member, IEEE. A New Line Symmetry Distance and Its Application to Data Clustering [J]. , 2009, 24(3): 544-556.
[12] Da Wang, Yu Hu, Hua-Wei Li, and Xiao-Wei Li. Design-for-Testability Features and Test Implementation of a Giga Hertz General Purpose Microprocessor [J]. , 2008, 23(6 ): 1037-1046 .
[13] Ji-Bao Lai , Hui-Qiang Wang, Xiao-Wu Liu, Ying Liang, Rui-Juan Zheng, and Guo-Sheng Zhao. WNN-Based Network Security Situation Quantitative Prediction Method and Its Optimization [J]. , 2008, 23(2): 222-230 .
[14] Ehab Z. Elfeky, Ruhul A. Sarker, and Daryl L. Essam. Analyzing the Simple Ranking and Selection Process for Constrained Evolutionary Optimization [J]. , 2008, 23(1): 19-34 .
[15] Sheng-Zhi Du, Zeng-Qiang Chen, and Zhu-Zhi Yuan. Evolutionary Pseudo-Relaxation Learning Algorithm for Bidirectional Associative Memory [J]. , 2005, 20(4): 559-566 .
Full text



[1] Tao Xuehong; Sun Wei; Ma Shaohan;. A Practical Propositional Knowledge Base Revision Algorithm[J]. , 1997, 12(2): 154 -159 .
[2] Cheng-Chun Shu, Hai-Yan Yu, and Hao-Zhi Liu. BEAP: An End-User Agile Programming Paradigm for Business Applications[J]. , 2006, 21(4): 609 -619 .
[3] Nam-Sup Park and Chong-Sun Hwang. Effective I/O Scheme Based on RTP for Multimedia Communication Systems[J]. , 2006, 21(6): 989 -996 .
[4] Jie Liang and Xue-Jia Lai. Improved Collision Attack on Hash Function MD5[J]. , 2007, 22(1): 79 -87 .
[5] En-Jian Bai and Xiao-Juan Liu. Some Notes on Prime-Square Sequences[J]. , 2007, 22(3): 481 -486 .
[6] Xiao-Lin Li and Jian-Nong Cao. Coordinated Workload Scheduling in Hierarchical Sensor Networks for Data Fusion Applications[J]. , 2008, 23(3): 355 -364 .
[7] Peter Szolovits. Possibilities for Healthcare Computing[J]. , 2011, 26(4): 625 -631 .
[8] Darko Brodić, Student Member, IEEE. Extended Approach to Water Flow Algorithm for Text Line Segmentation[J]. , 2012, 27(1): 187 -194 .
[9] Yue Wu, Yun-Ji Chen, Tian-Shi Chen, Qi Guo, Lei Zhang. An Elastic Architecture Adaptable to Various Application Scenarios[J]. , 2014, 29(2): 227 -238 .
[10] Jian-Liang Liu, Yong-Le Zhang, Lin Yang, Ming-Yang Guo, Zhen-Jun Liu, Lu Xu . SAC:Exploiting Stable Set Model to Enhance CacheFiles[J]. , 2014, 29(2): 293 -302 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved