由於近年來無線網路與數位行動裝置的快速成長，使得如何有效率的藉由無線網路提供資訊給使用者，以解決使用者的需求，成為一個重要的議題，並適合在具備高延展性的無線廣播系統上發展。而在過去研究的相關論文裡，所針對的資料，諸如股票、比賽分數等等，皆和地理位置沒有關係，但在行動裝置盛行的今天，由地理位置所衍生出來的空間查詢，已相形的重要。
空間查詢一直以來是資料庫領域的研究議題，所發展出來樹狀的索引資料結構，並不適用於無線廣播系統。近年來有論文針對此一問題，發表出以Hilbert Curve為基礎的索引機制，將樹狀的索引改變成線性資料結構，以符合無線廣播系統的需求。
在本篇論文中，我們以空間查詢中較俱代表性的KNN查詢為主軸，嘗試替Hilbert Curve為基礎的索引機制，加上少許且重要的地理資訊，讓查詢能更有效率的完成。

Because of the growing popularity of digital mobile devices and rapid advent of wireless technology, it become an import issue that provide user with information via wireless channel to solve the query, and wireless broadcast system that is high scalability is very suitable for this.
In the past, the research is only concerned with location independent data such as stock price and race score. In mobile computing era, location is also a dimension of data and spatial query gradually becomes important. Spatial query is always a researchable topic in the field of database, and tree index which have been developed is not suitable for wireless broadcast system. In a recent paper, a new index structure based on the Hilbert curve is proposed, and it is linear and more proper than tree index in wireless broadcast system.
In this paper, we address the issue of KNN (K Nearest Neighbor) query and try to add a little important geographic data on Hilbert Curve Index Structure. Let the KNN query be able to finish more efficiently.

[1] I. Kamel, C. Faloutsos, “On packing R-trees,” in Proc. of the 2th International Conference on Information and Knowledge Management (CIKM), November 1993, pp. 490-499.
[2] I. Kamel, C. Faloutsos, “Hilbert R-tree: An improved R-tree using fractals,” in Proc. of 20th International Conference on Very Large Data Bases (VLDB), September 1994, pp. 500-509.
[3] S.T. Leutenegger, J.M. Edgington and M.A. Lopez, “STR: A simple and efficient algorithm for R-tree packing,” in Proc. of the 13th International Conference on Data Engineering (ICDE), April 1997, pp. 497-506.
[4] N. Beckmann, H. P. Kriegel, “The R*-tree: An efficient and robust access method for points and rectangles,” in Proc. of the ACM SIGMOD, 1990, pp. 322-331.
[5] T. Sellis, N. Roussopoulos, C. Faloutsos, “The R+-tree: A dynamic index for multi-dimensional objects,” in Proc. of the 13th International Conference on Very Large Data Bases (VLDB), 1987, pp. 507-518.
[6] T. Imielinski, S. Viswanathan and B.R. Badrinath, “Data on air – organization and access,” IEEE Transactions on Knowledge and Data Engineering (TKDE), 1997.
[7] C. Gotsman, M. Lindenbaum, “On the metric properties of discrete space-filling curves,” IEEE Transactions on Image Processing, May 1996, pp. 794-797.
[8] P.K. Agarwal, M. Berg, J. Matousek and O. Schwarzkopf, “Constructing levels in arrangements and higher order Voronoi diagrams,” SIAM Journal on Computing, 1998, pp.654-667.
[9] B. Zheng, W. C. Lee, “DSI: A Fully Distributed Spatial Index for Location-Based Wireless Broadcast Services;” International Conference on Distributed Computing Systems(ICDCS), June 2005, pp. 349-358.
[10] B. Zheng, D.L. Lee, “Information dissemination via wireless broadcast,” Communications of the ACM, vol.48, May 2005, pp.105-110.
[11] J. Xu, B. Zheng, W.C. Lee and D.L. Lee, “Energy efficient index for querying location-dependent data in mobile broadcast environments,” in Proc. of the 19th IEEE International Conference on Data Engineering (ICDE), March 2003, pp. 239-250.
[12] B. Zheng, W.C. Lee and D.L. Lee, “Spatial index on air,” in Proc. of the 1st IEEE International Conference on Pervasive Computing and Communications (PerCom), March 2003, pp. 297-304.
[13] J. Xu, W.C. Lee, and X. Tang, “Exponential index: A parameterized distributed indexing scheme for data on air.” In Proc. of the 2nd ACM/USENIX International Conference on Mobile Systems, Applications, and Services (MobiSys), June 2004.
[14] B. Zheng, J. Xu,W.C. Lee and D.L. Lee, “Energy-conserving air indexes for nearest neighbor search,” in Proc. of the 9th International Conference on Extending Database Technology (EDBT), March 2004.
[15] Microsoft Corporation, What is the directband network? (2003), available at http://direct.msn.com/.
[16] A.Guttman., “R-trees:A dynamic index structure for spatial searching,” In Proc. of the ACM SIGMOD Conference on Management of Data , 1984, pp. 47-54.
[17] M. Minsky, S. Papert, “Perceptrons: An Introduction to Computational Geometry,” The MIT Press, 1969.