Properties and applications of data structures, such as space lower bounds, or time complexity of insertion and deletion of objects.

learn more… | top users | synonyms (2)

0
votes
0answers
27 views

Sparse matrix-vector multiplication materials needed

I've been assigned a project at school, the theme is the influence on cache memory when doing sparse matrix-vector multiplications. I've been searching for materials for quite some time but all I can ...
2
votes
1answer
62 views

Concurrent data structures vs. Distributed data structures

In the context of multi-processor/multi-threaded systems, there are plenty of well-studied concurrent data structures, including stacks, queues, linked lists, etc. Here is an excellent survey on ...
-2
votes
0answers
37 views

Data structures in Clauset-Newman-Moore algorithm for finding community structure in networks?

I am trying to implement the Clauset-Newman-Moore algorithm for discovering community structure in python. The paper describing the algorithm is in the comments because I cannot post more than 2 links ...
3
votes
1answer
167 views

Does a universal index exist?

Given a data table containing a very large number $N$ of rows, with each row containing a large number $k$ of fields, with each field containing a large but fixed number of bits, there are a number of ...
3
votes
2answers
103 views

Isomorphism between algebraic data-types

I have two types of trees in Haskell, defined as the least solution of the following equations: $T_1(A) \cong 1 + A + T_1(A) \times T_1(A)$ $T_2(A) \cong 1 + A \times T_2(A) + T_2(A) \times T_2(A)$ ...
-1
votes
0answers
27 views

Trees, and how to organize data and answer queries efficiently

Suppose there exists a set $X$, containing zero or more elements of some type, and we'd like to run a query, as efficiently as possible. For many interesting queries - value associated with a key, ...
3
votes
1answer
121 views

Number of bits required for encoding variables with fixed sum?

Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$ It's easy to store the variables using ...
3
votes
2answers
85 views

Minimal encoding of a set (unordered collection of elements)?

Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$. If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are ...
1
vote
1answer
52 views

Are there published algorithms for on-line creation of AVL trees from ordered streams?

Given an ordered stream of n items (n unknown in advance), it is well-known how to construct a red-black tree from them in O(n)-time. More specifically this is possible using only O(log n) additional ...
1
vote
1answer
46 views

Lower bounds on simple hash table operations?

There are a variety of hash tables that support worst-case O(1)-time lookups and deletions and expected O(1)-time lookups. Is there a known lower-bound on hashing that says that there cannot be a hash ...
4
votes
0answers
67 views

Why is it necessary to maintain a collection of forests in the dynamic graph data structure?

In their paper "Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity", Holm, de Lichtenberg, and Thorup describe a data structure ...
5
votes
2answers
310 views

Would a purely topological computational model be useful in decision problems in topology?

If one were to develop a purely topological computational model based upon the equivalence of information in knots and the model would perform transformations of that information. This would be the ...
1
vote
1answer
81 views

Why does the construction step of Aho-Corasick take linear time in the number of nodes?

The original paper's analysis of this, as far as I can tell is this: "THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords. PROOF. Straightforward." ...
1
vote
0answers
45 views

What should I read to learn about the different models of computation used in algorithm and especially data structure analysis?

Are there any good surveys? Courses? Lecture notes? I'm especially interested in material with practice exercises, if any is available. Thanks!
1
vote
1answer
87 views

Asymmetry in converting Burrows-Wheeler transform to suffix array?

Given a suffix array of a string $w$, it's possible to construct the Burrows-Wheeler transform of $w$ by subtracting one from the indices of the suffix array (wrapping around if necessary), then ...
4
votes
2answers
161 views

Shortest distance/path between two households

If you wanted to know the shortest distance/path between two household addresses, which data structure(s) would you use to return the answer efficiently? Say you are considering the set of all ...
4
votes
0answers
68 views

Splay tree potential function: why sum the logs of the sizes?

I'm teaching a course on data structures and will be covering splay trees early next week. I've read the paper on splay trees many times and am familiar with the analysis and intuition behind the data ...
1
vote
0answers
36 views

What can be done with unsorted binary trees

Where can I find work on self-balancing unsorted binary trees? (ie using binary trees as a substitute for lists or arrays?)
1
vote
0answers
56 views

What are some examples where the Catalan numbers show up in algorithms/data structures?

For some variants of RMQ data structures, the number of Cartesian trees (i.e. the Catalan numbers) is a part of the running-time analysis. What are some other examples where the Cataln numbers show up ...
15
votes
2answers
1k views

Is the traditional analysis of Bloom filters wrong?

This paper claims that the traditional analysis of the error rate in Bloom filters is incorrect, then provides a lengthy and nontrivial analysis of the actual error rate. The linked paper was ...
4
votes
1answer
151 views

Heap with $O(1)$ delete-key

Fibonacci heaps have $O(1)$ insertion and $O(\log n)$ delete-min and delete-key (under amortized complexity). Is there a heap data structure with $O(1)$ insertion and delete-key and $O(\log n)$ ...
20
votes
3answers
1k views

Nontrivial algorithm for computing a sliding window median

