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