Answering which-edge queries

Abstract

In this thesis, I formulate a novel problem called Which-Edge question on short- est path and maximum flow queries. Specifically, the Which-Edge-shortest-path problem aims to find k edges that minimize the total distance for a given set of shortest path queries on a graph. This query has important applications in logistics, urban planning, and network planning. I show the NP-hardness of the problem, as well as present efficient algorithms that compute highly accurate results in practice. The Which-Edge-Maximum-Flow problem aims to find which k edges would have the largest impact on a maximum flow query on a network. This problem has important applications in areas like social network and network planning. I shows the inapproximability of the problems and present our heuristic algorithms. Experimental evaluations are carried out on real datasets and results show that our algorithms are scalable and return high quality solutions. Efficient main-memory index structures are crucial to solve the Which-Edge problem. Adaptive Radix Tree (ART) is the most recent in-memory index structure. ART is designed to avoid cache miss, leverage SIMD data parallelism, minimize branch mis-prediction, and have small memory footprint. When an in-memory index structure like ART has significantly few cache misses and branch mis-predictions, it is natural to question whether misses in Translation Lookaside Buffer (TLB) matters. In this thesis, I tries to confirm whether this is the case and if the answer is positive, what are the measures that we can take to alleviate that and how effective they are.