اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA PRQ Search Method for Probabilistic Objects
65
0
0.0
(
0
)
تأليف
Jack Wang
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
This article proposes an PQR search method for probabilistic objects. The main idea of our method is to use a strategy called textit{pre-approximation} that can reduce the initial problem to a highly simplified version, implying that it makes the rest of steps easy to tackle. In particular, this strategy itself is pretty simple and easy to implement. Furthermore, motivated by the cost analysis, we further optimize our solution. The optimizations are mainly based on two insights: (romannumeral 1) the number of textit{effective subdivision}s is no more than 1; and (romannumeral 2) an entity with the larger textit{span} is more likely to subdivide a single region. We demonstrate the effectiveness and efficiency of our proposed approaches through extensive experiments under various experimental settings.
قيم البحث
اقرأ أيضاً
Many studies have been conducted on seeking the efficient solution for subgraph similarity search over certain (deterministic) graphs due to its wide application in many fields, including bioinformatics, social network analysis, and Resource Descript
ion Framework (RDF) data management. All these works assume that the underlying data are certain. However, in reality, graphs are often noisy and uncertain due to various factors, such as errors in data extraction, inconsistencies in data integration, and privacy preserving purposes. Therefore, in this paper, we study subgraph similarity search on large probabilistic graph databases. Different from previous works assuming that edges in an uncertain graph are independent of each other, we study the uncertain graphs where edges occurrences are correlated. We formally prove that subgraph similarity search over probabilistic graphs is #P-complete, thus, we employ a filter-and-verify framework to speed up the search. In the filtering phase,we develop tight lower and upper bounds of subgraph similarity probability based on a probabilistic matrix index, PMI. PMI is composed of discriminative subgraph features associated with tight lower and upper bounds of subgraph isomorphism probability. Based on PMI, we can sort out a large number of probabilistic graphs and maximize the pruning capability. During the verification phase, we develop an efficient sampling algorithm to validate the remaining candidates. The efficiency of our proposed solutions has been verified through extensive experiments.
We present the `Basic S* algorithm for computing shortest path through a metric simplicial complex. In particular, given a metric graph, $G$, which is constructed as a discrete representation of an underlying configuration space (a larger continuous
space/manifold typically of dimension greater than one), we consider the Rips complex, $mathcal{R}(G)$, associated with it. Such a complex, and hence shortest paths in it, represent the underlying metric space more closely than what the graph does. While discrete graph representations of continuous spaces is convenient for motion planning in configuration spaces of robotic systems, the metric induced in them by the ambient configuration space is significantly different from the metric of the configuration space itself. We remedy this problem using the simplicial complex representation. Our algorithm requires only an abstract graph, $G=(V,E)$, and a cost/length function, $d:Erightarrow mathbb{R}_+$, as inputs, and no global information such as an embedding or a global coordinate chart is required. The complexity of the Basic S* algorithm is comparable to that of Dijkstras search, but, as the results presented in this paper demonstrate, the shortest paths obtained using the proposed algorithm represent/approximate the geodesic paths in the original metric space significantly more closely.
Spreadsheets are end-user programs and domain models that are heavily employed in administration, financial forecasting, education, and science because of their intuitive, flexible, and direct approach to computation. As a result, institutions are sw
amped by millions of spreadsheets that are becoming increasingly difficult to manage, access, and control. This note presents the XLSearch system, a novel search engine for spreadsheets. It indexes spreadsheet formulae and efficiently answers formula queries via unification (a complex query language that allows metavariables in both the query as well as the index). But a web-based search engine is only one application of the underlying technology: Spreadsheet formula export to web standards like MathML combined with formula indexing can be used to find similar spreadsheets or common formula errors.
In this project we are presenting a grammar which unify the design and development of spatial databases. In order to make it, we combine nominal and spatial information, the former is represented by the relational model and latter by a modification o
f the same model. The modification lets to represent spatial data structures (as Quadtrees, Octrees, etc.) in a integrated way. This grammar is important because with it we can create tools to build systems that combine spatial-nominal characteristics such as Geographical Information Systems (GIS), Hypermedia Systems, Computed Aided Design Systems (CAD), and so on
In order to use persistence diagrams as a true statistical tool, it would be very useful to have a good notion of mean and variance for a set of diagrams. In 2011, Mileyko and his collaborators made the first study of the properties of the Frechet me
an in $(mathcal{D}_p,W_p)$, the space of persistence diagrams equipped with the p-th Wasserstein metric. In particular, they showed that the Frechet mean of a finite set of diagrams always exists, but is not necessarily unique. The means of a continuously-varying set of diagrams do not themselves (necessarily) vary continuously, which presents obvious problems when trying to extend the Frechet mean definition to the realm of vineyards. We fix this problem by altering the original definition of Frechet mean so that it now becomes a probability measure on the set of persistence diagrams; in a nutshell, the mean of a set of diagrams will be a weighted sum of atomic measures, where each atom is itself a persistence diagram determined using a perturbation of the input diagrams. This definition gives for each $N$ a map $(mathcal{D}_p)^N to mathbb{P}(mathcal{D}_p)$. We show that this map is Holder continuous on finite diagrams and thus can be used to build a useful statistic on time-varying persistence diagrams, better known as vineyards.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
