Processing transitive nearest-neighbor queries in multi-channel access environments

• Main Authors: ZHANG, Xiao, LEE, Wang-Chien, MITRA, Prasnjit, ZHENG, Baihua
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2008
• Subjects: Multi-Channel access; transitive nearest neighbor; query processing; query optimization; approximate nearest neighbor; Computer Sciences; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/404; https://ink.library.smu.edu.sg/context/sis_research/article/1403/viewcontent/ProcessingTNNinMultiChannel.pdf
• Institution: Singapore Management University

Wireless broadcast is an efficient way for information dissemination due to its good scalability [10]. Existing works typically assume mobile devices, such as cell phones and PDAs, can access only one channel at a time. In this paper, we consider a scenario of near future where a mobile device has the ability to process queries using information simultaneously received from multiple channels. We focus on the query processing of the transitive nearest neighbor (TNN) search [19]. Two TNN algorithms developed for a single broadcast channel environment are adapted to our new broadcast enviroment. Based on the obtained insights, we propose two new algorithms, namely Double-NN-Search and Hybrid-NN-Search algorithms. Further, we develop an optimization technique, called approximate-NN (ANN), to reduce the energy consumption in mobile devices. Finally, we conduct a comprehensive set of experiments to validate our proposals. The result shows that our new algorithms provide a better performance than the existing ones and the optimization technique efficiently reduces energy consumption.