2 Search Results for "Kelly, Robert"

Document
DOI: 10.4230/LIPIcs.OPODIS.2018.10
Concurrent Robin Hood Hashing

Authors: Robert Kelly, Barak A. Pearlmutter, and Phil Maguire

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
In this paper we examine the issues involved in adding concurrency to the Robin Hood hash table algorithm. We present a non-blocking obstruction-free K-CAS Robin Hood algorithm which requires only a single word compare-and-swap primitive, thus making it highly portable. The implementation maintains the attractive properties of the original Robin Hood structure, such as a low expected probe length, capability to operate effectively under a high load factor and good cache locality, all of which are essential for high performance on modern computer architectures. We compare our data-structures to various other lock-free and concurrent algorithms, as well as a simple hardware transactional variant, and show that our implementation performs better across a number of contexts.
Cite as

Robert Kelly, Barak A. Pearlmutter, and Phil Maguire. Concurrent Robin Hood Hashing. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kelly_et_al:LIPIcs.OPODIS.2018.10,
  author =	{Kelly, Robert and Pearlmutter, Barak A. and Maguire, Phil},
  title =	{{Concurrent Robin Hood Hashing}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.10},
  URN =		{urn:nbn:de:0030-drops-100701},
  doi =		{10.4230/LIPIcs.OPODIS.2018.10},
  annote =	{Keywords: concurrency, Robin Hood Hashing, data-structures, hash tables, non-blocking}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.58
Dynamically-Spaced Geo-Grid Segmentation for Weighted Point Sampling on a Polygon Map Layer (Short Paper)

Authors: Kelly Sims, Gautam Thakur, Kevin Sparks, Marie Urban, Amy Rose, and Robert Stewart

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

Abstract
Geo-grid algorithms divide a large polygon area into several smaller polygons, which are important for studying or executing a set of operations on underlying topological features of a map. The current geo-grid algorithms divide a large polygon in to a set of smaller but equal size polygons only (e.g. is ArcMaps Fishnet). The time to create a geo-grid is typically proportional to number of smaller polygons created. This raises two problems - (i) They cannot skip unwanted areas (such as water bodies, given about 71% percent of the Earth's surface is water-covered); (ii) They are incognizant to any underlying feature set that requires more deliberation. In this work, we propose a novel dynamically spaced geo-grid segmentation algorithm that overcomes these challenges and provides a computationally optimal output for borderline cases of an uneven polygon. Our method uses an underlying topological feature of population distributions, from the LandScan Global 2016 dataset, for creating grids as a function of these weighted features. We benchmark our results against available algorithms and found our approach improves geo-grid creation. Later on, we demonstrate the proposed approach is more effective in harvesting Points of Interest data from a crowd-sourced platform.
Cite as

Kelly Sims, Gautam Thakur, Kevin Sparks, Marie Urban, Amy Rose, and Robert Stewart. Dynamically-Spaced Geo-Grid Segmentation for Weighted Point Sampling on a Polygon Map Layer (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 58:1-58:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sims_et_al:LIPIcs.GISCIENCE.2018.58,
  author =	{Sims, Kelly and Thakur, Gautam and Sparks, Kevin and Urban, Marie and Rose, Amy and Stewart, Robert},
  title =	{{Dynamically-Spaced Geo-Grid Segmentation for Weighted Point Sampling on a Polygon Map Layer}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{58:1--58: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.58},
  URN =		{urn:nbn:de:0030-drops-93860},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.58},
  annote =	{Keywords: geofence, geo-grid, quadtree, points of interest (POI), volunteered geographic information (VGI)}
}
  • Refine by Author
  • 1 Kelly, Robert
  • 1 Maguire, Phil
  • 1 Pearlmutter, Barak A.
  • 1 Rose, Amy
  • 1 Sims, Kelly
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Concurrent algorithms
  • 1 Theory of computation → Divide and conquer

  • Refine by Keyword
  • 1 Robin Hood Hashing
  • 1 concurrency
  • 1 data-structures
  • 1 geo-grid
  • 1 geofence
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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