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.

Filter by
Sorted by
Tagged with
15
votes
2answers
1k views

Notable examples of the square root idea in complexity analysis

There are a number of algorithms and data structures which exploit the idea that $\max \left\{k, n/k\right\}$ gets its minimum value at $k=\sqrt n$. Common examples include baby-step giant-step ...
6
votes
1answer
244 views

Self-referentially defined graph structures

It is possible to define graphs $G$ such that whether an edge exists between two vertices $v_1$ and $v_2$ depends on non-local properties of $G$. In particular, I am interested in directed graphs ...
5
votes
1answer
1k views

Trees that structure partially ordered data

Suppose we have a binary search tree $T$ built over keys from a totally ordered set, and we want to support the standard dictionary lookup $\mbox{Find}(x)$ which returns a pointer to the node ...
0
votes
2answers
298 views

Is it possible to convert any tree to a B-tree or an R-tree?

I have a tree structure representing sentences. My tree's nodes are characterized by a type (sentence, phrase, or word), unique ID, text value and an arbitrary number of features. Each node has an ...
3
votes
0answers
211 views

Optimal term frequency analysis

I'm looking for a term-frequency analysis structure which is more efficient than a hash table in terms of worst-case performance and speed in practice. I specifically care about the operations insert ...
20
votes
4answers
3k views

Data Structure isomorphisms

Disclaimer: I am not a CS theorist. Coming from abstract algebra, I'm used to dealing with things that are equal up to a isomorphism - but I'm having a trouble translating this concept to data ...
17
votes
3answers
5k views

Merging Two Binary Search Trees

I'm looking for an algorithm to merge two binary search trees of arbitrary size and range. The obvious way I would go about implementing this would be to find entire subtrees whose range can fit into ...
4
votes
2answers
228 views

an efficient algorithm for mismatch profile

We have M=10000 binary sequences of length N=1000. given length L=15, for each pair of sequences, $S_1$ and $S_2$, we define the mismatch profile, mp($S_1$,$S_2$,$L$)[$m$], for m=0,1,...,L as ...
12
votes
6answers
852 views

Computing the approximate population of a bloom filter

Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set. Is it possible to approximate the number of elements inserted into the bloom filter? ...
6
votes
1answer
379 views

Updates on a cache-oblivious B-tree

Lately I have been studying cache-oblivious data structures and algorithms. I was reading about the cache-oblivious B-tree from the Handbook of Data Structures and Applications, with hopes of actually ...
10
votes
2answers
235 views

Tradeoff Bounds for Halfspace Range Counting

What is the current best bound for performing halfspace range counting queries on a set of $d$-dimensional points, expressed in the form of a time/space tradeoff. According to Matousek's seminal 1993 ...
10
votes
3answers
2k views

Find Shortest Pairwise Distance of Points in o(n log n)?

The following exercise has been handed out to students I supervise: Given $n$ points in the plane, devise an algorithm that finds a pair of points which distance is minimal among all pairs of ...
6
votes
3answers
490 views

How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts?

I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring ...
1
vote
1answer
569 views

Remove specific edge from ST (link-cut) tree

ST (or link cut) trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time: CUT(v) Deletes the edge from v to its parent JOIN(v, w)...
9
votes
2answers
407 views

A subset lookup algorithm

Suppose I have a list $\cal X$ of subsets of $\{1, ..., n\}$. I can do preprocessing on this list if necessary. After this preprocessing, I am presented with another set $A \subseteq \{1, ..., n \}$. ...
-2
votes
1answer
615 views

Fortunes Algorithm - Beach Line Data Structure [closed]

This is a cross-post from stackoverflow. I did not recieve a good answer, I guess it is because the question is more theoretical. I have to implement Fortunes algorithm for constructing Voronoi ...
5
votes
2answers
275 views

Self-organizing Sequential Search Heuristics

I've read the paper by Jon L. Bentley "Amortized analyses of self-organizing sequential search heuristics". It deals with different schemes for improving linear search. (such as after every access to ...
1
vote
0answers
103 views

What effect would using different types of orders have on a binary search tree?

Recently, I was coding a comparator function for use in a set backed by a binary search tree, and the set kept saying that it didn't contain elements that I had previously added to it. I eventually ...
6
votes
1answer
342 views

Non-trivial applications of Bloom filters

Does anyone have some nice examples of modifying algorithms that employ a set data structure to instead employ a Bloom filter? In other words, the damage done by the Bloom filter's false positive ...
3
votes
3answers
1k views

parallelizable fast matrix in-place transposition

what is the current state of the art in fast and parallel matrix in-place transposition? I would be very happy, if I could be given some pseudocode for this problem. As far as I could find papers, ...
-3
votes
1answer
6k views

unique binary tree from preorder and postorder traversals of a full binary tree [closed]

If we have a preorder and postorder traversals of a full binary tree T(i.e every internal node have exactly 2 children). can we uniquely construct the corresponding full binary tree T. If so.. could ...
8
votes
1answer
170 views

Dynamic planar exact k-nearest neighbors for pathological data

What are the best known results for a data structure offering the following operations on sets of points in 2-dimensional euclidean space: $insert(x)$ $delete(x)$ $nearest(k,x)$ (where $k$ is an ...
30
votes
5answers
3k views

Binary search generalizations for posets?

Suppose I have a poset "S" and a monotonic predicate "P" on S. I want to find one or all maximal elements of S satisfying P. EDIT: I'm interested in minimizing the number of evaluations of P. What ...
1
vote
2answers
2k views

Where can I find a copy of Guy Jacobson's thesis “Succinct Static Data Structures”?

I'm looking for a copy of Guy Jacobson's PhD thesis: http://dl.acm.org/citation.cfm?id=915547 but I couldn't find it so far. Does anybody know where can I access it ? I really need it. Thanks in ...
19
votes
2answers
2k views

Data structure for shortest paths

Let $G$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Is it possible to preprocess $G$ and produce a data structure of size $m \cdot \mathrm{polylog}(n)$ so that it can answer ...
2
votes
1answer
705 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 ...
17
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
290 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 ...
40
votes
4answers
35k 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
447 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
299 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
154 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
75 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-...
12
votes
1answer
263 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 ...
15
votes
2answers
500 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
443 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
404 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
2k 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
230 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
355 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
791 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
392 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
831 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
148 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 ...
4
votes
0answers
451 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
422 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
251 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
155 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 ...

1
3 4
5
6 7