共查询到10条相似文献,搜索用时 156 毫秒
1.
The optimal sequenced route query 总被引:2,自引:0,他引:2
Mehdi Sharifzadeh Mohammad Kolahdouzan Cyrus Shahabi 《The VLDB Journal The International Journal on Very Large Data Bases》2008,17(4):765-787
Real-world road-planning applications often result in the formulation of new variations of the nearest neighbor (NN) problem
requiring new solutions. In this paper, we study an unexplored form of NN queries named optimal sequenced route (OSR) query
in both vector and metric spaces. OSR strives to find a route of minimum length starting from a given source location and
passing through a number of typed locations in a particular order imposed on the types of the locations. We first transform the OSR problem into a shortest
path problem on a large planar graph. We show that a classic shortest path algorithm such as Dijkstra’s is impractical for
most real-world scenarios. Therefore, we propose LORD, a light threshold-based iterative algorithm, which utilizes various
thresholds to prune the locations that cannot belong to the optimal route. Then we propose R-LORD, an extension of LORD which
uses R-tree to examine the threshold values more efficiently. Finally, for applications that cannot tolerate the Euclidean
distance as estimation and require exact distance measures in metric spaces (e.g., road networks) we propose PNE that progressively
issues NN queries on different point types to construct the optimal route for the OSR query. Our extensive experiments on
both real-world and synthetic datasets verify that our algorithms significantly outperform a disk-based variation of the Dijkstra
approach in terms of processing time (up to two orders of magnitude) and required workspace (up to 90% reduction on average). 相似文献
2.
Graphs are widely used for modeling complicated data such as social networks, bibliographical networks and knowledge bases. The growing sizes of graph databases motivate the crucial need for developing powerful and scalable graph-based query engines. We propose a SPARQL-like language, G-SPARQL, for querying attributed graphs. The language enables the expression of different types of graph queries that are of large interest in the databases that are modeled as large graph such as pattern matching, reachability and shortest path queries. Each query can combine both structural predicates and value-based predicates (on the attributes of the graph nodes/edges). We describe an algebraic compilation mechanism for our proposed query language which is extended from the relational algebra and based on the basic construct of building SPARQL queries, the Triple Pattern. We describe an efficient hybrid Memory/Disk representation of large attributed graphs where only the topology of the graph is maintained in memory while the data of the graph are stored in a relational database. The execution engine of our proposed query language splits parts of the query plan to be pushed inside the relational database (using SQL) while the execution of other parts of the query plan is processed using memory-based algorithms, as necessary. Experimental results on real and synthetic datasets demonstrate the efficiency and the scalability of our approach and show that our approach outperforms native graph databases by several factors. 相似文献
3.
4.
Approximation-Based Similarity Search for 3-D Surface Segments 总被引:1,自引:0,他引:1
The issue of finding similar 3-D surface segments arises in many recent applications of spatial database systems, such as molecular biology, medical imaging, CAD, and geographic information systems. Surface segments being similar in shape to a given query segment are to be retrieved from the database. The two main questions are how to define shape similarity and how to efficiently execute similarity search queries. We propose a new similarity model based on shape approximation by multi-parametric surface functions that are adaptable to specific application domains. We then define shape similarity of two 3-D surface segments in terms of their mutual approximation errors. Applying the multi-step query processing paradigm, we propose algorithms to efficiently support complex similarity search queries in large spatial databases. A new query type, called the ellipsoid query, is utilized in the filter step. Ellipsoid queries, being specified by quadratic forms, represent a general concept for similarity search. Our major contribution is the introduction of efficient algorithms to perform ellipsoid queries on multidimensional index structures. Experimental results on a large 3-D protein database containing 94,000 surface segments demonstrate the successful application and the high performance of our method. 相似文献
5.
Xiaoying Wu Dimitri Theodoratos Stefanos Souldatos Theodore Dalamagas Timos Sellis 《World Wide Web》2010,13(4):441-474
Finding the occurrences of structural patterns in XML data is a key operation in XML query processing. Existing algorithms
for this operation focus almost exclusively on path patterns or tree patterns. Current applications of XML require querying
of data whose structure is complex or is not fully known to the user, or integrating XML data sources with different structures.
These applications have motivated recently the introduction of query languages that allow a partial specification of path
patterns in a query. In this paper, we consider partial path queries, a generalization of path pattern queries, and we focus
on their efficient evaluation under the indexed streaming evaluation model. Our approach explicitly deals with repeated labels
(that is, multiple occurrences of the same label in a query). We show that partial path queries can be represented as rooted
dags for which a topological ordering of the nodes exists. We present three algorithms for the efficient evaluation of these
queries. The first one exploits a structural summary of data to generate a set of path patterns that together are equivalent
to a partial path query. To evaluate these path patterns, we extend a previous algorithm for path-pattern queries so that
it can work on path patterns with repeated labels. The second one extracts a spanning tree from the query dag, uses a stack-based
algorithm to find the matches of the root-to-leaf paths in the tree, and merge-joins the matches to compute the answer. Finally,
the third one exploits multiple pointers of stack entries and a topological ordering of the query dag to apply a stack-based
holistic technique. We analyze our algorithms and perform extensive experimental evaluations. Our experimental results show
that the holistic algorithm outperforms the other ones. Our approaches are the first ones to efficiently evaluate this class
of queries in the indexed streaming model. 相似文献
6.
In modern geographic information systems, route search represents an important class of queries. In route search related applications,
users may want to define a number of traveling rules (traveling preferences) when they plan their trips. However, these traveling
rules are not considered in most existing techniques. In this paper, we propose a novel spatial query type, the multi-rule
partial sequenced route (MRPSR) query, which enables efficient trip planning with user defined traveling rules. The MRPSR
query provides a unified framework that subsumes the well-known trip planning query (TPQ) and the optimal sequenced route
(OSR) query. The difficulty in answering MRPSR queries lies in how to integrate multiple choices of points-of-interest (POI)
with traveling rules when searching for satisfying routes. We prove that MRPSR query is NP-hard and then provide three algorithms by mapping traveling rules to an activity on vertex network. Afterwards, we extend
all the proposed algorithms to road networks. By utilizing both real and synthetic POI datasets, we investigate the performance
of our algorithms. The results of extensive simulations show that our algorithms are able to answer MRPSR queries effectively
and efficiently with underlying road networks. Compared to the Light Optimal Route Discoverer (LORD) based brute-force solution,
the response time of our algorithms is significantly reduced while the distances of the computed routes are only slightly
longer than the shortest route. 相似文献
7.
针对连续多范围查询处理,结合多核多线程技术和大容量内存技术,通过将移动对象和查询放在内存中处理,提出了一种基于多线程的连续多范围查询处理框架.该框架基于多核处理器平台采用多线程技术周期性地处理查询和移动对象的更新,并周期性地计算多范围查询的结果.提出了基于移动对象数据均匀划分的多线程连续多范围查询处理算法,该算法以为查询建立的格网索引为基础.给出了该索引的构建思想和更新算法.考虑到基于内存的算法受Cache访问性能影响,提出了基于空间填充曲线的移动对象存储优化方法.实验证明,基于多核平台的多线程处理能够高效地处理连续多范围查询,同时通过移动对象存储优化能够提高算法运行中Cache访问命中率,进而提高算法性能. 相似文献
8.
9.
空间数据库的多类型最近邻查询逐渐受到人们的关注,关于K最近邻查询的研究也较多,但多类型K最近邻查询的研究还存在空白。针对道路网络中的多类型K-最近邻(MT-KNN)问题,结合多类型最近邻查询及K最近邻查询的理论,提出了多类型K最近邻查询算法。通过对分层编码视图进行扩展,建立了多路径分层编码视图,并利用逐步扩展局部路径的方法,实现了多类型K最近邻查询,实验结果分析表明算法具有较好的性能。 相似文献
10.
A number of indexing techniques have been proposed in recent times for optimizing the queries on XML and other semi-structured data models. Most of the semi-structured models use tree-like structures and query languages (XPath, XQuery, etc.) which make use of regular path expressions to optimize the query processing. In this paper, we propose two algorithms called Entry-point algorithm (EPA) and Two-point Entry algorithms that exploit different types of indices to efficiently process XPath queries. We discuss and compare two approaches namely, Root-first and Bottom-first in implementing the EPA. We present the experimental results of the algorithms using XML benchmark queries and data and compare the results with that of traditional methods of query processing with and without the use of indexes, and ToXin indexing approach. Our algorithms show improved performance results than the traditional methods and Toxin indexing approach. 相似文献