Search for: All records

One fundamental question in database theory is the following: Given a Boolean conjunctive queryQ, what is the best complexity for computing the answer to Q in terms of the input database sizeN? When restricted to the class of combinatorial algorithms, it is known that the best known complexity for any queryQis captured by thesubmodular widthofQ. However, beyond combinatorial algorithms, certain queries are known to admit faster algorithms that often involve a clever combination of fast matrix multiplication and data partitioning. Nevertheless, there is no systematic way to derive and analyze the complexity of such algorithms for arbitrary queriesQ. In this work, we introduce a general framework that captures the best complexity for answering any Boolean conjunctive queryQusing matrix multiplication. Our framework unifies both combinatorial and non-combinatorial techniques under the umbrella of information theory. It generalizes the notion of submodular width to a new stronger notion called the ω-submodular widththat naturally incorporates the power of fast matrix multiplication. We describe a matching algorithm that computes the answer to any queryQin time corresponding to the ω-submodularwidth ofQ. We show that our framework recovers the best known complexities for Boolean queries that have been studied in the literature, to the best of our knowledge, and also discovers new algorithms for some classes of queries that improve upon the best known complexities. 

Given a self-join-free conjunctive queryQand a set of tuplesS, asynthetic witness Dis a database instance such that the result ofQonDisS. In this work, we are interested in two problems. First, the existence problem ESW decides whether any synthetic witnessDexists. Second, given that a synthetic witness exists, the minimization problem SSW computes a synthetic witness of minimal size. The SSW problem is related to thesmallest witness problemrecently studied by Hu and Sintos [22]; however, the objective and the results are inherently different. More specifically, we show that SSW is poly-time solvable for a wider range of queries. Interestingly, in some cases, SSW is related to optimization problems in other domains, such as therole miningproblem in data mining and theedge concentrationproblem in graph drawing. Solutions to ESW and SSW are of practical interest, e.g., fortest database generationfor applications accessing a database and fordata compressionby encoding a datasetSas a pair of a queryQand databaseD. We prove that ESW is in P, presenting a simple algorithm that, given anyS, decides whether a synthetic witness exists in polynomial time in the size ofS. Next, we focus on the SSW problem. We show an algorithm that computes a minimal synthetic witness in polynomial time with respect to the size ofSfor any queryQthat has thehead-dominationproperty. IfQdoes not have such a property, then SSW is generally hard. More specifically, we show that for the class ofpath queries(of any constant length), SSW cannot be solved in polynomial time unless P = NP. We then extend this hardness result to the class ofBerge-acyclicqueries that do not have the head-domination property, obtaining a full dichotomy of SSW for Berge-acyclic queries. Finally, we investigate the hardness of SSW beyond Berge-acyclic queries by showing that SSW cannot be solved in polynomial time for some cyclic queries unless P = NP. 

ABSTRACT We investigate the dynamics of dust concentration in actively accreting, substructured, non-ideal magnetohydrodynamic wind-launching discs using two-dimensional and three-dimensional (3D) simulations incorporating pressureless dust fluids of various grain sizes and their aerodynamic feedback on gas dynamics. Our results reveal that mm/cm-sized grains are preferentially concentrated within the inner 5–10 au of the disc, where the dust-to-gas surface density ratio (local metallicity Z) significantly exceeds the canonical 0.01, reaching values up to 0.25. This enhancement arises from the interplay of dust settling and complex gas flows in the meridional plane, including mid-plane accretion streams at early times, mid-plane expansion driven by magnetically braked surface accretion at later times, and vigorous meridional circulation in spontaneously formed gas rings. The resulting size-dependent dust distribution has a strong spatial variation, with large grains preferentially accumulating in dense rings, particularly in the inner disc, while being depleted in low-density gas gaps. In 3D, these rings and gaps are unstable to Rossby wave instability, generating arc-shaped vortices that stand out more prominently than their gas counterparts in the inner disc because of preferential dust concentration at small radii. The substantial local enhancement of the dust relative to the gas could promote planetesimal formation via streaming instability, potentially aided by the ‘azimuthal drift’ streaming instability that operates efficiently in accreting discs and a lower Toomre Q expected in younger discs. Our findings suggest that actively accreting young discs may provide favourable conditions for early planetesimal formation, which warrants further investigation. 

