9/23/20091By: Kyriakos Mouratidis, Marios Hadjieleftheriou, and Dimitris PapadiasSIGMOD Conference, 2005Presented by Kaveh ShahabiCS 599 ‐ Geospatial Information Management ‐ Fall ‘09Sep 16th, 2009 Introduction Background, Definition, Motivation Related Work Safe Regions, Approximation, YPK‐CNN, SEA‐CNNCPMCPM NN module, Data structure, Handling Updates, Multiple Updates ANNs Analysis Analytical, Qualitative Results Conclusion NN: Finding the nearest neighbor to a query point in space Applications in GIS, Vision, Database, etc. kNN: returns top k nodes closest to the query point. CNN: Continuous Nearest Neighbor search Snapshot: One line query (B1 paper) Continuous: A series of queries and a monitoring system CkNN: the kthfirst CNN results Application: Continuouslylocating nearest gas stationswhile driving in a road CPM: Conceptual Partitioning and Monitoring Enhancing the performance and memory consumption in CNN searchesconsumption in CNN searches Extend to highly dynamic environments Extend for other types of queries (e.g. ANN) Snapshot: using an offline algorithm, all results are computed at once given the whole inputMonitoring: The client continuously asks for NN Monitoring: The client continuously asks for NN and a monitoring system on server should be optimized forsuch a case.9/23/20092 Zhang et. al.: Defines a region around query point (Voronai cell or expiry time) were re‐computation is not necessary Q‐index: a list of updates that influence a query is being kept using an R‐tree MQM: Each object has aresident domain assigned bythe serverqregionp Koudas et al.: e‐approximation kNN over streams of points“The returned kthNN lies at most e distance units The returned kNN lies at most e distance units farther from q than the actual kthNN of q” Is flexible with memory: more memory smaller e Both snapshot and continuous ekNN Yu et al. [YPK05]: regular grid cells with fixed sizeδ x δ as indexApplies the updates directly and re‐evaluates Applies the updates directly and reevaluates queries every T time units First time queries; a 2 step NN search Returning queries; update/re‐sort points inside the query region NN Module: Starts with a rectangle around q, then doubles the nearest distance and creates another box and continues till it finds k neighbors.p7p8p3p4p2qp5p1p10p6p9δR = 2 x dmax+ δ NN Module: Starts with a rectangle around q, then doubles the nearest distance and creates another box and continues till it finds k neighbors.p7p8p3p4p2qp5p1p10p6p9R = 2 x dmax+ δ NN Module: Starts with a rectangle around q, then doubles the nearest distance and creates another box and continues till it finds k neighbors.p7p8p3p4p2qp5p1p10p6p9R = 2 x dmax+ δ9/23/20093 NN Module: Starts with a rectangle around q, then doubles the nearest distance and creates another box and continues till it finds k neighbors.p7p8p3p4R p2qp5p1p10p6p9R = 2 x dmax+ δ NN Module: Starts with a rectangle around q, then doubles the nearest distance and creates another box and continues till it finds k neighbors.p7p8p3p4p2qp5p1p10p6p9R = 2 x dmax+ δ Update Handling: Assume p2moves. Now dmaxis max distance of previously discovered neighborsp7p8p3p4p2qp5p1p10p6p9R = 2 x dmax+ δ Update Handling: Assume p2moves. Now dmaxis max distance of previously discovered neighborsp7p8p3p4qp5p’2p1p10p6p9R = 2 x dmax+ δ Update Handling: Assume p2moves. Now dmaxis max distance of previously discovered neighbors.Only one rectangle needed.p7p8p3p4qp5p’2p1p10p6p9R = 2 x dmax+ δ SEA‐CNN.: Exclusively focuses on monitoring without any first‐time NN module. It also handles the special case of no neighbor node moving out.p7p8p3p4p2qp5p1p10p6p9δ• Uses circles instead of rectangles• Circle radius is the distance of the kthNN• If there is no node moving out then special case otherwise similar to YPK‐CNN9/23/20094 SEA‐CNN.: Exclusively focuses on monitoring without any first‐time NN module. It also handles the special case of no neighbor node moving out.p7p8p3p4p2qp5p1p10p6p9δ• Uses circles instead of rectangles• Circle radius is the distance of the kthNN• If there is no node moving out then special case otherwise similar to YPK‐CNN SEA‐CNN.: Exclusively focuses on monitoring without any first‐time NN module. It also handles the special case of no neighbor node moving out.p7p8p3p4qp5P’2p1p10p6p9δ• Uses circles instead of rectangles• Circle radius is the distance of the kthNN• If there is no node moving out then special case otherwise similar to YPK‐CNN SEA‐CNN.: Exclusively focuses on monitoring without any first‐time NN module. It also handles the special case of no neighbor node moving out.p7p8p3p4qp5P’2p1p10p6p9δ• Uses circles instead of rectangles• Circle radius is the distance of the kthNN• If there is no node moving out then special case otherwise similar to YPK‐CNN SEA‐CNN.: Exclusively focuses on monitoring without any first‐time NN module. It also handles the special case of no neighbor node moving out.p7p8p3p4p2qp5p1p10p6p9δ• Uses circles instead of rectangles• Circle radius is the distance of the kthNN• If there is no node moving out then special case otherwise similar to YPK‐CNN SEA‐CNN.: Exclusively focuses on monitoring without any first‐time NN module. It also handles the special case of no neighbor node moving out.p7p8p3p4p2q’ p5p1p10p6p9δ• Uses circles instead of rectangles• Circle radius is the distance of the kthNN• If there is no node moving out then special case otherwise similar to YPK‐CNN SEA‐CNN.: Exclusively focuses on monitoring without any first‐time NN module. It also handles the special case of no neighbor node moving out.p7p8p3p4p2q’ p5p1p10p6p9δ• Uses circles instead of rectangles• Circle radius is the distance of the kthNN• If there is no node moving out then special case otherwise similar to YPK‐CNN9/23/20095 Same grid cell with fixed size index structure. Uses circles to search cells (rectangles). If min_dist of a cell (rectangle) is larger than or equal to the distance of the discovered node (kthNN) then omit the cell. Terminates after discovering k NNs.NAÏVE APPROACH Main contribution is the rectangle shaped cells on the grid to index objectsRECTANGLESthe grid to index objects Insert each
View Full Document