题名 | 位置相关数据的模型及关键技术研究 |
作者 | 李肖南 |
学位类别 | 硕士 |
答辩日期 | 2008-06-04 |
授予单位 | 中国科学院研究生院 |
授予地点 | 中国科学院软件研究所 |
导师 | 丁治明 |
关键词 | 位置相关数据 关系代数 索引 缓存 |
其他题名 | Location Dependent Data: Model and Key Technologies |
学位专业 | 计算机软件与理论 |
中文摘要 | 本文介绍了移动计算领域一个较为年轻的新课题——位置相关数据。位置相关数据是一种向移动用户提供即时、即点信息服务的技术。通过位置相关服务用户在移动过程中可以获得与其所在位置相适应的数据信息。 本文首先对位置相关服务的背景问题、关联技术、系统结构等方面作了概要性的介绍。然后从集合和映射的角度出发,探讨了位置相关数据的数学模型。为了使关系数据库能够支持位置相关查询,本文还分析了关系代数的位置相关性,并通过引入位置绑定算子初步建立了位置相关的关系代数。通过对位置绑定策略的讨论,本文提出了两阶段的位置绑定策略,为位置相关查询的优化提供了思路。 为了提高位置绑定的效率,本文进一步研究了位置绑定数据的索引和缓存方法。利用位置相关数据的数据区域的互斥性,本文在~R~树的基础上作了改进并提出了~Contour-R~树索引及其上的相关算法。新索引方法在保持~R~树灵活性的同时避免了~R~在点查询时的回溯,从而能够提高服务器端的查询效率。位置相关数据缓存是减少服务器查询次数的一种技术。本文提出的跨区域语义缓存方法突破了现有基于单一有效区域缓存方法的限制,使得用户可以根据设备的存储能力自行设置有效区域的尺寸。实验表明,在有效区域面积相同的情况下,跨区域缓存比单一有效区域缓存具有更高的命中率。同时,利用本文给出的旋转表示法,对跨区域缓存进行探测只需要通过简单运算即可完成。 |
索取号 | 暂无 |
英文摘要 | In this artical, we investigated a relatively new topic in the domain of mobile computing, \textit{Location Dependent Data, LDD}. LDD is the technology that provides in-time, in-position information for mobile clients. With the support of location dependent service, users will be informed with the data that is particularly related to his/her location. A formal model of LDD based on set theory is given at first. To equip database with LDD capability, we elaborate the location dependency property of the classic relational algebra and introduce the new location binding operator, which results in \textit{location dependent relation algebra}. The \textit{two-stage location binding strategy} is proposed as a venue to the optimization of location dependent query. To reduce the cost of location binding operation, we further study two technical issues of LDD, index and cache. Index is used to boost location binding at the server side. We propose \textit{Contour-R Tree} for indexing data region. It is an variant of R tree. However, it takes advantage of the non-overlapping property of data region in LDD to eliminate back-trace during point query, which is a notorious problem of R tree. Meanwhile facility algorithms are provided to maintain the flexibility of our new index. Cache is used for reducing the total amount of location binding. The \textit{cross-region} cache proposed in this article is a break through from the in-region cache. It enables mobile clients to extend validity scope freely as long as the store space on their device allow. Experiments shows that the cross-region cache has higher hit ratio than in-region cache under the condition of identical area of validity scope. Moreover, the rotation representation given by this article greatly simplifies probing in cross-region cache. |
公开日期 | 2011-03-17 |
分类号 | 暂无 |
内容类型 | 学位论文 |
源URL | [http://124.16.136.157/handle/311060/6778] ![]() |
专题 | 软件研究所_基础软件国家工程研究中心_学位论文 |
推荐引用方式 GB/T 7714 | 李肖南. 位置相关数据的模型及关键技术研究[D]. 中国科学院软件研究所. 中国科学院研究生院. 2008. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论