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

304 questions
590 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 ...
2k 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 ...
286 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 ...
29k 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 ...
420 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 ...
271 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 <...
153 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 ...
73 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-...
199 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 ...
394 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. (...
394 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 ...
399 views

916 views

### Splittable stack

What is known about data structures that can maintain a sequence of items subject to the following two operations? Push(x): add x to the end of the sequence, and return an identifier for its position ...
721 views

### How many ephemeral stacks are required to simulate a queue in worst-case $O(1)$ time?

In "Real Time Queue Operations in Pure LISP" (ML implementation), Hood and Melville show an $O(1)$ worst-case simulation of a queue using 6 stacks and global rebuilding. Can a real-time queue be ...
581 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 ...
366 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 ...
670 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 ...
315 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

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