Interactive graph search (IGS) has emerged as a powerful paradigm for information retrieval across diverse applications. The goal of IGS is to identify the most appropriate (i.e., deepest) node within a hierarchy for an unknown object, typically leveraging human intelligence such as crowdsourcing as the oracle. Existing IGS algorithms usually rely on reachability queries, such as "is the target node reachable from node x ?", and assume that correct answers are always available. However, in practice, answering such queries is challenging due to the requirement for domain-specific knowledge, resulting in frequent errors in the oracle's responses. As a consequence, the reachability-query-based approaches would perform poorly. In this paper, we propose a practical solution to the IGS problem, leveraging the power of large language models (LLMs) to tackle the issue of reachability queries. Specifically, we formally analyze the inherent properties of real-world hierarchies with the notion of ambiguous nodes and overlapping nodes to debunk the difficulty of reachability queries. In addition, we develop a practical oracle based on LLMs that can answer reachability queries on (near) leaf nodes accurately. Building on the LLM oracle, we propose a similarity-based upward search algorithm, namely SuS, to address the IGS problem. We further enhance SuS with layer-wise search and fast initialization techniques. We evaluate SuS on two real-world datasets against four baseline methods, and the experimental results clearly demonstrate the superiority of our solution.

Proximity graph-based methods have emerged as a leading paradigm for approximate nearest neighbor (ANN) search in the system community. This paper presents fresh insights into the theoretical foundation of these methods. We describe an algorithm to build a proximity graph for (1+ε)-ANN search that has O((1/ε) λ • n log Δ) edges and guarantees (1/ε) λ • polylog Δ query time. Here, n and Δ are the size and aspect ratio of the data input, respectively, and λ = O(1) is the doubling dimension of the underlying metric space. Our construction time is near-linear to n , improving the Ω(n 2 ) bounds of all previous constructions. We complement our algorithm with lower bounds revealing an inherent limitation of proximity graphs: the number of edges needs to be at least Ω((1/ε) λ • n + n log Δ) in the worst case, up to a subpolynomial factor. The hard inputs used in our lower-bound arguments are non-geometric, thus prompting the question of whether improvement is possible in the Euclidean space (a key subclass of metric spaces). We provide an affirmative answer by using geometry to reduce the graph size to O((1/ε) λ • n) while preserving nearly the same query and construction time.

Interactive graph search (IGS) has proven to be a useful information retrieval paradigm in a diverse set of applications. Robust IGS algorithms are notoriously difficult to design because they are deeply rooted in graph theory. The current state-of-the-art algorithms either fail to achieve an optimal number of interaction rounds or rely on interfaces demanding tedious user inputs. Furthermore, previous research has paid little attention to the underlying computation bottleneck, which is currently dealt with using primitive implementations. This work remedies the above issues altogether. Utilizing novel findings on the problem characteristics, we develop an algorithmic framework for IGS that requires a designer to fill in the details for only two ''black-box'' operations. Our framework, when instantiated with surprisingly simple black-box implementations, yields optimal algorithms not only in all the scenarios explored before but also in new scenarios never studied. We accompany our framework, designed to minimize interaction rounds, with a new algorithm designed to reduce the CPU time complexity significantly. Extensive experiments on both real and synthetic data confirm both the efficacy and efficiency of the proposed techniques.

This paper studies how to design an index structure on a collection of sets$S_{1}, S_{2},{\ldots }, S_{n}$to answer the following queries: given distinct set ids$a, b \in [1, n]$, report$F(S_{a} \cap S_{b})$where$F(.)$is a filtering function. We present a solution that can support a great variety of filtering functions — range research, skyline, convex hull, nearest neighbor search, quantile (to name just a few) — with attractive performance guarantees. The guarantees are sensitive to the set collection'spseudoarboricity, a new notion for quantifying the density of$\lbrace S_{1}, S_{2},{\ldots }, S_{n}\rbrace$. Our index structures are simple to understand and implement.

