# 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.

309 questions
Filter by
Sorted by
Tagged with
403 views

339 views

### Getting started with Hashing for Information retrieval

I recently finished my bachelors and now work on Cross-lingual language search. I want to get started in hashing and see how they are useful in information retrieval. (Yes, I know what hashing is), ...
584 views

### A possibly new representation of DAGs

I had an idea for a way of representing DAGs, it's very easy to explain: Each node in the DAG is given an array of n integers. If it is possible to traverse from A to B then each of B's integers must ...
368 views

### a data structure for partial sequences

We have a set of bit sequences of length $L$ with only $K$ known bits and $L-K$ gaps. We want to store them in a data structure in a way that given a new bit sequence $x$ of length $L$, with $L$ known ...
693 views

### Array slice reversing data-structure

Given an array of $n$ elements, $A[n]$ consider a data-structure which supports the following operations: You are allowed a one time $\mathcal{O}(n)$ preprocessing step: $\text{Init}(A)$ And the ...
103 views

### Does kd-tree search look at more leaves in L1 than in Lmax ?

Dear theorists and experimenters, I find that kd-tree search looks at many more leaves in $L_1$ than in $L_{max}$ ($L_\infty$). Does anyone else see this ? If so, why ? (An $L_1$ simplex of volume 1 ...
1k views

### Lower Bounds for Data Structures

Are results known which rule out the existence of "too-good-to-be-true" data structures? For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz ...
319 views

### Applications of an access lemma for dynamic forests?

Sleator and Tarjan's amortized analysis of splay trees builds on their so-called Access Lemma. For purposes of analysis, assign an arbitrary weight to each node $v$, and let $size(v)$ denote the sum ...
1k views

### Analogs of compressed sensing

In compressed sensing, the goal is to find linear compression schemes for huge input signals that are known to have a sparse representation, so that the input signal can be recovered efficiently from ...
2k views

### Subrange of a Red and Black Tree

While trying to fix a bug in a library, I searched for papers on finding subranges on red and black trees without success. I'm considering a solution using zippers and something similar to the usual ...
365 views

### Functional Sparse-Matrix with good performance?

While writing a Petri Net program, I was faced with a choice about data structures to represent the graph. Adjacency lists (i.e. lists enumerating the arcs into and out of individual places or ...
426 views

### Limits on lock-free collections?

David Rodríguez - dribeas wrote in a comment on StackOverflow that "Not all collections can be implemented without locks". I'm not sure if this is true, and I can't find proof either way. This ...
324 views

### What is the name of this partition-indexed key-value data structure?

Consider a data structure that holds N elements having M partitions each holding N/M elements where M divides N. Each element has a key that satisfies an equivalence relation so as to index into one ...
213 views

### Graph nodes preserving changes to the overall graph

I remember reading about a kind of Graph data structure, where every change to the the graph could be preserved. I don't remember exactly neither the name, neither a good description (if it was the ...
386 views

### Is there a common mathematical symbology for collections?

Preface: So, it was suggested in 'Programmers' that I ask this over here. I am being asked to define several of my algorithms in mathematical terms to describe my work to a customer. I trying to ...
847 views

### Compact representation of DAG,

Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that: ...
448 views

### Searching nodes in semi-splay tree

If you search for a node in a semi-splay tree, it's basically to push certain nodes closer to the root, to reduce future search operations. My course also says that if you search for a node and the ...
751 views

### What is the initialization time of a link-cut tree?

Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two ...
206 views

### Union/find structure implemented by bitvectors

I'm having trouble understanding a concept in my book which is about finding a good structure to represent a union-find datastructure. Here we define a structure -referred to as collection- $V$ as ...
This question is inspired by an existing question about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation. The answer seems to be unknown. Here is a more ...