More Like this

1. A Tight Threshold Bound for Search Trees with 2-Way Comparisons

   https://doi.org/10.1007/978-981-97-2340-9_9  

   Atalig, Sunny; Chrobak, Marek (January 2024, Springer Nature Singapore)

   Chen, Xujin; Li, Bo (Ed.)

   We study search trees with 2-way comparisons (2WCST’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3WCST’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ− is the largest ratio that forces the less-than test, and λ+ −1 is the smallest ratio that forces the equal-to test. They determined that λ = 4 , but for the higher threshold they only showed that λ+ ∈ [ 37 , 49 ]. We give the tight +3 bound for the higher threshold, by proving that in fact λ = 7 . 

   more » « less
2. A Tight Threshold Bound for Search Trees with 2-Way Comparisons

   Sunny Atalig; Marek Chrobak (May 2024, Theory and Applications of Models of Computation - 18th Annual Conference)

   We study search trees with 2-way comparisons (2WCST’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3WCST’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ− is the largest ratio that forces the less-than test, and λ+ is the smallest ratio that forces the equal-to test. They determined that λ− = 41 , but for the higher threshold they only showed that λ+ ∈ [ 3/7 , 4/9 ]. We give the tight bound for the higher threshold, by proving that in fact λ+ = 3/7 . 

   more » « less
3. A tight threshold bound for search trees with 2-way comparisons

   https://doi.org/10.1016/j.tcs.2025.115589  

   Atalig, Sunny; Chrobak, Marek (December 2025, Theoretical Computer Science)

   We study search trees with 2-way comparisons (2WCST’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3WCST’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum- cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. In 2002, Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ− is the largest ratio that forces the less-than test, and λ+ is the smallest −1 ratio that admits the equal-to test. They determined that λ = 4 , but for the higher threshold they only showed that λ+ ∈ [ 37 , 49 ]. We give the tight bound for the higher threshold, by proving that in fact +3 λ=7. 

   more » « less
4. A Tight Threshold Bound for Search Trees with 2-way Comparisons

   Atalig, Sunny; Chrobak, Marek (May 2024, LNCS)

   We study search trees with 2-way comparisons (2WCST’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3WCST’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum- cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ− is the largest ratio that forces the less-than test, and λ+ is the smallest ratio that −1 forces the equal-to test. They determined that λ = 4 , but for the higher threshold they only showed that +34 +3 λ ∈ [7, 9]. We give the tight bound for the higher threshold, by proving that in fact λ = 7. 

   more » « less
5. X-Blossom: Massive Parallelization of Graph Maximum Matching

   https://doi.org/10.14778/3748191.3748199  

   Fan, Dayi; Lee, Rubao; Zhang, Xiaodong (June 2025, Proceedings of the VLDB Endowment)

   The blossom algorithm computes maximum matchings in graphs and has been widely applied across diverse domains, including machine learning, economic analysis, and other essential data analytics applications. As data scales and the demand for real-time processing intensifies, high-performance computing solutions have become indispensable. Over the years, substantial research efforts have been dedicated to improving the sequential blossom algorithm. However, developing an efficient parallel solution remains highly challenging due to the algorithm's intricate execution patterns, sequential recursive dependencies, dynamic data structure modifications, and inefficient path search. By thoroughly analyzing existing solutions, we have identified critical issues and proposed a new parallel framework called X-Blossom. This framework eliminates recursion entirely, enables efficient searches for multiple disjoint paths, and employs a simple path table to trace paths, removing the need for dynamic graphs and trees. These efforts in algorithm development result in significant performance enhancement. Extensive experiments on real-world datasets show that X-Blossom outperforms all existing solutions, achieving up to 992x speedup compared to the fastest sequential baseline, and an average of 431x speedup over the state-of-the-art parallel solution using 8 cores. It also demonstrates excellent scalability, achieving an average speedup of 1.72x when threads double in scalability tests to 64 cores. To the best of our knowledge, X-Blossom is the fastest solution for this class of graph algorithms. 

   more » « less