2 Search Results for "Morton, April"

Document
DOI: 10.4230/LIPIcs.SEA.2026.24
ZOR Filters: Fast and Smaller Than Fuse Filters

Authors: Antoine Limasset

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Probabilistic membership filters support fast approximate membership queries with controlled false-positive probability ε and are widely used across storage, analytics, networking, and bioinformatics [Chang et al., 2008; Niv Dayan et al., 2018; Broder and Mitzenmacher, 2004; Harris and Medvedev, 2020; Marchet and Limasset, 2023; Chikhi et al., 2025; Hernandez-Courbevoie et al., 2025]. In the static setting, low-overhead methods such as XOR, Fuse, and BuRR have been proposed [Graf and Lemire, 2020; Graf and Lemire, 2022; Dillinger et al., 2022; Ulrich and Renard, 2023]. Among these, Fuse filters are known for near-optimal query throughput. For XOR/Fuse-style peeling constructions, however, build success is only high probability, which complicates deterministic builds. We introduce ZOR filters, a deterministic continuation of XOR/Fuse-style constructions that guarantees termination while preserving the same XOR-based query mechanism. ZOR replaces restart-on-failure with deterministic peeling that abandons a small fraction of keys, and restores false-positive-only semantics by storing the remainder in a compact auxiliary structure. In our experiments, the abandoned fraction drops below 1% for moderate arity (e.g., N ≥ 5), so the auxiliary handles a negligible fraction of keys. As a result, ZOR filters can be substantially more memory-efficient than Fuse filters, with overhead below 1%, while not yet matching the near-optimal overhead of BuRR (below 0.1%). In query performance, ZOR-pure is close to Fuse and faster than BuRR on positive queries, while the complete interleaved variant trades additional negative-query latency for deterministic continuation. Relative to optimised Fuse/BuRR implementations [Graf and Lemire, 2022; Dillinger et al., 2022], the current ZOR prototype remains slower in construction because deterministic peeling requires explicit incidence handling; reducing this construction gap is an important direction for future work.
Cite as

Antoine Limasset. ZOR Filters: Fast and Smaller Than Fuse Filters. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{limasset:LIPIcs.SEA.2026.24,
  author =	{Limasset, Antoine},
  title =	{{ZOR Filters: Fast and Smaller Than Fuse Filters}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.24},
  URN =		{urn:nbn:de:0030-drops-260281},
  doi =		{10.4230/LIPIcs.SEA.2026.24},
  annote =	{Keywords: Data structure, Approximate Set Membership, Static filter}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.51
Need A Boost? A Comparison of Traditional Commuting Models with the XGBoost Model for Predicting Commuting Flows (Short Paper)

Authors: April Morton, Jesse Piburn, and Nicholas Nagle

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
Commuting models estimate the number of commuting trips from home to work locations in a given area. Since their infancy, they have been increasingly used in a variety of fields to reduce traffic and pollution, drive infrastructure choices, and solve a variety of other problems. Traditional commuting models, such as gravity and radiation models, typically have a strict structural form and limited number of input variables, which may limit their ability to predict commuting flows as well as machine learning models that might better capture the complex dynamics of the commuting process. To determine whether machine learning models might add value to the field of commuter flow prediction, we compare and discuss the performance of two standard traditional models with the XGBoost machine learning algorithm for predicting home to work commuter flows from a well-known United States commuting dataset. We find that the XGBoost model outperforms the traditional models on three commonly used metrics, indicating that machine learning models may add value to the field of commuter flow prediction.
Cite as

April Morton, Jesse Piburn, and Nicholas Nagle. Need A Boost? A Comparison of Traditional Commuting Models with the XGBoost Model for Predicting Commuting Flows (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 51:1-51:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{morton_et_al:LIPIcs.GISCIENCE.2018.51,
  author =	{Morton, April and Piburn, Jesse and Nagle, Nicholas},
  title =	{{Need A Boost? A Comparison of Traditional Commuting Models with the XGBoost Model for Predicting Commuting Flows}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{51:1--51:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.51},
  URN =		{urn:nbn:de:0030-drops-93793},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.51},
  annote =	{Keywords: Machine learning, commuting modeling}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2018

  • Refine by Author
  • 1 Limasset, Antoine
  • 1 Morton, April
  • 1 Nagle, Nicholas
  • 1 Piburn, Jesse

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Applied computing → Law, social and behavioral sciences
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 Approximate Set Membership
  • 1 Data structure
  • 1 Machine learning
  • 1 Static filter
  • 1 commuting modeling

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact