标题: 行动环境上之高效能与省电之KNN查询处理系统之研究
Study on Efficient and Energy-Conserving KNN Query Processing Systems in Mobile Environments
作者: 黄俊龙
Huang Jiun-Long
国立交通大学资讯工程学系(所)
关键字: NN 查询;k-NN 查询;空间资料库;行动计算;NN query;k-NN query;spatial database;mobile computing
公开日期: 2008
摘要: 在众多无线网路服务媒体所提供的服务查询中,以 Nearest Neighbor (NN)查询与
k-Nearest Neighbor (k-NN)查询最为常见。举例来说:人们在下了火车离开火车站后,
通常想找离火车站最近(NN)的饭店休息,因此他会要求服务媒体提供离火车站最近饭
店的位址资讯;在市区中的汽车驾驶想要从他现在的位址连接到高速公路上,因此他
会要求服务媒体提供离他目前位址最靠近的k 个(k-NN)交流道位址资讯。研究文献结
果指出,在行动资讯系统与行动设备间架设支援k-NN 查询的proxy 能在少量增加建置
成本的情形下,有效地增快查询的反应时间与降低行动资讯系统的总工作量。因此在
本计画中,我们想要针对NN 与k-NN 查询服务提出一个方案,提升行动资讯系统的延
展性与效能,并节省使用端行动设备的能源消耗。我们将研发适用于行动计算环境下
之支援k-NN 查询的系统架构,其主要议题如下:在第一年中,我们首先将研发提供整
合NN 查询服务的系统架构,用以提升行动资讯系统的延展性与系统效能;接着我们
将研发快速的estimated valid region 成长方法;最后我们将研发合适之快取管理演算
法。在第二年中,我们将着重于k-NN 查询。我们首先将修改之前设计之系统架构以支
援k-NN 查询。我们也将着手研发省电之行动设备端(mobile client)与服务提供端(service
provider)的沟通机制,由于行动设备大部分消耗电源在于与伺服器通讯,如果能有效的
减少行动设备与伺服器的通讯量,将有效的减少行动设备的能源消耗。因此我们将研
发适合行动资讯系统与行动设备的沟通机制,并将其与proxy 整合,减少proxy 与行动
设备间资料的传输量,并藉以减少行动设备的能源消耗。最后,我们将着手开发实验
平台并实作所开发之演算法,以便进行效能评估。
In most mobile services, location-dependent queries are deemed killer applications of next
generation mobile services. According to spatial constraints of queries, location-dependent
queries can be divided into several categories including proximity query and k nearest
neighbor query (referred to as k-NN query). A proximity query to find all objects within a
certain range. An example proximity query is “Find all taxis with distance less than 300
meters to me.” Proximity queries are also known as range queries or window queries. A k-NN
query is to find k nearest objects to a specific location (referred to the query location of the
k-NN query). For example, a user may issue a k-NN query like “Find the five nearest hotels”.
A nearest neighbor query (referred to as NN query) which finds the nearest object to a specific
location is a special case of k-NN queries with k = 1. For example, passengers will query the
nearest hotels for taking a rest. In addition, drivers will query the k nearest gas stations for
refueling. Research work shows that deploying proxies supporting NN and k-NN queries is
able to greatly reduce system response time and system workload at the cost of slightly
deployment cost. In this project, we aim to provide a scalable and energy-efficient system
architecture supporting NN and k-NN queries. In the first year, we will focus on NN queries.
Specifically, we will first develop a 3-tier system architecture for NN services. We will
develop an effective algorithm to speedup the growth of estimated valid region. In addition,
cache management algorithms will also be developed. In the second year, we will concentrate
on the issues of k-NN queries. We will first extend the proposed architecture for supporting
k-NN queries. In addition, the devised cache management algorithm will also be extended for
k-NN queries. We will also address some problems dedicated for k-NN queries. Then, we will
develop an experimental platform. Finally, we will implement the devised algorithms on the
experimental platform to perform performance evaluation.
官方说明文件#: NSC96-2221-E009-161-MY2
URI: http://hdl.handle.net/11536/102277
https://www.grb.gov.tw/search/planDetail?id=1591020&docId=272843
显示于类别:Research Plans