公开(公告)号：CN102253961A

公开(公告)日：2011-11-23

申请号：CN201110127113.4

申请日：2011-05-17

Applicant: 复旦大学

Inventor： 孙未未 ,  朱良 ,  荆一楠 ,  毛鼎鼎 ,  陈楚南 ,  陈坤杰

IPC: G06F17/30

Abstract: 本发明属于空间数据库技术领域，具体涉及一种基于Voronoi图的路网k聚集最近邻居节点查询（k-ANN）方法。其步骤为：首先通过R树索引求出每一个查询点的第一个最近邻居节点（1-NN），然后构造一个优先级队列存储所有查询点的1-NN，权值为查询点到目标节点的当前聚集距离，接着按照某种顺序在路网Voronoi图的基础上对某个查询点进行扩展，更新这个查询点下一个NN的聚集距离，对优先级队列进行插入或更新等操作，直到发现队首的目标节点被所有查询点扩展到，那么该目标节点就是1-ANN。从队列中删除1-ANN后，第二次满足条件的是2-ANN，依此类推。本发明在用户查询的响应时间和页面访问量上有着出色的性能。

公开(公告)号：CN102156756A

公开(公告)日：2011-08-17

申请号：CN201110124954.X

申请日：2011-05-16

Applicant: 复旦大学

Inventor： 孙未未 ,  陈楚南 ,  陈翀 ,  陈坤杰

IPC: G06F17/30

Abstract: 本发明属于空间数据库技术领域，具体涉及一种道路网络中查找最优路径的方法。该方法的步骤为：给定路网中的n个属性的点集合M1、M2、…、Mn，以及一个起点s和一个终点t，以s为起点，根据图嵌入框架提供的上下界，以迭代查找最近邻的方法找出贪心路径Rg；然后按顺序遍历n个属性的点集合M1、M2、…、Mn，以贪心路径的长度为上界，结合上下界对存在的路径进行剪枝；最后对剩下的候选路径进行精确计算，找出最优路径。通过本发明的基于图嵌入的查找方法，大大减小了搜索空间，因而有更高的查找效率。

公开(公告)号：CN102184236A

公开(公告)日：2011-09-14

申请号：CN201110124989.3

申请日：2011-05-16

Applicant: 复旦大学

Inventor： 孙未未 ,  陈坤杰 ,  朱良 ,  陈楚南

IPC: G06F17/30

Abstract: 本发明属于空间数据库技术领域，具体涉及一种空间数据库中基于距离的自适应页面替换方法。其步骤为：首先设定策略管理队列的目标容量及约束容量；由空间数据库提出具体页面的请求；缓存接收到请求后，检查缓存中是否存在请求页面内容，进行不同处理；接着加载请求页面的内容到缓存中并记录请求页面的坐标信息；最后约束管理队列容纳页面信息的个数。本发明命中率高，并可以解决LRU、LIRS、ARC等策略对空间局部性工作集不友好的缺点。

公开(公告)号：CN102184236B

公开(公告)日：2013-06-12

申请号：CN201110124989.3

申请日：2011-05-16

Applicant: 复旦大学

Inventor： 孙未未 ,  陈坤杰 ,  朱良 ,  陈楚南

IPC: G06F17/30

Abstract: 本发明属于空间数据库技术领域，具体涉及一种空间数据库中基于距离的自适应页面替换方法。其步骤为：首先设定策略管理队列的目标容量及约束容量；由空间数据库提出具体页面的请求；缓存接收到请求后，检查缓存中是否存在请求页面内容，进行不同处理；接着加载请求页面的内容到缓存中并记录请求页面的坐标信息；最后约束管理队列容纳页面信息的个数。本发明命中率高，并可以解决LRU、LIRS、ARC等策略对空间局部性工作集不友好的缺点。