Diffusion-based tabular data synthesis models have yielded promising results. However, we observe that when the data dimensionality increases, existing models tend to degenerate and may perform even worse than simpler, non-diffusion-based models. This is because limited training samples in high-dimensional space often hinder generative models from capturing the distribution accurately. To mitigate the insufficient learning signals and to stabilize training under such conditions, we propose CtrTab, a condition-controlled diffusion model that injects perturbed ground-truth samples as auxiliary inputs during training. This design introduces an implicit $L_2$ regularization on the model’s sensitivity to the control signal, improving robustness and stability in high-dimensional, low-data scenarios. Experimental results across multiple datasets show that CtrTab outperforms state-of-the-art models, with a performance gap in accuracy over 90% on average.

Graph clustering is a fundamental data mining task that clusters vertices into different groups. The structural graph clustering algorithm ($SCAN$) is a widely used graph clustering algorithm that derives not only clustering results, but also special roles of vertices like hubs and outliers. In this paper, we consider structural graph clustering on dynamic graphs under Jaccard similarity. The state-of-the-art index-based solution focuses on static graphs and incurs prohibitive update costs to maintain indices. Lately, an efficient approximate dynamic structural graph clustering algorithm DynStrClu under Jaccard similarity is proposed. However, their solution needs to fix input parameters while parameter settings of SCAN usually need to be fine-tuned to achieve good clustering results. Motivated by these limitations, we present a study on devising effective index structures for SCAN algorithm on dynamic graphs. Similar to the state-of-the-art dynamic scheme, our main idea to reduce the time complexity is still by bringing approximation to clustering results. However, our solution does not need to fix the input parameters. To achieve this, our solution includes two key components. The first is to maintain a bottom-$k$sketch for each vertex so that the similarities of affected vertices can be easily updated. The second key is a bucketing strategy that allows us to update clustering results and roles of vertices efficiently. Our theoretical analysis shows that our proposed algorithm achieves$O(\log \log {\frac{M+m}{p_{f}}}\cdot \log {\frac{M+m}{p_{f}}})$expected update cost and guarantees to return approximate clustering results with probability$1-p_{f}$after up to$M$updates. Extensive experiments show that our solution is up to two orders of magnitude faster than the state-of-the-art index-based solution while still achieving high-quality clustering results.

Question answering on free-form tables (a.k.a. TableQA) is a challenging task because of the flexible structure and complex schema of tables. Recent studies use Large Language Models (LLMs) for this task, exploiting their capability in understanding the questions and tabular data, which are typically given in natural language and contain many textual fields, respectively. While this approach has shown promising results, it overlooks the challenges brought by numerical values which are common in tabular data, and LLMs are known to struggle with such values. We aim to address this issue, and we propose a model named TabLaP that uses LLMs as a planner rather than an answer generator. This approach exploits LLMs' capability in multi-step reasoning while leaving the actual numerical calculations to a Python interpreter for accurate calculation. Recognizing the inaccurate nature of LLMs, we further make a first attempt to quantify the trustworthiness of the answers produced by TabLaP, such that users can use TabLaP in a regret-aware manner. Experimental results on two benchmark datasets show that TabLaP is substantially more accurate than the state-of-the-art models, improving the answer accuracy by 5.7% and 5.8% on the two datasets, respectively.

In this paper, we investigate three fundamental problems in the Massively Parallel Computation (MPC) model: (i) grid graph connectivity, (ii) approximate Euclidean Minimum Spanning Tree (EMST), and (iii) approximate DBSCAN. Our first result is a O(1)-round Las Vegas (i.e., succeeding with high probability) MPC algorithm for computing the connected components on a d-dimensional c-penetration grid graph ((d,c)-grid graph), where both d and c are positive integer constants. In such a grid graph, each vertex is a point with integer coordinates in ℕ^d, and an edge can only exist between two distinct vertices with 𝓁_∞-norm at most c. To our knowledge, the current best existing result for computing the connected components (CC’s) on (d,c)-grid graphs in the MPC model is to run the state-of-the-art MPC CC algorithms that are designed for general graphs: they achieve O(log log n + log D) [Behnezhad et al., 2019] and O(log log n + log 1/(λ)) [Sepehr Assadi et al., 2019] rounds, respectively, where D is the diameter and λ is the spectral gap of the graph. With our grid graph connectivity technique, our second main result is a O(1)-round Las Vegas MPC algorithm for computing approximate Euclidean MST. The existing state-of-the-art result on this problem is the O(1)-round MPC algorithm proposed by Andoni et al. [Alexandr Andoni et al., 2014], which only guarantees an approximation on the overall weight in expectation. In contrast, our algorithm not only guarantees a deterministic overall weight approximation, but also achieves a deterministic edge-wise weight approximation. The latter property is crucial to many applications, such as finding the Bichromatic Closest Pair and Single-Linkage Clustering. Last, but not least, our third main result is a O(1)-round Las Vegas MPC algorithm for computing an approximate DBSCAN clustering in O(1)-dimensional Euclidean space.

Mining cohesive subgraphs in bipartite graphs is of great importance to various real-world applications such as recommendation in e-commercial systems and fraud detections in social networks. In this paper, we study the problem of Bitruss Decomposition of a given bipartite graph G. The goal is to compute, for each edge e, the largest value of k such that e is still contained in a k-bitruss. Here, a k-bitruss is a maximal subgraph of G such that every edge of it is contained in at least k butterflies (i.e(2,2)-cliques) in the subgraph. All the previous state-of-the-art solutions are based on the well-known Peeling Process framework and have to ''touch'' every butterfly in the graph G for at least once, causing a O(⧖G) cost, where ⧖G is the number of butterflies in G. In the worst case, ⧖G can be as large as O(m2), where m is the number of edges in G. We propose the first algorithm called BiT-DT, whose running time is bounded by O(m^1.5 log m), significantly improving the state-of-the-art bound by roughly a factor of O(√m). The crucial idea of our algorithm is an efficient approach to identify the edges to be peeled next in the Peeling Process without maintaining a precise butterfly support for each edge. To further enhance the practical performance of our BiT-DT algorithm, we propose a heuristic to peel the edges in batch. Extensive experimental results on ten real-world datasets show that our proposed algorithm outperforms the state-of-the-art baselines by up to an order of magnitude in terms of running time.

We study structural clustering on graphs in dynamic scenarios, where graphs can be updated by arbitrary insertions or deletions of edges/vertices. Our goal is to efficiently compute structural clustering results under three conditions: 1) for any clustering parameters ε and μ provided on the fly, 2) for arbitrary graph update patterns, and 3) for all typical similarity measurements. To achieve this, we propose an algorithm named VD-STAR that is much simpler yet more efficient than state of the art. With a theoretical guarantee on clustering result's quality, VD-STAR can produce clustering results with up to 99.9% accuracy. Moreover, VD-STAR is easy to implement as it just needs to maintain sorted linked lists and hash tables, making it highly deployable in practice. Most importantly, VD-STAR improves the expected per-update time bound from state-of-the-art O(log2 n), which relies on specific assumption on update pattern, to O(log n) amortized in expectation without any assumption on update pattern. We further design two variants of VD-STAR to enhance its empirical performance. Experimental results show that our algorithms consistently outperform state-of-the-art competitors by up to 9,315 times in update time across nine real datasets, while maintaining similar update time and memory usage.

In recommender systems, the patterns of user behaviors (e.g., purchase, click) may vary greatly in different contexts (e.g., time and location). This is because user behavior is jointly determined by two types of factors: intrinsic factors , which reflect consistent user preference, and extrinsic factors , which reflect external incentives that may vary in different contexts. Differentiating between intrinsic and extrinsic factors helps learn user behaviors better. However, existing studies have only considered differentiating them from a single, pre-defined context (e.g., time or location), ignoring the fact that a user’s extrinsic factors may be influenced by the interplay of various contexts at the same time. In this article, we propose the intrinsic-extrinsic disentangled recommendation (IEDR) model, a generic framework that differentiates intrinsic from extrinsic factors considering various contexts simultaneously, enabling more accurate differentiation of factors and hence the improvement of recommendation accuracy. IEDR contains a context-invariant contrastive learning component to capture intrinsic factors, and a disentanglement component to extract extrinsic factors under the interplay of various contexts. The two components work together to achieve effective factor learning. Extensive experiments on real-world datasets demonstrate IEDR’s effectiveness in learning disentangled factors and significantly improving recommendation accuracy by up to 4% in NDCG.

We consider the Max Unique Coverage problem, including applications to the data stream model. The input is a universe of $n$ elements, a collection of $m$ subsets of this universe, and a cardinality constraint, $k$. The goal is to select a subcollection of at most $k$ sets that maximizes unique coverage, i.e, the number of elements contained in exactly one of the selected sets. The Max Unique Coverage problem has applications in wireless networks, radio broadcast, and envy-free pricing. Our first main result is a fixed-parameter tractable approximation scheme (FPT-AS) for Max Unique Coverage, parameterized by $k$ and the maximum element frequency, $r$, which can be implemented on a data stream. Our FPT-AS finds a $(1-ε)$-approximation while maintaining a kernel of size $\tilde{O}(k r/ε)$, which can be combined with subsampling to use $\tilde{O}(k^2 r / ε^3)$ space overall. This significantly improves on the previous-best FPT-AS with the same approximation, but a kernel of size $\tilde{O}(k^2 r / ε^2)$. In order to achieve our result, we show upper bounds on the ratio of a collection's coverage to the unique coverage of a maximizing subcollection; this is by constructing explicit algorithms that find a subcollection with unique coverage at least a logarithmic ratio of the collection's coverage. We complement our algorithms with our second main result, showing that $Ω(m / k^2)$ space is necessary to achieve a $(1.5 + o(1))/(\ln k - 1)$-approximation in the data stream. This dramatically improves the previous-best lower bound showing that $Ω(m / k^2)$ is necessary to achieve better than a $e^{-1+1/k}$-approximation.

We study the problem of interactive graph search (IGS). Given a query entity$\varphi$, the goal is to identify the target concept in a directed acyclic graph (DAG) concept hierarchy$H$, which best describes$\varphi$, through interactions with an oracle. In each interaction, a question in the form of “Does$\varphi$belong to concept$u?$” is asked and the oracle can only answer either YES or NO. The efficiency of an IGS algorithm is measured by the number of questions asked, to identify the target concept, which is referred to as query cost. In theory aspect, we propose the Target-Sensitive IGS (TS-IGS) algorithm that achieves a query cost complexity of$O(\log n. \log\frac{L}{\log n}+d\cdot\log_{d}n)$, where$L$is the length of the path from the root of$H$to the target concept. When$L\in O(\log n)$, our TS-IGS matches the known lower bound [1]. In practice aspect, we propose an algorithm called Example-Guided IGS (EG-IGS) that exploits the knowledge of entities and asks promising questions guided by examples similar to$\varphi$. We prove that EG-IGS achieves a finer-grained query cost bound than that of TS-IGS, and is extremely efficient in practice. Extensive experiments on six real-world datasets (including images, texts, and gene sequences) show that our EG-IGS outperforms all the existing competitors by up to two orders of magnitude in terms of query cost, and is robust in various settings. To further demonstrate the real feasibility of our EG-IGS technique, we develop a fully-automatic Amazon product categorization demo system with GPT-3.5 serving as the oracle.

In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in the Word RAM model. In DPSS, the input is a set, S , of n items, where each item, x , has a non-negative integer weight, w(x). Given a pair of query parameters, (α, β), each of which is a non-negative rational number, a parameterized subset sampling query on S seeks to return a subset T ⊆ S such that each item x∈ S is selected in T , independently, with probability p_x(α, β) which is the minimum between 1 and w(x) / (α \cdot W + β), where W is the total weight of the items in S . More specifically, the DPSS problem is defined in a dynamic setting, where the item set, S , can be updated with insertions of new items or deletions of existing items. Our first main result is an optimal algorithm for solving the DPSS problem, which achieves O(n) pre-processing time, O(1+μ_S(α,β)) expected time for each query parameterized by (α, β), given on-the-fly, and O(1) time for each update; here, μ_S(α,β) is the expected size of the query result. At all times, the worst-case space consumption of our algorithm is linear in the current number of items in S . Our second main contribution is a hardness result for the DPSS problem when the item weights are O(1)-word float numbers, rather than integers. Specifically, we reduce Integer Sorting to the deletion-only DPSS problem with float item weights. Our reduction shows that an optimal algorithm for deletion-only DPSS with float item weights (achieving all the same bounds as aforementioned) implies an algorithm for sorting N integers in O(N) expected time. The latter remains an important open problem. Moreover, a deletion-only DPSS algorithm which supports float item weights, with complexities worse, by at most a factor of o(√łog łog N), than the optimal counterparts, would already improve the current-best integer sorting algorithm [FOCS 2002]. Last but not least, a key technical ingredient for our first main result is a set of exact and efficient algorithms for generating Bernoulli (of certain forms) and Truncated Geometric random variates in O(1) expected time with O(n) worst-case space in the Word RAM model. Generating Bernoulli and geometric random variates efficiently is of great importance not only to sampling problems but also to encryption in cybersecurity. We believe that our new algorithms may be of independent interests for related research.

A successful campaign should be able to attract investment from the brand, and meanwhile manage the conflicting interests in the campaign cost between the brand and the influencers. As such, the agency between these two stakeholders plays a vital role. Motivated by the above, we stand in the agency's shoes to formulate an interesting yet practical problem, namely Profit Divergence Minimization in Investment-Persuasive Influencer Marketing Campaign (PDMIC). This problem aims to (i) minimize the divergence of the actual hiring prices from the asking prices of the influencers and meanwhile (ii) maintain the attractiveness of the pricing scheme for the influencers to the brand. We show that this problem is NP-hard. To mitigate the challenge of the extremely large searching space of the hiring prices of the influencers, we solve this problem by firstly considering a restrictive searching sub-space and then gradually expanding the searching sub-space to the whole space in the end (specifically, from binary price choices to a set of integer prices and then to any price in the feasible price range). We propose effective yet efficient approximate algorithms for solving the problem in each of these settings. Extensive experiments demonstrate the superiority of our methods.

A bipartite graph is a graph that consists of two disjoint sets of vertices and only edges between vertices from different vertex sets. In this paper, we study the counting problems of two common types of em motifs in bipartite graphs: (i) butterflies (2x2 bicliques) and (ii) bi-triangles (length-6 cycles). Unlike most of the existing algorithms that aim to obtain exact counts, our goal is to obtain precise enough estimations of these counts in bipartite graphs, as such estimations are already sufficient and of great usefulness in various applications. While there exist approximate algorithms for butterfly counting, these algorithms are mainly based on the techniques designed for general graphs, and hence, they are less effective on bipartite graphs. Not to mention that there is still a lack of study on approximate bi-triangle counting. Motivated by this, we first propose a novel butterfly counting algorithm, called one-sided weighted sampling, which is tailored for bipartite graphs. The basic idea of this algorithm is to estimate the total butterfly count with the number of butterflies containing two randomly sampled vertices from the same side of the two vertex sets. We prove that our estimation is unbiased, and our technique can be further extended (non-trivially) for bi-triangle count estimation. Theoretical analyses under a power-law random bipartite graph model and extensive experiments on multiple large real datasets demonstrate that our proposed approximate counting algorithms can reach high accuracy, yet achieve up to three orders (resp. four orders) of magnitude speed-up over the state-of-the-art exact butterfly (resp. bi-triangle) counting algorithms. Additionally, we present an approximate clustering coefficient estimation framework for bipartite graphs, which shows a similar speed-up over the exact solutions with less than 1% relative error.

Detecting beneficial feature interactions is essential in recommender systems, and existing approaches achieve this by examining all the possible feature interactions. However, the cost of examining all the possible higher-order feature interactions is prohibitive (exponentially growing with the order increasing). Hence existing approaches only detect limited order (e.g., combinations of up to four features) beneficial feature interactions, which may miss beneficial feature interactions with orders higher than the limitation. In this paper, we propose a hypergraph neural network based model named HIRS. HIRS is the first work that directly generates beneficial feature interactions of arbitrary orders and makes recommendation predictions accordingly. The number of generated feature interactions can be specified to be much smaller than the number of all the possible interactions and hence, our model admits a much lower running time. To achieve an effective algorithm, we exploit three properties of beneficial feature interactions, and propose deep-infomax-based methods to guide the interaction generation. Our experimental results show that HIRS outperforms state-of-the-art algorithms by up to 5% in terms of recommendation accuracy.

In this paper, we study the (approximate) Range Thresholding (RT) problem over streams. Each stream element is a d-dimensional point and with a positive integer weight. An RT query q specifies a d-dimensional axis-parallel rectangular range R(q) and a positive integer threshold τ(q). Once the query q is registered in the system, define s(q) as the total weight of the elements that satisfy: (i) they arrive after q's registration, and (ii) they fall in the range R(q). Given a real number 0 < ε < 1, the task of the system is to capture an arbitrary moment during the period between the first moment when s(q) ≥ (1 - ε)⋅ τ(q) and the first moment when s(q) ≥ τ(q). The challenge is to support a large number of RT queries simultaneously while achieving sub-quadratic overall running time and near-linear space consumption all the time.

Personalized PageRank (PPR) is a popular node proximity metric in graph mining and network research. A single-source PPR (SSPPR) query asks for the PPR value of each node on the graph. Due to its importance and wide applications, decades of efforts have been devoted to the efficient processing of SSPPR queries. Among existing algorithms, LocalPush is a fundamental method for SSPPR queries and serves as a cornerstone for subsequent algorithms. In LocalPush , a push operation is a crucial primitive operation, which distributes the probability at a node u to ALL u 's neighbors via the corresponding edges. Although this push operation works well on unweighted graphs, unfortunately, it can be rather inefficient on weighted graphs. In particular, on unbalanced weighted graphs where only a few of these edges take the majority of the total weight among them, the push operation would have to distribute "insignificant" probabilities along those edges which just take the minor weights, resulting in expensive overhead. To resolve this issue, in this paper, we propose the EdgePush algorithm, a novel method for computing SSPPR queries on weighted graphs. EdgePush decomposes the aforementioned push operations in edge-based push , allowing the algorithm to operate at the edge level granularity. As a result, it can flexibly distribute the probabilities according to edge weights. Furthermore, our EdgePush allows a fine-grained termination threshold for each individual edge, leading to a superior complexity over LocalPush. Notably, we prove that EdgePush improves the theoretical query cost of LocalPush by an order of up to O ( n ) when the graph's weights are unbalanced. Our experimental results demonstrate that EdgePush significantly outperforms state-of-the-art baselines in terms of query efficiency on large motif-based and real-world weighted graphs.

User and item attributes are essential side-information; their interactions (i.e., their co-occurrence in the sample data) can significantly enhance prediction accuracy in various recommender systems. We identify two different types of attribute interactions, inner interactions and cross interactions: inner interactions are those between only user attributes or those between only item attributes; cross interactions are those between user attributes and item attributes. Existing models do not distinguish these two types of attribute interactions, which may not be the most effective way to exploit the information carried by the interactions. To address this drawback, we propose a neural Graph Matching based Collaborative Filtering model (GMCF), which effectively captures the two types of attribute interactions through modeling and aggregating attribute interactions in a graph matching structure for recommendation. In our model, the two essential recommendation procedures, characteristic learning and preference matching, are explicitly conducted through graph learning (based on inner interactions) and node matching (based on cross interactions), respectively. Experimental results show that our model outperforms state-of-the-art models. Further studies verify the effectiveness of GMCF in improving the accuracy of recommendation.

