Most applications with graphs use adjacency lists to repre- sent them in memory. The purpose of this work is to put edge lists as a viable alternative. In order to achieve that, the algorithm of inter- polation search is used. Assuming that the values in the array are uni- formly distributed (i.e. there is no prior knowledge about the array), it is proven that the number of iterations has a mean and variance bounded to log2 log2 E (where E is number of directed edges). Its performance is measured and compared for edge lists of graphs with di erent prop- erties. Generally, higher average degree gives better results and Erdos- Renyi graphs outperform power law graphs. Additionally, the algorithm is evaluated with timing random walks on real and generated graphs.
Interpolation search Graph High performance computing Big data Edge list.
© Association for Information and Communication Technologies www.ict-act.org Developed by tdelev