FINCH
Proceedings of the VLDB EndowmentPublished 1 August 2008
Wei Wu, Fei Yang, Chee-Yong Chan, Kian‐Lee Tan
Citations105
SJR quartileQ1
SJR score1.83
SNIP1.80
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An algorithm named INCH is presented that can compute a RkNN query's search region (from which the query result candidates are drawn) and a method that enables us to apply any RKNN algorithm on bichromatic Rknn queries.
Abstract
A Reverse k -Nearest-Neighbor (RkNN) query finds the objects that take the query object as one of their k nearest neighbors. In this paper we propose new solutions for evaluating RkNN queries and its variant bichromatic RkNN queries on 2-dimensional location data. We present an algorithm named INCH that can compute a RkNN query's search region (from which the query result candidates are drawn). In our RkNN evaluation algorithm called FINCH, the search region restricts the search space, and the search region is tightened each time a new result candidate is found. We also propose a method that enables us to apply any RkNN algorithm on bichromatic RkNN queries. With that, our FINCH algorithm is also used to evaluate bichromatic RkNN queries. Experiments show that our solutions are more efficient than existing algorithms.
Keywords
Computer ScienceEngineering
R-trees
6,543 Citations1984Antonin Guttman
A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.
Computational Geometry: Algorithms and Applications
4,507 Citations1997Mark de Berg, Otfried Cheong +2 more
This report documents the program and the outcomes of Dagstuhl Seminar 21181 “Computational Geometry”, which was held online in a virtual manner, and 36 participants from various countries attended it.
Computational Geometry
1,444 Citations2000Mark de Berg, Marc van Kreveld +2 more
Nearest neighbor queries
1,408 Citations1995Nick Roussopoulos, Stephen Kelley +1 more
This paper presents an efficient branch-and-bound R-tree traversal algorithm to find the nearest neighbor object to a point, and then generalizes it to finding the k nearest neighbors.
ACM SIGMOD RecordIndexing the positions of continuously moving objects
916 Citations2000Simonas Šaltenis, Christian S. Jensen +2 more
ACM Transactions on Database SystemsDistance browsing in spatial databases
877 Citations1999Gı́sli R. Hjaltason, Hanan Samet
The incremental nearest neighbor algorithm significantly outperforms the existing k-nearest neighbor algorithm for distance browsing queries in a spatial database that uses the R-tree as a spatial index and it is proved informally that at any step in its execution the incremental nearest neighbors algorithm is optimal with respect to the spatial data structure that is employed.
ACM SIGMOD RecordInfluence sets based on reverse nearest neighbor queries
517 Citations2000Flip Korn, S. Muthukrishnan
Indexing the positions of continuously moving objects
491 Citations2000Simonas Šaltenis, Christian S. Jensen +2 more
A novel, R*-tree based indexing technique that supports the efficient querying of the current and projected future positions of moving objects and is capable of indexing objects moving in one-, two-, and three-dimensional space is proposed.
Communications of the ACMEvolution of mobile location-based services
456 Citations2003Bharat Rao, Louis Minakakis
Utilizing user location as a key determinant of information requirement needs is suggested to improve the quality of information provided to marketers and decision-makers.
Proceedings - International Database Engineering and Applications SymposiumNearest neighbor and reverse nearest neighbor queries for moving objects
273 Citations2003Rimantas Benetis, Christian S. Jensen +2 more
An algorithm for answering RNN queries for continuously moving points in the plane for the nearest neighbor (NN) query is proposed and a separate contribution for answering NN queries for continuous moving points is also proposed.
Elsevier eBookskReverse NN Search in Arbitrary Dimensionality
270 Citations2004Yufei Tao, Dimitris Papadias +1 more
The proposed algorithms for exact processing of RkNN with arbitrary values of k on dynamic multidimensional datasets utilize a conventional data-partitioning index on the dataset and do not require any pre-computation.
Reverse Nearest Neighbor Queries for Dynamic Databases.
209 Citations2000Ioana Stanoi, Divyakant Agrawal +1 more
An algorithmic approach that is exible enough to support a larger class of RNN queries is proposed and the current method of nearest neighbor search is extended to that of conditional nearest neighbor.
The VLDB JournalNearest and reverse nearest neighbor queries for moving objects
198 Citations2006Rimantas Benetis, Christian S. Jensen +2 more
This paper proposes algorithms for k nearest and reverse k nearest neighbor queries on the current and anticipated future positions of points moving continuously in the plane based on the indexing of object positions represented as linear functions of time.
ACM SIGMOD RecordEnhanced nearest neighbour search on the R-tree
173 Citations1998King Lum Cheung, Ada Wai-Chee Fu
This paper proposes an improved nearest neighbor search algorithm on the R-tree and its variants, which lies in the removal of two hueristics that have been used in previous R*-tree work, which it is proved cannot improve on the pruning power during a search.
An index structure for efficient reverse nearest neighbor queries
167 Citations2002Congyun Yang, King-Ip Lin
A new index structure is introduced, the Rdnn-tree, that answers both RNN and NN queries efficiently and outperforms existing methods in various aspects, and makes the index structure extremely preferable in both static and dynamic cases.
High dimensional reverse nearest neighbor queries
147 Citations2003Amit Surendra Singh, Hakan Ferhatosmanoğlu +1 more
This paper proposes an approximate solution to answer RNN queries in high dimensions using a novel type of query Boolean Range Query (BRQ), which can efficiently answer NN, RNN, and its variants with approximately same number of I/O as running a NN query.
Efficient reverse k-nearest neighbor search in arbitrary metric spaces
128 Citations2006Elke Achtert, Christian Böhm +4 more
This paper proposes the first approach for efficient RkNN search in arbitrary metric spaces where the value of k is specified at query time and uses the advantages of existing metric index structures but proposes to use conservative and progressive distance approximations in order to filter out true drops and true hits.
Discovery of Influence Sets in Frequently Updated Databases
127 Citations2001Ioana Stanoi, Mirek Riedewald +2 more
SpringerReferenceIndexing the Positions of Continuously Moving Objects
126 Citations2011
The coming years will witness dramatic advances in wireless communications as well as positioning technologies, as a result, tracking the changing positions of objects capable of continuous movemen will be a major challenge.
Continuous Evaluation of Monochromatic and Bichromatic Reverse Nearest Neighbors
110 Citations2007James M. Kang, Mohamed F. Mokbel +3 more
Extensive experimental analysis shows that IGERN is efficient, is scalable, and outperforms previous techniques for continuous reverse nearest neighbor queries.
IEEE Transactions on Knowledge and Data EngineeringReverse Nearest Neighbor Search in Metric Spaces
108 Citations2006Yufei Tao, Man Lung Yiu +1 more
This paper presents the first algorithms for efficient RNN search in generic metric spaces that require no detailed representations of objects, and can be applied as long as their mutual distances can be computed and the distance metric satisfies the triangle inequality.
Continuous Reverse Nearest Neighbor Monitoring
82 Citations2006Tian Xia, Donghui Zhang
This paper defines the monitoring region for the CRNN query, discusses how to perform initial computation, and then focuses on incremental CRNN monitoring upon updates.
IEEE Transactions on Knowledge and Data EngineeringReverse nearest neighbors in large graphs
82 Citations2006Man Lung Yiu, Dimitris Papadias +2 more
A fundamental lemma is provided, which can be used to prune the search space while traversing the graph in search for RNN, and two RNN methods are developed; an eager algorithm that attempts to prunes network nodes as soon as they are visited and a lazy technique that prunes thesearch space when a data point is discovered.
Continuous Reverse k-Nearest-Neighbor Monitoring
54 Citations2008Wei Wu, Fei Yang +2 more
Experimental study shows that the CRkNN solution based on the proposed CRange-k refinement method is more efficient and scalable than the state-of-the- art CR kNN solution.