Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)
自动化技术、信息技术     
多类别复合资源的空间匹配
蔡华林,陈刚,陈珂
浙江大学 计算机科学与技术系,浙江 杭州 310027
Spatial matching on multi-type resource
CAI Hua-lin, CHEN Gang, CHEN Ke
Department of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
 全文: PDF(1133 KB)   HTML
摘要：

针对现有的空间匹配(SPM)问题中无法适用于多类别资源的不足,提出并解决了多类别复合资源的空间匹配问题.假设度量空间下有资源提供者和用户2个对象集合,资源提供者能够提供多类别的资源,并且受限于有限的容量,用户对各种资源有不同数量需求.多类别复合资源的空间匹配将资源提供者与资源需求者进行匹配,使资源利用效益最大化,同时要求这个匹配是稳定匹配,稳定匹配是指每个用户优先与距其最近的资源提供者匹配,且所需资源未被比该用户更近的其他用户所耗尽.提出利用网络流、最近邻等方法来解决该问题的有效算法.通过大量的实验验证了这些算法的正确性和有效性,对这些算法以及特殊情形下的已有解决方法进行比较.
Abstract:

 A new problem called generalized spatial matching (GSPM) was proposed and solved aiming at the existing spatial matching (SPM) problem that cannot be applied to the multi-type resource. Assume there are two sets of objects in an arbitrary metric space. One set of objects indicate services providers and each of them provides several services constrained by a finite capacity. The other set of objects indicate the customers needing different quantity of service. GSPM assigns each providers capacity to the customers with the services it provides, aiming at maximizing the resource utilizing. The assignment is made stable which means that we assign each customer to its nearest provider who can provide at least one of the needed services, among all the providers whose capacities have not been exhausted in serving other closer customers. Several algorithms were developed to settle the problem. Our algorithms were verified with extensive experiments. Results showed that the proposed solutions efficiently solved the problem．
出版日期: 2018-06-06
:  TP 311  
基金资助:

国家“863”高技术研究发展计划资助项目（SS2013AA040601）
通讯作者: 陈珂，女，副研究员     E-mail: chenk@zju.edu.cn
作者简介: 作者简介： 蔡华林（1982-），男，博士生，从事数据库的研究. E-mail：chl@zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

蔡华林,陈刚,陈珂. 多类别复合资源的空间匹配[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2015.01.011.

CAI Hua-lin, CHEN Gang, CHEN Ke. Spatial matching on multi-type resource. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2015.01.011.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2015.01.011    或    http://www.zjujournals.com/eng/CN/Y2015/V49/I1/69

［1］ WONG R C, OZSU M T, YU P S, et al. Efficient method for maximizing bichromatic reverse nearest neighbor ［J］. Proceedings of the VLDB Endowment，2009, 2(1): 1126-1137．
［2］ KORN F, MUTHUKRISHNAN S. Influence sets based on reverse nearest neighbor queries［J］. ACM SIGMOD Record, 2000, 29(2): 201-212．
［3］ WONG R C, OZSU M T, FU A W, et al. Maximizing bichromatic reverse nearest neighbor for Lp-norm in two- and three-dimensional spaces ［J］. The VLDB Journal， 2011, 20(6): 893-919．
［4］ WONG R C, TAO Y, FU A W, et al. On efficient spatial matching ［C］∥ Proceedings of the 33rd International Conference on Very Large Data Bases. Vienna, Austria: VLDB Endowment, 2007: 579-590．
［5］ GALE D, SHAPLEY L S. College admissions and the stability of marriage ［J］. American Mathematical Monthly, 1962, 69(1): 9-15．
［6］ LEONG H U, YIU M L, MOURATIDIS K, et al. Capacity constrained assignment in spatial databases ［C］∥ Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. Vancouver: ACM, 2008: 15-28．
［7］ MA C, ZHOU Y, SHOU L, et al. Matching query processing in high-dimensional space ［C］∥ Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York: ACM, 2011: 1589-1594．
［8］ SUN Y, HUANG J, CHEN Y, et al. Location selection for utility maximization with capacity constraints ［C］∥ Proceedings of the 21st ACM International Conference on Information and Knowledge Management. Maui: ACM, 2012: 2154-2158．
［9］ LONG C, WONG R C, YU P S, et al. On optimal worst-case matching ［C］∥ Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2013: 845-856．
［10］ LIN Y, MOURATIDIS K. Shortlisting top-K assignments ［C］∥ Proceedings of the 25th International Conference on Scientific and Statistical Database Management. Baltimore: ACM, 2013: 112．
［11］ CORRAL A, MANOLOPOULOS Y, THEODORIDIS Y, et al. Closest pair queries in spatial databases ［J］. ACM SIGMOD Record, 2000, 29(2): 189200．
［12］ DINITZ Y. Dinitz algorithm: the original version and evens version ［M］. Berlin: Springer, 2006: 218-240．
[1] 王海艳, 程严. 基于离散系数的双向服务选择方法[J]. 浙江大学学报(工学版), 2017, 51(6): 1197-1204.
[2] 袁友伟, 余佳, 郑宏升, 王娇娇. 基于新颖性排名和多服务质量的云工作流调度算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1190-1196.
[3] 许荣斌, 石军, 张鹏飞, 谢莹. Petri网的映射变迁关系相似性度量[J]. 浙江大学学报(工学版), 2017, 51(6): 1205-1213.
[4] 常超, 刘克胜, 谭龙丹, 贾文超. 基于图模型的C程序数据流分析[J]. 浙江大学学报(工学版), 2017, 51(5): 1007-1015.
[5] 王继奎. 贝叶斯冲突Web数据可信度算法[J]. 浙江大学学报(工学版), 2016, 50(12): 2380-2385.
[6] 涂鼎, 陈岭, 陈根才, 吴勇, 王敬昌. 基于在线层次化非负矩阵分解的文本流主题检测[J]. 浙江大学学报(工学版), 2016, 50(8): 1618-1626.
[7] 杨莎, 叶振宇, 王淑刚, 陶海, 李石坚, 潘纲, 朱斌. 感认知增强的智能机械手系统[J]. 浙江大学学报(工学版), 2016, 50(6): 1155-1159.
[8] 罗林, 苏宏业, 班岚. Dirichlet过程混合模型在非线性过程监控中的应用[J]. 浙江大学学报(工学版), 2015, 49(11): 2230-2236.
[9] 汪宏浩, 王慧泉, 金仲和. 基于增量链接的可回滚星载软件在轨更新方法[J]. 浙江大学学报(工学版), 2015, 49(4): 724-731.
[10] 王继奎, 李少波. 基于真值发现的冲突数据源质量评价算法[J]. 浙江大学学报(工学版), 2015, 49(2): 303-318.
[11] 俞东进,殷昱煜,吴萌萌,刘愉. 基于混合协同过滤的Web服务QoS预测方法[J]. 浙江大学学报(工学版), 2014, 48(11): 2039-2045.
[12] 柯海丰,应晶. 基于R-ELM的实时车牌字符识别技术[J]. 浙江大学学报(工学版), 2014, 48(7): 1209-1216.
[13] 刘智慧, 张泉灵. 大数据技术研究综述[J]. 浙江大学学报(工学版), 2014, 48(6): 957-972.
[14] 田甜,巩敦卫. 基于覆盖难度选择路径的测试数据进化生成[J]. 浙江大学学报(工学版), 2014, 48(5): 948-994.
[15] 柯海丰,应晶. 基于R-ELM的实时车牌字符识别技术[J]. J4, 2014, 48(2): 0-0.