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

327 questions
Filter by
Sorted by
Tagged with
51 views

### How to build the tree with the "most different" solutions of a clustering?

Illustrate the question with an example : we have a similarity matrix for 1000 people, and the similarity represents how much their hobbies are the same (it does not really matter how it's built). Let'...
234 views

### Sublinear Time Regular Expression Search

Does there exist a data structure with the following properties. Given a string $s$, it performs some polynomial amount of precomputation to construct the data structure. After construction, it allows ...
171 views

39 views

### Practical worst-case polylogarithmic dynamic orthogonal range queries?

There are a number of data structures in the literature that solve the dynamic orthogonal range search problem in polylogarithmic time (say, range trees). My understanding is that these structures ...
44 views

### Unique fixed-length substrings

Input: A single long string (<10MB) and a number k Definition: A unique k-substring is a substring of length k, which occurs exactly once in the input document. Output (Approach 1): Either print ...
314 views

### Is there a simple, intuitive explanation for why trees in Fibonacci heaps have the sizes they do?

Fibonacci heaps have a simple rule that ensures its tree sizes grow exponentially with their ranks: A node can lose at most one child. Once that child is lost, the node must be cut from its parent. ...
85 views

### Optimal point placement on integer lattice

What is known about the following point placement problem? For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute \begin{eqnarray*} \mu_1(N,n)\triangleq\min_{\mathcal{P}\...
503 views

### Time Complexity for Nearest Neighbor Searches in kd-trees

Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof. In order to calculate the average number of ...
111 views

### Data structures for embedded simplicial complexes

I am looking for a data structure to encode an $n$-dimensional simplicial complex with an embedding in $\mathbb{R}^{n+1}$. I am aware of combinatorial maps, which generalize rotation systems of planar ...
100 views

### Lower bounds for list/set data structures without delete

I'm interested in lower bounds on the amortized time cost for either of the following dynamic data structure problems, in the cell probe or RAM model, or any model that lets us do operations on words ...
64 views

### Data structure for getting all matches of a prefix from a large list of strings [closed]

Suppose I have a very long list of strings (millions of them), ordered by importance. For example: ... barracudas oftwalj velasp offso skenep vitriolic offscre ... ...
44 views

### Updating set of lists dependent upon a few indices

I'm curious about a data structure for a set of "valid lists", where you have a set of lists of length $i$ $S_i$, have a list $L$ of possible items to append, and a boolean function $f$, and wish to ...
73 views

### Data structure to report points in the intersection of two circles

The circular range reporting is defined as follow: preprocess $n$ points in the plane so that the points inside a query circle, of any radius, can be reported quickly. This was solved beautifully ...
341 views

### A dynamic data structure to list triangles

Consider an undirected graph with $n$ nodes. Is there an efficient data structure that supports the following operations? Insert an edge into the graph Delete an edge from the graph Given a query ...
243 views

### Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?

I'm following course material from the course Advanced Data Structures. The result by Driscoll et al 1989 states the following (wording of the following theorem taken from lec notes, page 4, which ...
31 views

### Splay trees as dynamic weight-balanced trees?

Given a collection of keys $x_1 < x_2 < \dots < x_n$ with associated weights $w_1, w_2, \dots, w_n$, a weight-balanced tree for the keys $x_i$ with weights $w_i$ is defined as follows: The ...
143 views

### Simple proof that splay trees have the dynamic finger property?

Splay trees are conjectured to be dynamically optimal, and they're known to have a number of nice properties, including the dynamic finger property, which says that the amortized cost of an access in ...
836 views

### Can three stacks be implemented in one array, with O(1) push/pop time?

Two stacks can be efficiently implemented using one fixed sized array: stack #1 starts from the left end and grows to the right, and stack #2 starts from the right end and grows to the left. Is the ...
99 views

### What degree of hash function independence is needed for Bloom filters?

In the traditional analysis of Bloom filters, it's assumed that the hash functions are truly random functions, meaning that each hash function distributes each key uniformly and independently of each ...
Assume points are always in general position. For a set of $n$ points $S$ on the plane, a radial ordering with respect to $x\in S$ is a total ordering of the elements in $S-x$. Consider shooting an ...