text:
Group Nearest Neighbor Queries Dimitris Papadias† Qiongmao Shen† Yufei Tao§ Kyriakos Mouratidis† † § Department of Computer Science Department of Computer Science Hong Kong University of Science and Technology City University of Hong Kong Clear Water Bay, Hong Kong Tat Chee Avenue, Hong Kong {dimitris, qmshen, email@example.com firstname.lastname@example.com Abstract reverse nearest neighbor queries, where the goal is to Given two sets of points P and Q, a group nearest neighbor retrieve the data points whose nearest neighbor is a (GNN) query retrieves the point(s) of P with the smallest specified query point. Korn et al. [KMS02] study the same sum of distances to all points in Q. Consider, for instance, problem in the context of data streams. Given a query three users at locations q1, q2 and q3 that want to find a moving with steady velocity, [SR01, TP02] incrementally meeting point (e.g., a restaurant); the corresponding query maintain the NN (as the query moves), while [BJKS02, returns the data point p that minimizes the sum of Euclidean TPS02] propose techniques for continuous NN processing, distances |pqi| for 1≤i≤3. Assuming that Q fits in memory where the goal is to return all results up to a future time. and P is indexed by an R-tree, we propose several Kollios et al. [KGT99] develop various schemes for algorithms for finding the group nearest neighbors answering NN queries on 1D moving objects. An overview efficiently. As a second step, we extend our techniques for of existing NN methods for spatial and spatio-temporal situations where Q cannot fit in memory, covering both databases can be found in [TP03]. indexed and non-indexed query points. An experimental In this paper we discuss group nearest neighbor (GNN) evaluation identifies the best alternative based on the data queries, a novel form of NN search. The input of the and query properties. problem consists of a set P={p1,…,pN} of static data points in multidimensional space and a group of query points 1. Introduction Q={q1,…,qn}. The output contains the k (≥1) data point(s) Nearest neighbor (NN) search is one of the oldest problems with the smallest sum of distances to all points in Q. The in computer science. Several algorithms and theoretical distance between a data point p and Q is defined as performance bounds have been devised for exact and dist(p,Q)= i=1~n|pqi|, where |pqi| is the Euclidean distance ∑ approximate processing in main memory [S91, AMN+98]. between p and query point qi. As an example consider a Furthermore, the application of NN search to content-based database that manages (static) facilities (i.e., dataset P). The and similarity retrieval has led to the development of query contains a set of user locations Q={q1,…,qn} and the numerous cost models [PM97, WSB98, BGRS99, B00] and result returns the facility that minimizes the total travel indexing techniques [SYUK00, YOTJ01] for high- distance for all users. In addition to its relevance in dimensional versions of the problem. In spatial databases geographic information systems and mobile computing most of the work has focused on the point NN query that applications, GNN search is important in several other retrieves the k (≥1) objects from a dataset P that are closest domains. For instance, in clustering [JMF99] and outlier (usually according to Euclidean distance) to a query point detection [AY01], the quality of a solution can be evaluated q. The existing algorithms (reviewed in Section 2) assume by the distances between the points and their nearest cluster that P is indexed by a spatial access method and utilize centroid. Furthermore, the operability and speed of very some pruning bounds to restrict the search space. Shahabi large circuits depends on the relative distance between the et al. [SKS02] and Papadias et al. [PZMT03] deal with various components in them. GNN can be applied to detect nearest neighbor queries in spatial network databases, abnormalities and guide relocation of components [NO97]. where the distance between two points is defined as the Assuming that Q fits in memory and P is indexed by an R- length of the shortest path connecting them in the network. tree, we first propose three algorithms for solving this In addition to conventional (i.e., point) NN queries, recently problem. Then, we extend our techniques for cases that Q is there has been an increasing interest in alternative forms of too large to fit in memory, covering both indexed and non- spatial and spatio-temporal NN search. Ferhatosmanoglu et indexed query points. The rest of the paper is structured as al. [FSAA01] discover the NN in a constrained area of the follows. Section 2 outlines the related work on conventional data space. Korn and Muthukrishnan [KM00] discuss nearest neighbor search and top-k queries. Section 3 describes algorithms for the case that Q fits in memory and neighbor. In Figure 2.1a, for instance, an optimal algorithm Section 4 for the case that Q resides on the disk. Section 5 should visit only nodes R, N1, N2, and N6 (whereas DF also experimentally evaluates the algorithms and identifies the visits N4). The best-first (BF) algorithm of [HS99] achieves best one depending on the problem characteristics. Section the optimal I/O performance by maintaining a heap H with 6 concludes the paper with directions for future work. the entries visited so far, sorted by their mindist. As with DF, BF starts from the root, and inserts all the entries into 2. Related work H (together with their mindist), e.g., in Figure 2.1a, Following most approaches in the relevant literature, we H={<N1, mindist(N1,q)>, <N2, mindist(N2,q)>}. Then, at assume 2D data points indexed by an R-tree [G84]. The each step, BF visits the node in H with the smallest mindist. proposed techniques, however, are applicable to higher Continuing the example, the algorithm retrieves the content dimensions and other data-partition access methods such as of N1 and inserts all its entries in H, after which H={<N2, A-trees [SYUK00] etc. Figure 2.1 shows an R-tree for point mindist(N2,q)>, <N4, mindist(N4,q)>, <N3, mindist(N3,q)>}. set P={p1,p2,…,p12} assuming a capacity of three entries Similarly, the next two nodes accessed are N2 and N6 per node. Points that are close in space (e.g., p1, p2, p3) are (inserted in H after visiting N2), in which p11 is discovered clustered in the same leaf node (N3). Nodes are then as the current NN. At this time, the algorithm terminates recursively grouped together with the same principle until (with p11 as the final result) since the next entry (N4) in H is the top level, which consists of a single root. farther (from q) than p11. Both DF and BF can be easily Existing algorithms for point NN queries using R-trees extended for the retrieval of k>1 nearest neighbors. In follow the branch-and-bound paradigm, utilizing some addition, BF is also incremental. Namely, it reports the metrics to prune the search space. The most common such nearest neighbors in ascending order of their distance to the metric is mindist(N,q), which corresponds to the closest query, so that k does not have to be known in advance possible distance between q and any point in the subtree of (allowing different termination conditions to be used). node N. Figure 2.1a shows the mindist between point q and The branch-and-bound framework also applies to closest nodes N1, N2. Similarly, mindist(N1,N2) is the minimum pair queries that find the pair of objects from two datasets, possible distance between any two points that reside in the such that their distance is the minimum among all pairs. sub-trees of nodes N1 and N2. [HS98, CMTV00] propose various algorithms based on the concepts of DF and BF traversal. The difference from NN R N1 N2 is that the algorithms access two index structures (one for each data set) simultaneously. If the mindist of two N1 N2 N3 N4 N5 N6 intermediate nodes Ni and Nj (one from each R-tree) is already greater than the distance of the closest pair of p1 p2 p3 p4 p5 p6 objects found so far, the sub-trees of Ni and Nj cannot N3 N4 contain a closest pair (thus, the pair is pruned). p7 p8 p9 p10 p11 p12 As shown in the next section, a processing technique for N5 N6 GNN queries applies multiple conventional NN queries (a) Points and node extents (b) The corresponding R-tree (one for each query point) and then combines their results. Figure 2.1: Example of an R-tree and a point NN query Some related work on this topic has appeared in the literature of top-k (or ranked) queries over multiple data The first NN algorithm for R-trees [RKV95] searches the repositories (see [FLN01, BCG02, F02] for representative tree in a depth-first (DF) manner. Specifically, starting from papers). As an example, consider that a user wants to find the root, it visits the node with the minimum mindist from q the k images that are most similar to a query image, where (e.g., N1 in Figure 2.1). The process is repeated recursively similarity is defined according to n features, e.g., color until the leaf level (node N4), where the first potential histogram, object arrangement, texture, shape etc. The nearest neighbor is found (p5). During backtracking to the query is submitted to n retrieval engines that return the best upper level (node N1), the algorithm only visits entries matches for particular features together with their similarity whose minimum distance is smaller than the distance of the scores, i.e., the first engine will output a set of matches nearest neighbor already retrieved. In the example of Figure according to color, the second according to arrangement 2.1, after discovering p5, DF will backtrack to the root level and so on. The problem is to combine the multiple inputs in (without visiting N3), and then follow the path N2,N6 where order to determine the top-k results in terms of their overall the actual NN p11 is found. similarity. The DF algorithm is sub-optimal, i.e., it accesses more The main idea behind all techniques is to minimize the nodes than necessary. In particular, as proven in [PM97], an extent and cost of search performed on each retrieval optimal algorithm should visit only nodes intersecting the engine in order to compute the final result. The threshold vicinity circle that centers at the query point q and has algorithm [FLN01] works as follows (assuming retrieval of radius equal to the distance between q and its nearest the single best match): the first query is submitted to the dist(p11,Q), it is possible that there exists a point in P whose first search engine, which returns the closest image p1 distance to Q is smaller than dist(p11,Q). So MQM retrieves according to the first feature. The similarity between p1 and the second NN of q1 (p11, which has already been the query image with respect to the other features is encountered by q2) and updates the threshold t1 to |p11q1| computed. Then, the second query is submitted to the (=3). Since T (=6) now equals the summed distance second search engine, which returns p2 (best match between the best neighbor found so far and the points of Q, according to the second feature). The overall similarity of MQM terminates with p11 as the final result. In other words, p2 is also computed, and the best of p1 and p2 becomes the every non-encountered point has distance greater or equal current result. The process is repeated in a round-robin to T (=6), and therefore it cannot be closer to Q (in the fashion, i.e., after the last search engine is queried, the global sense) than p11. second match is retrieved with respect to the first feature and so on. The algorithm will terminate when the similarity of the current result is higher than the similarity that can be achieved by any subsequent solution. In the next section we adapt this approach to GNN processing. 3. Algorithms for memory-resident queries Assuming that the set Q of query points fits in memory and that the data points are indexed by an R-tree, we present three algorithms for processing GNN queries. For each algorithm we first illustrate retrieval of a single nearest neighbor, and then show the extension to k>1. Table 3.1 contains the primary symbols used in our description (some Figure 3.1: Example of a GNN query have not appeared yet, but will be clarified shortly). Figure 3.2 shows the pseudo code for MQM (1NN), where Symbol Description Q set of query points best_dist (initially ∞) is the distance of the best_NN found Qi a group of queries that fits in memory so far. In order to achieve locality of the node accesses for n (ni) number of queries in Q (Qi) individual queries, we sort the points in Q according to their M (Mi) MBR of Q (Qi) Hilbert value; thus, two subsequent queries are likely to q centroid of Q correspond to nearby points and access similar R-tree dist(p,Q) sum of distances between nodes. The algorithm for computing nearest neighbors of point p and query points in Q query points should be incremental (e.g., best-first search mindist(N,q) minimum distance between discussed in Section 2) because the termination condition is MBR of node N and centroid q not known in advance. The extension for the retrieval of k mindist(p,M) minimum distance between (>1) nearest neighbors is straightforward. The k neighbors data point p and query MBR M with the minimum overall distances are inserted in a list of ∑ n ⋅ mindist ( N ,M ) i i weighted mindist of node N k pairs <p, dist(p,Q)> (sorted on dist(p,Q)) and best_dist with respect to all query groups equals the distance of the k-th NN. Then, MQM proceeds in Table 3.1: Frequently used symbols the same way as in Figure 3.2, except that whenever a better 3.1 Multiple query method neighbor is found, it is inserted in best_NN and the last element of the list is removed. The multiple query method (MQM) utilizes the main idea of the threshold algorithm, i.e., it performs incremental NN MQM(Q: group of query points) queries for each point in Q and combines their results. For /* T : threshold ; best_dist distance of the current NN*/ sort points in Q according to Hilbert value; instance, in Figure 3.1 (where Q ={q1,q2}), MQM retrieves for each query point: ti=0; the first NN of q1 (point p10 with |p10q1|=2) and computes T=0; best_dist=∞; best_NN=null; //Initialization the distance |p10q2| (=5). Similarly, it finds the first NN of q2 while (T < best_dist) (point p11 with |p11q2|=3) and computes |p11q1|(=3). The get the next nearest neighbor pj of the next query point qi; point (p11) with the minimum sum of distances ti = |pjqi|; update T; (|p11q1|+|p11q2|=6) to all query points becomes the current if dist(pj,Q)<best_dist GNN of Q. best_NN =pj; //Update current GNN of Q For each query point qi, MQM stores a threshold ti, which is best_dist = dist(pj,Q) ; end of while; the distance of the current NN, i.e., t1=|p10q1|=2 and return best_NN; t2=|p11q2|=3. The total threshold T is defined as the sum of all thresholds (=5). Continuing the example, since T < Figure 3.2: The MQM algorithm 3.2 Single point method In particular, by applying an incremental point NN query at q, we stop when we find the first point p such that: n⋅|pq| − MQM may incur multiple accesses to the same node (and dist(q,Q) ≥ dist(best_NN,Q). By Lemma 1, dist(p,Q) ≥ retrieve the same data point, e.g., p11) through different n⋅|pq|−dist(q,Q) and, therefore, dist(p,Q) ≥ dist(best_NN,Q). queries. To avoid this problem, the single point method The same idea can be used for pruning intermediate nodes, (SPM) processes GNN queries by a single traversal. First, as summarized by the following heuristic. SPM computes the centroid q of Q, which is a point in space with a small value of dist(q,Q) (ideally, q is the point Heuristic 1: Let q be the centroid of Q and best_dist be the with the minimum dist(q,Q)). The intuition behind this distance of the best GNN found so far. Node N can be approach is that the nearest neighbor is a point of P "near" pruned if: q. It remains to derive (i) the computation of q, and (ii) the best_dist +dist (q,Q ) mindist (N ,q ) ≥ range around q in which we should look for points of P, n before we conclude that no better NN can be found. where mindist(N,q) is the minimum distance between the Towards the first goal, let (x,y) be the coordinates of MBR of N and the centroid q. An example of the heuristic centroid q and (xi,yi) be the coordinates of query point qi. is shown in Figure 3.3, where the best_dist = 5+4. Since, The centroid q minimizes the distance function: dist(q,Q)=1+2, the right part of the inequality equals 6, n meaning that both nodes in the figure will be pruned. dist (q, Q ) = ∑ ( x - xi ) 2 + ( y − yi )2 i =1 Since the partial derivatives of function dist(q,Q) with respect to its independent variables x and y are zero at the centroid q, we have the following equations: ∂ dist ( q, Q ) n x − xi =∑ =0 ∂x i =1 ( x − xi ) 2 + ( y − yi ) 2 ∂ dist ( q, Q ) y − yi n =∑ =0 Figure 3.3: Pruning of nodes in SPM ∂y i =1 ( x − xi ) 2 + ( y − yi ) 2 Based on the above observations, it is straightforward to implement SPM using the depth-first or best-first Unfortunately, the above equations cannot be solved into paradigms. Figure 3.4 shows the pseudo-code of DF SPM. closed form for n>2, or in other words, they must be Starting from the root of the R-tree (for P), entries are evaluated numerically, which implies that the centroid is sorted in a list according to their mindist from the query approximate. In our implementation, we use the gradient centroid q and are visited (recursively) in this order. Once descent [HYC01] method to quickly obtain a good the first entry with mindist(Nj,q) ≥ (best_dist+dist(q,Q))/n approximation. Specifically, starting with some arbitrary has been found, the subsequent ones in the list are pruned. initial coordinates, e.g. x=(1/n) i=1~nxi and, y=(1/n) i=1~nyi, ∑ ∑ The extension to k (>1) GNN queries is the same as the method modifies the coordinates as follows: conventional (point) NN algorithms. ∂ dist (q, Q) ∂ dist (q, Q ) x = x −η and y = y − η , SPM(Node: R-tree node, Q: group of query points) ∂x ∂y /* q: the centroid of Q*/ where is a step size. The process is repeated until the ŋ if Node is an intermediate node distance function dist(q,Q) converges to a minimum value. sort entries Nj in Node according to mindist(Nj,q) in list; Although the resulting point q is only an approximation of repeat get_next entry Nj from list; the ideal centroid, it suffices for the purposes of SPM. Next if mindist(Nj,q)< (best_dist+dist(q,Q))/n; /* Heuristic 1 we show how q can be used to prune the search space based SPM(Nj,Q); /* recursion*/ on the following lemma. until mindist(Nj,q) ≥ (best_dist+dist(q,Q))/n or end of list; Lemma 1: Let Q={q1,…,qn} be a group of query points and else if Node is a leaf node q an arbitrary point in space. The following inequality holds sort points pj in Node according to mindist(pj,q) in list; for any point p: dist(p,Q) ≥ n⋅|p q| - dist(q,Q), where |pq| repeat denotes the Euclidean distance between p and q. get_next entry pj from list; if |pjq|<(best_dist+dist(q,Q))/n; /* Heuristic 1 for points Proof: Due to the triangular inequality, for each query point if dist(pj,Q)< best_dist qi we have that: |pqi|+|qiq|≥|pq|. By summing up the n best_NN =pj; //Update current GNN inequalities: best_dist = dist(pj,Q) ; ∑ |pq | + ∑ |q q| ≥ n⋅|pq| qi ∈Q i qi ∈Q i ⇒ dist (p,Q ) ≥ n⋅|pq|-dist (q,Q ) until |pjq|≥ (best_dist+dist(q,Q))/n or end of list; return best_NN; Lemma 1 provides a threshold for the termination of SPM. Figure 3.4: The SPM algorithm 3.3 Minimum bounding method represent the tightest condition for successful node visits; i.e., it is possible for a node to satisfy the heuristic and still Like SPM, the minimum bounding method (MBM) not contain qualifying points. Consider, for instance, Figure performs a single query, but uses the minimum bounding 3.6, which includes 3 query points. The current best_dist is rectangle M of Q (instead of the centroid q) to prune the 7, and node N3 passes heuristic 3, since mindist(N3,q1) + search space. Specifically, starting from the root of the R- mindist(N3,q2) + mindist(N3,q3) = 5. Nevertheless, N3 tree for dataset P, MBM visits only nodes that may contain should not be visited, because the minimum distance that candidate points. In the sequel, we discuss heuristics for can be achieved by any point in N3 is greater than 7. The identifying such qualifying nodes. dotted lines in Figure 3.6 correspond to the distance Heuristic 2: Let M be the MBR of Q, and best_dist be the between the best possible point p' (not necessarily a data distance of the best GNN found so far. A node N cannot point) in N3 and the three query points. contain qualifying points, if: best_dist mindist (N ,M ) ≥ n where mindist(N,M) is the minimum distance between M and N, and n is the cardinality of Q. Figure 3.5 shows a group of query points Q={q1,q2} and the best_NN with best_dist=5. Since mindist(N1,M) = 3 > best_dist/2 = 2.5, N1 can be pruned without being visited. In other words, even if there is a data point p at the upper-right corner of N1 Figure 3.6: Example of a hypothetical optimal heuristic and all the query points were at the lower right corner of Q, it would still be the case that dist(p,Q)> best_dist. The Assuming that we can identify the best point p' in the node, concept of heuristic 2 also applies to the leaf entries. When we can obtain a tight heuristic a follows: if the distance of a point p is encountered, we first compute mindist(p,M) p' is smaller than best_dist visit the node; otherwise, reject from p to the MBR of Q. If mindist(p,M) best_dist/n, p is ≥ it. The combination of the best-first approach with this discarded since it cannot be closer than the best_NN. In this heuristic would lead to an I/O optimal method (such as the way we avoid performing the distance computations algorithm of [HS99] for conventional NN queries). Finding between p and the points of Q. point p', however, is similar to the problem of locating the query centroid (but this time in a region constrained by the node MBR), which, as discussed in Section 3.2, can only be solved numerically (i.e., approximately). Although an approximation suffices for SPM, for the correctness of best_dist it is necessary to have the precise solution (in order to avoid false misses). As a result, this hypothetical heuristic cannot be applied for exact GNN retrieval. Figure 3.5: Example of heuristic 2 Heuristics 2 and 3 can be used with both the depth-first and best-first traversal paradigms. For simplicity, we discuss The heuristic incurs minimum overhead, since for every MBM based on depth-fist traversal using the example of node it requires a single distance computation. However, it Figure 3.7. The root of the R-tree is retrieved and its entries is not very tight, i.e., it leads to unnecessary node accesses. are sorted by their mindist to M. Then, the node (N1) with For instance, node N2 (in Figure 3.5) passes heuristic 2 (and the minimum mindist is visited, inside which the entry of N4 should be visited), although it cannot contain qualifying has the smallest mindist. Points p5, p6, p4 (in N4) are points. Heuristic 3 presents a tighter bound for avoiding processed according to the value of mindist(pj,M) and p5 such visits. becomes the current GNN of Q (best_dist=11). Points p6 Heuristic 3: Let best_dist be the distance of the best GNN and p4 have larger distances and are discarded. When found so far. A node N can be safely pruned if: backtracking to N1, the subtree of N3 is pruned by heuristic ∑ mindist (N ,qi ) ≥ best_dist qi ∈Q 2. Thus, MBM backtracks again to the root and visits nodes N2 and N6, inside which p10 has the smallest mindist to M where mindist(N,qi) is the minimum distance between N and and is processed first, replacing p5 as the GNN query point qi ∈ Q. In Figure 3.5, since mindist(N2, q1) + (best_dist=7). Then, p11 becomes the best NN mindist(N2, q2) = 6 > best_dist = 5, N2 is pruned. (best_dist=6). Finally, N5 is pruned by heuristic 2, and the Because heuristic 3 requires multiple distance computations algorithm terminates with p11 as the final GNN. The (one for each query point) it is applied only for nodes that extension to retrieval of kNN and the best-first pass heuristic 2. Note that (like heuristic 2) heuristic 3 does implementation are straightforward. p1 p3 p4 p6 equal to dist(pi,qj). Heuristic 4 is applied in two cases: (i) N4 for each output pair <pi,qj>, on the data point pi and (ii) N3 N1 p5 when the global NN changes, on all qualifying points. 5 Every point p that fails the heuristic is deleted from the p2 8 6 q2 qualifying list. If p is encountered again in a subsequent q1 M 3 pair, it will be considered as a new point and pruned. Figure 2 5 3 p11 4.1a shows an example where the closest pairs are found 11 p10 N6 incrementally according to their distance i.e., (<p1,q1>, 2), p12 p8 p9 N2 (< p1,q2>, 2), (< p2,q1>, 3), (< p2,q3>, 3), (< p3,q3>, 4), N5 (<p2,q2>, 5). After pair <p2,q2> is output, we have a p7 complete NN, p2 with global distance 11. Heuristic 4 is Figure 3.7: Query processing of MBM applied to all qualifying points and p3 is discarded; even if its (non yet discovered) distances to q1 and q2 equal 5, its 4. Algorithms for disk-resident queries global distance will be 14 (i.e., greater than best_dist). We now discuss the situation that the query set does not fit in main memory. Section 4.1 considers that Q is indexed by an R-tree, and shows how to adapt the R-tree closest pair (CP) algorithm [HS98, CMTV00] for GNN queries with additional pruning rules. We argue, however, that the R-tree on Q offers limited benefits towards reducing the query time. Motivated by this, in Sections 4.2 and 4.3 we develop two alternative methods, based on MQM and MBM, which do not require any index on Q. Again, for simplicity, we (a) Discovery of 1st NN (b) Termination describe the algorithms for single NN retrieval before Figure 4.1: Example of GCP discussing k>1. For each remaining qualifying point pi, we compute a 4.1 Group closest pairs method threshold ti as: ti=(best_dist-curr_dist(pi)) / (n-counter(pi)). In the general case, that multiple qualifying points exist, the Assume an incremental CP algorithm that outputs closest global threshold T is the maximum of individual thresholds pairs <pi,qj> (pi∈P, qj∈Q) in ascending order of their ti, i.e., T is the largest distance of the output closest pair that distance. Consider that we keep the count(pi) of pairs in can lead to a better solution than the existing one. In Figure which pi has appeared, as well as, the accumulated distance 4.1a, for instance, T=t1=7, meaning that when the output (curr_dist(pi)) of pi in all these pairs. When the count of pi pair has distance ≥ 7, the algorithm can terminate. Every equals the cardinality n of Q, the global distance of pi, with application of heuristic 4 also modifies the corresponding respect to all query points, has been computed. If this thresholds, so that the value of T is always up to date. Based distance is smaller than the best global distance (best_dist) on these observations we are now ready to establish the found so far, pi becomes the current NN. termination condition, i.e., GCP terminates when (i) at least Two questions remain to be answered: (i) which are the a GNN has been found (best_dist<∞) and (ii) the qualifying qualifying data points that can lead to a better solution? (ii) list is empty, or the distance of the current pair becomes when can the algorithm terminate? Regarding the first larger than the global threshold T. Figure 4.1b continues the question, clearly all points encountered before the first example of Figure 4.1a. In this case the algorithm complete NN is found, are qualifying. Every such point pi is terminates after the pair (< p1,q3>, 6.3) is found, which kept in a list < pi, count(pi), curr_dist(pi)>. On the other establishes p1 as the best NN (and the list becomes empty). hand, if we already have a complete NN, every data point The pseudo-code of the GCP is shown in Figure 4.2. We that is encountered for the first time can be discarded since store the qualifying list as an in-memory hash table on point it cannot lead to a better solution. In general, the list of ids to facilitate the retrieval of information (i.e., counter(pi), qualifying points keeps increasing until a complete NN is curr_dist(pi)) about particular points (pi). If the size of the found. Then, non-qualifying points can be gradually list exceeds the available memory, part of the table is stored removed from the list based on the following heuristic: to the disk1. In case of kNN queries, best_dist equals the Heuristic 4: Assume that the current output of the CP global distance of the k-th complete neighbor found so far algorithm is <pi,qj>. We can immediately discard all points (i.e., pruning in the qualifying list can occur only after k p such that: complete neighbors are retrieved). (n-counter(p))⋅ dist(pi,qj) + curr_dist(p) ≥ best_dist 1 In other words, p cannot yield a global distance smaller In the worst case, the list may contain an entry for each point of than best_dist, even if all its un-computed distances are P. GCP alleviate the problem, Hjaltason and Samet [HS99] best_NN = NULL; best_dist = ∞; /* initialization proposed a heap management technique (included in our repeat implementation), according to which, part of the heap output next closest pair <pi,qj> and dist(pi,qj) migrates to the disk when its size exceeds the available if pi is not in list memory space. Nevertheless, as shown in Section 5, the if best_dist < ∞ continue; /* discard pi and process next pair cost of GCP is often very high, which motivates the else add < pi, 1, dist(pi,qj)> in list; subsequent algorithms. else /* pi has been encountered before and still resides in list counter(pi)++; curr_dist(pi)= curr_dist(pi)+ dist(pi,qj); p if counter(pi)= n 1 q 1 q 2 if curr_dist(pi)< best_dist best_NN = pi; //Update current GNN q 3 p 2 q 4 best_dist = curr_dist(pi); T=0; Q fo ecap sk ro w for each candidate point p in list q 5 if (n-counter(p))⋅ dist(pi,qj)+curr_dist(p) ≥ best_dist P fo ecapskro w remove p from list; /* pruned by heuristic 6 p 3 else /* p not pruned by heuristic 6 t= (best_dist-curr_dist(p)) / (n-counter(p)); (a) High pruning (b) Low pruning if t > T then T = t; /* update threshold Figure 4.3: Observations about the performance of GCP else remove pi from list; else /* counter(pi)< n 4.2 F-MQM if best_dist < ∞ /* a NN has been found already if (n-counter(pi))⋅ dist(pi,qj)+curr_dist(pi) ≥ best_dist MQM can be applied directly for disk-resident, non- remove pi from list; /* pruned by heuristic 6 indexed Q, with however, very high cost due to the large else /*not pruned by heuristic 6 number of individual queries that must be performed (as ti= (best_dist-curr_dist(pi)) / (n-counter(pi)); shown in Section 5, its cost increases fast with the if ti > T then T = ti; /* update threshold cardinality of Q). In order to overcome this problem, we until (best_dist < ∞) and (dist(pi,qj) ≥ T or list is empty); propose F-MQM (file-multiple query method), which splits return best_NN; Q into blocks {Q1, .., Qm} that fit in memory. For each Figure 4.2: The GCP algorithm block, it computes the GNN using one of the main memory When the workspace (i.e., MBR) of Q is small and algorithms (we apply MBM due to its superior performance contained in the workspace of P, GCP can terminate after - see Section 5), and finally it combines their results using outputting a small percentage of the total number of closest MQM. The complication is that once a NN of a group has pairs. Consider, for instance, Figure 4.3a, where there exist been retrieved, we cannot effectively compute its global some points of P (e.g., p2) that are near all query points. distance (i.e., with respect to all data points) immediately. The number of closest pairs that must be considered Instead, we follow a lazy approach: first we find the GNN depends only on the distance between p2 and its farthest p1 of the first group Q1; then, we load in memory the second neighbor (q5) in Q. Data point p3, for example, will not group Q2 and retrieve its NN p2. At the same time, we also participate in any output closest pair since its nearest compute the distance between p1 and Q2, whose current distance to any query point is larger than |p2q5|. distance becomes curr_dist(p1) = dist(p1,Q1) + dist(p1,Q2). Similarly, when we load Q3, we update the current distances On the other hand, if the MBR of Q is large or partially of p1 and p2 taking into account the objects of the third overlaps (or is disjoint) with the workspace of P, GCP must group. After the end of the first round, we only have one output many closest-pairs before it terminates. Figure 4.3b, data point (p1), whose global distance with respect to all shows such an example, where the distance between the query points has been computed. This point becomes the best_NN (p2) and its farthest query point (q2) is high. In current NN. addition to the computational overhead of GCP in this case, another disadvantage is its large heap requirements. Recall The process is repeated in a round robin fashion and at each that GCP applies an incremental CP algorithm that must step a new global distance is derived. For instance, when keep all closest pairs in the heap until the first NN is found. we read again the first group (to retrieve its second NN), The number of such pairs in the worst case equals the the distance of p2 (first NN of Q2) is completed with respect cardinality of the Cartesian product of the datasets 2 . To to all groups. Between p1 and p2, the point with the minimum global distance becomes the current NN. As in 2 This may happen if there is a data point (on the corner of the the case of MQM, the threshold tj for each group Qj equals workspace) such that (i) its distance to most query points is very dist(pj,Qj), where pj is the last retrieved neighbor of Qj. The small (so that the point cannot be pruned) and (ii) its distance to global threshold T is the sum of all thresholds. F-MQM a query point (located on the opposite corner of the workspace) terminates when T becomes equal or larger than the global is the largest possible. distance of the best NN found so far. The algorithm is illustrated in Figure 4.4. In order to differs, e.g., the last page may be half-full). For each group achieve locality, we first sort (externally) the points of Q Qi, we keep in memory its MBR Mi and ni (but not its according to their Hilbert value. Then, each group is contents). F-MBM descends the R-tree of P (in DF or BF obtained by taking a number of consecutive pages that fit in traversal), only following nodes that may contain qualifying memory. The extension for the retrieval of k (>1) GNNs is points. Given that we have the values of Mi and ni for each similar to main-memory MQM. In particular, best_NN is query group in memory, we can quickly identify qualifying now a list of k pairs <p, dist(p,Q)> (sorted by the global nodes as follows. dist(p,Q)) and best_dist equals the distance of the k-th NN. Heuristic 5: Let best_dist be the distance of the best GNN Then, it proceeds in the same way as in Figure 4.4. found so far and Mi be the MBR of group Qi. A node N can be safely pruned if: F-MQM(Q: group of query points) best_NN = NULL; best_dist = ∞; T=0; /* initialization ∑ ni ⋅ mindist (N ,M i ) ≥ best_dist Qi ∈Q sort points of Q according to Hilbert value and split them into groups {Q1, .., Qm} so that each group fits in memory; We refer to the left part of the inequality as the weighted while (T < best_dist) mindist of N. Figure 4.5 shows an example, where 5 query read next group Qj; points are split into two groups with MBRs M1, M2 and get the next nearest neighbor pj of group Qj ; best_dist = 20. According to heuristic 5, N can be pruned curr_dist(pj)= dist(pj,Qj) ; tj = dist(pj,Qj); update T; because its weighted mindist (2⋅mindist(N,M1) + if it is the first pass of the algorithm 3⋅mindist(N,M2)) is 20, and it cannot contain a better NN. for each cur. neighbor pi of Qi (1≤i<j) /*update other NN curr_dist(pi)= curr_dist(pi) + dist(pi,Qj) ; else /*local NN have been computed for all m groups for each cur. neighbor pi of Qi (1≤i≤m,i≠j) /*update other NN curr_dist(pi)= curr_dist(pi) + dist(pi,Qj) ; next=(j+1) modulo m; /*group whose global dist. is complete if curr_dist(pnext)<best_dist best_NN =pnext; /*update current GNN of Q best_dist = curr_dist(pnext) ; Figure 4.5: Example of heuristic 5 next=(j+1) modulo m; /*next group to process end while; When a leaf node N is reached, we have to compute the return best_NN; global distance of its data points with all groups. Initially Figure 4.4: The F-MQM algorithm the current distance curr_dist(pj) of each point pj ∈ N is set to 0. Then, for each new group Qi (1≤i≤m) that is loaded in F-MQM is expected to perform well if the number of query memory, curr_dist(pj) is updated as curr_dist(pj)+ groups is relatively small, minimizing the number of dist(pj,Qi). We can reduce the CPU-overhead of the applications of the main memory algorithm. On the other distance computations based on the following heuristic. hand, if there are numerous groups, the combination of the Heuristic 6: Let curr_dist(pj) be the accumulated distance individual results may be expensive. Furthermore, as in the of data point pj with respect to groups Q1,.., Qi-1. Then, pj case of (main-memory) MQM, the algorithm may perform can be safely excluded from further consideration if: redundant computations, if it encounters the same data n point as a nearest neighbor of different query groups. A curr _ dist (p j )+∑ nl ⋅ mindist (p j ,M l ) ≥ best_dist possible optimization is to keep each NN in memory, l=i together with its distances to all groups, so that we avoid Figure 4.6 shows an example of heuristic 6, where the first these computations if the same point is encountered later group Q1 has been processed and curr_dist(pj) = dist(pj,Q1) through another group. This however, may not be possible = 5+3. Point pj is not compared with the query points of Q2, if the main memory size is limited. since 8+3⋅mindist(pj,M2)=20 is already equal to best_dist. Thus, pj will not be considered for further computations 4.3 F-MBM (i.e., when subsequent groups are loaded in memory). We can extend both SPM and MBM for the case that Q does not fit in memory. Since, as shown in the experiments, MBM is more efficient, here we describe F-MBM, an adaptation of the minimum bounding method. First, the points of Q are sorted by their Hilbert value and are inserted in pages according to this order. A page Qi contains ni points (it is possible that the number of points Figure 4.6: Example of heuristic 6 The final clarification regards the order according to which and Nebraska. For all experiments we use a Pentium qualifying nodes and query groups are accessed. For nodes 2.4GHz CPU with 1GByte memory. The page size of the we use the weighted mindist, based on the intuition that R*-trees [BKSS00] is set to 1KByte, resulting in a capacity nodes with small values are likely to lead to neighbors with of 50 entries per node. All implementations are based on small global distance, so that subsequent visits can be the best-first traversal. Both versions of MQM and GCP pruned by heuristic 5. When a leaf node N has been require BF due to their incremental behavior. SPM and reached, each group Qi is read in memory in descending MBM (or F-MBM) could also be used with DF. order of mindist(N,Mi). The motivation is that groups that are far from the node are likely to prune numerous data 5.1 Comparison of algorithms for memory-resident points (thus, saving the distance computations for these queries points with respect to other groups). Figure 4.7 shows the We first compare the methods of Section 3 (MQM, SPM pseudo-code of F-MBM based on DF traversal (the BF and MBM) for main-memory queries. For this purpose, we implementation is similar). use workloads of 100 queries. Each query has a number n F-MBM(Node: R-tree node, Q: group of query points) of points, distributed uniformly in a MBR of area M, which /* Q consists of {Q1, .., Qm} that fit in memory is randomly generated in the workspace of P. The values of if Node is an intermediate node n and M are identical for all queries in the same workload sort entries Nj in Node (according to weighted mindist) in list; (i.e., the only change between two queries in the same repeat workload is the position of the query MBR). First we study get_next entry Nj from list; the effect of the cardinality of Q, by fixing M to 8% of the if weighted mindist(Nj)< best_dist /*N passes heuristic 5 workspace of P and the number k of retrieved group nearest F-MBM(Nj, Q) ; /* Recursion neighbors to 8. Figure 5.1 shows the average number of until weighted mindist(Nj)≥ best_dist or end of list; else if Node is a leaf node node accesses (NA) and CPU cost as functions of n for sort points pj in Node (according to weighted mindist) in list; datasets PP and TS. for each point pj in list : curr_dist(pj)=0; /* initialization MQM SPM MBM sort groups Qi in descending order of mindist(Node, Mi) ; 1E+4 number of node accesses 1 CPU cost (sec) repeat read next group Qi (1≤i≤m) ; 1E+3 for each point pj in list 0.1 n 100 if curr _ dist (p j )+ ∑ nl ⋅ mindist (p j ,M l ) ≥ best_dist l=i 0.01 10 remove pj from list; /* pj fails heuristic 6 else /* pj passes heuristic 6 1 0.001 curr_dist(pj)= curr_dist(pj)+dist(pj,Qi) ; 4 16 64 256 1024 4 16 64 256 1024 n n until weighted mindist(pj)≥best_dist or end list or end of groups; for each point p that remains in list /*after termination of loops (a) NA vs. n (PP dataset) (b) CPU vs. n (PP dataset) if curr_dist(p)< best_dist 1E+5 number of node accesses 10 CPU cost (sec) best_NN =p; //Update current GNN 1E+4 1 best_dist = curr_dist(p) ; return best_NN; 1E+3 0.1 100 Figure 4.7: The F-MBM algorithm 10 0.01 Starting from the root of the R-tree of P, entries are sorted 1 0.001 by their weighted mindist, and visited (recursively) in this 4 16 64 256 1024 4 16 64 256 1024 n n order. Once the first node that fails heuristic 5 is found, all subsequent nodes in the sorted list can also be pruned. For (c) NA vs. n (TS dataset) (d) CPU vs. n (TS dataset) leaf nodes, if a point violates heuristic 6, it is removed from Figure 5.1: Cost vs. cardinality n of Q (M=8%, k=8) the list and is not compared with subsequent groups. The MQM is, in general, the worst method and its cost increases extension to k NN is straightforward. fast with the query cardinality, because this leads to 5. Experiments multiple queries, some of which access the same nodes and In this section we evaluate the efficiency of the proposed retrieve the same points. These redundant computations, algorithms, using two real datasets: (i) PP [Web1] with affect both the node accesses and the CPU cost significantly 24493 populated places in North America, and (ii) TS (all diagrams are in logarithmic scale). Although most [Web2], which contains the centroids of 194971 MBRs queries access similar paths in the R-tree of P (and, representing streams (poly-lines) of Iowa, Kansas, Missouri therefore, MQM benefits from the existence of an LRU buffer), its total cost is still prohibitive for large n due to the high CPU overhead. On the other hand, the cardinality of Q previous diagrams: MBM is clearly the most efficient has little effect on the node accesses of SPM and MBM method, followed by SPM. because it does not play an important role in the pruning power of heuristic 1 (for SPM) and heuristics 2, 3 (for MQM SPM MBM 1E+3 number of node accesses 0.1 CPU cost (sec) MBM). It affects, however, the CPU time, because the distance computations for qualifying data points increase 100 with the number of query points. MBM is better than SPM due to the high pruning power of heuristic 3, as opposed to 0.01 heuristic 13. 10 In order to measure the effect of the MBR size of Q, we set n=64, k=8 and vary M from 2% to 32% of the workspace of 1 0.001 1 2 8 16 32 1 2 8 16 32 P. As shown in Figure 5.2, the cost (average NA and CPU k k time) of all algorithms increases with the query MBR. For (a) NA vs. k (PP dataset) (b) CPU vs. k (PP dataset) MQM, the termination condition is that the total threshold T 1E+4 number of node accesses 1 CPU cost (sec) (i.e., sum of thresholds for each query point) should exceed best_dist, which, however, increases with the MBR size. 1E+3 0.1 Therefore, MQM retrieves more NNs for each query point. 100 For SPM (MBM), the reason is the degradation of pruning 0.01 power of heuristic 1 (heuristic 2 and 3) with the MBR size 10 of Q. 1 0.001 32 MQM SPM MBM 1 2 k 8 16 32 1 2 8 k 16 1E+4 number of node accesses 1 CPU cost (sec) (c) NA vs. k (TS dataset) (d) CPU vs. k (TS dataset) 1E+3 0.1 Figure 5.3: Cost vs. num. of retrieved NNs (n=64, M=8%) 100 0.01 5.2 Comparison of algorithms for disk-resident queries 10 For this set of experiments we use both datasets (PP, TS) 1 2% 4% 8% 16% 32% 0.001 2% 4% 8% 16% 32% alternatively as query and data points. For GCP we assume MBR size of Q MBR size of Q that both datasets are indexed by R-trees, whereas for F- (a) NA vs. M size (PP) (b)CPU vs. M size (PP) MQM and F-MBM, the dataset that plays the role of Q is 1E+5 number of node accesses 10 CPU cost (sec) sorted (according to Hilbert values) and split into blocks of 1E+4 10000 points, that fit in memory. The cost of sorting and 1 building the R-trees is not taken into account. Since now the 1E+3 query cardinality n is fixed to that of the corresponding 0.1 100 dataset, we perform experiments by varying the relative 0.01 workspaces of the two datasets. 10 First, we assume that the workspaces of P and Q have the 1 0.001 same centroid, but the area M (of the MBR of Q) varies 2% 4% 8% 16% 32% 2% 4% 8% 16% 32% MBR size of Q MBR size of Q between 2% and 32% of the workspace of P (similar to the (c) NA vs. M size (TS) (d)CPU vs. M size (TS) experiments of Figure 5.2). Figure 5.4 shows NA and CPU time assuming that PP is the query dataset and k=8. GCP Figure 5.2: Cost vs. size of MBR of Q (n=64, k=8) has the worst performance and its cost increases fast with M Finally, in Figure 5.3, we set n= 64, M=8% and vary the for the reasons discussed in Section 4.1. When M exceeds number k of retrieved neighbors from 1 to 32. The value of 8% percent of the workspace of P, GCP does not terminate k does not influence the cost of any method significantly, at all due to the huge heap requirements. The other two because in most cases a large number of neighbors are algorithms are more than an order of magnitude faster. F- found in the same node with a few extra computations. The MQM outperforms F-MBM, except for NA in case of large relative performance of the algorithms is similar to the (> 4%) query workspaces. The good performance of F- MQM (compared to the main-memory results) is due to the 3 fact that the query set (PP) contains 24493 data points and, We implemented a version of MBM with only heuristic 2 and therefore, it generates only 3 query groups. Each query we found it inferior to SPM. Nevertheless, heuristic 2 is useful group is processed in memory (by MBM) and their results (in conjunction with heuristic 3) because it reduces the CPU time requirements of the algorithm. are combined with relatively small overhead. explain this, let us consider the 0% overlap case assuming GCP F-MQM F-MBM 1E+7 number of node accesses that the query workspace starts at the upper-right corner of 1E+4 CPU time (sec) the data workspace. The nearest neighbors of all query 1E+6 1E+3 groups must lie near this upper-right corner, since such 1E+2 points minimize the total distance. Therefore, F-MQM can 1E+5 find the best NN relatively fast, and terminate when all the 1E+1 points in or near the corner have been considered. On the 1E+4 other hand, because each query group has a large MBR 1E+0 (recall that it contains 10000 points), numerous nodes 1E+3 1E-1 2% 4% 8% 16% 32% 2% 4% 8% 16% 32% satisfy the pruning heuristic of F-MBM and are visited. MBR area of Q MBR area of Q GCP F-MQM F-MBM (a) NA vs. M size (b) CPU vs. M size 1E+7 number of node accesses 1E+4 CPU time (sec) Figure 5.4: Cost vs. size of MBR of Q (k=8, P=TS, Q=PP) 1E+3 1E+6 Figure 5.5 illustrates a similar experiment, where PP plays 1E+2 the role of the dataset and TS the role of the query set 1E+5 1E+1 (recall that the cardinality of TS is almost an order of 1E+0 magnitude higher than that of PP). In this case F-MBM is 1E+4 clearly better, due to the large number (20) of query groups 1E-1 whose results must be combined by F-MQM. Comparing 1E+3 1E-2 0% 25% 50% 75% 100% 0% 25% 50% 75% 100% Figure 5.5 with 5.4, we observe that the performance of F- overlap area overlap area MBM is similar, while F-MQM is significantly worse. This (a) NA vs. overlap area (b) CPU vs. overlap area is consistent with the main-memory behavior of MQM (Figure 5.1) where the cost increases fast with the Figure 5.6: Cost vs. overlap area (k=8, P=TS, Q=PP) cardinality of the query set. GCP is omitted from the Figure 5.7 repeats the experiment by setting Q=TS. The diagrams because it incurs excessively high cost. clear winner is F-MBM, again due to the numerous queries F-MQM F-MBM that must be performed by F-MQM. We also performed 1E+8 number of node accesses 1E+3 CPU time (sec) experiments by varying the number of neighbors retrieved, while keeping the other parameters fixed. As in the case of 1E+7 main-memory queries, k does not have a significant effect 1E+2 1E+6 on performance (and the diagrams are omitted). 1E+5 1E+1 F-MQM F-MBM 1E+4 1E+8 number of node accesses 1E+4 CPU time (sec) 1E+3 1E+0 1E+7 1E+3 2% 4% 8% 16% 32% 2% 4% 8% 16% 32% MBR area of Q MBR area of Q 1E+6 1E+2 (a) NA vs. M size (b) CPU vs. M size 1E+5 1E+1 Figure 5.5: Cost vs. size of MBR of Q (k=8, P=PP, Q=TS) 1E+4 1E+0 In order to further investigate the effect of the relative 1E+3 1E-1 0% 25% 50% 75% 100% 50% 75% 100% workspace positions, for the next set of experiments we overlap area 0% 25% overlap area assume that both datasets lie in workspaces of the same size, and vary the overlap area between the workspaces (a) NA vs. overlap area (b) CPU vs. overlap area from 0% (i.e., P and Q are totally disjoint) to 100% (i.e. on Figure 5.7: Cost vs. overlap area (k=8, P=PP, Q=TS) top of each other). Intermediate values are obtained by In summary, the best algorithm for disk-resident queries starting from the 100% case and shifting the query dataset depends on the number of query groups. F-MQM is usually on both axes. Figure 5.6 shows the cost of the algorithms preferable when the query dataset is partitioned in a small assuming that Q=PP. The cost of all algorithms grows fast number of groups; otherwise, F-MBM is better. GCP has with the overlap area because it: (i) increases the number of very poor performance in all cases. We also experimented potential candidates within the threshold of F-MQM (ii) with an alternative version of MBM that uses an R-tree on reduces the pruning power of F-MBM heuristics and (iii) Q (instead of Hilbert sorting). The technique, however, did increases the number of closest pairs that must be output not provide performance benefits because for each before the termination of GCP. F-MQM clearly qualifying point of P we have to compute its accumulated outperforms F-MBM for up to 50% overlap. In order to distance to all query points anyway. 6. Conclusion Algorithms for Middleware. PODS, 2001. [FSAA01] Ferhatosmanoglu, H., Stanoi, I., Agrawal, D., Abbadi, Given a dataset P and a group of query points Q, a group A. Constrained Nearest Neighbor Queries. SSTD, nearest neighbor query retrieves the point of P that 2001. minimizes the sum of distances to all points in Q. In this [G84] Guttman, A. R-trees: A Dynamic Index Structure for paper we describe several algorithms for processing such Spatial Searching. SIGMOD, 1984. queries, including main-memory and disk-resident Q, and [JMF99] Jain, A., Murthy, M., Flynn, P., Data Clustering: A experimentally evaluate their performance under a variety Review. ACM Comp. Surveys, 31(3): 264-323, 1999. of settings. Since the problem is by definition expensive, [HS98] Hjaltason, G., Samet, H. Incremental Distance Join the performance of different algorithms normally varies up Algorithms for Spatial Databases. SIGMOD, 1998. [HS99] Hjaltason, G., Samet, H. Distance Browsing in Spatial to orders of magnitude, which motivates efficient Databases. TODS, 24(2), 265-318, 1999. processing methods. [HYC01] Hochreiter, S., Younger, A.S., Conwell, P. Learning In the future we intend to explore the application of related to Learn Using Gradient Descent. ICANN, 2001. techniques to variations of group nearest neighbor search. [KGT99] Kollios, G., Gunopulos, D., Tsotras, V. Nearest Consider, for instance, that Q represents a set of facilities Neighbor Queries in Mobile Environment. STDBM, and the goal is to assign each object of P to a single facility 1999. so that the sum of distances (of each object to its nearest [KM00] Korn, F., Muthukrishnan, S. Influence Sets Based on facility) is minimized. Additional constraints (e.g., a facility Reverse Nearest Neighbor Queries. SIGMOD, 2000. [KMS02] Korn, F., Muthukrishnan, S. Srivastava, D. Reverse may serve at most k users) may further complicate the Nearest Neighbor Aggregates Over Data Streams. solutions. Similar problems have been studied in the VLDB, 2002. context of clustering and recourse allocation, but the [NO97] Nakano, K., Olariu, S. An Optimal Algorithm for the proposed methods are different from the ones presented in Angle-Restricted All Nearest Neighbor Problem on this paper. Furthermore, it would be interesting to study the Reconfigurable Mesh, with Applications. IEEE other distance metrics (e.g., network distance) that Trans. on Parallel and Distributed Systems 8(9): 983- necessitate alternative pruning heuristics and algorithms. 990, 1997. [PM97] Papadopoulos, A., Manolopoulos, Y. Performance of Acknowledgements Nearest Neighbor Queries in R-trees. ICDT, 1997. This work was supported by grant HKUST 6180/03E from [PZMT03] Papadias, D., Zhang, J., Mamoulis, N., Tao, Y. Query Processing in Spatial Network Databases. VLDB, Hong Kong RGC. 2003. [RKV95] Roussopoulos, N., Kelly, S., Vincent, F. Nearest References Neighbor Queries. SIGMOD, 1995. [AMN+98] Arya, S., Mount, D., Netanyahu, N., Silverman, R., [S91] Sproull, R. Refinements to Nearest Neighbor Wu, A. An Optimal Algorithm for Approximate Searching in K-Dimensional Trees. Algorithmica, Nearest Neighbor Searching, Journal of the ACM, 6(4): 579-589, 1991. 45(6): 891-923, 1998. [SKS02] Shahabi, C., Kolahdouzan, M., Sharifzadeh, M. A [AY01] Aggrawal, C., Yu, P. Outlier Detection for High Road Network Embedding Technique for K-Nearest Dimensional Data. SIGMOD, 2001. Neighbor Search in Moving Object Databases. ACM [B00] Bohm, C. A Cost Model for Query Processing in High GIS, 2002. Dimensional Data Spaces. TODS, Vol. 25(2): 129- [SR01] Song, Z., Roussopoulos, N. K-Nearest Neighbor 178, 2000. Search for Moving Query Point. SSTD, 2001. [BCG02] Bruno, N., Chaudhuri, S., Gravano, L. Top-k [SYUK00] Sakurai, Y., Yoshikawa, M., Uemura, S., Kojima, H. Selection Queries over Relational Databases: The A-tree: An Index Structure for High-Dimensional Mapping Strategies and Performance Evaluation. Spaces Using Relative Approximation. VLDB, 2000. TODS 27(2): 153-187, 2002. [TP02] Tao, Y., Papadias, D. Time Parameterized Queries in [BGRS99] Beyer, K., Goldstein, J., Ramakrishnan, R., Shaft, U. Spatio-Temporal Databases. SIGMOD, 2002. When Is Nearest Neighbor Meaningful? ICDT, 1999. [TP03] Tao, Y., Papadias, D. Spatial Queries in Dynamic [BJKS02] Benetis, R., Jensen, C., Karciauskas, G., Saltenis, S. Environments. ACM TODS, 28(2): 101-139, 2003. Nearest Neighbor and Reverse Nearest Neighbor [TPS02] Tao, Y., Papadias, D., Shen, Q. Continuous Nearest Queries for Moving Objects. IDEAS, 2002. Neighbor Search. VLDB, 2002. [BKSS90] Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, [Web1] www.maproom.psu.edu/dcw/ B. The R*-tree: An Efficient and Robust Access [Web2] dke.cti.gr/People/ytheod/research/datasets/ Method for Points and Rectangles. SIGMOD, 1990. [WSB98] Weber, R., Schek, H.J., Blott, S. A Quantitative [CMTV00] Corral, A., Manolopoulos, Y., Theodoridis, Y., Analysis and Performance Study for Similarity-Search Vassilakopoulos, M. Closest Pair Queries in Spatial Methods in High-Dimensional Spaces. VLDB, 1998. Databases. SIGMOD, 2000. [YOTJ01] Yu, C., Ooi, B, Tan, K., Jagadish, H. Indexing the [F02] Fagin, R. Combining Fuzzy Information: an Distance: An Efficient Method to KNN Processing. Overview. SIGMOD Record, 31 (2): 109-118, 2002. VLDB, 2001. [FLN01] Fagin, R., Lotem, A., Naor, M. Optimal Aggregation
Pages to are hidden for
"Group Nearest Neighbor Queries"Please download to view full document


text:
- Home
- News
- Sports
- Classifieds
- Obituaries
- Entertainment
- Special Sections
- Games
- June Real Estate Guide
- Summer Life in Whitley County
COLUMBIA CITY — The second annual Veterans Marathon will take off down Van Buren Street Saturday morning with over 750 runners signed up to take part in the day's three different races.
After a successful first run, marathon officials are asking Whitley County residents to use safety and patience while on the road and at home.
"Our main concern is always safety," race director Gary Bird said. "We want everyone to have an enjoyable time in our community. We just ask that residents be aware of the runners and take any precautions necessary."
Residents and drivers are asked to plan accordingly pinning up any loose animals for the morning and using safety around runners.
Businesses are encouraged to welcome runners on their marques or doors as they start coming into town Friday.
The marathon will get underway at 8 a.m. at which time traffic downtown will be controlled by the Columbia City Police and Whitley County Sheriffs Departments.
Both the marathon and half-marathon runners will head east of Columbia City out to parts of Raber and Keiser Road before coming back to town to end the first half of the marathon. The second stint will take runners down Old Trail and out by Wolf Road.
The course will be closed and all roads will be open at 2 p.m.

subset: commoncrawl


text:
ROGERSVILLE — A Hawkins County man on parole for his part in the 2010 assault of a 99-year-old Rogersville woman during the burglary of her home is in trouble again, accused of stealing a Jeep the day after he sold it.
Johnny Kay Seals, 43, 165 Country Estates, Rogersville, was sentenced to six years in February 2011 in exchange for guilty pleas to aggravated burglary and aggravated assault charges in the 2010 beating and burglary.
According to the Tennessee Department of Corrections, Seals is currently on parole until Oct. 30, 2015.


text:
INTRODUCTIONS: Please Use This Thread To Introduce Yourself!
View Single Post
Junior Member
Join Date: Nov 2011
Posts: 9
Re: INTRODUCTIONS: Please Use This Thread To Introduce Yourself!
Hello att you all!
Real name
? Jonathan Strömberg
? Yes, 15 years ago.
How long have you been playing
? Since I was 10.
Origin of user name
? Mellanslag means space-bar on swedish. I don't have an explation wy i Chosed mellanslag?
Some really cool drummers
? Jason Bittner, Neal Peart, Mike Portnoy, Nicko McBrian, Chad Smith, Emil Viksten and Thomas Lang are a few of menu cool drummers!
Brand of drumki
t? It is a Tama Imperialstar 22" 22" 12" 13" 16" and 14"x5.5", but i hope to replace it with a PDP or a Superstar soon.
Brand of cymbal
? Paiste make really great cymbals, i haves played with Paiste since i got started.
Where do you practice
? At home and at school.
Are you in a band
? Kinda, me and a friend plays a lot, but it not seriously.
Do you play covers or originals
? My friend plays something, i don't if he wrote it or someone els.
Style of music
? Jazz, Rock, Metal. I want to be as wide as possible.
Favourite take out food
? Pizza
What country do you live in
? Sweden, Forshaga
Wy drums
? Because it was the most fun to play at a "try an instrument" day.
My kit.
View Public Profile
Send a private message to mellanslag
Find all posts by mellanslag


text:
Cameron Robert Amber, 20, a resident of Churubusco, passed away at 6:35 p.m. Thursday, Dec. 2, 2010, from the results of a two-vehicle accident on U. S. 33, south of Churubusco.
Amber was born Feb. 5, 1990 in Columbia City, a son of Robert C. and Marna (Friskney) Amber and was a lifelong resident of Churubusco. He graduated from Churubusco High School in 2009, and was the school's quarterback for its semistate football team in 2007. He had served with the U. S. Air Force, coached Churubusco Youth Football and enjoyed his diesel truck.
He had been employed at 80/20 in Columbia City since August.
The surviving relatives include his parents, Bob and Marna Amber of Churubusco; two sisters, Ashton (James Ford) Amber of Fort Wayne and Taylor Amber, a student at Huntington University; a brother, Carlin Amber, at home; his paternal grandparents, Don and Patty Amber of Churubusco; his maternal grandmother, Marjorie Friskney of Albion; his fiancee, Nicole Pippenger of Avilla; and a nephew, Braylon McCoy.
He was preceded in death by his maternal grandfather, Willis J. Friskney Aug. 1, 2010.
Funeral services will be at 11 a.m. Monday at the Churubusco United Methodist Church, with Pastors Corinne K. Boruff and Timothy Grable, officiating. The family will receive friends at the church from 2 to 8 p.m. Sunday, or one hour prior to the service Monday morning. Interment will be in the Eel River Cemetery, south of Churubusco.
In lieu of flowers, memorials should be directed to Churubusco Youth Football; or the trust for the child of Cameron and Nicole in care of Star Financial Bank.
Sheets & Childs Funeral Home in Churubusco is in charge of the arrangements.
To leave an online condolence for the family in memory of Cameron, log on to www.sheetsandchilds.net [1].
[1] http://www.sheetsandchilds.net


text:
Our make ahead Thanksgiving recipes will help ease the burden of cooking on this busy holiday.
All of these "Make ahead Thanksgiving" recipes can be prepared ahead of the feast day, so that your main concern on the day itself is simply the "ruling roast" or the "big bird."
Cheese Ball [3]
Crab Dip [5]
Soups and Salads
Vermont Butternut Squash Soup [7]
Side Dishes
Mashed Potato Casserole [9]
Green Bean Casserole [11]
Apple-Stuffed Acorn Squash [12]
Sweet Potato Souffle [13]
Indian Pudding [14]
Caramel Turtle Tart [16]
Steamed Cranberry Pudding [18]
See all of our traditional Thanksgiving Recipes, including classic turkey recipes [19]!
- Recipe Collections [20]
- Cooking & Recipes [21]


text:
HUNTSVILLE, Ala. (WHNT) — Several people across the Tennessee Valley are working to answer questions and get residents who qualify signed up for health insurance through the Affordable Care Act before the March 31st deadline.
Toni McGriff is a navigator for the Affordable Care Act. She's also the president of Progressive Women of Northeast Alabama.
McGriff and two other members of her group have been working in several counties to make sure anyone who has questions about signing up for health care coverage through the ACA gets answers.
"An awful lot of people can't go online, don't have computers, can't do it for themselves," McGriff says.
So they decided to help, and became trained navigators for the ACA. "We are trained to help people access the website, and navigate through it," McGriff says.
They have answered questions as well as countless phone calls, and ultimately signed up quite a few Tennessee Valley residents.
But McGriff says there are a number of people who can't get insurance who fall into the Medicaid gap.
Alabama is one of the states that didn't expand Medicaid when given the option.
Governor Robert Bentley chose not to expand Medicaid because he says while the federal government would cover the initial cost of the expansion, it would eventually fall on the state to cover the tab and he says the state just doesn't have the money.
Joann Cummings is also a navigator. She says she deals with people who are classified in that gap often.
"There's a lot of working poor people in Alabama who just don't make enough money to go into the marketplace but they would have been getting Medicaid," Cummings said.
With the deadline to sign up for health care coverage on Monday, March 31, both of these navigators say time is of the essence for those who can enroll, and for every question, they are quick with an answer.
There are navigators in several Tennessee Valley counties.
Those counties with the appropriate contact information to enlist a navigator's help are below.
DeKalb, Jackson and Marshall Counties – email@example.com (256) 674 – 3145
Morgan and Limestone Counties – email@example.com
Lauderdale County – firstname.lastname@example.com (256) 856 – 9810
Madison and all other north Alabama counties – email@example.com


text:
Discovering Historic Savannah, GA
No matter how long your stay in Savannah, you'll be forever beckoned back to this magical, one-of-a-kind Southern city. Ancient oak trees with Spanish moss arch like natural canopies across historical downtown's redbrick streets. Magnolias bloom in abundance, wafting sweetness through the air on warm spring and summer evenings. And The Planters Inn is the perfect place to make the most of your visit to this haunting-in-more-ways-than-one city.
Historic Savannah, GA – America's Most Haunted City
Georgia's first city has a spooky side, and has well-earned its title of America's Most Haunted City. Whether from Civil War battlefields, former spots of centuries-old pirate ships, or private homes, wide, wild and varying accounts of Savannah's most infamous spirits are yours for the taking while on any number of the entertaining and thrilling ghost tours of the city.
You'll Have More Fun Than Time!
Savannah offers all kinds of "Savannah Experiences" designed to fit your lifestyle and interests. From romantic, historic and culinary getaways to eco-tourism, shopping, festival and family-centered vacations, you'll find it all in Savannah,GA.
Stay at our historic Savannah hotel on Reynolds Square and visit Savannah's finest attractions, like the City Market, Forsyth Park, Lucas Theatre, and much more just minutes from our comfortable rooms.
For a quick overview of the city, watch Fox News recent feature, Savannah In 5.


text:
Aldo Aberiwen Boat Shoe
Compare at $90.00
Find It In Store
Item # 301214
Add a nautical vibe to your laid back attire with the Aberiwen boat shoe by Aldo. Flat in height, but high in style, these leather slip-ons will keep your casual look right on trend.
- Leather upper
- Webbed lacing detail
- Round toe
- Fully lined in leather
- Synthetic sole
- Imported
- View more Aldo
By: Lissette616
Location: Miami
November 30, 2014
No regrets
"I love it. comfortable and super soft.. i truly recommend it..no regrets...buying my next pair :)"
By: Ferdi
Location: Laredo
August 20, 2014
Loved them
"Super soft and comfortable shoes. Color is great, and leather looks very nice."
By: bunniehop
Location: Sac, CA
August 19, 2014
Comfy and adorable
"I have been wearing these non stop since I got them. Very comfortable, flexible, cushion insole is amazing. I wear them with everything, skinny jeans, knee shorts, dresses, at the office, over the weekend. Classic with a current look. Price is equal to the quality and I will get a lot of use out of them- they go with everything."
By: DottyDrackap
Location: Ohio
May 28, 2014
Questionable Quality
"I love the appearance of these shoes, but the durability did not meet my expectations. The insole in right shoe started to fall out and bunch up within a few days of wearing the shoes. I splurged to get these shoes, and was very disappointed to find that they fell apart in less than a month. Although they are adorable and over all comfy I wouldn't recommend these shoes to other buyers."
Click anywhere to close this.


text: "I think what's changed is that customers have been experimenting for a long time and now they're getting ready to buy. It wasn't the technology that drove us to do this. It was the maturation of the marketplace and the attitude toward using this technology. It's as simple as that."


text:
Filter Results
- results
- state & global data
- slides
- view as grid
- view as list
Medicaid Managed Care in the Era of Health Reform – Briefing and Panel Discussion
Amid increasing state and national interest in using managed care delivery models for Medicaid beneficiaries, the Kaiser Family Foundation's Commission on Medicaid and the Uninsured (KCMU) hosted a public briefing on Tuesday, June 25, 2013 to provide information on recent transitions from fee-for-service to managed care, and to discuss their…Event Read More
Medicaid in an Era of Health & Delivery System Reform: Results from a 50-State Medicaid Budget Survey for State Fiscal Years 2014 and 2015
This report provides an in depth examination of the changes taking place in state Medicaid programs across the country. The findings in this report are drawn from the 14th annual budget survey of Medicaid officials in all 50 states and the District of Columbia conducted by the Kaiser Commission on Medicaid and the Uninsured and Health Management Associates (HMA), with the support of the National Association of Medicaid Directors. This report highlights policy changes implemented in state Medicaid programs in FY 2014 and those planned for implementation in FY 2015 based on information provided by the nation's state Medicaid Directors. Key areas covered include changes in eligibility and enrollment, delivery systems, provider payments and taxes, benefits, pharmacy programs, program integrity and program administration.Report Read More
The Washington State Health Care Landscape
This fact sheet provides an overview of population health, health coverage, and health care delivery in Washington under the Affordable Care Act (ACA).Fact Sheet Read More
Medicare Spending Peaks at Age 96
In his latest column for The Wall Street Journal's Think Tank, Drew Altman discusses the implications of a Kaiser finding: per capita Medicare spending peaks at age 96, and the main reason is not end-of-life care. All previous columns by Drew Altman are available online.News Release Read More
Safety-Net Emergency Departments: A Look at Current Experiences and Challenges
Safety-net hospital emergency departments (EDs) are an important part of our health care system, especially, but not only, for the uninsured and others with low income. With multiple major changes unfolding in our system today, including the development of new models of health care delivery, payment reforms, expanded insurance coverage, and increasing demand for primary care access, safety-net EDs are a sort of crucible in which these shifts and transitions can be seen playing out. To understand more about their current experiences and challenges as the Affordable Care Act (ACA) begins to takes hold, we conducted interviews with ED directors in a convenience sample of 15 safety-net hospitals around the country in June and July 2014.Issue Brief Read More
Aiming for Fewer Hospital U-turns: The Medicare Hospital Readmission Reduction Program
This Issue Brief describes the Medicare Hospital Readmission Reduction Program (HRRP), which penalizes hospitals that have relatively higher readmission rates, analyzes the impact of this program on Medicare patients and hospitals, and discusses several issues that have been raised regarding its implementation.Issue Brief Read More
Ask the Experts About Reform: Where Are We Now and Where Are We Headed?
The Alliance for Health Reform and Eli Lilly co-sponsored this briefing to have an expanded panel of prominent experts answer questions about the current health reform efforts. Questions addressed include: What is the status of major reform bills? How do they differ from each other, and from the plan that…Event Read More
Rural Health: Laying the Foundation for Health Reform
The Alliance for Health Reform and the Robert Wood Johnson Foundation co-sponsored this briefing to have a panel of experts answer questions about how some aspects of pending health reform proposals may have a substantial impact on rural care. What provisions in the various reform proposals affect rural health care?…Event Read More
States Expanding Medicaid Under the Affordable Care Act Expect 18% Enrollment Growth in Fiscal Year 2015, With Federal Funds Picking Up Most of the Cost
States expect the number of people enrolled in Medicaid will increase an average of 13.2 percent across the country in state fiscal year 2015 (which runs through June in most states), showing the early effects of the first full year of Affordable Care Act implementation, according to the 14th annual 50-State Medicaid budget survey by the Kaiser Family Foundation's Commission on Medicaid and the Uninsured (KCMU).News Release Read More
Awaiting New Medicaid Managed Care Rules: Key Issues to Watch
More than half of all Medicaid beneficiaries now receive their services in risk-based managed care plans, and states' use of managed care is expanding. States operate their own Medicaid managed care programs within federal rules and requirements. The federal regulations were last updated in 2002 and a new proposed rule is expected in Spring 2015. This brief identifies key issues in the regulation and discusses how CMS might address them.Issue Brief Read More


text:
Stock Photo:
High resolution christian cross made of wood over a beautiful sky background, ideal for holiday, Christmas, Easter and religion designs
- Image ID: 88823617
- Copyright: design36
High quality images curated from over 150 countries.
Over 50 million photos, vectors, illustrations, and more.
Simple and flat pricing by image or by month.
Over 230,000 images downloaded every day.


text:
Keep word counts low, especially on top-level pages that should be telling the story rather than conveying lots of detailed information. Most basic informational pages ought to be no longer than 400-500 words, and top-level pages should aim for between 200-300 words.
Flipping through the site, any visitor should be able to quickly absorb the most important information on the page to determine whether she needs to take the time to read the entire page.
On primary public-facing pages (that is, all pages one click away from the home page), the text should be written specifically with a first-time visitor in mind. Opening paragraphs of other pages can simply summarize and/or contextualize the page's content. We typically set the opening paragraph in larger font size to draw attention to it and make it easy to read.
The use of contractions (it's, we're, you'll, etc.) is encouraged. Some of the rules that are applied to formal writing don't apply as strictly to Web writing. For example, if the natural rhythm of a sentence is best suited by ending it with a preposition, so be it.
USF is staffed by an extremely knowledgeable and thoughtful group, and using words like "our" and "we" can help convey that online. Again, one of the best ways to check the style of Web writing is to read it to yourself out loud.
Along with short paragraphs, breaking up a page with subheadings allows a Web reader to quickly determine what information is most important for her needs. This is a good general principle for all content pages of a site; for long, policies-and-procedures-type pages, it's absolutely essential.
As a general rule, there ought to be a subheading for every 150-200 words of Web content. And top-level pages often benefit from a much more widespread use of headings and subheadings. Many good top-level pages pair small subheadings with short paragraphs to give a visitor a very clear idea of what's to be found throughout that section of the site. Organize your text so that the hierarchy is no deeper than four levels. Lower-level heads are hard to distinguish and disorienting to online readers.
'Overuse white space' is a good rule of thumb for Web writing. Reading from computer screens is on average 25% slower than from paper, so short paragraphs and frequent subheadings give users more room to read.
On most basic content pages there shouldn't be more than one or two bulleted or numbered lists. If you have a page that is burdened with lots of lists, you may want to consider alternative ways of presenting that content.
Links within the text are important means of limiting duplicate information and directing visitors to key content within the site. On section homepages these links should complement the navigation as a secondary means of directing readers to section subpages. Links to external sites are ok, but should be carefully considered and not overused. Be judicious: Too many links within a paragraph also diminishes their effectiveness as content guides.
By using USF's Editorial Style Guide, we can bring stylistic consistency to all university publications, from newsletters and emails to brochures and flyers.
Next page: Page Content Strategies »


text:
This bird has been reportedly found in the following regions:
No details have been posted.
I live near Perth Australia and I just noticed this ... read more
Zebra spiders are highly common to the Pacific Northwest! ... read more
Another one of my favorites. In the winter, their ... read more
Proteaceae is one of my favourite plant familes for ... read more
[ Home |
About |
Advertise |
Media Kit |
Mission |
Featured Companies |
Submit an Article |
Terms of Use |
Tour |
Rules |
Privacy Policy |
Cookie Policy |
Contact Us ]
Back to the top
Copyright © 2000-2015 Dave's Garden, an Internet Brands company. All Rights Reserved.


text:
Katy Perry, Selena Gomez: Beyond the Velvet Rope
Caught in the Act
7 of 11
Selena Gomez celebrates her Nylon magazine cover with some help from her Spring Breakers co-star Ashley Benson at Soho House in Los Angeles. The starlet also signed a Coach "Selena" bag as part of an online auction for CharityBuzz; proceeds go to UNICEF.
Tags: Ashley Benson, Selena Gomez


text: VANCOUVER, BC - The BC Bears senior men's provincial program have announced the traveling roster for their tour to South America along with their long list of players for their 2014 Canadian Rugby Championship campaign. As part of the 125th Anniversary of the British Columbia Rugby Union, the flagship senior men's team will face Buenos Aires on July 16 in Argentina before shifting to Montevideo where they will battle the Uruguayan national team on July 19. The traveling roster is comprised of 24 players recently selected from the 2013-14 BC Rugby club season and the recent McKechnie Cup sub-union series. Bears Director of Rugby Jim Dixon has also announced a long list of 47 players that will be in mix for the team's six CRC games in August and September. "These players have consistently delivered for the clubs and sub-unions throughout the season and deserve their places," said Dixon. "Unfortunately we cannot take the entire squad to South America, but we and the players know there is a long way to go until our first CRC game and everyone named is essential to our chance of achieving success. The management team are looking forward to the two training camps scheduled for the end of June and start of July."The Bears will depart for Buenos Aires on July 12th from Vancouver. BC's senior men will be looking for their seventh victory over a full international Test side when they face Uruguay to wrap up their tour. BC has previously defeated Australia (11-8, 1958), British Lions (8-3, 1966), Japan (38-7, 1976), Scotland (22-13, 1985), Japan (46-10, 1989) and Russia (38-16, 2009). The tour roster features Canada Sevens-capped backs Sean Ferguson (UBC Thunderbirds) and Pat Kay (UVic Vikes). The roster will also have experience in Canada-A reps Micha Govorchin (Burnaby Lake RC) and Callum Morrison (UBCOB Ravens) who recently represented their country at the Americas Rugby Championship this past Fall in Langford. Canada under-20 scrum half James Pitblado (UVic Vikes) has also been named to the tour along with junior national team graduates Admir Cejvanovic (Burnaby Lake RC), Luke Campbell (UVic Vike), Chase Kelliher (UVic Vikes) and Nathan Yanagiya (UVic Vikes). BC Bears 2014 ScheduleJuly 16: BC Bears vs Buenos Aires Reps (Buenos Aires, Argentina)July 19: BC Bears vs Uruguay (Montevideo, Uruguay)Aug 9: CRC BC Bears at Prairie Wolf Pack (Calgary Rugby Park, Alberta)Aug 16: CRC Prairie Wolf Pack at BC Bears (Apple Bowl, Kelowna)Sept 4: CRC Atlantic Rock at BC Bears (Klahanie Park, West Vancouver)Sept 7: CRC Ontario Blues at BC Bears (Klahanie Park, West Vancouver)Sept 18: CRC BC Bears at Ontario Blues (Guelph University Stadium, Guelph, Ont)Sept 21: CRC BC Bears at Atlantic Rock (Swiler's Rugby Complex, St. John's Newfoundland)BC Bears Long List - Canadian Rugby Championship1. Ryan Ackerman (Burnaby Lake RC)2. Noah Barker (James Bay AA)3. Luke Campbell (UVic Vikes)4. Admir Cejvanovic (Burnaby Lake RC)5. Taylor Dalziel (James Bay AA) 6. Joe Dolesau (Burnaby Lake RC)7. Sean Ferguson (UBC Thunderbirds)8. Garrett Garbe (UBCOB Ravens)9. Micha Govorchin (Burnaby Lake RC)10. Jeke Gotegote (Burnaby Lake RC)11. Ben Grant (UBC Thunderbirds)12. Kevin Gurniak (Vancouver Rowing Club)13. Caleb Hansen (Vancouver Rowing Club)14. Jordan Harvey (Capilano RFC)15. Keenan Horton (Castaway Wanderers RFC)16. Jake Ilnicki (Castaway Wanderers / WIlliams Lake)17. Riley Ilnicki (Castaway Wanderers RFC)18. Gurvinder Kalar (Burnaby Lake RC)19. Pat Kay (UVic Vikes)20. Gord Kehoe (Castaway Wanderers RFC)21. Chase Kelliher (UVic Vikes)22. Andrew Lackner (Burnaby Lake RC)23. Matt Law (UBCOB Ravens)24. Anthony Luca (Burnaby Lake RC)25. Scott MacKay (Burnaby Lake RC)26. Nate Mantle (Burnaby Lake RC)27. Alex Mascott (UBC Thunderbirds)28. Cody McClary (Port Alberni Black Sheep)29. Glenn McKinnon (Capilano RFC)30. Clayton Meeres (James Bay AA)31. John Morris (Castaway Wanderers RFC)32. Callum Morrison (UBCOB Ravens)33. Brian Murphy (Burnaby Lake RC)34 James Pitblado (UVic Vikes)35. Scott Plummer (Burnaby Lake RC)36. Cole Racine (James Bay AA)37. Cody Rockson (Burnaby Lake RC)38. Geoff Ryan (Burnaby Lake RC)39. Jorden Sandover-Best (UBC Thunderbirds)40. Chris Seyler (Vancouver Rowing Club)41. Brock Staller (UBC Thunderbirds)42. Evan Thomas (Burnaby Lake RC)43. Clayton Thornber (UVic Vikes) 44. Adam Timler (Bayside AA)45. Bryan Tyrer (UBC Thunderbirds)46. Shea Wakefield (UVic Vikes)47. Nathan Yanagiya (UVic Vikes) 48. Adam Zaruba (Capilano RFC)BC Bears South America Tour Roster1. Noah Barker (James Bay AA)2. Luke Campbell (UVic Vikes)3. Admir Cejvanovic (Burnaby Lake RC)4. Sean Ferguson (UBC Thunderbirds)5. Micha Govorchin (Burnaby Lake RC)6. Caleb Hansen (Vancouver Rowing Club) 7. Jake Ilnicki (Castaway Wanderers / Williams Lake)8. Pat Kay (UVic Vikes)9. Gord Kehoe (Castaway Wanderers RFC)10. Chase Kelliher (UVic Vikes)11. Andrew Lackner (Burnaby Lake RC)12. Anthony Luca (Burnaby Lake RC) 13. Scott MacKay (Burnaby Lake RC)14. Nate Mantle (Burnaby Lake RC)15. Callum Morrison (UBCOB Ravens)16. John Morris (Castaway Wanderers RFC)17. James Pitblado (UVic Vikes)18. Cole Racine (James Bay AA)19. Cody Rockson (Burnaby Lake RC)20. Brock Staller (UBC Thunderbirds)21. Adam Timler (Bayside AA)22. Evan Thomas (Burnaby Lake RC)23. Bryan Tyrer (UBC Thunderbirds)24. Shea Wakefield (UVic Vikes) BC Bears South America Tour StaffDirector of Rugby: Jim DixonForwards Coach: Ken GoodlandBacks Coach: Tom LukeAssistant Coach: Roger RobinsonStrength and Conditioning: Conan CooperAthletic Therapist: Jessica SmithTour Manager: Simon SmoldonThe BC Bears senior men's provincial program is proudly sponsored by Canadian Direct Insurance. BC Rugby would also like to recognize partners Langara Fishing Adventures and Rugby Canada for their support of the program. -30-


text:
The Carlos Coelho Story
Born in Brazil, Carlos E. Coelho studied Oboe in the United States at the Manhattan School of Music; SUNY Purchase (State Univ. of New York); Temple University (Philadelphia); and CUNY (City Univ. of New York), where he is a candidate for the Doctorate in Oboe Performance degree.
His teachers included Henry Schuman, Elaine Douvas, and Louis Rosenblatt. He also studied with Ingo Goritzki at the Hochschule für Musik und Theater in Hannover, Germany.
Music Runs in the Family
Carlos' first Oboe teacher was his father, who was director of the Conservatorio Musical de Tatui, one of the largest music schools in South America. Carlos and his father are not the only musicians in the family. His brother Tadeu is a professor of Flute at the North Carolina School for the Arts. Brother Benjamin, formerly the Principal Bassoonist of the Teatro Municipal in Rio de Janeiro, is now a Bassoon professor at the University of Iowa School of Music. A graduate of the Cleveland Institute of Music, brother Luiz is a band director in Cleveland, Ohio.
Formerly the Principal Oboist of the Campinas Symphony Orchestra and faculty member of the University of Campinas in Brazil, Carlos has also performed with the International Chamber Music Ensemble of the Associazione Musicale Riky Haertelt from Torino, Italy.
The Shop
Mr. Coelho is one of only two craftsmen in the United States trained in the F. Lorée factory in France. Since he established his business in 1992, he has repaired professional Oboes and English Horns for clients from his workshop, and has been a clinician at several master classes at universities across the United States, Brazil and Puerto Rico.
Carlos Coelho Woodwinds in Indianapolis, Indiana, provides a full range of repair and appraisal services. Carlos E. Coelho Woodwinds is an authorized official F. Lorée dealer, who receives his instruments directly from Lorée, Paris.
Mr. Coelho has designed Oboe and English Horn shaper tips, which are used by some of the world's top players. These shaper tips are made using computer-guided machines, which ensure great accuracy and precision.


text:
View photos from the 2014 USO Gala »
For more event information, please contact Emily Farwig at (703) 740-4970, firstname.lastname@example.com.
For sponsorship information, please contact Kelly Carlin at (571) 385-1365, firstname.lastname@example.com.
For media inquiries, please contact Gayle Fishel at (703) 908-6433, firstname.lastname@example.com
The USO has a limited room block at the Renaissance Hotel for a rate of $299 per night. To make your reservation, please click on the following link:
6:00 p.m. - Welcome Reception7:00 p.m. - Dinner and Evening Program
An estimated 1,000 guests will gather to pay special tribute to our men and women in uniform. Guests will include Washington dignitaries, Members of Congress, military leadership, USO corporate sponsors, members of the USO Board of Governors, and the media.
We would love to hear from you.
USO P.O. Box 96860 Washington, DC 20077-7677 Phone: 1-888-484-3876
© 2015 USO, Inc. All Rights Reserved.


text:
Oracle (Paperback)
|Author: RJ Scott
|Editor: Alison Todd
|Illustrator: Reese Dante
Learn more about Oracle:
Format: Paperback
Publisher: Createspace Independent Pub
Sku: 236537959
Publish Date: 8/13/2012
Dimensions: (in Inches) 9H x 6L x 0.75T
Pages: 310
See more in Romance / Adult
From the Publisher:
Oracle is a modern-day story about a mysterious man, an Empath, who appears to be a descendant of the Sybil at the oracle in Delphi. He holds power that, should it fall into the wrong hands, would become avaluable weapon.Young Alex Sheridan washed up on a beach with scars and marks covering most of his body. Scars that hide a horrific past and a key to his future.Luke MacKinnon is a shy professor of ancient languages brought in by the U.S. Army to translate documents that could lead to a powerful weapon; a modern-day Oracle. When the two meet, their connection is instant. Can Luke and Alex survive the evil that wants the Oracle's power?


text:
WESTCHESTER COUNTY, N.Y. -- Police are warning Westchester residents of ongoing telephone scams that have affected residents.
Residents are reminded that no government agency will ever demand a fine to be paid via Western Union or pre-paid debit card.
Residents are asked to beware of the following scams:
"Grandchild in Jail": In this scam, the caller will claim to be a friend or relative that got into trouble or was involved in an accident in another country (often Mexico, Canada or one of the Caribbean Islands) and needs money to get out of jail. In some cases the scammer will claim to be a police officer, saying their child/grandchild has been arrested and needs to have money sent to them for bail.
"IRS Tax Warrant": The caller will claim to be an agent or police officer from the Internal Revenue Service calling about a past due tax balance that is owed. The caller will tell the victim that unless the debt is paid immediately, they will send a team of officers to the victim's home to immediately arrest them.
"Jury Duty Warrant":The caller will claim to be a police officer or a warrant officer from Westchester County or New York State claiming to have a warrant for the victim for failing to report for jury duty. The scammer will also claim that unless the fine is paid immediately, the police will be sent to the victim's home to arrest them.
"Delinquent Con Edison Bill": The caller will claim to be a representative of Con Edison. In some cases the scammer has the victim's correct Con Edison Account Number. The scammer will then advise the resident that their Con Edison bill is past due and must be paid immediately to avoid termination of service.
- 1 Man ID'd In I-87 Fatal Motorcycle Crash
- 2 Man, 24, Killed In Sprain Brook Parkway One-Car Crash ID'd
- 3 Police Corral 90-Pound Alligator Crossing Street In New York City
- 4 Presidential Run Puts Spotlight On Trump's Westchester Estate
- 5 Outside Clinton Home, Astorino Seeks Hillary's Take On Affordable Housing


text:
Posts Tagged «gross baboon»
Leave Jay Z Alone
I would also like to know if Barneys has done what they did to those African-American kids to low-rent, mad, white trash. It might be worth an ask.… Read More »
Last year I Mean What took a sabbatical or a hiatus or a drug induced coma…something that kept me from consistently sharing my POV on all things ridiculous. Since then, Anderson Cooper @CNN started The Ridiculist, Chelsea Handler's show has gained in popularity and just about every Tom, Dick (big or otherwise) and Harry has chimed in their two cents via Twitter or Instagram (snore) and the only person losing out on telling it like it is was me. Since my accident I have been stockpiling my daily horrors on what's wrong with the world to the point of getting… Read More »
So glad that Obama stopped being a Friggin' Narc. Now pass me the box of Twinkies.… Read More »
Brooke Mueller in rehab is such old news that it's weird that she was even in the news today for going to rehab…again…which is like her weekly adventure.… Read More »
All this talk about the Fiscal Cliff reminds me of Road Runner and Wile E. Coyote. … Read More »
When innocent, good-hearted, well-intentioned, loving people die…way too young…it gives me pause to come back from days of grief to the real world and read a newspaper. There I am accosted by people that should be ashamed of themselves for opening their pie holes and spewing or Tweeting the kind of nonsense that should otherwise have them carving their draggy asses into hell rather than having a prime spot on the media landscape. Must I name names or will that make me equally as evil? Fine. John Sununu. How much longer must we listen to this jerk for? Hasn't he… Read More »


text:
New Order (writer)
Bizarre Love Triangle on MusicBrainz
Pete Yorn on Last.fm
Pete Yorn (b. July 27, 1974) is an American singer-songwriter and guitarist originally from Montville, New Jersey, United States. Yorn started as a drummer who also played guitar. In 1990, he was drumming for his band in a high school talent contest when someone suggested he sing the Replacements song "Talent Show." That went over so well, a competing band asked him to sing Neil Young's "Rockin' in the Free World" with them.
Read more about Pete Yorn on Last.fm.
Purchase for download
Also from this album:
Long Time Nothing New,Don't Wanna Cry


text:
Theatre in the Wild will be closed from 21 to 26 January, 2007 for routine maintenance, and the Festival of the Lion King show will be suspended during this period.
Source: Hong Kong Disneyland
Printable View
Theatre in the Wild will be closed from 21 to 26 January, 2007 for routine maintenance, and the Festival of the Lion King show will be suspended during this period.
Source: Hong Kong Disneyland
Not surprising given the reported number of times they have had technical difficulties and had to stop a show mid-stream
Even when I saw it last year they halted the show several minutes in due to some technical snafu.
ORWEN: I wonder what sort of testical difficulties they've been having? Did someone sing off key or mis a cue? Or did the fire breathing man get heartburn? I just don't understand!
They stop the show without warning and all the performers immediately leave the stage. Then they spend about 10 minutes moving the animal floats around (electronically), and hopefully everyone comes back and they finish the show.
ORWEN: Why, that's just awful!! If I was there to watch a show and they did that to me I'd...I'd....well, I'd demand my money back!!
ORGOCH: Stop yer belly-achin', sister! Ya oughtta be glad they'd even let a fat witch--like yerself--inta the park ta begin with! Just be glad they don't charge ya a group rate ta git in!!
Oh well... that closing effectively kills 21.7% of what is there to do at HKDL... But honestly, I sure hope they maintain this park on a regular schedule (as opposed to the MK) so I am willing to live with the inconvenience.
ORDDU: Though it's been said before, it's worth repeating; this is why it's so important to create as many new attractions for this park as soon as possible to help absorb the obvious over-flow of disappointed guests who won't be able to find enough to do, which means they aren't getting their money's worth.
ORWEN: And what happens on a day when Space Mountain breaks down at the same time Winnie the Pooh goes out of service? Yes, they really need a lot more attractions to help take up the slack.


text:
Union Pacific Boy Scouts of America 3-Bay Cylindrical Hopper #2010
6-27449 | Price: $79.99
BOY SCOUTS OF AMERICA® STANDARD O SCALE CARS?To compliment the Boy Scouts of America diesel locomotive: a limited selection of 100th Anniversary Standard O Scale rolling stock with Scout-inspired decoration as well as prototypical data found on actual Union Pacific freight cars. A perfect match for the U.P locomotive.
- Die-cast metal sprung trucks and operating couplers
- Hidden uncoupling tabs
- Rotating bearing caps
- Opening roof hatches
- Separately applied underframe details
Road Number: 2010
Gauge: Standard O Scale
Dimensions: Length: 13 ¾"
RailLine: Union Pacific
Minimum Curve: O-31
Lionel 2010 Volume 2


text:
Beyond the Border
News and analysis from the Texas-Mexico region.
Monthly Archive for April, 2013
FBI 302s cause a stir in Zetas trial
UPDATE: The U.S. Attorney's Office has acknowledged there was a misunderstanding and is alerting everyone involved. Things got a little dramatic at the end of jury selection today in the trial of five men accused of laundering money for the Zetas drug cartel. At the end of the day, Assistant U.S. Attorney Douglas Gardner told […] [Read More]