共查询到20条相似文献,搜索用时 46 毫秒
1.
An important query for spatio-temporal databases is to find nearest trajectories of moving objects. Existing work on this
topic focuses on the closest trajectories in the whole data space. In this paper, we introduce and solve constrained k-nearest neighbor (CkNN) queries and historical continuous CkNN (HCCkNN) queries on R-tree-like structures storing historical information about moving object trajectories. Given a trajectory
set D, a query object (point or trajectory) q, a temporal extent T, and a constrained region CR, (i) a CkNN query over trajectories retrieves from D within T, the k (≥ 1) trajectories that lie closest to q and intersect (or are enclosed by) CR; and (ii) an HCCkNN query on trajectories retrieves the constrained k nearest neighbors (CkNNs) of q at any time instance of T. We propose a suite of algorithms for processing CkNN queries and HCCkNN queries respectively, with different properties and advantages. In particular, we thoroughly investigate two types of CkNN queries, i.e., CkNNP and CkNNT, which are defined with respect to stationary query points and moving query trajectories, respectively; and two types of
HCCkNN queries, namely, HCCkNNP and HCCkNNT, which are continuous counterparts of CkNNP and CkNNT, respectively. Our methods utilize an existing data-partitioning index for trajectory data (i.e., TB-tree) to achieve low
I/O and CPU cost. Extensive experiments with both real and synthetic datasets demonstrate the performance of the proposed
algorithms in terms of efficiency and scalability. 相似文献
2.
Muhammad Aamir Cheema Wenjie Zhang Xuemin Lin Ying Zhang 《The VLDB Journal The International Journal on Very Large Data Bases》2012,21(5):703-728
Given a set of objects and a query q, a point p is called the reverse k nearest neighbor (RkNN) of q if q is one of the k closest objects of p. In this paper, we introduce the concept of influence zone that is the area such that every point inside this area is the RkNN of q and every point outside this area is not the RkNN. The influence zone has several applications in location-based services, marketing and decision support systems. It can also be used to efficiently process RkNN queries. First, we present efficient algorithm to compute the influence zone. Then, based on the influence zone, we present efficient algorithms to process RkNN queries that significantly outperform existing best-known techniques for both the snapshot and continuous RkNN queries. We also present a detailed theoretical analysis to analyze the area of the influence zone and IO costs of our RkNN processing algorithms. Our experiments demonstrate the accuracy of our theoretical analysis. This paper is an extended version of our previous work (Cheema et?al. in Proceedings of ICDE, pp. 577–588, 2011). We make the following new contributions in this extended version: (1) we conduct a rigorous complexity analysis and show that the complexity of one of our proposed algorithms in Cheema et?al. (Proceedings of ICDE, pp. 577–588, 2011) can be reduced from O(m 2) to O( km) where m?>?k is the number of objects used to compute the influence zone, (2) we show that our techniques can be applied to dimensionality higher than two, and (3) we present efficient techniques to handle data updates. 相似文献
3.
Efficient k-Nearest-Neighbor Search Algorithms for Historical Moving Object Trajectories 总被引:1,自引:0,他引:1 下载免费PDF全文
Yun-Jun Gao Chun Li Gen-Cai Chen Ling Chen Xian-Ta Jiang and Chun Chen 《计算机科学技术学报》2007,22(2):232-244
κ Nearest Neighbor (κNN) search is one of the most important operations in spatial and spatio-temporal databases. Although it has received considerable attention in the database literature, there is little prior work on κNN retrieval for moving object trajectories. Motivated by this observation, this paper studies the problem of efficiently processing κNN (κ≥ 1) search on R-tree-like structures storing historical information about moving object trajectories. Two algorithms are developed based on best-first traversal paradigm, called BFPκNN and BFTκNN, which handle the κNN retrieval with respect to the static query point and the moving query trajectory, respectively. Both algorithms minimize the number of node access, that is, they perform a single access only to those qualifying nodes that may contain the final result. Aiming at saving main-memory consumption and reducing CPU cost further, several effective pruning heuristics are also presented. Extensive experiments with synthetic and real datasets confirm that the proposed algorithms in this paper outperform their competitors significantly in both efficiency and scalability. 相似文献
4.
The Group Nearest Neighbor (GNN) search is an important approach for expert and intelligent systems, i.e., Geographic Information System (GIS) and Decision Support System (DSS). However, traditional GNN search starts from users’ perspective and selects the locations or objects that users like. Such applications fail to help the managers since they do not provide managerial insights. In this paper, we focus on solving the problem from the managers’ perspective. In particular, we propose a novel GNN query, namely, the reverse top-k group nearest neighbor (RkGNN) query which returns k groups of data objects so that each group has the query object q as their group nearest neighbor (GNN). This query is an important tool for decision support, e.g., location-based service, product data analysis, trip planning, and disaster management because it provides data analysts an intuitive way for finding significant groups of data objects with respect to q. Despite their importance, this kind of queries has not received adequate attention from the research community and it is a challenging task to efficiently answer the RkGNN queries. To this end, we first formalize the reverse top-k group nearest neighbor query in both monochromatic and bichromatic cases, and then propose effective pruning methods, i.e., sorting and threshold pruning, MBR property pruning, and window pruning, to reduce the search space during the RkGNN query processing. Furthermore, we improve the performance by employing the reuse heap technique. As an extension to the RkGNN query, we also study an interesting variant of the RkGNN query, namely a constrained reverse top-k group nearest neighbor (CRkGN) query. Extensive experiments using synthetic and real datasets demonstrate the efficiency and effectiveness of our approaches. 相似文献
5.
Kyoung-Won Lee Dong-Wan Choi Chin-Wan Chung 《Journal of Intelligent Information Systems》2014,43(2):349-377
This article presents a novel type of queries in spatial databases, called the direction-aware bichromatic reverse k nearest neighbor(DBRkNN) queries, which extend the bichromatic reverse nearest neighbor queries. Given two disjoint sets, P and S, of spatial objects, and a query object q in S, the DBRkNN query returns a subset P′ of P such that k nearest neighbors of each object in P′ include q and each object in P′ has a direction toward q within a pre-defined distance. We formally define the DBRkNN query, and then propose an efficient algorithm, called DART, for processing the DBRkNN query. Our method utilizes a grid-based index to cluster the spatial objects, and the B+-tree to index the direction angle. We adopt a filter-refinement framework that is widely used in many algorithms for reverse nearest neighbor queries. In the filtering step, DART eliminates all the objects that are away from the query object more than a pre-defined distance, or have an invalid direction angle. In the refinement step, remaining objects are verified whether the query object is actually one of the k nearest neighbors of them. As a major extension of DART, we also present an improved algorithm, called DART+, for DBRkNN queries. From extensive experiments with several datasets, we show that DART outperforms an R-tree-based naive algorithm in both indexing time and query processing time. In addition, our extension algorithm, DART+, also shows significantly better performance than DART. 相似文献
6.
The problem of kNN (k Nearest Neighbor) queries has received considerable attention in the database and information retrieval communities. Given a dataset D and a kNN query q, the k nearest neighbor algorithm finds the closest k data points to q. The applications of kNN queries are board, not only in spatio-temporal databases but also in many areas. For example, they can be used in multimedia databases, data mining, scientific databases and video retrieval. The past studies of kNN query processing did not consider the case that the server may receive multiple kNN queries at one time. Their algorithms process queries independently. Thus, the server will be busy with continuously reaccessing the database to obtain the data that have already been acquired. This results in wasting I/O costs and degrading the performance of the whole system. In this paper, we focus on this problem and propose an algorithm named COrrelated kNN query Evaluation (COKE). The main idea of COKE is an “information sharing” strategy whereby the server reuses the query results of previously executed queries for efficiently processing subsequent queries. We conduct a comprehensive set of experiments to analyze the performance of COKE and compare it with the Best-First Search (BFS) algorithm. Empirical studies indicate that COKE outperforms BFS, and achieves lower I/O costs and less running time. 相似文献
7.
Sarana Nutanong Rui Zhang Egemen Tanin Lars Kulik 《The VLDB Journal The International Journal on Very Large Data Bases》2010,19(3):307-332
The moving k nearest neighbor (MkNN) query continuously finds the k nearest neighbors of a moving query point. MkNN queries can be efficiently processed through the use of safe regions. In general, a safe region is a region within which
the query point can move without changing the query answer. This paper presents an incremental safe-region-based technique
for answering MkNN queries, called the V*-Diagram, as well as analysis and evaluation of its associated algorithm, V*-kNN. Traditional safe-region approaches compute a safe region based on the data objects but independent of the query location.
Our approach exploits the knowledge of the query location and the boundary of the search space in addition to the data objects.
As a result, V*-kNN has much smaller I/O and computation costs than existing methods. We further provide cost models to estimate the number
of data accesses for V*-kNN and a competitive technique, RIS-kNN. The V*-Diagram and V*-kNN are also applicable to the domain of spatial networks and we present algorithms to construct a spatial-network V*-Diagram.
Our experimental results show that V*-kNN significantly outperforms the competitive technique. The results also verify the accuracy of the cost models. 相似文献
8.
Min-Joong Lee Dong-Wan Choi SangYeon Kim Ha-Myung Park Sunghee Choi Chin-Wan Chung 《GeoInformatica》2016,20(3):471-502
Finding k nearest neighbor objects in spatial databases is a fundamental problem in many geospatial systems and the direction is one of the key features of a spatial object. Moreover, the recent tremendous growth of sensor technologies in mobile devices produces an enormous amount of spatio-directional (i.e., spatially and directionally encoded) objects such as photos. Therefore, an efficient and proper utilization of the direction feature is a new challenge. Inspired by this issue and the traditional k nearest neighbor search problem, we devise a new type of query, called the direction-constrained k nearest neighbor (DCkNN) query. The DCkNN query finds k nearest neighbors from the location of the query such that the direction of each neighbor is in a certain range from the direction of the query. We develop a new index structure called MULTI, to efficiently answer the DCkNN query with two novel index access algorithms based on the cost analysis. Furthermore, our problem and solution can be generalized to deal with spatio-circulant dimensional (such as a direction and circulant periods of time such as an hour, a day, and a week) objects. Experimental results show that our proposed index structure and access algorithms outperform two adapted algorithms from existing kNN algorithms. 相似文献
9.
10.
不同于传统的k-Skyband 查询方法,提出一种相互k-Skyband 查询(MkSB),它从对称角度执行Skyline查询,找出所有既在q的动态k-Skyband(DkSB)中又在q的反向k-Skyband(RkSB)中的数据对象.进一步地,为了更好地支持用户决策和数据分析,排序操作被引入到MkSB算法中.因为MkSB 需要执行q的DkSB 和反向RkSB,故它需要遍历索引多次,从而导致了大量冗余的I/O 开销.利用信息重用技术和若干有效的修剪方法,MkSB 将多次的索引搜索合并成单次,极大地降低了I/O访问次数.同时,证明了基于窗口查询的MkSB(WMkSB)算法具有最低的I/O 代价.在真实与合成数据集上的实验结果表明,所提出的算法是有效的且明显胜过基于BBS 的算法,尤其WMkSB 算法具有极少的I/O 开销,通常能够减少95%以上的冗余I/O. 相似文献
11.
Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks 总被引:2,自引:0,他引:2
Muhammad Aamir Cheema Wenjie Zhang Xuemin Lin Ying Zhang Xuefei Li 《The VLDB Journal The International Journal on Very Large Data Bases》2012,21(1):69-95
In this paper, we study the problem of continuous monitoring of reverse k nearest neighbors queries in Euclidean space as well as in spatial networks. Existing techniques are sensitive toward objects
and queries movement. For example, the results of a query are to be recomputed whenever the query changes its location. We
present a framework for continuous reverse k nearest neighbor (RkNN) queries by assigning each object and query with a safe region such that the expensive recomputation is not required as long as the query and objects remain in their respective safe regions.
This significantly improves the computation cost. As a byproduct, our framework also reduces the communication cost in client–server
architectures because an object does not report its location to the server unless it leaves its safe region or the server
sends a location update request. We also conduct a rigid cost analysis for our Euclidean space RkNN algorithm. We show that our techniques can also be applied to answer bichromatic RkNN queries in Euclidean space as well as in spatial networks. Furthermore, we show that our techniques can be extended for
the spatial networks that are represented by directed graphs. The extensive experiments demonstrate that our techniques outperform
the existing techniques by an order of magnitude in terms of computation cost and communication cost. 相似文献
12.
Yuxia Yao Xueyan Tang Ee-Peng Lim 《The VLDB Journal The International Journal on Very Large Data Bases》2009,18(1):99-117
Wireless sensor networks have been widely used in civilian and military applications. Primarily designed for monitoring purposes,
many sensor applications require continuous collection and processing of sensed data. Due to the limited power supply for
sensor nodes, energy efficiency is a major performance concern in query processing. In this paper, we focus on continuous
kNN query processing in object tracking sensor networks. We propose a localized scheme to monitor nearest neighbors to a query
point. The key idea is to establish a monitoring area for each query so that only the updates relevant to the query are collected.
The monitoring area is set up when the kNN query is initially evaluated and is expanded and shrunk on the fly upon object movement. We analyze the optimal maintenance
of the monitoring area and develop an adaptive algorithm to dynamically decide when to shrink the monitoring area. Experimental
results show that establishing a monitoring area for continuous kNN query processing greatly reduces energy consumption and prolongs network lifetime. 相似文献
13.
In a wireless mobile environment, data broadcasting provides an efficient way to disseminate data. Via data broadcasting, a server can provide location-based services to a large client population in a wireless environment. Among different location-based services, the k nearest neighbors (kNN) search is important and is used to find the k closest objects to a given point. However, the kNN search in a broadcast environment is particularly challenging due to the sequential access to the data on a broadcast channel. We propose efficient protocols for the kNN search on a broadcast R-tree, which is a popular multi-dimensional index tree, in a wireless broadcast environment in terms of latency and tuning time as well as memory usage. We investigate how a server schedules the broadcast and provide the corresponding kNN search algorithms at the mobile clients. One of our kNN search protocols further allows a kNN search to start at an arbitrary time instance and it can skip the waiting time for the beginning of a broadcast cycle, thereby reducing the latency. The experimental results validate that our mechanisms achieve the objectives. 相似文献
14.
Shichao Zhang 《Applied Intelligence》2011,35(1):123-133
Data preparation is an important step in mining incomplete data. To deal with this problem, this paper introduces a new imputation
approach called SN (Shell Neighbors) imputation, or simply SNI. The SNI fills in an incomplete instance (with missing values)
in a given dataset by only using its left and right nearest neighbors with respect to each factor (attribute), referred them
to Shell Neighbors. The left and right nearest neighbors are selected from a set of nearest neighbors of the incomplete instance. The size of
the sets of the nearest neighbors is determined with the cross-validation method. And then the SNI is generalized to deal
with missing data in datasets with mixed attributes, for example, continuous and categorical attributes. Some experiments
are conducted for evaluating the proposed approach, and demonstrate that the generalized SNI method outperforms the kNN imputation method at imputation accuracy and classification accuracy. 相似文献
15.
The similarity join has become an important database primitive for supporting similarity searches and data mining. A similarity join combines two sets of complex objects such that the result contains all pairs of similar objects. Two types of the similarity join are well-known, the distance range join, in which the user defines a distance threshold for the join, and the closest pair query or k-distance join, which retrieves the k most similar pairs. In this paper, we propose an important, third similarity join operation called the k-nearest neighbour join, which combines each point of one point set with its k nearest neighbours in the other set. We discover that many standard algorithms of Knowledge Discovery in Databases (KDD) such as k-means and k-medoid clustering, nearest neighbour classification, data cleansing, postprocessing of sampling-based data mining, etc. can be implemented on top of the k-nn join operation to achieve performance improvements without affecting the quality of the result of these algorithms. We propose a new algorithm to compute the k-nearest neighbour join using the multipage index (MuX), a specialised index structure for the similarity join. To reduce both CPU and I/O costs, we develop optimal loading and processing strategies. 相似文献
16.
Direction-based surrounder queries for mobile recommendations 总被引:1,自引:0,他引:1
Xi Guo Baihua Zheng Yoshiharu Ishikawa Yunjun Gao 《The VLDB Journal The International Journal on Very Large Data Bases》2011,20(5):743-766
Location-based recommendation services recommend objects to the user based on the user’s preferences. In general, the nearest
objects are good choices considering their spatial proximity to the user. However, not only the distance of an object to the
user but also their directional relationship are important. Motivated by these, we propose a new spatial query, namely a direction-based surrounder (DBS) query, which retrieves the nearest objects around the user from different directions. We define the DBS query not only
in a two-dimensional Euclidean space
\mathbbE{\mathbb{E}} but also in a road network
\mathbbR{\mathbb{R}} . In the Euclidean space
\mathbbE{\mathbb{E}} , we consider two objects a and b are directional close w.r.t. a query point q iff the included angle Daqb{\angle aqb} is bounded by a threshold specified by the user at the query time. In a road network
\mathbbR{\mathbb{R}} , we consider two objects a and b are directional close iff their shortest paths to q overlap. We say object a dominates object b iff they are directional close and meanwhile a is closer to q than b. All the objects that are not dominated by others based on the above dominance relationship constitute direction-based surrounders (DBSs). In this paper, we formalize the DBS query, study it in both the snapshot and continuous settings, and conduct extensive
experiments with both real and synthetic datasets to evaluate our proposed algorithms. The experimental results demonstrate
that the proposed algorithms can answer DBS queries efficiently. 相似文献
17.
Recently, Reverse k Nearest Neighbors (RkNN) queries, returning every answer for which the query is one of its k nearest neighbors, have been extensively studied on the database research community. But the RkNN query cannot retrieve spatio-textual objects which are described by their spatial location and a set of keywords. Therefore, researchers proposed a RSTkNN query to find these objects, taking both spatial and textual similarity into consideration. However, the RSTkNN query cannot control the size of answer set and to be sorted according to the degree of influence on the query. In this paper, we propose a new problem Ranked Reverse Boolean Spatial Keyword Nearest Neighbors query called Ranked-RBSKNN query, which considers both spatial similarity and textual relevance, and returns t answers with most degree of influence. We propose a separate index and a hybrid index to process such queries efficiently. Experimental results on different real-world and synthetic datasets show that our approaches achieve better performance. 相似文献
18.
Given a set D of trajectories, a query object q, and a query time extent Γ, a mutual (i.e., symmetric) nearest neighbor (MNN) query over trajectories finds from D, the set of trajectories that are among the k1 nearest neighbors (NNs) of q within Γ, and meanwhile, have q as one of their k2 NNs. This type of queries is useful in many applications such as decision making, data mining, and pattern recognition, as it considers both the proximity of the trajectories to q and the proximity of q to the trajectories. In this paper, we first formalize MNN search and identify its characteristics, and then develop several algorithms for processing MNN queries efficiently. In particular, we investigate two classes of MNN queries, i.e., MNNP and MNNT queries, which are defined with respect to stationary query points and moving query trajectories, respectively. Our methods utilize the batch processing and reusing technology to reduce the I/O cost (i.e., number of node/page accesses) and CPU time significantly. In addition, we extend our techniques to tackle historical continuous MNN (HCMNN) search for moving object trajectories, which returns the mutual nearest neighbors of q (for a specified k1 and k2) at any time instance of Γ. Extensive experiments with real and synthetic datasets demonstrate the performance of our proposed algorithms in terms of efficiency and scalability. 相似文献
19.
A new approach called shortest feature line segment (SFLS) is proposed to implement pattern classification in this paper, which can retain the ideas and advantages of nearest feature line (NFL) and at the same time can counteract the drawbacks of NFL. The proposed SFLS uses the length of the feature line segment satisfying given geometric relation with query point instead of the perpendicular distance defined in NFL. SFLS has clear geometric-theoretic foundation and is relatively simple. Experimental results on some artificial datasets and real-world datasets are provided, together with the comparisons between SFLS and other neighborhood-based classification methods, including nearest neighbor (NN), k-NN, NFL and some refined NFL methods, etc. It can be concluded that SFLS is a simple yet effective classification approach. 相似文献
20.
Nearest Neighbor (NN) search has been in the core of spatial and spatiotemporal database research during the last decade.
The literature on NN query processing algorithms so far deals with either stationary or moving query points over static datasets
or future (predicted) locations over a set of continuously moving points. With the increasing number of Mobile Location Services
(MLS), the need for effective k-NN query processing over historical trajectory data has become the vehicle for data analysis, thus improving existing or
even proposing new services. In this paper, we investigate mechanisms to perform NN search on R-tree-like structures storing
historical information about moving object trajectories. The proposed (depth-first and best-first) algorithms vary with respect
to the type of the query object (stationary or moving point) as well as the type of the query result (historical continuous
or not), thus resulting in four types of NN queries. We also propose novel metrics to support our search ordering and pruning
strategies. Using the implementation of the proposed algorithms on two members of the R-tree family for trajectory data (namely,
the TB-tree and the 3D-R-tree), we demonstrate their scalability and efficiency through an extensive experimental study using
large synthetic and real datasets.
相似文献
Yannis Theodoridis (Corresponding author)Email: URL: http://dke.cti.gr http://isl.cs.unipi.gr/db |