Questions about properties and applications of data structures.
4
votes
0answers
247 views
Multiple-sources dominator trees: compact representation and fast algorithm?
I recently learnt about the concept of dominator trees and was fascinated by it.
I was wondering how the problem extends to computing dominators from multiple sources, or even from all vertices in ...
1
vote
0answers
48 views
Give a simple way to augment Van emde boas tree, to find/delete median in O(log log u) time
I need a simple augmentation to support median/order statistic queries in
O(log log n) time,without increasing the time for other operations.
1
vote
2answers
287 views
How do top researchers keep track new results in datastructures
Is there any twitter or some feed,which constantly sends new results which are being published to your mail.
1
vote
0answers
25 views
Data Structure for Set Intersection? [migrated]
Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated?
Init an empty set
Add an ...
8
votes
0answers
129 views
How fast can we compute the set inclusion poset of a set family?
Given a set family $\mathcal{F}$ of subsets of a universe $U$.
Let $S_1,S_2 \in \mathcal F$ and we want to answer is $S_1 \subseteq S_2$.
I am looking for a data-structure that will allow me to ...
3
votes
1answer
75 views
Outer part of Voronoi diagram in 3D
Given a set of points $V \subset \mathbb{R}^d$, the Voronoi diagram divides $\mathbb{R}^d$ into $|V|$ parts such that for every $v \in V$, the part of $\mathbb{R}^d$ for which $v$ is closer than any ...
3
votes
1answer
100 views
Optimal insertion times in insertion-only data structures beyond Bentley-Saxe
The Bentley-Saxe trick allows us to go from a static decomposable problem to a problem admitting insertions, where the insertion time is off the optimal time by a factor of $\log n$.
Is this tight ? ...
9
votes
1answer
178 views
Heapsort:Heaps =~ Quicksort:BSTs =~ Mergesort:___?
Please excuse the terseness of the title, I may have sacrificed clarity on the altar of conciseness.
One can see that inserting elements of an array into a binary search tree and reading them back ...
2
votes
1answer
80 views
Verifying consistency of strict and non-strict partial orders constraints
I am building a set of constraints of the kind $x < y$ and $x \leq y$, where $<$ is a strict order and $\leq$ is a non-strict order on the same set, and $x$ and $y$ are abstract variables ...
3
votes
1answer
114 views
What is the fastest deterministic algorithm for incremental dynamic tree reachability?
As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time.
...
10
votes
0answers
162 views
Data structure for updates on intervals and querying number of zeros
I am looking for a data structure that would maintain an integer table t of size n, and allowing the following operations in time $O(\log n)$.
increase(a,b), which increases t[a],t[a+1],..,t[b].
...
6
votes
2answers
124 views
Almost universal string hashing in $Z_{2^n}$ and sublinear space
Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$:
For $p$ prime and $x_i \in \mathbb{Z_p}$, $h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$ for $a \in ...
3
votes
1answer
93 views
How to find the first $k$ points of high enough level using a priority search tree?
In reading Chan's paper,
Closest Point Problems Simplified on a RAM,
the following came up as a sub-problem:
Given a set $P$ of points in the plane, and a query point $q$, find the first $k$ points ...
1
vote
0answers
131 views
Dynamic shortest path data structure for DAG
Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.
I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
12
votes
0answers
175 views
How much independence is required for separate chaining?
If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In "The Power of Simple Tabulation Hashing", Pătraşcu and ...
3
votes
1answer
150 views
Breadth first search and Eppstein K shortest paths algorithm
I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf
I have trouble particularly ...
3
votes
2answers
255 views
Efficient algorithm to find overlapping circles of various sizes
I have a collection of N circles in the plane with various position and radius. Circles move around according to one force and become bound to each other once they overlap.
I need a fast way to ...
4
votes
1answer
211 views
Dynamic Data structure for All nearest smaller values
I need a data structure that stores a sequence of numbers and supports the following operations. The input to each operation includes the position of an item in the current sequence (not the value or ...
8
votes
1answer
248 views
logic in the presence of doubt, uncertainty, lies
I was reading Harry Frankfurt's On Bulls*t, a 1986 philosophical essay about this blurry notion between truth and falsity.
This is not a gratuitous exercise. This may have applications to computer ...
11
votes
4answers
410 views
Shortest number of editing move between two words
I am looking for a data structure and an algorithm to compute the minimum number of changes required to transform one word into another, given the two words as inputs, where the only allowed changes ...
4
votes
1answer
221 views
Multidimensional B+ tree
I've got an idea for indexing multidimensional data. I haven't been able to find anything equivalent and am wondering if it is indeed a novel approach.
The idea is a 'stacked' B+ tree implementation ...
15
votes
2answers
440 views
Exponential Speedup in External Memory
Background
The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses). These running times are generally given in ...
5
votes
1answer
161 views
Revision Tracking Graph
Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it. C(x) contains all edges on all paths from a node 0 ( C(0) = ...
11
votes
1answer
207 views
Minimal elements of a monotonic predicate over the powerset $2^{|n|}$
Consider a monotonic predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking ...
6
votes
1answer
260 views
What is a zipper, and how does it relate to a tree-like structure?
I was reading a chapter in LYAH which didn't really make sense to me. I understand that zippers can arbitrarily traverse a tree-like structure, but I need some clarification on it. Also, can zippers ...
18
votes
1answer
475 views
How close can we get to linear multiply, add, and compare (on integers)?
Accoring to K. W. Regan's article "Connect the Stars", he mentions at the end that it is still an open problem to find a representation of integers such that the addition, multiplication, and ...
0
votes
0answers
118 views
Efficient update of the keys in associative container
I need to maintain a set $\langle(k_1, v_1), (k_2, v_2), \dots, (k_N, v_N)\rangle$ of key-value pairs subject to the following update operation. Given two keys $a < b$ and a "shift" value $C$ as ...
2
votes
1answer
158 views
Does the order of insertion affect the topology of an R-Tree
Say I have 2 permutations of the the same set of elements.
I create 2 R-Trees, one for each permutation.
Do I end up with 2 structurally identical R-Trees or not?
PS: My elements are rectangles on a ...
6
votes
0answers
122 views
Data structures lower bounds on Turing machines
Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ?
I guess that people are mostly interested in models with random access, but ...
21
votes
4answers
1k views
Handbook of advanced data structures
I am looking for a book on advanced data structures that goes beyond what is covered in standard textbooks like Cormen, Leiserson, Rivest, and Stein's "Introduction to Algorithms".
A book that can be ...
4
votes
0answers
98 views
On aB-trees and its practical implementation
I'm reading the paper Succincter by M. Patrascu (link).
It introduces on page 7 the aB-tree. This is a regular B-ary tree that represents an array of values. It stores the element of the array in the ...
3
votes
2answers
149 views
Dynamic and/or practical succinct data structures for triangulations
Does anybody know of any results on succinct data structures for triangulations that can be constructed efficiently, and preferably also updated efficiently?
Does anybody know of practical ...
5
votes
1answer
116 views
Local updates in weight-balanced search trees
In Kurt Mehlhorn's monograph "Data Structures and Algorithms 1: Sorting and Searching", he poses the following question (III.9.22):
Design a balanced tree scheme where the worst case rebalancing ...
0
votes
0answers
154 views
Is there a typo in this paper? [closed]
I'm studying Andrew W. Moore's tutorial on Kd-Trees. On page 6-7 there is a formular (6.6) and I wonder if there is an error in it. Shouldn't there be hri^max in the bottom case?
-2
votes
2answers
467 views
Most efficient algorithm to compute set difference?
What is the most efficient algorithm to compute the difference between two set data structures? In particular, the algorithm should efficiently discover elements in the first set that are also in the ...
3
votes
1answer
279 views
Formal Representation of Haskell Data-Types
I come from Haskell programming and currently writing my (Diploma/Master) thesis. I'm having trouble finding a formal/mathematical notation for a Haskell data-type.
The Haskell data type is:
...
11
votes
0answers
145 views
Minimal rare subgraphs
I am looking for any related work to the following problem. Say you have a large directed graph $G$ and you want to find rare (or unique) subgraphs of minimal size that are not isomorphic to any other ...
2
votes
0answers
181 views
Name this list-of-lists data structure
Is there a canonical name for the following data structure for list of lists?
Suppose we have got a list of length $Z$ of finite lists $[a_0,\dots,a_n], [b_0,\dots,b_m], [c_0,\dots,c_o], \dots$ of ...
6
votes
1answer
245 views
Continuity vs Uniformity when designing Hash functions
Reading available literature (yep, including wikipedia), I see that hash functions should have (continuity) and map values that differ very little to similar/same hash codes, in particular for (hash ...
0
votes
1answer
119 views
Combining multiple time-based datasources with different periods
I have two time-based data sources (one providing data by month and the other by week) that must be combined to create a third daily source (recognizing that at best we're getting one possible ...
10
votes
0answers
259 views
Lock-free, constant update-time concurrent tree data-structures?
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.
I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
1
vote
1answer
251 views
Simple k-nearest-neighbor algorithm for euclidean data with highly variable density?
An elaboration on this question, but with more constraints.
The idea is the same, to find a simple, fast algorithm for k-nearest-neighbors in 2 euclidean dimensions. The bucketing grid seems to work ...
2
votes
0answers
63 views
Load-balancing; Alternate methods of keeping track of nodes?
Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network.
One popular method uses ...
4
votes
3answers
270 views
Is there a name for a hashtable with a tree for each bin instead of a list?
It is well-known that the worst case performance for a chaining hashtable, is O(n), where n is the number of objects in the table. The normal assumption is that the hash is either uniform, or secure, ...
7
votes
0answers
98 views
Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space
A dynamic predecessor data structure supporting findPredecessor, insert, and delete over ...
6
votes
0answers
141 views
Relational model for data structure reasoning
I am trying to find out if there is any work on applying the Codd's relational model (underlying relational databases) for reasoning about linked data structures. Any connections with UML models and ...
6
votes
1answer
352 views
Need a good overview for Succinct Data Structure algorithms
(already asked on main site, but asking also here for better coverage, sorry)
Since I knew about Succinct Data Structures I'm in a desperate need of a good overview of most recent developments in ...
14
votes
1answer
387 views
Bloom filter hashes: more or bigger?
In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions. Kirsch and Mitzenmacher showed that you actually only need two, and can generate the rest as ...
3
votes
0answers
188 views
Efficient synchronization of two instances of an ordered list
What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move ...
6
votes
2answers
197 views
Dynamic Upper Envelope of lines in the plane
There are easy algorithms to calculate the upper envelope of an arrangement of lines in the plane. See e.g. section 2.3 in the survey
Davenport-Schinzel sequences and their geometric applications.
...
