BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Joseph A. Simons

Joseph A. Simons contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputational GeometrySoftware Engineering

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2014arXiv

Data-Oblivious Graph Algorithms in Outsourced External Memory

Motivated by privacy preservation for outsourced data, data-oblivious external memory is a computational framework where a client performs computations on data stored at a semi-trusted server in a way that does not reveal her data to the server. This approach facilitates collaboration and reliability over traditional frameworks, and it provides privacy protection, even though the server has full access to the data and he can monitor how it is accessed by the client. The challenge is that even if data is encrypted, the server can learn information based on the client data access pattern; hence, access patterns must also be obfuscated. We investigate privacy-preserving algorithms for outsourced external memory that are based on the use of data-oblivious algorithms, that is, algorithms where each possible sequence of data accesses is independent of the data values. We give new efficient data-oblivious algorithms in the outsourced external memory model for a number of fundamental graph problems. Our results include new data-oblivious external-memory methods for constructing minimum spanning trees, performing various traversals on rooted trees, answering least common ancestor queries on trees, computing biconnected components, and forming open ear decompositions. None of our algorithms make use of constant-time random oracles.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Windows into Geometric Events: Data Structures for Time-Windowed Querying of Temporal Point Sets

We study geometric data structures for sets of point-based temporal events, answering time-windowed queries, i.e., given a contiguous time interval we answer common geometric queries about the point events with time stamps in this interval. The geometric queries we consider include queries based on the skyline, convex hull, and proximity relations of the point set. We provide space efficient data structures which answer queries in polylogarithmic time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Confluent Hasse diagrams

We show that a transitively reduced digraph has a confluent upward drawing if and only if its reachability relation has order dimension at most two. In this case, we construct a confluent upward drawing with $O(n^2)$ features, in an $O(n) \times O(n)$ grid in $O(n^2)$ time. For the digraphs representing series-parallel partial orders we show how to construct a drawing with $O(n)$ features in an $O(n) \times O(n)$ grid in $O(n)$ time from a series-parallel decomposition of the partial order. Our drawings are optimal in the number of confluent junctions they use.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fixed parameter tractability of crossing minimization of almost-trees

We investigate exact crossing minimization for graphs that differ from trees by a small number of additional edges, for several variants of the crossing minimization problem. In particular, we provide fixed parameter tractable algorithms for the 1-page book crossing number, the 2-page book crossing number, and the minimum number of crossed edges in 1-page and 2-page book drawings.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Set-Difference Range Queries

We introduce the problem of performing set-difference range queries, where answers to queries are set-theoretic symmetric differences between sets of items in two geometric ranges. We describe a general framework for answering such queries based on a novel use of data-streaming sketches we call signed symmetric-difference sketches. We show that such sketches can be realized using invertible Bloom filters (IBFs), which can be composed, differenced, and searched so as to solve set-difference range queries in a wide range of scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Fully Retroactive Approximate Range and Nearest Neighbor Searching

We describe fully retroactive dynamic data structures for approximate range reporting and approximate nearest neighbor reporting. We show how to maintain, for any positive constant $d$, a set of $n$ points in $\R^d$ indexed by time such that we can perform insertions or deletions at any point in the timeline in $O(\log n)$ amortized time. We support, for any small constant $ε>0$, $(1+ε)$-approximate range reporting queries at any point in the timeline in $O(\log n + k)$ time, where $k$ is the output size. We also show how to answer $(1+ε)$-approximate nearest neighbor queries for any point in the past or present in $O(\log n)$ time.

0 citations0 reviewsNo code linkedOpen access