This paper initializes the study of range subgraph counting and range subgraph listing, both of which are motivated by the significant demands in practice to perform graph analytics on subgraphs pertinent to only selected, as opposed to all, vertices. In the first problem, there is an undirected graph G where each vertex carries a real-valued attribute. Given an interval q and a pattern Q, a query counts the number of occurrences of Q in the subgraph of G induced by the vertices whose attributes fall in q. The second problem has the same setup except that a query needs to enumerate (rather than count) those occurrences with a small delay. In both problems, our goal is to understand the tradeoff between space usage and query cost, or more specifically: (i) given a target on query efficiency, how much pre-computed information about G must we store? (ii) Or conversely, given a budget on space usage, what is the best query time we can hope for? We establish a suite of upper- and lower-bound results on such tradeoffs for various query patterns.

We present a dynamic index structure for join sampling. Built for an (equi-) join Q --- let IN be the total number of tuples in the input relations of Q --- the structure uses ~O(IN) space, supports a tuple update of any relation in ~O(1) time, and returns a uniform sample from the join result in ~O(INρ* / /max{1, OUT} ) time with high probability (w.h.p.), where OUT and ρ* are the join's output size and fractional edge covering number, respectively; notation ~O(.) hides a factor polylogarithmic to IN. We further show how our result justifies the O(INρ* ) running time of existing worst-case optimal join algorithms (for full result reporting) even when OUT łl INρ*. Specifically, unless the combinatorial k-clique hypothesis is false, no combinatorial algorithms (i.e., algorithms not relying on fast matrix multiplication) can compute the join result in O(INρ*-ε ) time w.h.p. even if OUT łe INε, regardless of how small the constant ε > 0 is.

Keyword search, which finds the documents containing all the keywords supplied by a user, has proved to be an effective approach for querying non-structured information that does not conform to any pre-set schemas. In the last two decades, a vast amount of research --- especially in the field of "spatial keyword search'' --- has been carried out to design indexes for answering queries that integrate keyword search with structured predicates imposed on pre-determined attributes (common examples of such predicates are range conditions, linear constraints, prioritization by distance, etc.). Although the past investigation has led to a plethora of empirical solutions, little progress has been made in theory. In fact, for most problems in the literature, the state of the art is still the naive method that answers a query purely based on the keyword conditions or the structured predicates. In this paper, we remedy the issue by developing new indexes with strong theoretical guarantees for a suite of problems with heavy importance in real applications. Many of our indexes are near-optimal, subject to widely-accepted conjectures.

Partial order multiway search(POMS) is a fundamental problem that finds applications in crowdsourcing, distributed file systems, software testing, and more. This problem involves an interaction between an algorithm 𝒜 and an oracle, conducted on a directed acyclic graph 𝒢 known to both parties. Initially, the oracle selects a vertextin 𝒢 called thetarget. Subsequently, 𝒜 must identify the target vertex by probing reachability. In eachprobe, 𝒜 selects a setQof vertices in 𝒢, the number of which is limited by a pre-agreed valuek. The oracle then reveals, for each vertexq∈Q, whetherqcan reach the target in 𝒢. The objective of 𝒜 is to minimize the number of probes. We propose an algorithm to solve POMS in \(O(\log _{1+k} n + \frac{d}{k} \log _{1+d} n)\) probes, wherenrepresents the number of vertices in 𝒢, andddenotes the largest out-degree of the vertices in 𝒢. The probing complexity is asymptotically optimal. Our study also explores two new POMS variants: The first one, namedtaciturn POMS, is similar to classical POMS but assumes a weaker oracle, and the second one, namedEM POMS, is a direct extension of classical POMS to theexternal memory(EM) model. For both variants, we introduce algorithms whose performance matches or nearly matches the corresponding theoretical lower bounds.

We study partial order multiway search (POMS), which is a game between an algorithm A and an oracle, played on a directed acyclic graph G known to both parties. First, the oracle picks a vertex t in G called the target. Then, A needs to figure out which vertex is t by probing reachability. Specifically, in each probe, A selects a set Q of vertices in G whose size is bounded by a (pre-agreed) limit; the oracle reveals, for each vertex q ∈ Q, whether q can reach the target in G. The objective of A is to minimize the number of probes. This problem finds use in crowdsourcing, distributed file systems, software testing, etc.

