Questions tagged [ds.data-structures]
Properties and applications of data structures, such as space lower bounds, or time complexity of insertion and deletion of objects.
339
questions
13
votes
0
answers
532
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)$ ...
- 566
1
vote
1
answer
892
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 ...
- 161
3
votes
0
answers
75
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 virtual-...
- 131
4
votes
3
answers
296
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, ...
- 258
7
votes
1
answer
212
views
Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space
A dynamic predecessor data structure supporting findPredecessor, insert, and delete over ...
- 11.1k
7
votes
0
answers
227
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 ...
- 4,776
14
votes
1
answer
4k
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 ...
- 243
15
votes
1
answer
638
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 ...
- 303
8
votes
2
answers
3k
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 ...
- 181
8
votes
2
answers
1k
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.
...
- 1,327
15
votes
2
answers
1k
views
Notable examples of the square root idea in complexity analysis
There are a number of algorithms and data structures which exploit the idea that $\max \left\{k, n/k\right\}$ gets its minimum value at $k=\sqrt n$. Common examples include
baby-step giant-step ...
6
votes
1
answer
250
views
Self-referentially defined graph structures
It is possible to define graphs $G$ such that whether an edge exists between two vertices $v_1$ and $v_2$ depends on non-local properties of $G$.
In particular, I am interested in directed graphs ...
- 61
5
votes
1
answer
1k
views
Trees that structure partially ordered data
Suppose we have a binary search tree $T$ built over keys from a totally ordered set, and we want to support the standard dictionary lookup $\mbox{Find}(x)$ which returns a pointer to the node ...
- 1,327
0
votes
2
answers
310
views
Is it possible to convert any tree to a B-tree or an R-tree?
I have a tree structure representing sentences. My tree's nodes are characterized by a type (sentence, phrase, or word), unique ID, text value and an arbitrary number of features. Each node has an ...
- 109
3
votes
0
answers
212
views
Optimal term frequency analysis
I'm looking for a term-frequency analysis structure which is more efficient than a hash table in terms of worst-case performance and speed in practice. I specifically care about the operations insert ...
- 566
20
votes
4
answers
3k
views
Data Structure isomorphisms
Disclaimer: I am not a CS theorist.
Coming from abstract algebra, I'm used to dealing with things that are equal up to a isomorphism - but I'm having a trouble translating this concept to data ...
- 203
17
votes
3
answers
5k
views
Merging Two Binary Search Trees
I'm looking for an algorithm to merge two binary search trees of arbitrary size and range. The obvious way I would go about implementing this would be to find entire subtrees whose range can fit into ...
- 273
4
votes
2
answers
236
views
an efficient algorithm for mismatch profile
We have M=10000 binary sequences of length N=1000.
given length L=15, for each pair of sequences, $S_1$ and $S_2$, we define the mismatch profile, mp($S_1$,$S_2$,$L$)[$m$], for m=0,1,...,L as ...
- 360
12
votes
6
answers
989
views
Computing the approximate population of a bloom filter
Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set.
Is it possible to approximate the number of elements inserted into the bloom filter?
...
- 221
6
votes
1
answer
400
views
Updates on a cache-oblivious B-tree
Lately I have been studying cache-oblivious data structures and algorithms. I was reading about the cache-oblivious B-tree from the Handbook of Data Structures and Applications, with hopes of actually ...
- 3,160
10
votes
2
answers
264
views
Tradeoff Bounds for Halfspace Range Counting
What is the current best bound for performing halfspace range counting queries on a set of $d$-dimensional points, expressed in the form of a time/space tradeoff. According to Matousek's seminal 1993 ...
- 103
10
votes
3
answers
2k
views
Find Shortest Pairwise Distance of Points in o(n log n)?
The following exercise has been handed out to students I supervise:
Given $n$ points in the plane, devise an algorithm that finds a pair of points which distance is minimal among all pairs of ...
- 4,535
6
votes
3
answers
496
views
How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts?
I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring ...
- 177
1
vote
1
answer
598
views
Remove specific edge from ST (link-cut) tree
ST (or link cut) trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time:
CUT(v) Deletes the edge from v to its parent
JOIN(v, w)...
- 13
9
votes
2
answers
416
views
A subset lookup algorithm
Suppose I have a list $\cal X$ of subsets of $\{1, ..., n\}$. I can do preprocessing on this list if necessary. After this preprocessing, I am presented with another set $A \subseteq \{1, ..., n \}$. ...
- 3,478
-2
votes
1
answer
647
views
Fortunes Algorithm - Beach Line Data Structure [closed]
This is a cross-post from stackoverflow. I did not recieve a good answer, I guess it is because the question is more theoretical.
I have to implement Fortunes algorithm for constructing Voronoi ...
- 97
5
votes
2
answers
278
views
Self-organizing Sequential Search Heuristics
I've read the paper by Jon L. Bentley "Amortized analyses of self-organizing sequential search heuristics". It deals with different schemes for improving linear search. (such as after every access to ...
- 595
1
vote
0
answers
103
views
What effect would using different types of orders have on a binary search tree?
Recently, I was coding a comparator function for use in a set backed by a binary search tree, and the set kept saying that it didn't contain elements that I had previously added to it. I eventually ...
- 111
6
votes
1
answer
345
views
Non-trivial applications of Bloom filters
Does anyone have some nice examples of modifying algorithms that employ a set data structure to instead employ a Bloom filter? In other words, the damage done by the Bloom filter's false positive ...
- 1,196
3
votes
3
answers
1k
views
parallelizable fast matrix in-place transposition
what is the current state of the art in fast and parallel matrix in-place transposition?
I would be very happy, if I could be given some pseudocode for this problem. As far as I could find papers, ...
- 1,155
-3
votes
1
answer
6k
views
unique binary tree from preorder and postorder traversals of a full binary tree [closed]
If we have a preorder and postorder traversals of a full binary tree T(i.e every internal node have exactly 2 children). can we uniquely construct the corresponding full binary tree T.
If so.. could ...
- 11
8
votes
1
answer
179
views
Dynamic planar exact k-nearest neighbors for pathological data
What are the best known results for a data structure offering the following operations on sets of points in 2-dimensional euclidean space:
$insert(x)$
$delete(x)$
$nearest(k,x)$ (where $k$ is an ...
- 11.1k
30
votes
5
answers
4k
views
Binary search generalizations for posets?
Suppose I have a poset "S" and a monotonic predicate "P" on S.
I want to find one or all maximal elements of S satisfying P.
EDIT: I'm interested in minimizing the number of evaluations of P.
What ...
- 8,721
2
votes
2
answers
2k
views
Where can I find a copy of Guy Jacobson's thesis "Succinct Static Data Structures"?
I'm looking for a copy of Guy Jacobson's PhD thesis: http://dl.acm.org/citation.cfm?id=915547 but I couldn't find it so far. Does anybody know where can I access it ? I really need it.
Thanks in ...
- 79
20
votes
2
answers
2k
views
Data structure for shortest paths
Let $G$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Is it possible to preprocess $G$ and produce a data structure of size $m \cdot \mathrm{polylog}(n)$ so that it can answer ...
- 1,559
2
votes
1
answer
814
views
What data structures exist for fast calculation of distances between multi-dimensional points
I'm writing a program that receives data over a network connection. Every data point is simply a 4 dimensional vertex, lets call the dimensions X,Y,Z,W. The values of each dimension are exponentially ...
- 123
18
votes
2
answers
3k
views
What persistent data structure for a set of partially ordered elements?
I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable.
One problem with hashtables is that two equal ...
- 803
7
votes
2
answers
338
views
Rearranging strings to minimise storage in a trie
I'm currently thinking about the following problem.
Problem
Input: a set $W$ of strings over an alphabet $\Sigma$.
Goal: permute the characters in each string so that the trie that will contain the ...
- 3,254
44
votes
4
answers
41k
views
Why would one ever use an Octree over a KD-tree?
I have some experience in scientific computing, and have extensively used kd-trees for BSP (binary space partitioning) applications. I have recently become rather more familiar with octrees, a similar ...
- 857
20
votes
5
answers
460
views
Reducing space usage of st-connectivity with multiple passes?
Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream.
Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar
Rajagopalan ...
- 18.8k
15
votes
1
answer
302
views
Maintaining order in a list in $AC^0$ in $O(1)$ time
The order maintenance problem (or "maintaining order in a list") is to support the operations:
singleton: creates a list with one item, returns a pointer to it
<...
- 11.1k
-3
votes
3
answers
158
views
Working with all leaves on a certain level of a b-tree
I want to work with a b-tree of any size. I want to do something with all leaves of the lowest depth $d$. Then if a certain condition holds, I want to recursively consider the same condition for the ...
- 101
0
votes
1
answer
76
views
How to automatically generate indexes and preaggregations from queries
This question might be a little ill-specified, but the idea I want to explore is:
User writes a bunch of queries that they want to perform over some data (for concreteness, just consider it a read-...
- 1
12
votes
1
answer
316
views
Optimal preprocessing for certain types of queries
Suppose we have a semigroup $(S,\circ)$ with elements $S=\lbrace s_1,s_2,\dots,s_n\rbrace$. Our goal is to compute products $s_i\circ s_{i+1}\circ \cdots\circ s_j$.
In their paper "Optimal ...
- 221
15
votes
2
answers
543
views
Reusing 5-independent hash functions for linear probing
In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. (...
- 11.1k
4
votes
1
answer
505
views
Does kd tree requires triangular inequality for finding k-nearest neighbors
I have 3-dimensional data I want to store in a kd-tree. Additionally I have a domain-specific distance function in this space for which I have a hard time to prove the triangular inequality. Here is ...
- 143
13
votes
0
answers
408
views
Exact nearest neighbor in $d$-dimensional Euclidean space
Suppose that we have $n$ points in $d$-dimensional Euclidean space $\mathbb{R}^d$. We wish to solve the standard exact nearest neighbor problem: build a data structure such that on any query $q\in \...
- 181
34
votes
3
answers
2k
views
Comparison-based data structure for finding items
Is there a data structure that takes an unordered array of $n$ items, performs preprocessing in $O(n)$ and answers queries: is there some element $x$ on the list, each query in worst time $O(\log n)$?
...
- 443
0
votes
3
answers
234
views
Joining lists with some common elements in average case
What are some ways of commutatively combining a pair of lists to produce a list comprised of elements from the pair of inputs, with no duplicates, with time complexity better than $O(n \log(n))$? ...
19
votes
2
answers
2k
views
A data structure for minimum dot product queries
Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of ...
- 1,559