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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 243
15 votes
1 answer
637 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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 1,317
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
244 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 ...
user avatar
  • 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 ...
user avatar
  • 1,317
0 votes
2 answers
303 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 273
4 votes
2 answers
234 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 ...
user avatar
  • 360
12 votes
6 answers
946 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? ...
user avatar
6 votes
1 answer
394 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 ...
user avatar
  • 3,160
10 votes
2 answers
256 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 ...
user avatar
  • 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 ...
user avatar
  • 4,525
6 votes
3 answers
495 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 ...
user avatar
  • 177
1 vote
1 answer
587 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)...
user avatar
  • 13
9 votes
2 answers
413 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 \}$. ...
user avatar
  • 3,458
-2 votes
1 answer
644 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 ...
user avatar
  • 97
5 votes
2 answers
277 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 1,186
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, ...
user avatar
  • 1,145
-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 ...
user avatar
  • 11
8 votes
1 answer
173 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 ...
user avatar
  • 11k
30 votes
5 answers
3k 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 ...
user avatar
  • 8,651
1 vote
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 ...
user avatar
  • 69
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 ...
user avatar
  • 1,559
2 votes
1 answer
759 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 ...
user avatar
  • 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 ...
user avatar
  • 793
7 votes
2 answers
301 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 ...
user avatar
42 votes
4 answers
39k 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 ...
user avatar
  • 837
20 votes
5 answers
457 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 ...
user avatar
15 votes
1 answer
300 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 <...
user avatar
  • 11k
-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 ...
user avatar
  • 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-...
user avatar
  • 1
12 votes
1 answer
297 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 ...
user avatar
15 votes
2 answers
527 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. (...
user avatar
  • 11k
4 votes
1 answer
466 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 ...
user avatar
  • 143
13 votes
0 answers
405 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 \...
user avatar
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)$? ...
user avatar
  • 443
0 votes
3 answers
233 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))$? ...
user avatar
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 ...
user avatar
  • 1,559
27 votes
2 answers
3k views

I dreamt of a data structure, does it exist?

I haven't managed to find this data structure, but I'm not an expert in the field. The structure implements a set, and is basically an array of comparable elements with an invariant. The invariant is ...
user avatar
  • 653
3 votes
0 answers
359 views

Connected Components over Graph with "colored" edges.

We have an undirected graph $G(V,E)$. Each edge $e \in E$ is associated with a set $C_{e}\neq \emptyset$ of colors, $C_{e} \subseteq C$. The problem is to find all the colored connected components. ...
user avatar
8 votes
2 answers
799 views

Finding a subset of a set in a collection of sets

What data structures would you recommend that represent a collections of subsets of $\{1, \dots, n\}$ and support the following operations? $insert(S)$: inserts $S$ in the collection. $query(S)$: ...
user avatar
11 votes
2 answers
398 views

Set data structure for efficient repeated insertions

I'm looking for a space-efficient data structure that holds sets (no repetition) of wordsize elements and supports fast insertion (amortized O(1)). By "space-efficient" I mean, ideally, $n + o(n)$ ...
user avatar
  • 1,493
4 votes
2 answers
863 views

Encoding of binary trees as a regular language?

There are many ways of representing binary trees as strings. For example, I could encode a tree as either nil or a pair of trees, such as (nil, ((nil, nil), nil)) ...
user avatar
2 votes
2 answers
152 views

Maintaining multiple field dynamic values

This question is posted on behalf of my friend, who is a networks engineer handling massive data (so not a toy problem). He needs to maintain a lookup/insertion/deletion structure storing nodes with ...
user avatar
  • 729

1
3 4
5
6 7