I need to calculate the running median: Input: $n$, $k$, vector $(x_1, x_2, \dotsc, x_n)$. Output: vector $(y_1, y_2, \dotsc, y_{n-k+1})$, where $y_i$ is the median of $(x_i, x_{i+1}, \dotsc, ...
4
votes
0answers
40 views

Has there been any work done on incremental connectivity in path graphs?

This set of lecture notes describes a data structure for decremental connectivity in path graphs that supports queries and removals in amortized O(1) each. Has there been any work done on incremental ...
5
votes
0answers
149 views

Data structures for Finite Automata

I am a Control Engineer and I have been working on Discrete Event Systems and Supervisory Control, based on Finite Automata Theory. My problem is to represent large automata (about $2 \times 10^6$ ...
-3
votes
1answer
141 views

Isn't weakly universal hashing even a stronger than truly random? [closed]

So as far as I know the weakly universal hashing is defined as: for any $x, y \subset U, Pr(h(x) = h(y)) \le \frac{1}{m}$ where m is a smaller number than the cardinality of $U$, and h are chosen ...
1
vote
0answers
83 views

Binary Search Tree DELETE survey

In helping out @bapi-chatterjee on a BST question , when it came to teasing out the combinatorics of BST_DELETE(i) I ran into a wall where even under the conservative assumption that the parent tree ...
2
votes
0answers
96 views

Height of randomly built binary search tree by insert and delete?

In Introduction to algorithm (CLRS), even in its third edition (published in 2009) it is noted in Sec 12.4 that little is known about height of randomly built binary search tree using insert and ...
3
votes
1answer
140 views

Algorithm to Bulk Delete nodes from a Treap

I have a Treap, and want to bulk delete nodes in a given key range (i.e. the nodes to be deleted are consecutive nodes in an in-order walk of the tree). If I have $n$ nodes in the Treap, and $k$ nodes ...
1
vote
0answers
44 views

Atomic snapshot algorithms on tree-structured shared registers

Background: Atomic snapshot memory is a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (*scanned) in its entirety. The Gang of Six algorithm ...
7
votes
2answers
257 views

Testing boolean vectors orthogonality with fast query-time

Consider the following problems, Problem1: INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$ TASK: preprocess INPUT in such a ...
4
votes
1answer
133 views

Deterministic dynamic dictionary on a small universe

We want to maintain a dictionary of $m$ elements with insert/delete and lookup in the word RAM model. Assume $m=O(n)$ at all times, so there can't be too many inserts without deletions. The universe ...
5
votes
0answers
77 views

Dynamic 2-dimensional orthogonal range reporting in external memory and linear space

Orthogonal 2-dimensional range reporting is the problem of storing a set of values from $U \times V$, where $U$ and $V$ are totally ordered universes, subject to queries of the form "Return all stored ...
4
votes
0answers
92 views

Concurrent algorithm for strongly connected components (SCCs)

Is anybody aware of a concurrent version of Tarjan's SCCs algorithm, Kosaraju's algorithm or any other fast, O(|V| + |E|) algorithm for finding SCCs? Neither of those algorithms seem to be very hard ...
5
votes
0answers
104 views

Maintain mex with efficient union

Do you know of any data structure $S[A]$, that maintains a (finite) set $A \subset \mathbb{Z}_{\geq0}$ of non-negative integers, subject to the following operations: Given $S[A],$ calculate minimal ...
2
votes
1answer
104 views

Why isn't the decrease key operation in a pairing heap $O(1)$

According to the paper (1986) Decrease-key is implemented by first by removing the node from the tree $O(1)$, decreasing the key $O(1)$, then linking it with the root node $O(1)$. The paper admits ...
1
vote
3answers
310 views

Is there an array structure that allows for O(1) complexity for reverse, zip, slice etc operations?

Many operations on arrays have $O(n)$ complexity. If we represent arrays as accessors methods, many of them could be done in $O(1)$. For example, the $i$th item in the reverse of an array $A$ of ...
11
votes
1answer
121 views

Integer priority queue with distribution-sensitive deleteMin

Is there in an integer priority queue that uses $O(n)$ words of space with the following operations, all in worst-case time and without access to randomness: ...
9
votes
2answers
348 views

Select two numbers that sum to $p$, using sub-linear query time

Here is a nearest neighbor problem. Given reals $a_1, \ldots, a_n$ (very large $n$!), plus target real $p$, find $a_i$ and $a_j$ whose SUM is closest to $p$. We allow reasonable ...
2
votes
1answer
99 views

Bloom filter for predecessor queries?

Given a threshold $k$ is it possible to make a succinct data structure $S$ to answer queries of the form, given query $x$ does there exist a value $s$ in $S$ such that $s-k \leq x \leq s+k$? Like a ...
7
votes
1answer
195 views

Can we perform an n-d range search over an arbitrary box without resorting to simplex methods?

Suppose I have some set of points in d-dimensional space, each with some mass. Our problem size will be the number of points in this set. After some roughly (within polylog factors) linear ...
-2
votes
1answer
267 views

Find all items which are subsets of an item

I have a problem that I think should have been studied. I am looking for algorithms for it. Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items. Each key and each ...
2
votes
1answer
519 views

Search for all nearest neighbors within a certain radius of a point in 3D?

I have about 80 million spatial points(3D) and I want to find all the nearest neighbors of a query point which lie under a sphere of a certain radius(can be given as input) with the query point as ...
1
vote
0answers
82 views

Linear time algorithm for computing the labels of leaves in a recursively defined tree [closed]

The original copy of the question on MSE. Let $S=(s_0, ..., s_{N-1})$ be a sequence of $N=2^p$ numbers. We consider a labelled binary tree of height $p$ as follows: The root has label $S$, for each ...
3
votes
1answer
55 views

Persistant bag/set with direct access to known elements

I'm looking for a bag or set data structure that will allow for the following operations: Add an element to the set, and get a "pointer" to that element. ...
8
votes
1answer
178 views

Storing a bit vector in uninitialized memory and minimal space

A well-known trick for storing bit vectors using uninitialized memory can allocate a bit vector of size $n$ in which all of the bits are set to $0$ by allocating $(2 n + 1)\lceil \lg n \rceil$ bits of ...
4
votes
1answer
390 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
74 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
388 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.
19
votes
1answer
396 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
136 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 ...