Hybrid Breadth-Depth Search Algorithm in Crowd Transaction Network
Authors: 
Zhishuo Liu, Ziqi Dong, Fang Tian, Fan Zhang, Nianci Kou, Dongxin Yao, Lida LiAuthors Info & Claims
Pages 204 - 211
Abstract
In the Crowd Intelligence-based Transaction Network (CITN), each intelligent individual stores the commodity information in a local node. The information is shared via searching and routing in the circle of friends. The demand of searching the commodity information in an efficient way motivates this study. We develop an algorithm that can search the information for a certain node in a short period of time and with low network resource consumption. This paper proposes a heuristic search algorithm, the hybrid breadth-depth (HBD) algorithm, which helps to find suitable suppliers and commodities in the CITN for any demand of the buyers. The HBD algorithm takes full advantage of the breadth-first search (BFS) and depth-first search (DFS). It defines the relevance between nodes, optimizes the search rules and forwarding paths based on the relevance between nodes and the neighbor nodes in their circles of friends, and improves both the success rate and efficiency. Our test on the performance of the HBD algorithm shows that it is superior in the success rate, search time, matching degree, network resource consumption, and scalability. Compared with previous search algorithms such as the food algorithm and the random walk algorithm, in the CITN, the HBD algorithm can greatly reduce the search time and the network resource consumption, and increase the success rate and matching degree.
References
[1]
Chai, Y., Miao, C., Sun, B., Zheng, Y. and Li, Q. (2017), "Crowd science and engineering: concept and research framework", International Journal of Crowd Science, Vol. 1, No. 1, pp. 2--8.
[2]
Yu, C., Chai, Y. and Liu, Y. (2018), "Literature review on collective intelligence: A crowd science perspective", International Journal of Crowd Science, Vol. 2, No. 1, pp. 64--73.
[3]
Baryshnikov, Y., Coffman, E., Jelenković, P., MomčIlović, P., & Rubenstein, D. (2004), "Flood search under the california split rule", Operations Research Letters, Vol. 32, No. 3, pp. 199--206.
[4]
Shenvi, N., Kempe, J., & Whaley, K. B. (2003), "Quantum random-walk search algorithm", Physical Review A, Vol. 67, No. 5, pp. 052307.
[5]
Chao-Yang, P., Zheng-Wei, Z., Ping-Xing, C., & Guang-Can, G. (2006), "Design of quantum VQ iteration and quantum VQ encoding algorithm taking O (N1/2) steps for data compression", Chinese Physics, Vol. 15, No. 3, pp. 618.
[6]
Ripeanu, M., Iamnitchi, A. and Foster, I. (2002), "Mapping the gnutella network", IEEE Internet Computing, No. 1, pp. 50--57.
[7]
Gkantsidis, C., Mihail, M. and Saberi, A. (2006), "Random walks in peer-to-peer networks: algorithms and evaluation", Performance Evaluation, Vol. 63, No. 3, pp. 241--263.
[8]
Sugawara, J. (2005), "Proposal and evaluation of modified-BFS using the number of links in P2P networks", Technical Report of Ieice Ocs, No. 104, pp. 5--8.
[9]
Kalogeraki, V., Gunopulos, D. and Zeinalipour-Yazti, D. (2002), "A local search mechanism for peer-to-peer networks", in Proceedings of the Eleventh International Conference on Information and Knowledge Management, ACM, pp. 300--307.
[10]
Yang, B. and Garcia-Molina, H. (2002), "Improving search in peer-to-peer networks", in Proceedings 22nd International Conference on Distributed Computing Systems, IEEE, pp. 5--14.
[11]
Xu, K., Xiong, Y. and Wu, J. (2005), "Summary of peer-to-peer network research".
[12]
Cai, K., Tang, H. and Ding, S. (2011), P2P peer-to-peer network principle and application, Science Press, Beijing, China.
[13]
Huang, L. (2016), Research on Resource Searching in an Unstructured P2P Network Based on Dynamic Greedy Strategy (Master thesis, Beijing Jiaotong University).
[14]
Himali, D. R. and Prasad, S. K. (2011), "Spun: A p2p probabilistic search algorithm based on successful paths in unstructured networks", in 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, IEEE, pp. 1610--1617.
[15]
Joseph, S. and Hoshiai, T. (2003), "Decentralized meta-data strategies: Effective peer-to-peer search", IEICE Transactions on Communications, Vol. 86, No. 6, pp. 1740--1753
[16]
Tang, D., He, M. and Meng, Q. (2007), "Research on Searching in Unstructured P2P Network Based 0n Power-Law Distribution and Small World Character", Journal of Computer Research and Development, Vol. 44, No. 9, pp. 1566--1571.
Index Terms
- Hybrid Breadth-Depth Search Algorithm in Crowd Transaction Network
Recommendations
Game of Bloxorz Solving Agent Using Informed and Uninformed Search Strategies
AbstractBloxorz is a block sliding puzzle game that can be categorized as a pathfinding problem. Pathfinding problems are well known problems in Artificial Intelligence field. In this paper, we proposed a single agent implementation to solve level-1 of ...
End-Vertices of AT-free Bigraphs
Computing and CombinatoricsAbstractThe end-vertex problem for a search algorithm asks whether a vertex of the input graph is the last visited vertex of an execution of that search algorithm. We consider the end-vertex problem restricted to AT-free bigraphs for various search ...
A Unified View of Graph Searching
Graph searching is perhaps one of the simplest and most widely used tools in graph algorithms. Despite this, few theoretical results are known about the vertex orderings that can be produced by a specific search algorithm. A simple characterizing ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2019
246 pages
ISBN:9781450376402
DOI:10.1145/3371238
Copyright © 2019 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 October 2019
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- National Basic Research Program of China (973 Program)
Conference
ICCSE'19
ICCSE'19: The 4th International Conference on Crowd Science and Engineering
October 18 - 21, 2019
Jinan, China
Acceptance Rates
ICCSE'19 Paper Acceptance Rate 35 of 92 submissions, 38%;
Overall Acceptance Rate 92 of 247 submissions, 37%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 55Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in