\em Structural Clustering ($\strclu$) is one of the most popular graph clustering paradigms. In this paper, we consider $\strclu$ under Jaccard similarity on a dynamic graph, G = (V, E), subject to edge insertions and deletions (updates). The goal is to maintain certain information under updates, so that the strclu clustering result on~G can be retrieved in O(|V| + |E|)$ time, upon request. The state-of-the-art worst-case cost is~O(|V|) per update; we improve this update-time bound \em significantly with the ρ-approximate notion. Specifically, for a specified failure probability, δ^*, and \em every sequence of~M updates (no need to know M's value in advance), our algorithm, $\dynelm$, achieves~O(?og^2 |V| + og |V| \cdot ?og \fracM ?^* )$ amortized cost for each update, \em at all times in linear space. Moreover, $\dynelm$ provides a provable "sandwich'' guarantee on the clustering quality at all times after each update with probability at least 1 - ^*. We further develop dynelm into our ultimate algorithm, dynstr, which also supports \em cluster-group-by queries. Given Q \subseteq V, this puts the non-empty intersection of Q and each strclu cluster into a distinct group. dynstr not only achieves all the guarantees of dynelm, but also runs \em cluster-group-by queries in~O(|Q|\cdot og |V|) time. We demonstrate the performance of our algorithms via extensive experiments, on 15 real datasets. Experimental results confirm that our algorithms are up to three orders of magnitude more efficient than state-of-the-art competitors, and still provide quality structural clustering results.

Personalized PageRank (PPR) is a critical measure of the importance of a node t to a source node s in a graph. The Single-Source PPR (SSPPR) query computes the PPR's of all the nodes with respect to s on a directed graph G with n nodes and m edges; and it is an essential operation widely used in graph applications. In this paper, we propose novel algorithms for answering two variants of SSPPR queries: (i) high-precision queries and (ii) approximate queries.

Personalized PageRank (PPR) is a widely used node proximity measure in graph mining and network analysis. Given a source node s and a target node t, the PPR value π(s,t) represents the probability that a random walk from s terminates at t, and thus indicates the bidirectional importance between s and t. The majority of the existing work focuses on the single-source queries, which asks for the PPR value of a given source node s and every node t ∈ V. However, the single-source query only reflects the importance of each node t with respect to s. In this paper, we consider the single-target PPR query, which measures the opposite direction of importance for PPR. Given a target node t, the single-target PPR query asks for the PPR value of every node $s\in V$ to a given target node t. We propose RBS, a novel algorithm that answers approximate single-target queries with optimal computational complexity. We show that RBS improves three concrete applications: heavy hitters PPR query, single-source SimRank computation, and scalable graph neural networks. We conduct experiments to demonstrate that RBS outperforms the state-of-the-art algorithms in terms of both efficiency and precision on real-world benchmark datasets.

Inspired by the great success of machine learning in the past decade, people have been thinking about the possibility of improving the theoretical results by exploring data distribution. In this paper, we revisit a fundamental problem called Distributed Tracking (DT) under an assumption that the data follows a certain (known or unknown) distribution, and propose a number Data-dependent algorithms with improved theoretical bounds. Informally, in the DT problem, there is a coordinator and k players, where the coordinator holds a threshold N and each player has a counter. At each time stamp, at most one counter can be increased by one. The job of the coordinator is to capture the exact moment when the sum of all these k counters reaches N. The goal is to minimise the communication cost. While our first type of algorithms assume the concrete data distribution is known in advance, our second type of algorithms can learn the distribution on the fly. Both of the algorithms achieve a communication cost bounded by O(k log log N) with high probability, improving the state-of-the-art data-independent bound O(k log N/k). We further propose a number of implementation optimisation heuristics to improve both efficiency and robustness of the algorithms. Finally, we conduct extensive experiments on three real datasets and four synthetic datasets. The experimental results show that the communication cost of our algorithms is as least as $20%$ of that of the state-of-the-art algorithms.

Resolution parameters in graph clustering control the size and structure of clusters formed by solving a parametric objective function. Typically there is more than one meaningful way to cluster a graph, and solving the same objective function for different resolution parameters produces clusterings at different levels of granularity, each of which can be meaningful depending on the application. In this paper, we address the task of efficiently solving a parameterized graph clustering objective for all values of a resolution parameter. Specifically, we consider a new analysis-friendly objective we call LambdaPrime, involving a parameter λ ∈ (0,1). LambdaPrime is an adaptation of LambdaCC, a significant family of instances of the Correlation Clustering (minimization) problem. Indeed, LambdaPrime and LambdaCC are closely related to other parameterized clustering problems, such as parametric generalizations of modularity. They capture a number of specific clustering problems as special cases, including sparsest cut and cluster deletion. While previous work provides approximation results for a single value of the resolution parameter, we seek a set of approximately optimal clusterings for all values of λ in polynomial time. More specifically, we show that when a graph has m edges and n nodes, there exists a set of at most m clusterings such that, for every λ ∈ (0,1), the family contains an optimal solution to the LambdaPrime objective. This bound is tight on star graphs. We obtain a family of O(log n) clusterings by solving the parametric linear programming (LP) relaxation of LambdaPrime at O(log n) λ values, and rounding each LP solution using existing approximation algorithms. We prove that this is asymptotically tight: for a certain class of ring graphs, for all values of λ, Ω(log n) feasible solutions are required to provide a constant-factor approximation for the LambdaPrime LP relaxation. To minimize the size of the clustering family, we further propose an algorithm that yields a family of solutions of a size no more than twice of the minimum LP-approximating family.

We describe new algorithms for the predecessor problem in the Noisy Comparison Model. In this problem, given a sorted list L of n (distinct) elements and a query q, we seek the predecessor of q in L: denoted by u, the largest element less than or equal to q. In the Noisy Comparison Model, the result of a comparison between two elements is non-deterministic. Moreover, multiple comparisons of the same pair of elements might have different results: each is generated independently, and is correct with probability p > 1/2. Given an overall error tolerance Q, the cost of an algorithm is measured by the total number of noisy comparisons; these must guarantee the predecessor is returned with probability at least 1 - Q. Feige et al. showed that predecessor queries can be answered by a modified binary search with Theta(log (n/Q)) noisy comparisons. We design result-sensitive algorithms for answering predecessor queries. The query cost is related to the index, k, of the predecessor u in L. Our first algorithm answers predecessor queries with O(log ((log^{*(c)} n)/Q) + log (k/Q)) noisy comparisons, for an arbitrarily large constant c. The function log^{*(c)} n iterates c times the iterated-logarithm function, log^* n. Our second algorithm is a genuinely result-sensitive algorithm whose expected query cost is bounded by O(log (k/Q)), and is guaranteed to terminate after at most O(log((log n)/Q)) noisy comparisons. Our results strictly improve the state-of-the-art bounds when k is in omega(1) intersected with o(n^epsilon), where epsilon > 0 is some constant. Moreover, we show that our result-sensitive algorithms immediately improve not only predecessor-query algorithms, but also binary-search-like algorithms for solving key applications.

OPTICS is a popular method for visualizing multidimensional clusters. All the existing implementations of this method have a time complexity of $O(n^2)$ --- where n is the size of the input dataset --- and thus, may not be suitable for datasets of large volumes. This paper alleviates the problem by resorting to approximation with guarantees. The main result is a new algorithm that runs in $O(n łog n)$ time under any fixed dimensionality, and computes a visualization that has provably small discrepancies from that of OPTICS. As a side product, our algorithm gives an index structure that occupies linear space, and supports the cluster group-by query with near-optimal cost. The quality of the cluster visualizations produced by our techniques and the efficiency of the proposed algorithms are demonstrated with an empirical evaluation on real data.

Dynamic clustering---how to efficiently maintain data clusters along with updates in the underlying dataset---is a difficult topic. This is especially true for density-based clustering, where objects are aggregated based on transitivity of proximity, under which deciding the cluster(s) of an object may require the inspection of numerous other objects. The phenomenon is unfortunate, given the popular usage of this clustering approach in many applications demanding data updates.

DBSCAN is a method proposed in 1996 for clustering multi-dimensional points, and has received extensive applications. Its computational hardness is still unsolved to this date. The original KDD‚96 paper claimed an algorithm of O ( n log n ) ”average runtime complexity„ (where n is the number of data points) without a rigorous proof. In 2013, a genuine O ( n log n )-time algorithm was found in 2D space under Euclidean distance. The hardness of dimensionality d ≥3 has remained open ever since. This article considers the problem of computing DBSCAN clusters from scratch (assuming no existing indexes) under Euclidean distance. We prove that, for d ≥3, the problem requires ω( n 4/3 ) time to solve, unless very significant breakthroughs—ones widely believed to be impossible—could be made in theoretical computer science. Motivated by this, we propose a relaxed version of the problem called ρ- approximate DBSCAN , which returns the same clusters as DBSCAN, unless the clusters are ”unstable„ (i.e., they change once the input parameters are slightly perturbed). The ρ-approximate problem can be settled in O ( n ) expected time regardless of the constant dimensionality d . The article also enhances the previous result on the exact DBSCAN problem in 2D space. We show that, if the n data points have been pre-sorted on each dimension (i.e., one sorted list per dimension), the problem can be settled in O ( n ) worst-case time. As a corollary, when all the coordinates are integers, the 2D DBSCAN problem can be solved in O ( n log log n ) time deterministically, improving the existing O ( n log n ) bound.

This paper studies a type of continuous queries called range thresholding on streams (RTS). Imagine the stream as an unbounded sequence of elements each of which is a real value. A query registers an interval, and must be notified as soon as a certain number of incoming elements fall into the interval. The system needs to support multiple queries simultaneously, and aims to minimize the space consumption and computation time. Currently, all the solutions to this problem entail quadratic time O(nm) to process n stream elements and m queries, which severely limits their applicability to only a small number of queries. We propose the first algorithm that breaks the quadratic barrier, by reducing the computation cost dramatically to O(n + m), subject only to a polylogarithmic factor. The algorithm is general enough to guarantee the same on weighted versions of the queries even in d-dimensional space of any constant d. Its vast advantage over the previous methods in practical environments has been confirmed through extensive experimentation.

DBSCAN is a popular method for clustering multi-dimensional objects. Just as notable as the method's vast success is the research community's quest for its efficient computation. The original KDD'96 paper claimed an algorithm with O(n log n) running time, where n is the number of objects. Unfortunately, this is a mis-claim; and that algorithm actually requires O(n2) time. There has been a fix in 2D space, where a genuine O(n log n)-time algorithm has been found. Looking for a fix for dimensionality d ≥ 3 is currently an important open problem.

Locality-Sensitive Hashing (LSH) and its variants are well-known methods for solving the c-approximate NN Search problem in high-dimensional space. Traditionally, several LSH functions are concatenated to form a "static" compound hash function for building a hash table. In this paper, we propose to use a base of m single LSH functions to construct "dynamic" compound hash functions, and define a new LSH scheme called Collision Counting LSH (C2LSH). If the number of LSH functions under which a data object o collides with a query object q is greater than a pre-specified collision threhold l, then o can be regarded as a good candidate of c-approximate NN of q. This is the basic idea of C2LSH.