# Questions tagged [search-algorithms]

Algorithms for finding an element in some specified data-structure (most commonly, in a tree).

653 questions
Filter by
Sorted by
Tagged with
1 vote
37 views

### A nearest neighbor data structure for meshes

I am trying to find a lightweight data structure to find the nearest neighbor mesh (a mesh being a collection of non-unique triangles) for a given point in R3 (3D Euclidean space). I have seen nearest ...
• 157
1 vote
44 views

### Search algorithm with at most a constant $k$ failed accesses [duplicate]

Let $A$ be an array sorted in non-increasing order. Let $m$ be a natural number. For example, let $m = 10$. We want to find the index $i$ such that $A[:i]$ contain elements less than or equal to $m$, ...
79 views

### Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?

I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y ...
• 101
1 vote
19 views

• 121
1 vote
638 views

### Split the given array into K subsets such that maximum sum of all subsets is minimum

Given an array of $N$ elements, $A$, and a number $K$. ($1 \leq K \leq N$) . Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum ...
1 vote
48 views

### Examples of comparison-based algorithms that are not a sort or a search over lists

Can you share examples of comparison-based algorithms used in practice that are not a sort or a search over lists? Heapify is an example of a comparison-based algorithm that is neither a sort nor a ...
• 283
88 views

### Searching a bitonic array with roughly $2\log n$ comparisons

I don't know how to search a bitonic array with roughly $2\log n$ comparisons in the worst case. What I am trying now is to find the maximum integer using roughly $\log n$ comparisons (binary search) —...
• 141
1 vote
27 views

### Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Let suppose we order the nodes first by degree (in + out), to get a list of node structures: ...
1 vote
74 views

Text: ...
234 views

### True/False: If v is a leaf in every spanning tree resulting from DFS(s), then v is a leaf in every spanning tree resulting from BFS(s)

Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph. True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning ...
28 views

### Data structure for incremental KNN (IKNN) search over high-dimensional vectors

I have a database $D$ of n-dimensional numerical vectors, and I want to do an incremental KNN (IKNN) search over the vectors in $D$. More precisely, given a query vector $v_q \in D$ I need to find $k$ ...
• 111
74 views

### Can A* with an inadmissible heuristic still be optimal?

It is clear to me that if some heuristic $h(x)$ is admissible, then $A^*$ is guaranteed to find a least-cost path. But is it also possible that $A^*$ is optimal if $h(x)$ is not admissible? In other ...
• 21
88 views

### How do search engines implement fuzzy search?

Googling "large horse walks into house" also returns results that contain "large horse in a house" and "the house has large horses". How is Google able to return near-...
• 151
47 views

### In a connected graph, determine all nodes reachable with a "edge-simple" path from node A to node B

I'm asked to write an algorithm which determine all points which appear in a "edge-simple" path connecting node A and node B, i-e a path which doesn't go 2 times in the same edge, but it can ...
220 views

• 11
1 vote
63 views

### Difference Between k-center and k-mean/median

I know that k-mean/median is to find a set $F$ that minimize $$\sum_{i\in C}\min_{j \in F} d(i,j)$$ Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance). ...
40 views

### Using graph symmetries to speed up subgraph enumeration

I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $\text{Aut}(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
1 vote
38 views

### Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash

I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to ...
20 views

### SMA*+: Usefulness of culling heuristics

The paper on SMA*+ proposes a very interesting idea of having a culling heuristic different from the full path cost estimation (so called $f$-cost). In the benchmark they use a culling heuristic equal ...
• 423