|Sponsor||Ling Liu / Bugra Gedik
216 / 263 CCB
With the emergence of positioning technologies like GPS, popularity of mobile communications and the coming era of ubiquitous computing, location management has become an active area of research. An interesting problem in this domai n is the investigation of indexing and searching mechanisms that will enable energy efficient querying of location dependent information in broadcast environments. One special case of this problem is what we call the "kNN Search on the Air" ;, which can be described as the problem of broadcasting a spatial index (an R-tree like structure in our case) on the wireless medium and querying this broadcast on a client device in order to answer k nearest neighbor (kNN) queries in an energy efficien t way. To illustrate the problem, consider a battlefield scenario where several mobile units ranging from soldiers to tanks, report their positions to a central server through a wireless channel. The server builds a spatial index on this position informat ion and broadcasts it to the battlefield. Then the mobile devices can tune in and process the broadcast to answer spatial queries on the broadcasted position information. One such query can be posted by a tank as: "Give me the positions and names of the 10 nearest friendly units".
The student is expected to first read references  and  in order to get familiar with the ideas involved in and mechanisms used for indexing in broadcast environments. References ,  and  are essential for understanding R-trees and kNN s earch on R-trees. It is important to note that the traditional kNN algorithms do not directly apply in broadcast environments as the access is sequential (we do not consider caching a complete broadcast cycle on the client device). As a result, the way an R-tree is broadcasted and searched is crucial and has implications on two important performance measures: access latency and tuning time (see  and ). For instance a breadth-first like (BFS-like) broadcast or a dept-first like (DFS-like) broadcast c an be used, as shown in Figure 1 below. In a BFS-like broadcast (see Figure 1a), explicit links can be used for each node in order to point the location of its child nodes and special markers can be used to seperate each layer. In a DFS-like broadcast (se e Figure 1b), explicit links can be used for each node in order to point the next node in DFS order after skipping the current branch and special markers can be used to indicate each backtack. These two diffrent organizations require two different search algorithms and may have different advantages in terms of the two performance measures, access latency and tuning time.
There are two main goals in this project:, each forming a seperate mini-project designed to be taken in order:
 T. Imielinski, S. Viswanathan, and B.R. Badrinath, "Energy Efficient Indexing on Air". In Proceedings of the IEEE ICDE, 1994.
 S. Hambrusch, C.-M. Liu, W. Aref, and S. Prabhakar, "Query Processing in Broadcasted Spatial Index Trees", SSTD 2001.
 A. Guttman, "R-trees: A Dynamic Index Structure for Spatial Searching". In Proceedings of the ACM SIGMOD, 1984.
 N. Roussopoulos, S. Kelley, F. Vincent, "Nearest Neighbor Queries". In Proceedings of the ACM SIGMOD, 1995.
 T. Seidl, H. P. Kriegel, "Optimal Multi-Step k-Nearest Neighbor Search". In Proceedings of the ACM SIGMOD, 1998.
Some knowledge of spatial index structures, especially R-trees, is helpfull.
A report, describing your designs and findings (with references to related work) and source code for any implementation you have done to validate your ideas.
You will be graded on the novelty and quality of report and implementation.