Selecting the best items in a dataset is a common task in data exploration. However, the concept of “best” lies in the eyes of the beholder: Different users may consider different attributes more important and, hence, arrive at different rankings. Nevertheless, one can remove “dominated” items and create a “representative” subset of the data, comprising the “best items” in it. A Pareto-optimal representative is guaranteed to contain the best item of each possible ranking, but it can be a large portion of data. A much smaller representative can be found if we relax the requirement of including the best item for each user and instead just limit the users’ “regret.” Existing work defines regret as the loss in score by limiting consideration to the representative instead of the full dataset, for any chosen ranking function. However, the score is often not a meaningful number, and users may not understand its absolute value. Sometimes small ranges in score can include large fractions of the dataset. In contrast, users do understand the notion of rank ordering. Therefore, we consider items’ positions in the ranked list in defining the regret and propose the rank-regret representative as the minimal subset of the data containing at least one of the top- k of any possible ranking function. This problem is polynomial time solvable in two-dimensional space but is NP-hard on three or more dimensions. We design a suite of algorithms to fulfill different purposes, such as whether relaxation is permitted on k , the result size, or both, whether a distribution is known, whether theoretical guarantees or practical efficiency is important, and so on. Experiments on real datasets demonstrate that we can efficiently find small subsets with small rank-regrets.

In ICDT'19, Kara, Ngo, Nikolic, Olteanu, and Zhang gave a structure which maintains the number T of triangles in an undirected graph G = (V, E) along with the edge insertions/deletions in G. Using O(m) space (m = |E|), their structure supports an update in O(√m log m) amortized time which is optimal (up to polylog factors) subject to the OMv-conjecture (Henzinger, Krinninger, Nanongkai, and Saranurak, STOC'15). Aiming to improve the update efficiency, we study: - the optimal tradeoff between update time and approximation quality. We require a structure to provide the (ε, Γ)-guarantee: when queried, it should return an estimate t of T that has relative error at most ε if T ≥ Γ, or an absolute error at most ε ⋅ Γ, otherwise. We prove that, under any ε ≤ 0.49 and subject to the OMv-conjecture, no structure can guarantee O(m^{0.5-δ}/Γ) expected amortized update time and O(m^{2/3-δ}) query time simultaneously for any constant δ > 0; this is true for Γ = m^c of any constant c in [0, 1/2). We match the lower bound with a structure that ensures Õ((1/ε)³ ⋅ √m/Γ) amortized update time with high probability, and O(1) query time. - (for exact counting) how to achieve arboricity-sensitive update time. For any 1 ≤ Γ ≤ √m, we describe a structure of O(min{α m + m log m, (m/Γ)²}) space that maintains T precisely, and supports an update in Õ(min{α + Γ, √m}) amortized time, where α is the largest arboricity of G in history (and does not need to be known). Our structure reconstructs the aforementioned ICDT'19 result up to polylog factors by setting Γ = √m, but achieves Õ(m^{0.5-δ}) update time as long as α = O(m^{0.5-δ}).

This paper initializes the study of online-to-batch conversion when the samples in batch learning are not i.i.d. Our motivation originated from two facts. First, sample sets in reality are seldom i.i.d., thus preventing the application of the existing conversions. Second, the online model of learning permits an adversarial stream of samples that almost for sure violates the i.i.d. assumption, raising the possibility of adapting an online algorithm effectively to learn from a non-i.i.d. sample set. We present a set of techniques to utilize an online algorithm as a black box to perform batch learning in the absence of the i.i.d. assumption. Our techniques are generic, and are applicable to virtually any online algorithms on classification. This provides strong evidence that the great variety of known algorithms in the online-learning literature can indeed be harnessed to learn from sufficiently-representative non-i.i.d. samples.