File Download
Supplementary
-
Citations:
- Appears in Collections:
postgraduate thesis: Answering which-edge queries
Title | Answering which-edge queries |
---|---|
Authors | |
Advisors | Advisor(s):Kao, CM |
Issue Date | 2018 |
Publisher | The University of Hong Kong (Pokfulam, Hong Kong) |
Citation | Wong, P. K. [汪可方]. (2018). Answering which-edge queries. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. |
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. |
Degree | Doctor of Philosophy |
Subject | Graph theory - Data processing |
Dept/Program | Computer Science |
Persistent Identifier | http://hdl.handle.net/10722/255475 |
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Kao, CM | - |
dc.contributor.author | Wong, Petrie, Ke-fang | - |
dc.contributor.author | 汪可方 | - |
dc.date.accessioned | 2018-07-05T07:43:41Z | - |
dc.date.available | 2018-07-05T07:43:41Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | Wong, P. K. [汪可方]. (2018). Answering which-edge queries. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. | - |
dc.identifier.uri | http://hdl.handle.net/10722/255475 | - |
dc.description.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. | - |
dc.language | eng | - |
dc.publisher | The University of Hong Kong (Pokfulam, Hong Kong) | - |
dc.relation.ispartof | HKU Theses Online (HKUTO) | - |
dc.rights | The author retains all proprietary rights, (such as patent rights) and the right to use in future works. | - |
dc.rights | This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. | - |
dc.subject.lcsh | Graph theory - Data processing | - |
dc.title | Answering which-edge queries | - |
dc.type | PG_Thesis | - |
dc.description.thesisname | Doctor of Philosophy | - |
dc.description.thesislevel | Doctoral | - |
dc.description.thesisdiscipline | Computer Science | - |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.5353/th_991044019384903414 | - |
dc.date.hkucongregation | 2018 | - |
dc.identifier.mmsid | 991044019384903414 | - |