Browsing by Author "Koehler H"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    BatchHL+: batch dynamic labelling for distance queries on large-scale networks
    (Springer-Verlag GmbH Germany, part of Springer Nature, 2024-01) Farhan M; Koehler H; Wang Q
    Many real-world applications operate on dynamic graphs to perform important tasks. In this article, we study batch-dynamic algorithms that are capable of updating distance labelling efficiently in order to reflect the effects of rapid changes on such graphs. To explore the full pruning potentials, we first characterize the minimal set of vertices being affected by batch updates. Then, we reveal patterns of interactions among different updates (edge insertions and edge deletions) and leverage them to design pruning rules for reducing update search space. These interesting findings lead us to developing a new batch-dynamic method, called BatchHL+ , which can dynamize labelling for distance queries much more efficiently than existing work. We provide formal proofs for the correctness and minimality of BatchHL+ which are non-trivial and require a delicate analysis of patterns of interactions. Empirically, we have evaluated the performance of BatchHL+ on 15 real-world networks. The results show that BatchHL+ significantly outperforms the state-of-the-art methods with up to 3 orders of magnitude faster in reflecting updates of rapidly changing graphs for distance queries.
  • Thumbnail Image
    Item
    Learning to Bound for Maximum Common Subgraph Algorithms
    (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany, 2025-08-08) Kothalawala BW; Koehler H; Wang Q; Garcia de la Banda M
    Identifying the maximum common subgraph between two graphs is a computationally challenging NP-hard problem. While the McSplit algorithm represents a state-of-the-art approach within a branch-and-bound (BnB) framework, several extensions have been proposed to enhance its vertex pair selection strategy, often utilizing reinforcement learning techniques. Nonetheless, the quality of the upper bound remains a critical factor in accelerating the search process by effectively pruning unpromising branches. This research introduces a novel, more restrictive upper bound derived from a detailed analysis of the McSplit algorithm's generated partitions. To enhance the effectiveness of this bound, we propose a reinforcement learning approach that strategically directs computational effort towards the most promising regions within the search space.
  • Thumbnail Image
    Item
    Mining Meaningful Keys and Foreign Keys with High Precision and Recall
    (VLDB Endowment, 2025-01-01) Koehler H; Link S; Palpanas T; Tatbul N
    We demonstrate a next-generation Entity/Relationship (E/R) Profiler that mines meaningful key/foreign key relationships from a given data repository. Core novelties include a strict hierarchy of key variants ranging from candidate keys to SQL unique constraints that represent different ways to identify incomplete entities, a measure of orthogonality that separates accidental from meaningful keys, and algorithms for mining approximate keys for all these variants under different thresholds of arity, completeness, dirtiness, and orthogonality. We showcase the high precision and recall achieved by our tool and how it facilitates the users’ understanding which entity and referential integrity constraints govern their data.
  • Thumbnail Image
    Item
    Stable Tree Labelling for Accelerating Distance Queries on Dynamic Road Networks
    (OpenProceedings.org, 2024-11-11) Koehler H; Farhan M; Wang Q
    Finding the shortest-path distance between two arbitrary vertices is an important problem in road networks. Due to real-time traffic conditions, road networks undergo dynamic changes all the time. Current state-of-the-art methods incrementally maintain a distance labelling based on a hierarchy among vertices to support efficient distance computation. However, their labelling sizes are often large and cannot be efficiently maintained. To combat these issues, we present a simple yet efficient labelling method, namely Stable Tree Labelling (STL), for answering distance queries on dynamic road networks. We observe that the properties of an underlying hierarchy play an important role in improving and balancing query and update performance. Thus, we introduce the notion of stable tree hierarchy which lays the ground for developing efficient maintenance algorithms on dynamic road networks. Based on stable tree hierarchy, STL can be efficiently constructed as a 2-hop labelling. A crucial ingredient of STL is to only store distances within subgraphs in labels, rather than distances in the entire graph, which restricts the labels affected by dynamic changes. We further develop two efficient maintenance algorithms upon STL: Label Search algorithm and Pareto Search algorithm. Label Search algorithm identifies affected ancestors in a stable tree hierarchy and performs efficient searches to update labels from those ancestors. Pareto Search algorithm explores the interaction between search spaces of different ancestors, and combines searches from multiple ancestors into only two searches for each update, eliminating duplicate graph traversals. The experiments show that our algorithms significantly outperform state-of-the-art dynamic methods in maintaining the labelling and query processing, while requiring an order of magnitude less space.