不確定網(wǎng)絡(luò)條件可信近鄰查詢
doi: 10.11999/JEIT150748 cstr: 32379.14.JEIT150748
-
2.
(北京科技大學(xué)計算機與通信工程學(xué)院 北京 100083) ②(德州學(xué)院 德州 253000)
基金項目:
國家自然科學(xué)基金(61163025)，北京市重點實驗室2012年度階梯計劃項目(Z121101002812005)
Credible Nearest Neighbor Query in Uncertain Network
-
2.
(School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing 100083, China)
Funds:
The National Natural Science Foundation of China (61163025), The Project of Beijing Key Laboratory of Knowledge Engineering for Materials Science (Z121101002812005)
-
摘要: 不確定因素在現(xiàn)實世界中普遍存在，因此研究不確定網(wǎng)絡(luò)條件可信近鄰查詢具有重要意義。該文給出一種新的解決方法。將不確定網(wǎng)絡(luò)建模為不確定賦權(quán)圖，定義不確定圖的樣本圖，樣本圖指數(shù)，基礎(chǔ)網(wǎng)絡(luò)，可達路徑長度及可達路徑期望長度，并給出基于不確定理論的高效不確定圖條件可信近鄰查詢算法。將不確定網(wǎng)絡(luò)上的近鄰查詢等價地轉(zhuǎn)化為基礎(chǔ)網(wǎng)絡(luò)上的近臨查詢問題。理論分析和實驗結(jié)果表明所提可信近鄰查詢算法能夠從非確定角度解決不確定網(wǎng)絡(luò)環(huán)境下的近鄰查詢問題。
-
關(guān)鍵詞:
- 不確定網(wǎng)絡(luò) /
- 不確定圖 /
- 樣本圖指數(shù) /
- 可信距離 /
- 基礎(chǔ)網(wǎng)絡(luò)
Abstract: Uncertain factors are a common phenomenon in the real world; therefore, it is very meaningful to study on the trusted neighbor query under uncertain network conditions. This paper puts forwards a new solution. The uncertain network is modeled as uncertain weighed graph, and these definitions of the uncertain graph are given, such as sample graph, sample graph index, base network, length of feasible path and expected length of feasible path. Based on these the high-efficiency credible neighbor query algorithm for uncertain graph is put forward under constraint conditions. This algorithm is transforms the issue of neighbor query in the uncertain network equivalently to the issue of neighbor query in the base network. The theoretic analysis and experimental results show that the credible neighbor query algorithm proposed in the paper can solve the neighbor query problem in the environment of the uncertain network from non-deterministic perspective.-
Key words:
- Uncertain networks /
- Uncertain graph /
- Sample graph index /
- Credible distance /
- Basic networks
-
羅亮, 吳文峻, 張飛. 面向云計算數(shù)據(jù)中心的能耗建模方法[J]. 軟件學(xué)報, 2014, 25(7): 1371-1387. doi: 10.13328/j.cnki. jos.004604. LUO L, WU W J, and ZHANG F. Energy modeling based on clouddata center[J]. Journal of Software, 2014, 25(7): 1371-1387. doi: 10.13328/j.cnki.jos.004604. 殷波, 王穎, 邱雪松, 等. 一種面向云服務(wù)提供商的資源分配機制[J]. 電子與信息學(xué)報, 2014, 36(1): 15-21. doi: 10.3724/ SP.J.1146.2013.00427. YIN Bo, WANG Ying, QIU Xuesong, et al. A resource provisioning mechanism for service providers in cloud[J]. Journal of Electronics Information Technology, 2014, 36(1): 15-21. doi: 10.3724/SP.J.1146.2013.00427. 張海杰, 姜守旭, 鄒兆年. 不確定圖上的高效top-k近鄰查詢處理算法[J]. 計算機學(xué)報, 2011, 34(10): 1885-1896. doi: 10.3724/SP.J.1016.2011.01885. ZHANG Haijie, JIANG Shouxu, and ZOU Zhaonian. An efficient algorithm for top-k proximity query on uncertain graph[J]. Chinese Journal of Computers, 2011, 34(10): 1885-1896. doi: 10.3724/SP.J.1016.2011.01885. 高峻, 郝忠孝. 受限模糊網(wǎng)絡(luò)可信近鄰查詢[J]. 計算機工程, 2015, 41(1): 54-60. doi: 10.3969/j.issn.1000-3428.2015.01.010. GAO Jun and HAO Zhongxiao. Credible nearest neighbor query in constraint fuzzy network[J]. Computer Engineering, 2015, 41(1): 54-60. doi: 10.3969/j.issn.1000-3428.2015.01. 010. LIU B. Uncertainty Theory[M]. 2nd ed., Berlin: Springer- Verlag, 2007, Chapter 1-Chapter 2 . LIU B. Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty[M]. Berlin: Springer-Verlag, 2010, Chapter 1-Chapter 2. LIU B. Uncertainty distribution and independence of uncertain processes[J]. Fuzzy Optimization and Decision Making, 2014, 13(3): 259-271. doi: 10.1007/s10700-014- 9181-5. ZHOU J, CHEN L, and WANG K. Path optimality conditions for minimum spanning tree problem with uncertain edge weights[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2015, 23(1): 49-71. doi: 10.1142/s0218488515500038. GAO X L. Uncertain relations on a finite set and their properties[J]. Pure and Applied Mathematics Journal, 2014, 3(1): 13-19. doi: 10.11648/j.pamj.s.20140301.13. GAO X L. Tree index of uncertain graphs[J]. Soft Computing, 2015. doi: 10.1007/s00500-015-1597-5. GAO X L and GAO Y. Connectedness index of uncertainty graphs[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2013, 21(1): 127137. doi: 10.1142/S0218488513500074. GAO X L. Regularity index of uncertain graph[J]. Journal of Intelligent Fuzzy Systems, 2014, 27(4): 1671-1678. doi: 10.3233/IFS-141133. DING S B. Uncertain minimum cost flow problem[J]. Soft Computing, 2014, 18(11): 2201-2207. doi: 10.1007/s00500- 013-1194-4. Gao X, Gao Y, and Ralescu D. On Lius inference rule for uncertain systems[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2010, 18(1): 1-11. doi: 10.1142/S0218488510006349. Gao Y, Yang L X, et al. On distribution function of the diameter in uncertain graph[J]. Information Sciences, 2015, 296(1): 61-74. doi: 10.1016/j.ins.2014.10.048. GAO Y. Shortest path problem with uncertain arc lengths[J]. Computers and Mathematics with Applications, 2011, 62(6): 2591-2600. doi: 10.1016/j.camwa.2011.07.058. LIU B. Some research problems in uncertainty theory[J]. Journal of Uncertain Systems, 2009, 3(1): 3-10. -
計量
- 文章訪問數(shù): 1254
- HTML全文瀏覽量: 134
- PDF下載量: 365
- 被引次數(shù): 0
下載:
