FCHI: A Fine Cell-based Hybrid Index for Energy Efficient k Nearest Neighbor Query Processing on Air
Seokjin Im, Jin-Tak Choi · 한국정보기술학회논문지 · 2010
For Location Dependent Information Service with wireless data broadcast, several indexing schemes have been developed for efficient k Nearest Neighbor (kNN) query processing. The existing distributed indexing schemes show a trade-off between access time and energy consumption because each distributed index carries only partial information on data distribution. In this paper, we propose Fine Cell-based Hybrid Index (FCHI) for energy efficient kNN query processing of the clients by avoiding the trade-off of the existing distributed indexing schemes. With this end, FCHI effectively integrates global information on data distribution using fine cells with the distributed indexes carrying the original coordinates of data items. FCHI enables less access time and energy consumption by fast determination of search space shrunken sufficiently using the global information and by filtering data items using the coordinates in distributed indexes. Also FCHI supports linear access pattern of the clients with its table-formed linear structure. By the simulation studies with real data set and uniformly distributed data set, we show that the proposed FCHI provides a significant performance improvement on access time and tuning time than those of the existing schemes.