9/28/20091Continuous Nearest Neighbor Monitoring in Road NetworksK. Mouratidis1M.L. Yiu2, D. Papadias3, N. Mamoulis2Afsin AkdoganUniversity of Southern CaliforniaComputer Science Department1CS 599 - Geospatial Information ManagementIntroductionThe k-NN problem: Given a query point q and a set of objectsP,findthek objects in P that are closest to q.p4p32qp1p2p6p5p7CS 599 ‐ Geospatial Information ManagementIntroductionExisting methods are designed for Euclidean spaces.Consider a road network (where edge weights correspondto their length, or travel time). Queries and objects move inthe network.N2N3Network distance: the length (i.e., sum of weights) of theshortest path connecting them. (Example: taxi – pedestrians)3N1Network distance between [N1,N3] = [N1,N2] + [N2,N3] CS 599 ‐ Geospatial Information ManagementIntroductionContinuous NN monitoring in a Road Network:Queries and objects move in an unpredictable manner in thenetwork, issuing an update whenever they moveNetworkedges issue weight updatesCentral server processes the stream of updates, andcontinuously reports the k NNs of each query accordingto network distanceSample query:4CS 599 ‐ Geospatial Information ManagementSample Querypedestrian: query and taxis: data objects.- show me 2 closest taxis”CS 599 ‐ Geospatial Information Management5Objects and queries move in an unpredictable manner to different directions with different speeds.Related WorkEuclidean NN monitoring: Yu et al. ICDE’05, Xiong et al.ICDE’05, Mouratidis et al. SIGMOD’05YPK-CNN, SEA-CNN and CPM algorithms- Search in the cells around query- Grid index: cannot capture network-imposed constraintsCircles/rectangles:nomappingtonetworkdistancespace-Circles/rectangles:nomappingtonetworkdistancespace- Do not deal with edge updatesSnapshot NN in road networks: e.g., Papadias et al.VLDB’03, Kolahdouzan and Shahabi VLDB’04- Static data objects, One-time results6CS 599 ‐ Geospatial Information Management9/28/20092Incremental Monitoring (IMA) and Group Monitoring (GMA) AlgorithmsTwo methods (IMA, GMA) for: monitoring NNs according tonetwork distance, with low CPU cost.Edges: indexed with a quad-tree.ShdihStore eachedge with(i)the objects in it(ii)an influence listQueries: For each query we store its current NNs, and itsexpansion tree. (Memory consumption)7CS 599 ‐ Geospatial Information ManagementIMA: Initial NN computationInitial result (k=3): expansion tree, infl. intervals,andmarksq.kNN_dist = 7n3= 9An edge e affects q, if it contains an interval where the network dist is less than q.k-NNParts until marks are valid.q.kNN_dist = The network distance of furthest NN from qq= root. Retrieves kNNs with Dijkstra algorithmStore q in influence lists of affecting edgesTerminates when the next node has weight larger than q.kNN_dist8CS 599 ‐ Geospatial Information ManagementTypes of Object UpdatesOnly updates affecting the expansion tree can alter the result! (p5 not)(i) Current NNs moving within distance q.kNN_dist from q (e.g., p3)(ii) Incoming object: used to lie further than q.kNN_dist but their new location is closer to q than q.kNN_dist (e.g., p4)(iii) Outgoing object: current NNs moving further away than q.kNN_dist from q (e.g., p1)9CS 599 ‐ Geospatial Information ManagementIMA: Object updates (Case 1)Outgoing no more than incoming NNs:10At least k objects within distance q.kNN_distRemove outgoing NNs (p1)Calculate union of remaining NNs and incoming objects ((p3’,p2) U p4’)Report best k among themIn brief: update result and shrink expansion treeCS 599 ‐ Geospatial Information ManagementIMA: Object updates (Case 1)New (shrunk) expansion treeNew q.kNN_dist11CS 599 ‐ Geospatial Information ManagementIMA: Object updates (Case 2)More outgoing than incoming:Fewer k objects within distance q.kNNNotice: q.Tree grows according to the new q.kNN_dist !12In brief: re-compute from marks (not from q. it speeds things up) and expand treeCS 599 ‐ Geospatial Information Management9/28/20093IMA: Object updates (Case 2)New (grown) expansion treeNew q.kNN_dist13CS 599 ‐ Geospatial Information ManagementIMA: Query updatesRe-compute starting from valid tree marksValid expansion treen5 is reachable via a shorter path14Sub‐tree q’ remains valid and NNs as well. They are just subject to some trivial distance updates. The rest of the tree is discardedCS 599 ‐ Geospatial Information ManagementIMA: Edge updates - Weight increaseThere might exist shorter alternatives paths to objects in sub‐treen9 is reachable via shorter pathInvalid expansion tree15Updated Edge with higher weightCS 599 ‐ Geospatial Information ManagementIMA: Edge updates - Weight decreaseValid because all nodes therein become shorter by 2 unitsNewMarksUpdated Edgeold=3new=116QUESTION: Why did we set the new marks?Marks show valid parts. The update can NOT affect the paths to nodes/objects that lie closer than d(n7,q)=3, because any path passing through n1n7 has length at least d(n7,q)NewMarksold3new1CS 599 ‐ Geospatial Information ManagementGMA: Main ideaIntersection node: degree above 2 (e.g., n1, n2, n5)Terminal node: degree 1 (e.g., n8, n9, n4, n3)Sequence: path between consecutive intersection or terminal nodes{n1n8},{n1n7,n7n6,n6n5},{n2n5}…Lemma 1: The k-NN set of any query in sequence s is in theunion of (i) the objects in s, (ii) the k-NNs of its intersectionnodes (endpoints).17CS 599 ‐ Geospatial Information ManagementGMA: Main idea (example)Main ideaGMA groups together the queries falling in the same sequence and monitors static nodes (at the endpoints of the sequence), instead of each Objects on sequence between n1and n5={p4, p5}2-NNs of intersection n1={p1, p5}2-NNs of intersection n5={p3, p2}2-NNs of q1or q2 ∈ {p4, p5} ∪ {p1, p5} ∪ {p3, p2}n.k = the max number of NNs required by any query in n.Q18query individuallyCS 599 ‐ Geospatial Information Management9/28/20094GMA: Active nodesactive node: a node n is active if n is the endpoint on anysequence that has at least 1 query (e.g., n1, n5)GMA monitors the k-NNs of active nodes (using IMA), andusesthemtocomputetheNNsoftheactualuserqueriesusesthemtocomputetheNNsoftheactualuserqueriesGMA reduces CPU time by(i) shared execution among queries in the same sequence(ii) reduction from NN monitoring of moving queries to NNmonitoring of static active nodes.19CS 599 ‐ Geospatial Information ManagementGMA: Initial Result (2NN of q1)Mark for q1201. First Consider edge n1n7and add {p5} to q1.NN list2. Among the 2
View Full Document
Unlocking...