ABSTRACT Recent high angular resolution ALMA observations have revealed rich information about protoplanetary discs, including ubiquitous substructures and three-dimensional gas kinematics at different emission layers. One interpretation of these observations is embedded planets. Previous 3D planet–disc interaction studies are either based on viscous simulations or non-ideal magnetohydrodynamics (MHD) simulations with simple prescribed magnetic diffusivities. This study investigates the dynamics of gap formation in 3D non-ideal MHD discs using non-ideal MHD coefficients from the look-up table that is self-consistently calculated based on the thermochemical code. We find a concentration of the poloidal magnetic flux in the planet-opened gap (in agreement with previous work) and enhanced field-matter coupling due to gas depletion, which together enable efficient magnetic braking of the gap material, driving a fast accretion layer significantly displaced from the disc mid-plane. The fast accretion helps deplete the gap further and is expected to negatively impact the planet growth. It also affects the corotation torque by shrinking the region of horseshoe orbits on the trailing side of the planet. Together with the magnetically driven disc wind, the fast accretion layer generates a large, persistent meridional vortex in the gap, which breaks the mirror symmetry of gas kinematics between the top and bottom disc surfaces. Finally, by studying the kinematics at the emission surfaces, we discuss the implications of planets in realistic non-ideal MHD discs on kinematics observations. 

Data summarization is a powerful approach to deal with large-scale data analytics, which has wide applications in web search, recommendation systems, approximate query processing, etc. It computes a small, compact summary that preserves vital properties of the original data. In this paper, we study the data summarization problem of conjunctive query results, i.e., computing a k-size subset of a conjunctive query output, for any given k>0, that optimizes a certain objective. More specifically, we are interested in two commonly studied objectives: cohesion, which measures the maximum distance between a tuple in the query result tuples and its closest tuple in the summary (k-center clustering); and diversity, which measures the pairwise distances between the summary items. A simple approach that computes the entire query output and then applies existing algorithms on top of these materialized tuples suffers from high computational complexity because the query output can be large, e.g., for a relational database of N tuples, the number of result tuples can be N^O(1).We propose O(1)-approximation algorithms that compute well-representative summaries of size k in time O(N*k^O(1)), or even O(N+ k^O(1)) in some cases, without computing all result tuples. We also propose the first efficient (2+\eps)-approximation algorithm for the k-center clustering problem over relational data. Our main idea is to formulate a few oracles that enable us to access specific query result tuples with certain properties, to show how these oracles can be implemented efficiently, and to compute desired summaries with few invocations of these oracles. 

Finding patterns in graphs is a fundamental problem in databases and data mining. In many applications, graphs are temporal and evolve over time, so we are interested in finding durable patterns, such as triangles and paths, which persist over a long time. While there has been work on finding durable simple patterns, existing algorithms do not have provable guarantees and run in strictly super-linear time. The paper leverages the observation that many graphs arising in practice are naturally proximity graphs or can be approximated as such, where nodes are embedded as points in some high-dimensional space, and two nodes are connected by an edge if they are close to each other. We work with an implicit representation of the proximity graph, where nodes are additionally annotated by time intervals, and design near-linear-time algorithms for finding (approximately) durable patterns above a given durability threshold. We also consider an interactive setting where a client experiments with different durability thresholds in a sequence of queries; we show how to compute incremental changes to result patterns efficiently in time near-linear to the size of the changes. 

ABSTRACT Rings and gaps are routinely observed in the dust continuum emission of protoplanetary discs (PPDs). How they form and evolve remains debated. Previous studies have demonstrated the possibility of spontaneous gas rings and gaps formation in wind-launching discs. Here, we show that such gas substructures are unstable to the Rossby wave instability (RWI) through numerical simulations. Specifically, shorter wavelength azimuthal modes develop earlier, and longer wavelength ones dominate later, forming elongated (arc-like) anticyclonic vortices in the rings and (strongly magnetized) cyclonic vortices in the gaps that persist until the end of the simulation. Highly elongated vortices with aspect ratios of 10 or more are found to decay with time in our non-ideal magnetohydrodynamic (MHD) simulation, in contrast with the hydro case. This difference could be caused by magnetically induced motions, particularly strong meridional circulations with large values of the azimuthal component of the vorticity, which may be incompatible with the columnar structure preferred by vortices. The cyclonic and anticyclonic RWI vortices saturate at moderate levels, modifying but not destroying the rings and gaps in the radial gas distribution of the disc. In particular, they do not shut-off the poloidal magnetic flux accumulation in low-density regions and the characteristic meridional flow patterns that are crucial to the ring and gap formation in wind-launching discs. Nevertheless, the RWI and their associated vortices open up the possibility of producing non-axisymmetric dust features observed in a small fraction of PPDs through non-ideal MHD, although detailed dust treatment is needed to explore this possibility.