DSI: A Fully Distributed Spatial Index for Wireless Data Broadcast

• Main Authors: LEE, Wang-Chien, ZHENG, Baihua
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2005
• Subjects: Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/522; https://ink.library.smu.edu.sg/context/sis_research/article/1521/viewcontent/ICDCS05__DSI.pdf
• Institution: Singapore Management University

Recent announcement of the MSN Direct Service has demonstrated the feasibility and industrial interest in utilizing wireless broadcast for pervasive information services. To support location-based services in wireless data broadcast systems, a distributed spatial index (called DSI) is proposed in this paper. DSI is highly efficient because it has a linear yet fully distributed structure that facilitates multiple search paths to be naturally mixed together by sharing links. Moreover, DSI is very resilient in error-prone wireless communication environments. Search algorithms for two classical location-based queries, window queries and kNN queries, based on DSI are presented. Performance evaluation of DSI shows that DSI significantly outperforms R-tree and Hilbert Curve Index, two state-of-the-art spatial indexing techniques for wireless data broadcast