Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
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 ...
15
votes
2answers
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 ...
7
votes
2answers
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 ...
32
votes
4answers
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 ...
20
votes
5answers
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 ...
15
votes
1answer
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 <...
-3
votes
3answers
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 ...
0
votes
1answer
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-...
11
votes
1answer
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 ...
14
votes
1answer
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. (...
4
votes
1answer
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 ...
13
votes
0answers
399 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 \...
34
votes
3answers
1k 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)$? ...
0
votes
3answers
227 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))$? ...
19
votes
2answers
1k 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 ...
27
votes
2answers
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 ...
3
votes
0answers
354 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. ...
8
votes
2answers
756 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)$: ...
11
votes
2answers
361 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)$ ...
4
votes
2answers
771 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)) ...
2
votes
2answers
147 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 ...
3
votes
0answers
389 views

worst case external fragmentation in buddy memory systems

Unfortunately, I can't find any freely available text with an estimation of exact upper bound of (external) fragmentation overhead for (binary) buddy memory allocator. Estimation $M(1+ \log 2 m)$ (...
9
votes
2answers
398 views

Efficient algorithms for searching a collection of trees

I have a large dataset of trees and I would like to search it by specifying a treelet (connected subgraph). The query should return all the occourrences of the treelet in the dataset. Are there ...
10
votes
1answer
225 views

Fingerprinting for dynamic sets

Does there exist a w-bit word-RAM data structure with O(1) time per operation for the following problem?: Maintain a set of w-bit non-negative integers that supports the operations add(x) : add x to ...
2
votes
2answers
146 views

Keyed queues with depth queries and delete

I'm interested in a data structure (let's call it a DMV queue, or DMV for short) over keys (say, strings) with the following operations: empty is a DMV containing no keys. enqueue(q,k) adds the key k ...
10
votes
4answers
759 views

Costs of performing approx. nearest neighbor search in a skip quadtree

NOTE: The question has been restated in my answers: Assuming now that we can find the lowest sibling ancestors in $O(1)$ time, can the ANN be really performed in $O(\log n)$? Quadtrees are efficient ...
-1
votes
1answer
302 views

Amortized Analysis [closed]

I have two questions. My book: "We must ensure that the total amortized cost of a sequence of operations provides an upper bound on the total actual cost of the sequence. This must hold for all ...
8
votes
0answers
105 views

Rank Queries of Uniformly Drawn Order Statistics

Put a uniform distribution on the integers $\{1,\cdots, M\}$. Draw $N$ samples, and sort them as $x_1 \leq \cdots \leq x_N$. A rank query calculates $rank(j) = \mbox{card} \{ i : x_i \leq x_j \}$ for ...
35
votes
6answers
6k views

A probabilistic set with no false positives?

So, Bloom filters are pretty cool -- they are sets that support membership checking with no false negatives, but a small chance of a false positive. Recently though, I've been wanting a "Bloom filter" ...
3
votes
1answer
185 views

Prefix Dictionary Problem in External Memory

I'm interested in an external memory data structure able to support the following operations on variable length binary sequences: (1) Insert such a sequence. (2) Given a query sequence, find the ...
0
votes
1answer
171 views

How do I store data with a query that's a approximated ? [closed]

I'm trying to find a way to store my data with fast access (better than O(n)). My database consists of data (4096 byte strings) that represents some information about some items. The problem is, that ...
2
votes
0answers
303 views

Simple to implement approximate quantile data structure for a stream of integers?

I'm looking for a simple data structure that will let me compute arbitrary approximate quantiles, within a percent or two error, on a stream of 64-bit integers (think of $n$ as being potentially as ...
10
votes
2answers
3k views

Data structure that allow efficient tag based lookups

I am looking for a highly efficient data structure for storage of data similar to the following. Id Tags Order1 Order2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 ...
9
votes
2answers
501 views

Does there exist a data structure for quick list manipulation and order queries?

We have a set, $L$, of lists of elements from the set $N = \{ 1, 2, 3, ..., n \}$. Each element from $N$ appears in a single list in $L$. I am looking for a data structure which can perform the ...
4
votes
1answer
1k views

Given a B-Tree, determine the order keys were inserted

Given a B-tree, determine what order the keys were inserted in. There may be multiple answers: I'd like to generate them all. Is there any known method for this? Or similar problems? Clarification:...
10
votes
6answers
775 views

A data structure for sets of trees.

Tries allow for efficient storage of lists of elements. The prefixes are shared so it is space efficient. I am looking for a similar way to efficiently store trees. I would like to be able to check ...
5
votes
1answer
544 views

Dynamic Tree Marked Ancestor Queries

Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it ...
7
votes
0answers
145 views

Does the cohomological approach to Boolean complexity nicely model any BDD heuristics?

In this question, I learned that complexity theorists had considered using Grothendieck topologies to model Boolean circuits. This has not, apparently, led to any new lower bounds yet, but I'm not so ...
9
votes
1answer
559 views

Deciding if a wildcard string is completely matched by another wildcard string in a set

Here's a problem that has been bugging me for a while. Let's say a string is a sequence of 1s and 0s, and a wildcard string is a sequence of 1, 0, and ?s. All strings and wildcard strings have the ...
17
votes
0answers
280 views

Sequences with sublogarithmic concat and approximate split

Is there a data structure for representing sequences that supports the operations: concat takes two sequences of size $m$ and $n$ and produces a new sequence of size $m+n$ by joining them in time $o(\...
22
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
3answers
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
2
votes
0answers
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 ...
12
votes
0answers
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 ...
14
votes
3answers
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 ...
16
votes
3answers
2k views

Bootstrapping a Finger Tree Structure

After working with 2-3 finger trees for quite a bit I have been impressed by their speed in most operations. However, the one issue I have run into is the large overhead associated with the initial ...
2
votes
0answers
155 views

How can an R+ tree extend its coverage?

In the original article on R+ tree, Algorithm Insert recursively searches for all leaf nodes that overlap the given input rectangle ...