Sean Chester
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Sean Chester has a total of 40 co-authors. Here are the top co-authors by number of shared publications:
Alex Thomo
University of Victoria, Victoria, BC, Canada
8 shared publicationsS. Venkatesh
University of Victoria, Victoria, Canada
8 shared publications- Ira Assent
Aarhus University
5 shared publications Sue Whitesides
University of Victoria, Victoria, Canada
5 shared publicationsKenneth S. Bøgh
Aarhus University, Aarhus, Denmark
4 shared publications- Bruce M. Kapron
University of Victoria
3 shared publications
Latest Publications
- Open Access
- 25 August 2025
- Published by Association for Computing Machinery (ACM)
- p. 90-100
The Batch Insertion Operator for Shared Mobility Route Planning on Time-Dependent Road Networks
- 25 August 2025
- Published by Association for Computing Machinery (ACM)
- p. 90-100
Open AccessThe Batch Insertion Operator for Shared Mobility Route Planning on Time-Dependent Road Networks
- Open Access
- 8 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 236-249
CLOVER: A GPU-native, Spatio-graph-based Approach to Exact kNN
- 8 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 236-249
Open AccessCLOVER: A GPU-native, Spatio-graph-based Approach to Exact kNN
- Open Access
- 10 December 2023
- Published by Association for Computing Machinery (ACM)
- p. 1-10
Lock-free Vertex Clustering for Multicore Mesh Reduction
Modern data collection methods can capture representations of 3D objects at resolutions much greater than they can be discretely rendered as an image. To improve the efficiency of storage, transmission, rendering, and editing of 3D models constructed from such data, it is beneficial to first employ a mesh reduction technique to reduce the size of a mesh. Vertex clustering, a technique that merges close vertices together, has particularly wide applicability, because it operates only on vertices and their spatial proximity. However, it is also very difficult to accelerate with parallelisation in a deterministic manner because it contains extensive algorithmic dependencies. Prior work treats the non-trivial clustering step of this process serially to preserve vertex priorities, which fundamentally limits to mid-single digits the acceleration rates that are possible for the process overall. This paper introduces a novel lock-free parallel algorithm, P-Weld, that exposes parallelism with a graph-theoretic lens that iteratively peels away layers of a mesh that have no remaining dependencies. Concurrent updates to shared data are managed with a linearisable sequence of atomic instructions that exactly reproduces the serial clustering. The resulting parallelism and improved spatial locality yield a 3.86 × speedup on a standard 14-million vertex mesh and a 2.93 × speedup on a 400-million vertex LiDaR point cloud covering the city of Vancouver, Canada, relative to a popular open source library.
- 10 December 2023
- Published by Association for Computing Machinery (ACM)
- p. 1-10
Open AccessLock-free Vertex Clustering for Multicore Mesh Reduction
Modern data collection methods can capture representations of 3D objects at resolutions much greater than they can be discretely rendered as an image. To improve the efficiency of storage, transmission, rendering, and editing of 3D models constructed from such data, it is beneficial to first employ a mesh reduction technique to reduce the size of a mesh. Vertex clustering, a technique that merges close vertices together, has particularly wide applicability, because it operates only on vertices and their spatial proximity. However, it is also very difficult to accelerate with parallelisation in a deterministic manner because it contains extensive algorithmic dependencies. Prior work treats the non-trivial clustering step of this process serially to preserve vertex priorities, which fundamentally limits to mid-single digits the acceleration rates that are possible for the process overall. This paper introduces a novel lock-free parallel algorithm, P-Weld, that exposes parallelism with a graph-theoretic lens that iteratively peels away layers of a mesh that have no remaining dependencies. Concurrent updates to shared data are managed with a linearisable sequence of atomic instructions that exactly reproduces the serial clustering. The resulting parallelism and improved spatial locality yield a 3.86 × speedup on a standard 14-million vertex mesh and a 2.93 × speedup on a 400-million vertex LiDaR point cloud covering the city of Vancouver, Canada, relative to a popular open source library.
- Open Access
- 3 May 2022
- Published by Springer Nature in BMC Bioinformatics
- Vol. 23 (1) , 1-28
KnotAli: informed energy minimization through the use of evolutionary information
Improving the prediction of structures, especially those containing pseudoknots (structures with crossing base pairs) is an ongoing challenge. Homology-based methods utilize structural similarities within a family to predict the structure. However, their prediction is limited to the consensus structure, and by the quality of the alignment. Minimum free energy (MFE) based methods, on the other hand, do not rely on familial information and can predict structures of novel RNA molecules. Their prediction normally suffers from inaccuracies due to their underlying energy parameters. We present a new method for prediction of RNA pseudoknotted secondary structures that combines the strengths of MFE prediction and alignment-based methods. KnotAli takes a multiple RNA sequence alignment as input and uses covariation and thermodynamic energy minimization to predict possibly pseudoknotted secondary structures for each individual sequence in the alignment. We compared KnotAli’s performance to that of three other alignment-based programs, two that can handle pseudoknotted structures and one control, on a large data set of 3034 RNA sequences with varying lengths and levels of sequence conservation from 10 families with pseudoknotted and pseudoknot-free reference structures. We produced sequence alignments for each family using two well-known sequence aligners (MUSCLE and MAFFT). We found KnotAli’s performance to be superior in 6 of the 10 families for MUSCLE and 7 of the 10 for MAFFT. While both KnotAli and Cacofold use background noise correction strategies, we found KnotAli’s predictions to be less dependent on the alignment quality. KnotAli can be found online at the Zenodo image: https://doi.org/10.5281/zenodo.5794719
- 3 May 2022
- Published by Springer Nature in BMC Bioinformatics
- Vol. 23 (1) , 1-28
Open AccessKnotAli: informed energy minimization through the use of evolutionary information
Improving the prediction of structures, especially those containing pseudoknots (structures with crossing base pairs) is an ongoing challenge. Homology-based methods utilize structural similarities within a family to predict the structure. However, their prediction is limited to the consensus structure, and by the quality of the alignment. Minimum free energy (MFE) based methods, on the other hand, do not rely on familial information and can predict structures of novel RNA molecules. Their prediction normally suffers from inaccuracies due to their underlying energy parameters. We present a new method for prediction of RNA pseudoknotted secondary structures that combines the strengths of MFE prediction and alignment-based methods. KnotAli takes a multiple RNA sequence alignment as input and uses covariation and thermodynamic energy minimization to predict possibly pseudoknotted secondary structures for each individual sequence in the alignment. We compared KnotAli’s performance to that of three other alignment-based programs, two that can handle pseudoknotted structures and one control, on a large data set of 3034 RNA sequences with varying lengths and levels of sequence conservation from 10 families with pseudoknotted and pseudoknot-free reference structures. We produced sequence alignments for each family using two well-known sequence aligners (MUSCLE and MAFFT). We found KnotAli’s performance to be superior in 6 of the 10 families for MUSCLE and 7 of the 10 for MAFFT. While both KnotAli and Cacofold use background noise correction strategies, we found KnotAli’s predictions to be less dependent on the alignment quality. KnotAli can be found online at the Zenodo image: https://doi.org/10.5281/zenodo.5794719
- 5 December 2020
- Published by Elsevier in Information Systems
- Vol. 97, 101687
Efficient top-k recently-frequent term querying over spatio-temporal textual streams
- 5 December 2020
- Published by Elsevier in Information Systems
- Vol. 97, 101687
Efficient top-k recently-frequent term querying over spatio-temporal textual streams
- 1 April 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 425-436
Improving Spatial Data Processing by Clipping Minimum Bounding Boxes
The majority of spatial processing techniques rely heavily on the idea of approximating each group of spatial objects by their minimum bounding box (MBB). As each MBB is compact to store (requiring only two multi-dimensional points) and intersection tests between MBBs are cheap to execute, these approximations are used predominantly to perform the (initial) filtering step of spatial data processing. However, fitting (groups of) spatial objects into a rough box often results in a very poor approximation of the underlying data. The resulting MBBs contain a lot of "dead space"-fragments of bounded area that contain no actual objects-that can significantly reduce the filtering efficacy. This paper introduces the general concept of a clipped bounding box (CBB) that addresses the principal disadvantage of MBBs, i.e., their poor approximation of spatial objects. Essentially, a CBB "clips away" dead space from the corners of an MBB by storing only a few auxiliary points. Turning to four popular R-tree implementations (a ubiquitous application of MBBs), we demonstrate how minor modifications to the query algorithm can exploit our CBB auxiliary points to avoid many unnecessary recursions into dead space. Extensive experiments show that clipped R-tree variants substantially reduce I/Os: e.g., by clipping the state-of-the-art revised R*-tree we can eliminate on average 19% of I/Os.
- 1 April 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 425-436
Improving Spatial Data Processing by Clipping Minimum Bounding Boxes
The majority of spatial processing techniques rely heavily on the idea of approximating each group of spatial objects by their minimum bounding box (MBB). As each MBB is compact to store (requiring only two multi-dimensional points) and intersection tests between MBBs are cheap to execute, these approximations are used predominantly to perform the (initial) filtering step of spatial data processing. However, fitting (groups of) spatial objects into a rough box often results in a very poor approximation of the underlying data. The resulting MBBs contain a lot of "dead space"-fragments of bounded area that contain no actual objects-that can significantly reduce the filtering efficacy. This paper introduces the general concept of a clipped bounding box (CBB) that addresses the principal disadvantage of MBBs, i.e., their poor approximation of spatial objects. Essentially, a CBB "clips away" dead space from the corners of an MBB by storing only a few auxiliary points. Turning to four popular R-tree implementations (a ubiquitous application of MBBs), we demonstrate how minor modifications to the query algorithm can exploit our CBB auxiliary points to avoid many unnecessary recursions into dead space. Extensive experiments show that clipped R-tree variants substantially reduce I/Os: e.g., by clipping the state-of-the-art revised R*-tree we can eliminate on average 19% of I/Os.
- Open Access
- 9 May 2017
- Published by Association for Computing Machinery (ACM)
- p. 447-462
Template Skycube Algorithms for Heterogeneous Parallelism on Multicore and GPU Architectures
Multicore CPUs and cheap co-processors such as GPUs create opportunities for vastly accelerating database queries. However, given the differences in their threading models, expected granularities of parallelism, and memory subsystems, effectively utilising all cores with all co-processors for an intensive query is very difficult. This paper introduces a novel templating methodology to create portable, yet architecture-aware, algorithms. We apply this methodology on the very compute-intensive task of calculating the *skycube*, a materialisation of exponentially many skyline query results, which finds applications in data exploration and multi-criteria decision making. We define three parallel templates, two that leverage insights from previous skycube research and a third that exploits a novel point-based paradigm to expose more data parallelism. An experimental study shows that, relative to the state-of-the-art that does not parallelise well due to its memory and cache requirements, our algorithms provide an order of magnitude improvement on either architecture and proportionately improve as more GPUs are added.
- 9 May 2017
- Published by Association for Computing Machinery (ACM)
- p. 447-462
Open AccessTemplate Skycube Algorithms for Heterogeneous Parallelism on Multicore and GPU Architectures
Multicore CPUs and cheap co-processors such as GPUs create opportunities for vastly accelerating database queries. However, given the differences in their threading models, expected granularities of parallelism, and memory subsystems, effectively utilising all cores with all co-processors for an intensive query is very difficult. This paper introduces a novel templating methodology to create portable, yet architecture-aware, algorithms. We apply this methodology on the very compute-intensive task of calculating the *skycube*, a materialisation of exponentially many skyline query results, which finds applications in data exploration and multi-criteria decision making. We define three parallel templates, two that leverage insights from previous skycube research and a third that exploits a novel point-based paradigm to expose more data parallelism. An experimental study shows that, relative to the state-of-the-art that does not parallelise well due to its memory and cache requirements, our algorithms provide an order of magnitude improvement on either architecture and proportionately improve as more GPUs are added.
- Open Access
- 24 October 2016
- Published by Association for Computing Machinery (ACM)
- p. 459-468
Group-Aware Weighted Bipartite B-Matching
The weighted bipartite B-matching (WBM) problem models a host of data management applications, ranging from recommender systems to Internet advertising and e-commerce. Many of these applications, however, demand versatile assignment constraints, which WBM is weak at modelling. In this paper, we investigate powerful generalisations of WBM. We first show that a recent proposal for conflict-aware WBM by Chen et al. is hard to approximate by reducing their problem from Maximum Weight Independent Set. We then propose two related problems, collectively called group-aware WBM. For the first problem, which constrains the degree of groups of vertices, we show that a linear programming formulation produces a Totally Unimodular (TU) matrix and is thus polynomial-time solvable. Nonetheless, we also give a simple greedy algorithm subject to a 2-extendible system that scales to higher workloads. For the second problem, which instead limits the budget of groups of vertices, we prove its NP-hardness but again give a greedy algorithm with an approximation guarantee. Our experimental evaluation reveals that the greedy algorithms vastly outperform their theoretical guarantees and scale to bipartite graphs with more than eleven million edges.
- 24 October 2016
- Published by Association for Computing Machinery (ACM)
- p. 459-468
Open AccessGroup-Aware Weighted Bipartite B-Matching
The weighted bipartite B-matching (WBM) problem models a host of data management applications, ranging from recommender systems to Internet advertising and e-commerce. Many of these applications, however, demand versatile assignment constraints, which WBM is weak at modelling. In this paper, we investigate powerful generalisations of WBM. We first show that a recent proposal for conflict-aware WBM by Chen et al. is hard to approximate by reducing their problem from Maximum Weight Independent Set. We then propose two related problems, collectively called group-aware WBM. For the first problem, which constrains the degree of groups of vertices, we show that a linear programming formulation produces a Totally Unimodular (TU) matrix and is thus polynomial-time solvable. Nonetheless, we also give a simple greedy algorithm subject to a 2-extendible system that scales to higher workloads. For the second problem, which instead limits the budget of groups of vertices, we prove its NP-hardness but again give a greedy algorithm with an approximation guarantee. Our experimental evaluation reveals that the greedy algorithms vastly outperform their theoretical guarantees and scale to bipartite graphs with more than eleven million edges.
- 20 August 2016
- Published by Springer Nature in The VLDB Journal
- Vol. 25 (6) , 817-841
SkyAlign: a portable, work-efficient skyline algorithm for multicore and GPU architectures
- 20 August 2016
- Published by Springer Nature in The VLDB Journal
- Vol. 25 (6) , 817-841
SkyAlign: a portable, work-efficient skyline algorithm for multicore and GPU architectures
- Open Access
- 1 May 2015
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 8 (9) , 962-973
Work-efficient parallel skyline computation for the GPU
The skyline operator returns records in a dataset that provide optimal trade-offs of multiple dimensions. State-of-the-art skyline computation involves complex tree traversals, data-ordering, and conditional branching to minimize the number of point-to-point comparisons. Meanwhile, GPGPU computing offers the potential for parallelizing skyline computation across thousands of cores. However, attempts to port skyline algorithms to the GPU have prioritized throughput and failed to outperform sequential algorithms. In this paper, we introduce a new skyline algorithm, designed for the GPU, that uses a global, static partitioning scheme. With the partitioning, we can permit controlled branching to exploit transitive relationships and avoid most point-to-point comparisons. The result is a non-traditional GPU algorithm, SkyAlign, that prioritizes work-efficiency and respectable throughput, rather than maximal throughput, to achieve orders of magnitude faster performance.
- 1 May 2015
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 8 (9) , 962-973
Open AccessWork-efficient parallel skyline computation for the GPU
The skyline operator returns records in a dataset that provide optimal trade-offs of multiple dimensions. State-of-the-art skyline computation involves complex tree traversals, data-ordering, and conditional branching to minimize the number of point-to-point comparisons. Meanwhile, GPGPU computing offers the potential for parallelizing skyline computation across thousands of cores. However, attempts to port skyline algorithms to the GPU have prioritized throughput and failed to outperform sequential algorithms. In this paper, we introduce a new skyline algorithm, designed for the GPU, that uses a global, static partitioning scheme. With the partitioning, we can permit controlled branching to exploit transitive relationships and avoid most point-to-point comparisons. The result is a non-traditional GPU algorithm, SkyAlign, that prioritizes work-efficiency and respectable throughput, rather than maximal throughput, to achieve orders of magnitude faster performance.