File Download
Supplementary

postgraduate thesis: Answering which-edge queries

TitleAnswering which-edge queries
Authors
Advisors
Advisor(s):Kao, CM
Issue Date2018
PublisherThe 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.
AbstractIn 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.
DegreeDoctor of Philosophy
SubjectGraph theory - Data processing
Dept/ProgramComputer Science
Persistent Identifierhttp://hdl.handle.net/10722/255475

 

DC FieldValueLanguage
dc.contributor.advisorKao, CM-
dc.contributor.authorWong, Petrie, Ke-fang-
dc.contributor.author汪可方-
dc.date.accessioned2018-07-05T07:43:41Z-
dc.date.available2018-07-05T07:43:41Z-
dc.date.issued2018-
dc.identifier.citationWong, P. K. [汪可方]. (2018). Answering which-edge queries. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR.-
dc.identifier.urihttp://hdl.handle.net/10722/255475-
dc.description.abstractIn 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.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subject.lcshGraph theory - Data processing-
dc.titleAnswering which-edge queries-
dc.typePG_Thesis-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineComputer Science-
dc.description.naturepublished_or_final_version-
dc.date.hkucongregation2018-
dc.identifier.mmsid991044019384903414-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats