Bibliographic record
Abstract
This thesis delves into the exploration of shortest path queries in planar graphs, with an emphasis on the utilization of space-efficient data structures. Our investigation primarily targets connected, undirected, static pointer planar graphs, focusing on scenarios where queries predominantly start or end at a select subset of nodes. \n \nThe shortest path problem, central to our study, boasts a rich historical context and has profound real-world implications in diverse fields such as web mapping, robotics, and VLSI circuit design. Our research is pivoted on the space-efficient representation of planar graphs, a critical consideration in 2D visualizations and city map representations. \n \nIn this thesis, shortest path queries are delineated into three categories: shortest path, distance oracle, and port queries, each with distinct computational characteristics and storage requirements. A significant portion of our research is focused on center-based configurations in graphs, where a small subset of nodes, designated as ‘centers,’ plays a pivotal role. These centers are crucial, either due to their strategic importance within the graph, which necessitates more prompt responses to queries, or due to their high frequency in the query list. We explore various scenarios within this configuration. Our approach prioritizes handling queries involving these centers more efficiently, aiming to provide rapid responses for strategically important queries and to enhance overall query processing speed. This method is particularly effective, as addressing the queries linked to these relatively few but significant centers can substantially improve the efficiency of the entire system. Such prioritization reflects practical applications like urban navigation, where focusing on key locations can significantly expedite overall navigation and operational efficiency. \n \nFor shortest path queries in a center-based configuration, we have developed a data structure that efficiently answers queries from other nodes to centers in O(length of the path) time. In the first scenario, where all queries are from or to a center, the space requirement is 3n+2m+2km+o(nk), where n represents the number of nodes, m the number of edges, and k the number of centers. Additionally, our approach supports distributed storage and processing, facilitating parallel computing. \n \nFor distance oracle queries in unweighted graphs within a center-based configuration, our methods manage responses in O(log^(1+ϵ) n) time with an additional o(nk) space requirement. In general, for unweighted graphs without any specific configuration, the distance oracle requires 2n + 2m + 2nm + o(n) bits of space, offering responses in a similar time frame. The strength of our approach lies in its distributability across multiple servers, which enhances concurrent query processing, a feature particularly beneficial in center-based configurations. \n \nMoreover, we introduce a specialized data structure for distributed routing tables, capable of responding to port queries in constant time. This structure efficiently utilizes space, limiting the aggregate bit requirement for all routing tables within graph G to 3.2n^2+o(n^2) bits.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.004 |
| Meta-epidemiology (narrow) | 0.001 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.001 |
| Bibliometrics | 0.001 | 0.002 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.002 | 0.003 |
| Open science | 0.001 | 0.002 |
| Research integrity | 0.001 | 0.001 |
| Insufficient payload (model declined to judge) | 0.008 | 0.001 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".