›› 2010, Vol. 25 ›› Issue (2): 330-346.

Special Issue: Computer Networks and Distributed Computing

• Distributed Computing and Systems • Previous Articles     Next Articles

Location-Based Data Dissemination for Spatial Queries in Wireless Broadcast Environments

Kwangjin Park1 and Hyunseung Choo2   

  1. 1School of Electrical Electronics and Information Engineering, Wonkwang University, Iksan-Shi, Chunrabuk-do 570-749, Korea
    2School of Information and Communication Engineering, Sungkyunkwan University, 440-746, Suwon, Korea
  • Received:2009-01-20 Revised:2009-10-09 Online:2010-03-05 Published:2010-03-05
  • About author:
    Kwangjin Park received the Ph.D. degree in computer science from Korea University in 2006. He was a postdoctoral fellow in the Atlantic Data Systems (Atlas) Research Group at the Institute National de Recherche en Informatique et en Automatique (INRIA)-Rennes and located at the Laboratoire dinformatique de Nantes-Atlantique (LINA), Nantes. In 2008, he joined the School of Electrical Electronics and Information Engineering, Wonkwang University, where he is an assistant professor. His research interests include spatiotemporal databases, mobile databases, and data dissemination.
    Hyunseung Choo received the Ph.D. degree in computer science from the University of Texas at Arlington in 1996. From 1997 to 1998, he was a patent examiner at the Korean Industrial Property Office. In 1998, he joined the School of Information and Communication Engineering, Sungkyunkwan University, where he is an associate professor and director of the Convergence Research Institute. Currently, he is director of the Intelligent Human-Computer Interaction (HCI) Convergence Research Center (8-year research program) supported by the Ministry of Information and Communication, Korea, under the Information Technology.
  • Supported by:

    This paper was supported by Wonkwang University in 2009.

Most current research on Location-Based Services (LBSs, for short) assumes point-to-point wireless communication, where the server processes a query and returns the query result to the user via a point-to-point wireless channel. However, LBSs via point-to-point wireless channel suffer from a tremendous amount of traffic and service requests from the user and thereby result in poor performance. In this paper, we present broadcast-based spatial query processing algorithms designed to support k-NN (k-Nearest Neighbor) and range queries via a wireless network. The task of the query processor is to selectively monitor the wireless broadcast channel, when the data items are disseminated by the server, according to their locations. Experiments are conducted to evaluate the performance of the proposed algorithms. Comprehensive experiments illustrate that the presented algorithms are highly scalable and are more efficient than the previous techniques in terms of both access time and energy consumption.

[1] Zheng B, Lee W C, Lee D. Search K nearest neighbors on air. In Proc. MDM, Melbourne, Australia, Jan. 21-24, 2003, pp181-195.

[2] Zheng B, Lee W C, Lee D L. Spatial queries in wireless broadcast systems. Wireless Network, 2004, 10(6): 723-736.

[3] Xu J, Zheng B, Lee W C, Lee D L. D-tree: An index structure for planar point queries in location-based wireless services. IEEE Trans. Knowledge and Data Engineering, 2004, 16(12): 1526-1542.

[4] Deolasee P, Katkar A, Panchbudhe A, Ramamritham K, Shenoy P. Adaptive push-pull: Disseminating dynamic Web data. In Proc. WWW 2001, Hong Kong, China, May 1-5, 2001, pp.265-274.

[5] Stathatos K, Roussopoulos N, Baras J S. Adaptive data broadcast in hybrid networks. In Proc. VLDB, Athens, Greece, Aug. 25-29, 1997, pp.326-335.

[6] Zheng B, Xu J, LeeWC, Lee D L. Grid-partition index: A hybrid method for nearest-neighbor queries in wireless locationbased services. VLDB Journal, 2006, 15(1): 21-39.

[7] Zheng B, LeeWC, Lee D. Search continuous nearest neighbor on air. In Proc. MobiQuitous 2004, Boston, USA, Aug. 22-26, 2004, pp.22-26.

[8] Imielinski T, Viswanathan S, Badrinath B R. Energy efficient indexing on air. In Proc. SIGMOD 1994, Minneapolis, USA, May 24-27, 1994, pp.25-36.

[9] Imielinski T, Viswanathan S, Badrinath B R. Data on air: Organization and access. IEEE Trans. Knowledge and Data Eng., 1997, 9(3): 353-372.

[10] Chung Y D, Kim M H. An index replication scheme for wireless data broadcasting. Journal of Systems and Software, 2000, 51(3): 191-199.

[11] Park K, Song M, and Hwang C. Broadcasting and prefetching schemes for location dependent information services. In Proc. W2GIS 2004, Goyang, Korea, Nov. 2004, pp.26-37.

[12] Park K, Song M, Hwang C S. Location-based caching scheme for mobile clients. In Proc. WAIM 2005, Hangzhou, China, Oct. 11-13, 2005, pp.233-244.

[13] Park K, Song M, Hwang C. Continuous spatial queries via wireless data broadcast. In Proc. SAC 2006, Dijon, France, April 23-27, 2006, pp.78-82.

[14] Park K, Song M, Kong K, Kang S, Hwang C, Chung K, Jung S. Effective low-latency k-nearest neighbor search via wireless data broadcast. In Proc. DASFAA 2006, Singapore, April 12-15, 2006, pp.900-909.

[15] Roussopoulos N, Kelley S, Vincent F. Nearest neighbor queries. In Proc. SIGMOD 1995, San Jose, USA, May 22-25, 1995, pp.71-79.

[16] Guttman A. R-trees: A dynamic index structure for spatial searching. In Proc. SIGMOD 1984, Boston, USA, June 1821, 1984, pp.47-57.

[17] Xiong X, Mokbel M F, Aref W G. SEA-CNN: Scalable processing of continuous K-nearest neighbor queries in spatiotemporal databases. In Proc. ICDE 2005, Tokyo, Japan, April 5-8, 2005, pp.643-654.

[18] Gedik B, Singh A, Liu L. Energy efficient exact kNN search in wireless broadcast environments. In Proc. GIS 2004, Washington DC, USA, Nov. 12-13, 2004, pp.137-146.

[19] Kalashnikov D V, Prabhakar S, Aref W G, Hambrusch S E. Efficient evaluation of continuous range queries on moving objects. In Proc. DEXA 2002, Aix-en-Provence, France, Sep. 26, 2002, pp.731-740.

[20] Xu J, Lee W C, Tang X. Exponential index: A parameterized distributed indexing scheme for data on air. In Proc. Mobisys 2004, Boston, USA, June 6-9, 2004, pp.153-164.

[21] Hambrusch S E, Liu C M, Aref W, Prabhakar S. Query processing in broadcasted spatial index trees. In Proc. SSTD 2001, Redondo Beach, USA, July 12-15, 2001, pp.502-521.

[22] Lee W C, Zheng B. DSI: A fully distributed spatial index for location-based wireless broadcast services. In Proc. ICDCS 2005, Columbus, USA, June 6-10, 2005, pp.349-358.

[23] Shallit J O. On infinite products associated with sums of digits. Journal of Number Theory, 1985, 21(2): 128-134.

[24] http://www.rtreeportal.org.

[25] Camp T, Boleng J, Davies V. A survey of mobility models for ad hoc network research. Wireless Communication and Mobile Computing, 2002, 2(5): 483-502.

[26] Kasten O. Energy consumption. ETH-Zurich, Swiss Federal Institute of Technology, http://www.inf.ethz.ch/∼kasten/research/ bathtub/energy consumption.html.

[27] Shih E, Cho S H, Ickes N, Min R, Sinha A. Wang A, Chandrakasan A. Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In Proc. MOBICOM 2001, Rome, Italy, July 16-21, 2001, pp.272-287.

[28] Lu G, Krishnamachari B, Raghavendra C S. An adaptive energy-efficient and low-latency MAC for data gathering in sensor networks. In Proc. WMAN 2004, Santa Fe, USA, April 2004, pp.1-12.

[29] Ruzzelli A G, O’Hare G M P, Tynan R, Cotan P, Havinga P J M. Protocol assessment issues in low duty cycle sensor networks: The switching energy. In Proc. SUTC 2006, Taichun, China, June 5-7, pp.136-143.

[30] Cai J, Goodman D J. General packet radio service in GSM. IEEE Communications Magazine, 1997, 35(10): 122-131.

No related articles found!
Full text



[1] Chen Yiyun;. Head Boundedness of Nonterminating Rewritings[J]. , 1995, 10(3): 281 -284 .
[2] Zhang Zhong;. Simulation of ATPG Neural Network and Its Experimental Results[J]. , 1995, 10(4): 310 -324 .
[3] WANG Xiaodong; XU Ming; ZHOU Xingming;. Fast Multicast on Multistage Interconnection Networks Using Multi-Head Worms[J]. , 1999, 14(3): 250 -258 .
[4] Wei-Sheng Si and Cheng-Zhi Li. RMAC: A Reliable MAC Protocol Supporting Multicast for Wireless Ad Hoc Networks[J]. , 2005, 20(5): 702 -712 .
[5] Yong-Dong Zhang, Sheng Tang, and Jin-Tao Li. Secure and Incidental Distortion Tolerant Digital Signature for Image Authentication[J]. , 2007, 22(4): 618 -625 .
[6] You-Jian Zhao, Zu-Hui Yue, and Jian-Ping Wu. Research on Next-Generation Scalable Routers Implemented with H-Torus Topology[J]. , 2008, 23(4 ): 684 .
[7] Bin Wang, Member, CCF, Xiao-Chun Yang, Senior Member, CCF, Member ACM, IEEE, Guo-Ren Wang, Senior Member, CCF, Member, ACM, IEEE, and Ge Yu, Senior Member, CCF, Member, ACM, IEEE. Outlier Detection over Sliding Windows for Probabilistic Data Streams[J]. , 2010, 25(3): 389 -400 .
[8] Benjamín Sahelices, Agustín de Dios, Pablo Ibáñez, Member, IEEE, Víctor Viñals-Yúfera, Member, ACM, IEEE, and José María Llabería. Efficient Handling of Lock Hand-off in DSM Multiprocessors with Buffering Coherence Controllers[J]. , 2012, 27(1): 75 -91 .
[9] Ke-Yan Cao, Guo-Ren Wang, Dong-Hong Han, Guo-Hui Ding, Ai-Xia Wang, and Ling-Xu Shi. Continuous Outlier Monitoring on Uncertain Data Streams[J]. , 2014, 29(3): 436 -448 .
[10] Yun-Cen Huang, Jie-Qing Feng, Matthias NieBner, Yuan-Min Cui, Baoguang Yang . Feature-Adaptive Rendering of Loop Subdivision Surfaces on Modern GPUs[J]. , 2014, 29(6): 1014 -1025 .

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