text:
Carnegie Mellon University. Extract from Andrew Moore's PhD Thesis: Ecient Memory-based Learning for Robot Control
- Tyrone Hawkins
- 2 years ago
- Views:
1 An intoductory tutorial on kd-trees Andrew W. Moore Carnegie Mellon University Extract from Andrew Moore's PhD Thesis: Ecient Memory-based Learning for Robot Control PhD. Thesis Technical Report No. 209, Computer Laboratory, University ofcambridge
2 Chapter 6 Kd-trees for Cheap Learning This chapter gives a specication of the nearest neighbour algorithm. It also gives both an informal and formal introduction to the kd-tree data structure. Then there is an explicit, detailed account of how the nearest neighbour search algorithm is implemented eciently, which is followed byanempirical investigation into the algorithm's performance. Finally, there is discussion of some other algorithms related to the nearest neighbour search. 6.1 Nearest Neighbour Specication Given two multi-dimensional spaces Domain = < k d and Range = < kr,letan exemplar be a member of Domain Range and let an exemplar-set be a nite set of exemplars. Given an exemplar-set, E, and a target domain vector, d, then a nearest neighbour of d is any. exemplar (d 0 r 0 ) 2 E such that None-nearer(E d d 0 ). Notice that there might be more than one suitable exemplar. This ambiguity captures the requirement that any nearest neighbour is adequate. None-nearer is dened thus: None-nearer(E d d 0 ), 8(d 00 r 00 ) 2 E j d ; d 0 jj d ; d 00 j (6.1) In Equation 6.1 the distance metric is Euclidean, though any other L p -norm could have been used. j d ; d 0 j= where d i is the ith component ofvector d. vu u X t i=k d i=1 (d i ; d 0 i) 2 (6.2) In the following sections I describe some algorithms to realize this abstract specication with the additional informal requirement that the computation time should be relatively short. 6-1
3 Algorithm: Nearest Neighbour by Scanning. Data Structures: domain-vector Avector of k d oating point numbers. range-vector Avector of k r oating point numbers. exemplar A pair: (domain-vector range-vector) Input: exlist, oftype list of exemplar dom, oftype domain-vector Output: nearest, oftype exemplar Preconditions: exlist is not empty Postconditions: if nearest represents the exemplar (d 0 r 0 ), and exlist represents the exemplar set E, and dom represents the vector d, then (d 0 r 0 ) 2 E and None-nearer(E d d 0 ). Code: 1. nearest-dist := innity 2. nearest := undened 3. for ex := each exemplar in exlist 3.1 dist := distance between dom and the domain of ex 3.2 if dist < nearest-dist then nearest-dist := dist nearest := ex Table 6.1: Finding Nearest Neighbour by scanning a list. 6.2 Naive Nearest Neighbour This operation could be achieved by representing the exemplar-set as a list of exemplars. In Table 6.1, I give the trivial nearest neighbour algorithm which scans the entire list. This algorithm has time complexity O(N) where N is the size of E. By structuring the exemplar-set more intelligently, it is possible to avoid making a distance computation for every member. 6.3 Introduction to kd-trees A kd-tree is a data structure for storing a nite set of points from a k-dimensional space. It was examined in detail by J.Bentley [Bentley, 1980 Friedman et al., 1977]. Recently, S.Omohundro has recommended it in a survey of possible techniques to increase the speed of neural network learning [Omohundro, 1987]. A kd-tree is a binary tree. The contents of each node are depicted in Table 6.2. Here I provide an informal description of the structure and meaning of the tree, and in the following subsection I 6-2
4 Field Name: Field Type Description dom-elt domain-vector Apoint from k d -d space range-elt range-vector Apoint from k r -d space split integer The splitting dimension left kd-tree A kd-tree representing those points to the left of the splitting plane right kd-tree A kd-tree representing those points to the right of the splitting plane Table 6.2: The elds of a kd-tree node give a formal denition of the invariants and semantics. The exemplar-set E is represented by the set of nodes in the kd-tree, each node representing one exemplar. The dom-elt eld represents the domain-vector of the exemplar and the range-elt eld represents the range-vector. The dom-elt component is the index for the node. It splits the space into two subspaces according to the splitting hyperplane of the node. All the points in the \left" subspace are represented by theleft subtree, and the points in the \right" subspace by the right subtree. The splitting hyperplane is a plane which passes through dom-elt and which is perpendicular to the direction specied by the split eld. Let i be the value of the split eld. Then apoint is to the left of dom-elt if and only if its ith component is less than the ith component of dom-elt. The complimentary denition holds for the right eld. If a node has no children, then the splitting hyperplane is not required. Figure 6.1 demonstrates a kd-tree representation of the four dom-elt points (2 5), (3 8), (6 3) and (8 9). The root node, with dom-elt (2 5) splits the plane in the y-axis into two subspaces. The point (3 8) lies in the lower subspace, that is f(x y) j y<5g, and so is in the left subtree. Figure 6.2 shows how the nodes partition the plane Formal Specication of a kd-tree The reader who is content with the informal description above can omit this section. I dene a mapping which maps the tree to the exemplar-set it represents: exset-rep : kd-tree! exemplar-set (6.3) exset-rep(empty) = exset-rep(< d r ; empty empty >) = f(d r)g exset-rep(< d r split tree left tree right >) = exset-rep(tree left ) [f(d r)g[exset-rep(tree right ) (6.4) 6-3
5 [2,5] [6,3] [3,8] [8,9] Figure 6.1 A 2d-tree of four elements. The splitting planes are not indicated. The [2,5] node splits along the y = 5 plane and the [3,8] node splits along the x = 3 plane. [3,8] [8,9] Figure 6.2 [2,5] How the tree of Figure 6.1 splits up the x,y plane. [6,3] 6-4
6 The invariant is that subtrees only ever contain dom-elts which are on the correct side of all their ancestors' splitting planes. Is-legal-kdtree(empty): Is-legal-kdtree(< d r ; empty empty >): Is-legal-kdtree(< d r split tree left tree right >), 8(d 0 r 0 ) 2 exset-rep(tree left ) d 0 split d split^ 8(d 0 r 0 ) 2 exset-rep(tree right ) d 0 split >d split^ Is-legal-kdtree(tree left )^ Is-legal-kdtree(tree right ) (6.5) Constructing a kd-tree Given an exemplar-set E, akd-tree can be constructed by the algorithm in Table 6.3. The pivotchoosing procedure of Step 2 inspects the set and chooses a \good" domain vector from this set to use as the tree's root. The discussion of how sucharootischosen is deferred to Section 6.7. Whichever exemplar is chosen as root will not aect the correctness of the kd-tree, though the tree's maximum depth and the shape of the hyperregions will be aected. 6.4 Nearest Neighbour Search In this section, I describe the nearest neighbour algorithm which operates on kd-trees. I begin with an informal description and worked example, and then give the precise algorithm. A rst approximation is initially found at the leaf node which contains the target point. In Figure 6.3 the target point is marked X and the leaf node of the region containing the target is coloured black. As is exemplied in this case, this rst approximation is not necessarily the nearest neighbour, but at least we know any potential nearer neighbour must lie closer, and so must lie within the circle centred on X and passing through the leaf node. We nowback up to the parent of the current node. In Figure 6.4 this parent is the black node. We compute whether it is possible for a closer solution to that so far found to exist in this parent's other child. Here it is not possible, because the circle does not intersect with the (shaded) space occupied by the parent's other child. If no closer neighbour can exist in the other child, the algorithm can immediately move up a further level, else it must recursively explore the other child. In this example, the next parent which is checked will need to be explored, because the area it covers (i.e. everywhere north of the central horizontal line) does intersect with the best circle so far. Table 6.4 describes my actual implementation of the nearest neighbour algorithm. It is called with four parameters: the kd-tree, the target domain vector, a representation of a hyperrectangle in Domain, andavalue indicating the maximum distance from the target which isworth searching. The search will only take place within those portions of the kd-tree which lie both in the hyper- 6-5
7 Algorithm: Constructing a kd-tree Input: exset, oftype exemplar-set Output: kd, oftype kdtree Pre: None Post: exset = exset-rep(kd) ^ Is-legal-kdtree(kd) Code: 1. If exset is empty then return the empty kdtree 2. Call pivot-choosing procedure, which returns twovalues: ex := a member of exset split := the splitting dimension 3. d := domain vector of ex 4. exset' := exset with ex removed 5. r := range vector of ex 6. exsetleft := f(d 0 r 0 ) 2 exset' j d 0 split d split g 7. exsetright := f(d 0 r 0 ) 2 exset' j d 0 split >d split g 8. kdleft := recursively construct kd-tree from exsetleft 9. kdright := recursively construct kd-tree from exsetright 10. kd := < d r split kdleft kdright > Proof: By induction on the length of exset and the denitions of exset-rep and Is-legal-kdtree. Table 6.3: Constructing a kd-tree from a set of exemplars. Figure 6.3 The black dot is the dot which owns the leaf node containing the target (the cross). Any nearer neighbour must lie inside this circle. 6-6
8 Figure 6.4 The black dot is the parent of the closest found so far. In this case the black dot's other child (shaded grey) need not be searched. rectangle, and within the maximum distance to the target. The caller of the routine will generally specify the innite hyperrectangle which covers the whole of Domain, and the innite maximum distance. Before discussing its execution, I will explain how the operations on the hyperrectangles can be implemented. A hyperrectangle is represented by two arrays: one of its minimum coordinates, the other of its maximum coordinates. To cut the hyperrectangle, so that one of its edges is moved closer to its centre, the appropriate array component is altered. To check to see if a hyperrectangle hr intersects with a hypersphere radius r centered at point t, we nd the point p in hr which is closest to t. Write hr min i as the minimum extreme of hr in the ith dimension and hr max i maximum extreme. p i,theith component of this closest point is computed thus: p i = 8 >< >: hr min if t i i hr min i t i if hr min <t i i < hr max i hr min if t i i hr max i The objects intersect only if the distance between p and t is less than or equal to r. as the (6.6) The search is depth rst, and uses the heuristic of searching rst the child node which contains the target. Step 1 deals with the trivial empty tree case, and Steps 2 and 3 assign two important local variables. Step 4 cuts the current hyperrectangle into the two hyperrectangles covering the space occupied by the child nodes. Steps 5{7 determine which child contains the target. After Step 8, when this initial child is searched, it may be possible to prove that there cannot be any closer point in the hyperrectangle of the further child. In particular, the point at the current node must be out of range. The test is made in Steps 9 and 10. Step 9 restricts the maximum radius in which any possible closer point could lie, and then the test in Step 10 checks whether there is any 6-7
9 Algorithm: Nearest Neighbour in a kd-tree Input: kd, oftype kdtree target, oftype domain vector hr, oftype hyperrectangle max-dist-sqd, oftype oat Output: nearest, oftype exemplar dist-sqd, oftype oat Pre: Is-legal-kdtree(kd) Post: Informally, the postcondition is that nearest is a nearest exemplar to target which also lies both within the hyperrectangle hr and within distance p max-dist-sqd of target. p dist-sqd is the distance of this nearest point. If there is no such point then dist-sqd contains innity. Code: 1. if kd is empty then set dist-sqd to innity and exit. 2. s := split eld of kd 3. pivot := dom-elt eld of kd 4. Cut hr into two sub-hyperrectangles left-hr and right-hr. The cut plane is through pivot and perpendicular to the s dimension. 5. target-in-left := target s pivot s 6. if target-in-left then 6.1 nearer-kd := left eld of kd and nearer-hr := left-hr 6.2 further-kd := right eld of kd and further-hr := right-hr 7. if not target-in-left then 7.1 nearer-kd := right eld of kd and nearer-hr := right-hr 7.2 further-kd := left eld of kd and further-hr := left-hr 8. Recursively call Nearest Neighbour with parameters (nearer-kd,target, nearer-hr,max-dist-sqd), storing the results in nearest and dist-sqd 9. max-dist-sqd := minimum of max-dist-sqd and dist-sqd 10. A nearer point could only lie in further-kd if there were some part of further-hr within distance p max-dist-sqd of target. if this is the case then 10.1 if (pivot ; target) 2 < dist-sqd then nearest := (pivot range-elt eld of kd) dist-sqd := (pivot ; target) max-dist-sqd := dist-sqd 10.2 Recursively call Nearest Neighbour with parameters (further-kd,target, further-hr,max-dist-sqd), storing the results in temp-nearest and temp-dist-sqd 10.3 If temp-dist-sqd < dist-sqd then nearest := temp-nearest and dist-sqd := temp-dist-sqd Proof: Outlined in text Table 6.4: The Nearest Neighbour Algorithm 6-8
10 space in the hyperrectangle of the further child which lies within this radius. If it is not possible then no further search is necessary. Ifitis possible, then Step 10:1checks if the point associated with the current node of the tree is closer than the closest yet. Then, in Step 10.2, the further child is recursively searched. The maximum distance worth examining in this further search isthe distance to the closest point yet discovered. The proof that this will nd the nearest neighbour within the constraints is by induction on the size of the kd-tree. If the cuto were not made in Step 10, then the proof would be straightforward: the point returned is the closest out of (i) the closest point in the nearer child, (ii) the point at the current node and (iii) the closest point in the further child. If the cuto were made in Step 10, then the point returned is the closest point in the nearest child, and we can show that neither the current point, nor any point in the further child can possibly be closer. Many local optimizations are possible which while not altering the asymptotic performance of the algorithm will multiply the speed by a constant factor. In particular, it is in practice possible to hold almost all of the search state globally, instead of passing it as recursive parameters. 6.5 Theoretical Behaviour Given a kd-tree with N nodes, how many nodes need to be inspected in order to nd the proven nearest neighbour using the algorithm in Section 6.4?. It is clear at once that on average, at least O(log N) inspections are necessary, because any nearest neighbour search requires traversal to at least one leaf of the tree. It is also clear that no more than N nodes are searched: the algorithm visits each node at most once. Figure 6.5 graphically shows why we might expect considerably fewer than N nodes to be visited: the shaded areas correspond to areas of the kd-tree which were cut o. The important values are (i) the worst case number of inspections and (ii) the expected number of inspections. It is actually easy to construct worst case distributions of the points which will force nearly all the nodes to be inspected. In Figure 6.6, the tree is two-dimensional, and the points are scattered along the circumference of a circle. If we request the nearest neighbour with the target close to the centre of the circle, it will therefore be necessary for each rectangle, and hence each leaf, to be inspected (this is in order to ensure that there is no point lying inside the circle in any rectangle). Calculation of the expected number of inspections is dicult, because the analysis depends critically on the expected distribution of the points in the kd-tree, and the expected distribution of the target points presented to the nearest neighbour algorithm. The analysis is performed in [Friedman et al., 1977]. This paper considers the expected number of hyperrectangles corresponding to leaf nodes which will provably need to be searched. Such hyperrectangles intersect the volume enclosed by ahypersphere centered on the query point whose surface passes through the nearest neighbour. For example, in Figure 6.5 the hypersphere (in this 6-9
11 Figure 6.5 Generally during a nearest neighbour search only a few leaf nodes need to be inspected. Figure 6.6 A bad distribution which forces almost all nodes to be inspected. 6-10
12 case a circle) is shown, and the number of intersecting hyperrectangles is two. The paper shows that the expected number of intersecting hyperrectangles is independent of N, the number of exemplars. The asymptotic search timeisthus logarithmic because the time to descend from the root of the tree to the leaves is logarithmic (in a balanced tree), and then an expected constant amountofbacktracking is required. However, this reasoning was based on the assumption that the hyperrectangles in the tree tend to be hypercubic in shape. Empirical evidence in my investigations has shown that this is not generally the case for their tree building strategy. This is discussed and demonstrated in Section 6.7. A second danger is that the cost, while independent ofn, is exponentially dependent onk, the dimensionality of the domain vectors 1. Thus theoretical analysis provides some insight into the cost, but here, empirical investigation will be used to examine the expense of nearest neighbour in practice. 6.6 Empirical Behaviour In this section I investigate the empirical behaviour of the nearest neighbour searching algorithm. We expect that the number of nodes inspected in the tree varies according to the following properties of the tree: N, the size of the tree. k dom, the dimensionality of the domain vectors in the tree. This value is the k in kd-tree. d distrib, the distribution of the domain vectors. This can be quantied as the \true" dimensionality of the vectors. For example, if the vectors had three components, but all lay onthe surface of a sphere, then the underlying dimensionality would be 2. In general, discovery of the underlying dimensionality ofagiven sample of points is extremely dicult, but for these tests it is a straightforward matter to generate such points. To makeakd-tree with underlying dimensionality d distrib, I use randomly generated k dom -dimensional domain vectors which lie on a d distrib -dimensional hyperelliptical surface. The random vector generation algorithm is as follows: Generate d distrib random angles i 2 [0 2) where 0 i<d distrib. Then let the jth component of the vector be Q i=d;1 i=0 sin( i + ij ). The phase angles ij are dened as ij = 1 2 if the jth bit of the binary representation of i is 1 and is zero otherwise. d target, the probability distribution from which the search target vector will be selected. I shall assume that this distribution is the same as that which determines the domain vectors. This is indeed what will happen when the kd-tree is used for learning control. 1 This was pointed out to the author by N. Maclaren. 6-11
13 Figure 6.7 Number of inspections required during a nearest neighbour search against the size of the kd-tree. In this experiment the tree was four-dimensional and the underlying distribution of the points was threedimensional In the following sections I investigate how performance depends on each of these properties Performance against Tree Size Figures 6.7 and 6.8 graph the number of nodes inspected against the number of nodes in the entire kd-tree. Each value was derived by generating a random kd-tree, and then requesting 500 random nearest neighbour searches on the kd-tree. The average number of inspected nodes was recorded. Anodewas counted as being inspected if the distance between it and the target was computed. Figure 6.7 was obtained from a 4d-tree with an distribution distribution d distrib = 3. Figure 6.8 used an 8d-tree with an underlying distribution d distrib =8. It is immediately clear that after a certain point, the expense of a nearest neighbour search has no detectable increase with the size of the tree. This agrees with the proposed model of search cost logarithmic with a large additive constant term Performance against the \k" in kd-tree Figure 6.9 graphs the number of nodes inspected against k dom, the number of components in the kd-tree's domain vectors for a 10,000 node tree. The underlying dimensionality was also k dom. The number of inspections per search rises very quickly, possibly exponentially, withk dom. This behaviour, the massive increase in cost with dimension, is familiar in computational geometry. 6-12
14 Figure 6.8 Number of inspections against kd-tree size for an eight-dimensional tree with an eight-dimensional underlying distribution Figure Number of inspections graphed against tree dimension. In these experiments the points had an underlying distribution with the same dimensionality as the tree
15 Figure Number of inspections graphed against underlying dimensionality for a fourteen-dimensional tree Performance against the Distribution Dimensionality This experiment conrms that it is d distrib, the distribution dimension from which the points were selected, rather than k dom which critically aects the search performance. The trials for Figure 6.10 used a 10,000 node kd-tree with domain dimension of 14, for various values of d distrib. The important observation is that for 14d-trees, the performance does improve greatly if the underlying distribution-dimension is relatively low. Conversely, Figure 6.11 shows that for a xed (4-d) underlying dimensionality, the search expense does not seem to increase any worse than linearly with k dom When the Target is not Chosen from the kd-tree's Distribution In this experiment the points were distributed on a three dimensional elliptical surface in tendimensional space. The target vector was, however, chosen at random from a ten-dimensional distribution. The kd-tree contained 10,000 points. The average number of inspections over 50 searches was found to be 8,396. This compares with another experiment in which bothpoints and target were distributed in ten dimensions and the average number of inspections was only 248. The reason for the appalling performance was exemplied in Figure 6.6: if the target is very far from its nearest neighbour then very many leaf nodes must be checked Conclusion The speed of the search (measured as the number of distance computations required) seems to vary ::: 6-14
16 Figure 6.11 Number of inspections graphed against tree dimension, given a constant four dimensional underlying distribution :::only marginally with tree size. If the tree is suciently large with respect to the number of dimensions, it is essentially constant. :::very quickly with the dimensionality of the distribution of the datapoints, d distrib. :::linearly with the number of components in the kd-tree's domain (k dom ), given a xed distribution dimension (d distrib ). There is also evidence to suggest that unless the target vector is drawn from the same distribution as the kd-tree points, performance can be greatly worsened. These results support the belief that real time searching for nearest neighbours is practical in a robotic system where we can expect the underlying dimensionality of the data points to be low, roughly less than 10. This need not mean that the vectors in the input space should have less than ten components. For data points obtained from robotic systems it will not be easy to decide what the underlying dimensionality is. However Chapter 10 will show that the data does tend to lie within a number of low dimensional subspaces. 6.7 Further kd-tree Operations In this section I discuss some other operations on kd-trees which are required for use in the SAB learning system. These include incrementally adding a point toakd-tree, range searching, and selecting a pivot point. 6-15
17 6.7.1 Range Searching a kd-tree range-search : exemplar-set Domain <!exemplar-set The abstract range search operation on an exemplar-set nds all exemplars whose domain vectors are within a given distance of a target point: range-search(e d r) = f(d 0 r 0 ) 2 E j (d ; d 0 ) 2 <r 2 g This is implemented by a modied nearest neighbour search. The modications are that (i) the initial distance is not reduced as closer points are discovered and (ii) all discovered points within the distance are returned, not just the nearest. The complexity of this operation is shown, in [Preparata and Shamos, 1985], to still be logarithmic in N (the size of E) for a xed range size Choosing a Pivot from an Exemplar Set The tree building algorithm of Section 6.3 requires that a pivot and a splitting plane be selected from which to build the root of a kd-tree. It is desirable for the tree to be reasonably balanced, and also for the shapes of the hyperregions corresponding to leaf nodes to be fairly equally proportioned. The rst criterion is important because a badly unbalanced tree would perhaps have O(N) accessing behaviour instead of O(log N). The second criterion is in order to maximize cuto opportunities for the nearest neighbour search. This is dicult to formalize, but can be motivated by an illustration. In Figure 6.12 is a perfectly balanced kd-tree in which the leaf regions are very non-square. Figure 6.13 illustrates a kd-tree representing the same set of points, but which promotes squareness at the expense of some balance. One pivoting strategy which would lead to a perfectly balanced tree, and which is suggested in [Omohundro, 1987], istopick the splitting dimension as that with maximum variance, and let the pivot be the point with the median split component. This will, it is hoped, tend to promote square regions because having split in one dimension, the next level in the tree is unlikely to nd that the same dimension has maximum spread, and so will choose a dierent dimension. For uniform distributions this tends to perform reasonably well, but for badly skewed distributions the hyperregions tend to take long thin shapes. This is exemplied in Figure 6.12 which has been balanced using this standard median pivot choice. To avoid this bad case, I choose a pivot which splits the exemplar set in the middle of the range of the most spread dimension. As can be seen in Figure 6.13, this tends to favour squarer regions at the expense of a slight imbalance in the kd-tree. This means that large empty areas of space are lled with only a few hyperrectangles which are themselves large. Thus, the number of leaf nodes which need to be inspected in case they contain a nearer neighbour is smaller than for the original case, which had many small thin hyperrectangles. 6-16
18 Figure 6.12 A 2d tree balanced using the `median of the most spread dimension' pivoting strategy. Figure 6.13 A 2d tree balanced using the `closest to the centre of the widest dimension' pivoting strategy. 6-17
19 My pivot choice algorithm is to rstly choose the splitting dimension as the longest dimension of the current hyperrectangle, and then choose the pivot as the point closest to the middle of the hyperrectangle along this dimension. Occasionally, this pivot may even be an extreme point along its dimension, leading to an entirely unbalanced node. This is worth it, because it creates a large empty leaf node. It is possible but extremely unlikely that the points could be distributed in such away as to cause the tree to have one empty child at every level. This would be unacceptable, and so above a certain depth threshold, the pivots are chosen using the standard median technique. Selecting the median as the split and selecting the closest to the centre of the range are both O(N) operations, and so either way a tree rebalance is O(N log N) Incrementally Adding a Point to a kd-tree Firstly, the leaf node which contains the new point is computed. The hyperrectangle corresponding to this leaf is also obtained. See Section 6.4 for hyperrectangle implementation. When the leaf node is found it may either be (i) empty, in which case it is simply replaced by a new singleton node, or (ii) it contains a singleton node. In case (ii) the singleton node must be given a child, and so its previously irrelevant spliteldmust be dened. The split eld should be chosen to preserve the squareness of the new subhyperrectangles. A simple heuristic is used. The split dimension is chosen as the dimension in which thehyperrectangle is longest. This heuristic is motivated by the same requirement as for tree balancing that the regions should be as square as possible, even if this means some loss of balance. This splitting choice is just a heuristic, and there is no guarantee that a series of points added in this way will preserve the balance of the kd-tree, nor that the hyperrectangles will be well shaped for nearest neighbour search. Thus, on occasion (such as when the depth exceeds a small multiple of the best possible depth) the tree is rebuilt. Incremental addition costs O(log N) Q Nearest Neighbours This uses a modied version of the nearest neighbour search. Instead of only searching within a sphere whose radius is the closest distance yet found, the search is within a sphere whose radius is the Qth closest yet found. Until Q points have been found, this distance is innity Deleting a Point from a kd-tree If the point is at a leaf, this is straightforward. Otherwise, it is dicult, because the structure of both trees below this node are pivoted around the point we wish to remove. One solution would be to rebuild the tree below the deleted point, but on occasion this would be very expensive. My solution is to mark the point as deleted with an extra eld in the kd-tree node, and to ignore deletion nodes in nearest neighbour and similar searches. When the tree is next rebuilt, all deletion nodes are removed. 6-18
20 Bibliography [Bentley, 1980] J. L. Bentley. Multidimensional Divide and Conquer. Communications of the ACM, 23(4): , [Friedman et al., 1977] J. H. Friedman, J. L. Bentley, and R. A. Finkel. An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Trans. on Mathematical Software, 3(3):209{ 226, September [Omohundro, 1987] S. M. Omohundro. Ecient Algorithms with Neural Network Behaviour. Journal of Complex Systems, 1(2):273{347, [Preparata and Shamos, 1985] F. P. Preparata and M. Shamos. Computational Geometry. Springer-Verlag, Bib-1
Data Warehousing und Data Mining
Data Warehousing und Data Mining Multidimensionale Indexstrukturen Ulf Leser Wissensmanagement in der Bioinformatik Content of this Lecture Multidimensional Indexing Grid-Files Kd-trees Ulf Leser: DataMore information
Section 1.1. Introduction to R n
The Calculus of Functions of Several Variables Section. Introduction to R n Calculus is the study of functional relationships and how related quantities change with each other. In your first exposure toMore information
Computational Geometry. Lecture 1: Introduction and Convex Hulls
Lecture 1: Introduction and convex hulls 1 Geometry: points, lines,... Plane (two-dimensional), R 2 Space (three-dimensional), R 3 Space (higher-dimensional), R d A point in the plane, 3-dimensional space,More information
R-trees. R-Trees: A Dynamic Index Structure For Spatial Searching. R-Tree. Invariants
R-Trees: A Dynamic Index Structure For Spatial Searching A. Guttman R-trees Generalization of B+-trees to higher dimensions Disk-based index structure Occupancy guarantee Multiple search paths InsertionsMore information
Divide-and-Conquer. Three main steps : 1. divide; 2. conquer; 3. merge.
Divide-and-Conquer Three main steps : 1. divide; 2. conquer; 3. merge. 1 Let I denote the (sub)problem instance and S be its solution. The divide-and-conquer strategy can be described as follows. ProcedureMore information
Common Core Unit Summary Grades 6 to 8
Common Core Unit Summary Grades 6 to 8 Grade 8: Unit 1: Congruence and Similarity- 8G1-8G5 rotations reflections and translations,( RRT=congruence) understand congruence of 2 d figures after RRT DilationsMore information
SOLVING DATABASE QUERIES USING ORTHOGONAL RANGE SEARCHING CPS234: Computational Geometry Prof. Pankaj Agarwal Prepared by: Khalid Al Issa (email@example.com) Fall 2005 BACKGROUND : RANGE SEARCHING, aMore information
Vector storage and access; algorithms in GIS. This is lecture 6
Vector storage and access; algorithms in GIS This is lecture 6 Vector data storage and access Vectors are built from points, line and areas. (x,y) Surface: (x,y,z) Vector data access Access to vectorMore information
. INNER PRODUCT SPACES.. Definition So far we have studied abstract vector spaces. These are a generalisation of the geometric spaces R and R. But these have more structure than just that of a vector space.More information
Full and Complete Binary Trees
Full and Complete Binary Trees Binary Tree Theorems 1 Here are two important types of binary trees. Note that the definitions, while similar, are logically independent. Definition: a binary tree T is fullMore information
MATHEMATICS CLASS - XII BLUE PRINT - II. (1 Mark) (4 Marks) (6 Marks)
BLUE PRINT - II MATHEMATICS CLASS - XII S.No. Topic VSA SA LA TOTAL ( Mark) (4 Marks) (6 Marks). (a) Relations and Functions 4 () 6 () 0 () (b) Inverse trigonometric Functions. (a) Matrices DeterminantsMore information
Classification algorithm in Data mining: An Overview
Classification algorithm in Data mining: An Overview S.Neelamegam #1, Dr.E.Ramaraj *2 #1 M.phil Scholar, Department of Computer Science and Engineering, Alagappa University, Karaikudi. *2 Professor, DepartmentMore information
A Non-Linear Schema Theorem for Genetic Algorithms
A Non-Linear Schema Theorem for Genetic Algorithms William A Greene Computer Science Department University of New Orleans New Orleans, LA 70148 bill@csunoedu 504-280-6755 Abstract We generalize HollandMore information
Binary Search Trees. A Generic Tree. Binary Trees. Nodes in a binary search tree ( B-S-T) are of the form. P parent. Key. Satellite data L R
Binary Search Trees A Generic Tree Nodes in a binary search tree ( B-S-T) are of the form P parent Key A Satellite data L R B C D E F G H I J The B-S-T has a root node which is the only node whose parentMore information
Outline BST Operations Worst case Average case Balancing AVL Red-black B-trees. Binary Search Trees. Lecturer: Georgy Gimel farb
Binary Search Trees Lecturer: Georgy Gimel farb COMPSCI 220 Algorithms and Data Structures 1 / 27 1 Properties of Binary Search Trees 2 Basic BST operations The worst-case time complexity of BST operationsMore information
Topology-based network security
Topology-based network security Tiit Pikma Supervised by Vitaly Skachek Research Seminar in Cryptography University of Tartu, Spring 2013 1 Introduction In both wired and wireless networks, there is theMore information
Introduction to Statistical Machine Learning
CHAPTER Introduction to Statistical Machine Learning We start with a gentle introduction to statistical machine learning. Readers familiar with machine learning may wish to skip directly to Section 2,More information
Faster deterministic integer factorisation
David Harvey (joint work with Edgar Costa, NYU) University of New South Wales 25th October 2011 The obvious mathematical breakthrough would be the development of an easy way to factor large prime numbersMore information
Design, Implementation and Preliminary Analysis of General Multidimensional Trees
Exchange Internship Design, Implementation and Preliminary Analysis of General Multidimensional Trees Author: Nikolett Bereczky Supervisors: Amalia Duch Brown, Krisztián Németh Ponent: Lluís Solano CreatedMore information
28 Closest-Point Problems -------------------------------------------------------------------
28 Closest-Point Problems ------------------------------------------------------------------- Geometric problems involving points on the plane usually involve implicit or explicit treatment of distancesMore information
Approximation Algorithms
Approximation Algorithms or: How I Learned to Stop Worrying and Deal with NP-Completeness Ong Jit Sheng, Jonathan (A0073924B) March, 2012 Overview Key Results (I) General techniques: Greedy algorithmsMore information
Chapter 4 Multi-Stage Interconnection Networks The general concept of the multi-stage interconnection network, together with its routing properties, have been used in the preceding chapter to describeMore information
! Solve problem to optimality. ! Solve problem in poly-time. ! Solve arbitrary instances of the problem. !-approximation algorithm.
Approximation Algorithms Chapter Approximation Algorithms Q Suppose I need to solve an NP-hard problem What should I do? A Theory says you're unlikely to find a poly-time algorithm Must sacrifice one ofMore information
Binary Space Partitions for Axis-Parallel Line Segments: Size-Height Tradeoffs
Binary Space Partitions for Axis-Parallel Line Segments: Size-Height Tradeoffs Sunil Arya Department of Computer Science The Hong Kong University of Science and Technology Clear Water Bay, Kowloon, HongMore information
Clustering Via Decision Tree Construction
Clustering Via Decision Tree Construction Bing Liu 1, Yiyuan Xia 2, and Philip S. Yu 3 1 Department of Computer Science, University of Illinois at Chicago, 851 S. Morgan Street, Chicago, IL 60607-7053.More information
Utah Core Curriculum for Mathematics
Core Curriculum for Mathematics correlated to correlated to 2005 Chapter 1 (pp. 2 57) Variables, Expressions, and Integers Lesson 1.1 (pp. 5 9) Expressions and Variables 2.2.1 Evaluate algebraic expressionsMore information
Current Standard: Mathematical Concepts and Applications Shape, Space, and Measurement- Primary
Shape, Space, and Measurement- Primary A student shall apply concepts of shape, space, and measurement to solve problems involving two- and three-dimensional shapes by demonstrating an understanding of:More information
Multimedia Databases. Wolf-Tilo Balke Philipp Wille Institut für Informationssysteme Technische Universität Braunschweig http://www.ifis.cs.tu-bs.
Multimedia Databases Wolf-Tilo Balke Philipp Wille Institut für Informationssysteme Technische Universität Braunschweig http://www.ifis.cs.tu-bs.de 14 Previous Lecture 13 Indexes for Multimedia Data 13.1More information
princeton univ. F 13 cos 521: Advanced Algorithm Design Lecture 6: Provable Approximation via Linear Programming Lecturer: Sanjeev Arora
princeton univ. F 13 cos 521: Advanced Algorithm Design Lecture 6: Provable Approximation via Linear Programming Lecturer: Sanjeev Arora Scribe: One of the running themes in this course is the notion ofMore information
Efficiency of algorithms. Algorithms. Efficiency of algorithms. Binary search and linear search. Best, worst and average case.
Algorithms Efficiency of algorithms Computational resources: time and space Best, worst and average case performance How to compare algorithms: machine-independent measure of efficiency Growth rate ComplexityMore information
root node level: internal node edge leaf node CS@VT Data Structures & Algorithms 2000-2009 McQuain
inary Trees 1 A binary tree is either empty, or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root, which are disjoint from eachMore information
NEW YORK STATE TEACHER CERTIFICATION EXAMINATIONS TEST DESIGN AND FRAMEWORK September 2014 Authorized for Distribution by the New York State Education Department This test design and framework documentMore information
Introduction to Support Vector Machines. Colin Campbell, Bristol University
Introduction to Support Vector Machines Colin Campbell, Bristol University 1 Outline of talk. Part 1. An Introduction to SVMs 1.1. SVMs for binary classification. 1.2. Soft margins and multi-class classification.More information
Module1. x 1000. y 800.
Module1 1 Welcome to the first module of the course. It is indeed an exciting event to share with you the subject that has lot to offer both from theoretical side and practical aspects. To begin with,More information
Persistent Data Structures
6.854 Advanced Algorithms Lecture 2: September 9, 2005 Scribes: Sommer Gentry, Eddie Kohler Lecturer: David Karger Persistent Data Structures 2.1 Introduction and motivation So far, we ve seen only ephemeralMore information
Lecture 4 Online and streaming algorithms for clustering
CSE 291: Geometric algorithms Spring 2013 Lecture 4 Online and streaming algorithms for clustering 4.1 On-line k-clustering To the extent that clustering takes place in the brain, it happens in an on-lineMore information
Clustering. Chapter 7. 7.1 Introduction to Clustering Techniques. 7.1.1 Points, Spaces, and Distances
240 Chapter 7 Clustering Clustering is the process of examining a collection of points, and grouping the points into clusters according to some distance measure. The goal is that points in the same clusterMore information
Linear Codes. Chapter 3. 3.1 Basics
Chapter 3 Linear Codes In order to define codes that we can encode and decode efficiently, we add more structure to the codespace. We shall be mainly interested in linear codes. A linear code of lengthMore information
NEW MEXICO Grade 6 MATHEMATICS STANDARDS
PROCESS STANDARDS To help New Mexico students achieve the Content Standards enumerated below, teachers are encouraged to base instruction on the following Process Standards: Problem Solving Build new mathematicalMore information
Graphs without proper subgraphs of minimum degree 3 and short cycles
Graphs without proper subgraphs of minimum degree 3 and short cycles Lothar Narins, Alexey Pokrovskiy, Tibor Szabó Department of Mathematics, Freie Universität, Berlin, Germany. August 22, 2014 AbstractMore information
Algebra I. In this technological age, mathematics is more important than ever. When students
In this technological age, mathematics is more important than ever. When students leave school, they are more and more likely to use mathematics in their work and everyday lives operating computer equipment,More information
Number Sense and Operations
Number Sense and Operations representing as they: 6.N.1 6.N.2 6.N.3 6.N.4 6.N.5 6.N.6 6.N.7 6.N.8 6.N.9 6.N.10 6.N.11 6.N.12 6.N.13. 6.N.14 6.N.15 Demonstrate an understanding of positive integer exponentsMore information
Efficient Data Structures for Decision Diagrams
Artificial Intelligence Laboratory Efficient Data Structures for Decision Diagrams Master Thesis Nacereddine Ouaret Professor: Supervisors: Boi Faltings Thomas Léauté Radoslaw Szymanek Contents Introduction...More information
OPTIMUM PARTITION PARAMETER OF DIVIDE-AND-CONQUER ALGORITHM FOR SOLVING CLOSEST-PAIR PROBLEM Mohammad Zaidul Karim 1 and Nargis Akter 2 1 Department of Computer Science and Engineering, Daffodil InternationalMore information
1/1 7/4 2/2 12/7 10/30 12/25
Binary Heaps A binary heap is dened to be a binary tree with a key in each node such that: 1. All leaves are on, at most, two adjacent levels. 2. All leaves on the lowest level occur to the left, and allMore information
Copyrighted Material. Chapter 1 DEGREE OF A CURVE
Chapter 1 DEGREE OF A CURVE Road Map The idea of degree is a fundamental concept, which will take us several chapters to explore in depth. We begin by explaining what an algebraic curve is, and offer twoMore information
KDDCS: A Load-Balanced In-Network Data-Centric Storage Scheme for Sensor Networks
KDDCS: A Load-Balanced In-Network Data-Centric Storage Scheme for Sensor Networks Mohamed Aly Kirk Pruhs Panos K. Chrysanthis Department of Computer Science University of Pittsburgh Pittsburgh, PA 1526,More information
Binary Search. Search for x in a sorted array A.
Divide and Conquer A general paradigm for algorithm design; inspired by emperors and colonizers. Three-step process: 1. Divide the problem into smaller problems. 2. Conquer by solving these problems. 3.More information
Clustering. Danilo Croce Web Mining & Retrieval a.a. 2015/201 16/03/2016
Clustering Danilo Croce Web Mining & Retrieval a.a. 2015/201 16/03/2016 1 Supervised learning vs. unsupervised learning Supervised learning: discover patterns in the data that relate data attributes withMore information
Introduction to Algorithms March 10, 2004 Massachusetts Institute of Technology Professors Erik Demaine and Shafi Goldwasser Quiz 1.
Introduction to Algorithms March 10, 2004 Massachusetts Institute of Technology 6.046J/18.410J Professors Erik Demaine and Shafi Goldwasser Quiz 1 Quiz 1 Do not open this quiz booklet until you are directedMore information
Converting a Number from Decimal to Binary
Converting a Number from Decimal to Binary Convert nonnegative integer in decimal format (base 10) into equivalent binary number (base 2) Rightmost bit of x Remainder of x after division by two RecursiveMore information
Manifold Learning Examples PCA, LLE and ISOMAP
Manifold Learning Examples PCA, LLE and ISOMAP Dan Ventura October 14, 28 Abstract We try to give a helpful concrete example that demonstrates how to use PCA, LLE and Isomap, attempts to provide some intuitionMore information
Algebra 1 2008. Academic Content Standards Grade Eight and Grade Nine Ohio. Grade Eight. Number, Number Sense and Operations Standard
Academic Content Standards Grade Eight and Grade Nine Ohio Algebra 1 2008 Grade Eight STANDARDS Number, Number Sense and Operations Standard Number and Number Systems 1. Use scientific notation to expressMore information
Binary Heap Algorithms
CS Data Structures and Algorithms Lecture Slides Wednesday, April 5, 2009 Glenn G. Chappell Department of Computer Science University of Alaska Fairbanks email@example.com 2005 2009 Glenn G. ChappellMore information
Lecture 10 Union-Find The union-nd data structure is motivated by Kruskal's minimum spanning tree algorithm (Algorithm 2.6), in which we needed two operations on disjoint sets of vertices: determine whetherMore information
Arrangements And Duality
Arrangements And Duality 3.1 Introduction 3 Point configurations are tbe most basic structure we study in computational geometry. But what about configurations of more complicated shapes? For example,More information
Many algorithms, particularly divide and conquer algorithms, have time complexities which are naturally
Recurrence Relations Many algorithms, particularly divide and conquer algorithms, have time complexities which are naturally modeled by recurrence relations. A recurrence relation is an equation whichMore information
Analysis of Algorithms I: Binary Search Trees
Analysis of Algorithms I: Binary Search Trees Xi Chen Columbia University Hash table: A data structure that maintains a subset of keys from a universe set U = {0, 1,..., p 1} and supports all three dictionaryMore information
Big Ideas in Mathematics
Big Ideas in Mathematics which are important to all mathematics learning. (Adapted from the NCTM Curriculum Focal Points, 2006) The Mathematics Big Ideas are organized using the PA Mathematics StandardsMore information
Balanced Binary Search Tree
AVL Trees / Slide 1 Balanced Binary Search Tree Worst case height of binary search tree: N-1 Insertion, deletion can be O(N) in the worst case We want a tree with small height Height of a binary tree withMore information
Factoring Patterns in the Gaussian Plane
Factoring Patterns in the Gaussian Plane Steve Phelps Introduction This paper describes discoveries made at the Park City Mathematics Institute, 00, as well as some proofs. Before the summer I understoodMore information
Going Big in Data Dimensionality:
LUDWIG- MAXIMILIANS- UNIVERSITY MUNICH DEPARTMENT INSTITUTE FOR INFORMATICS DATABASE Going Big in Data Dimensionality: Challenges and Solutions for Mining High Dimensional Data Peer Kröger Lehrstuhl fürMore information
Chapter 11. 11.1 Load Balancing. Approximation Algorithms. Load Balancing. Load Balancing on 2 Machines. Load Balancing: Greedy Scheduling
Approximation Algorithms Chapter Approximation Algorithms Q. Suppose I need to solve an NP-hard problem. What should I do? A. Theory says you're unlikely to find a poly-time algorithm. Must sacrifice oneMore information
Linear Codes. In the V[n,q] setting, the terms word and vector are interchangeable.
Linear Codes Linear Codes In the V[n,q] setting, an important class of codes are the linear codes, these codes are the ones whose code words form a sub-vector space of V[n,q]. If the subspace of V[n,q]More information
Prentice Hall Algebra 2 2011 Correlated to: Colorado P-12 Academic Standards for High School Mathematics, Adopted 12/2009
Content Area: Mathematics Grade Level Expectations: High School Standard: Number Sense, Properties, and Operations Understand the structure and properties of our number system. At their most basic levelMore information
Improved Billboard Clouds for Extreme Model Simplification
Improved Billboard Clouds for Extreme Model Simplification I.-T. Huang, K. L. Novins and B. C. Wünsche Graphics Group, Department of Computer Science, University of Auckland, Private Bag 92019, Auckland,More information
Math 241, Exam 1 Information.
Math 241, Exam 1 Information. 9/24/12, LC 310, 11:15-12:05. Exam 1 will be based on: Sections 12.1-12.5, 14.1-14.3. The corresponding assigned homework problems (see http://www.math.sc.edu/ boylan/sccourses/241fa12/241.html)More information
x 2 f 2 e 1 e 4 e 3 e 2 q f 4 x 4 f 3 x 3
Karl-Franzens-Universitat Graz & Technische Universitat Graz SPEZIALFORSCHUNGSBEREICH F 003 OPTIMIERUNG und KONTROLLE Projektbereich DISKRETE OPTIMIERUNG O. Aichholzer F. Aurenhammer R. Hainz New ResultsMore information
Local outlier detection in data forensics: data mining approach to flag unusual schools
Local outlier detection in data forensics: data mining approach to flag unusual schools Mayuko Simon Data Recognition Corporation Paper presented at the 2012 Conference on Statistical Detection of PotentialMore information
Lecture 7: Approximation via Randomized Rounding
Lecture 7: Approximation via Randomized Rounding Often LPs return a fractional solution where the solution x, which is supposed to be in {0, } n, is in [0, ] n instead. There is a generic way of obtainingMore information
Distance based clustering
// Distance based clustering Chapter ² ² Clustering Clustering is the art of finding groups in data (Kaufman and Rousseeuw, 99). What is a cluster? Group of objects separated from other clusters MeansMore information
EE602 Algorithms GEOMETRIC INTERSECTION CHAPTER 27
EE602 Algorithms GEOMETRIC INTERSECTION CHAPTER 27 The Problem Given a set of N objects, do any two intersect? Objects could be lines, rectangles, circles, polygons, or other geometric objects Simple toMore information
Fast Matching of Binary Features
Fast Matching of Binary Features Marius Muja and David G. Lowe Laboratory for Computational Intelligence University of British Columbia, Vancouver, Canada {mariusm,firstname.lastname@example.com Abstract There has beenMore information
! Solve problem to optimality. ! Solve problem in poly-time. ! Solve arbitrary instances of the problem. #-approximation algorithm.
Approximation Algorithms 11 Approximation Algorithms Q Suppose I need to solve an NP-hard problem What should I do? A Theory says you're unlikely to find a poly-time algorithm Must sacrifice one of threeMore information
Centroid: The point of intersection of the three medians of a triangle. Centroid
Vocabulary Words Acute Triangles: A triangle with all acute angles. Examples 80 50 50 Angle: A figure formed by two noncollinear rays that have a common endpoint and are not opposite rays. Angle Bisector:More information
Section 2.4: Equations of Lines and Planes
Section.4: Equations of Lines and Planes An equation of three variable F (x, y, z) 0 is called an equation of a surface S if For instance, (x 1, y 1, z 1 ) S if and only if F (x 1, y 1, z 1 ) 0. x + yMore information
Computer Graphics Global Illumination (2): Monte-Carlo Ray Tracing and Photon Mapping. Lecture 15 Taku Komura
Computer Graphics Global Illumination (2): Monte-Carlo Ray Tracing and Photon Mapping Lecture 15 Taku Komura In the previous lectures We did ray tracing and radiosity Ray tracing is good to render specularMore information
Binary Heaps * * * * * * * / / \ / \ / \ / \ / \ * * * * * * * * * * * / / \ / \ / / \ / \ * * * * * * * * * *
Binary Heaps A binary heap is another data structure. It implements a priority queue. Priority Queue has the following operations: isempty add (with priority) remove (highest priority) peek (at highestMore information
The Australian Curriculum Mathematics
The Australian Curriculum Mathematics Mathematics ACARA The Australian Curriculum Number Algebra Number place value Fractions decimals Real numbers Foundation Year Year 1 Year 2 Year 3 Year 4 Year 5 YearMore information
Binary Trees and Huffman Encoding Binary Search Trees
Binary Trees and Huffman Encoding Binary Search Trees Computer Science E119 Harvard Extension School Fall 2012 David G. Sullivan, Ph.D. Motivation: Maintaining a Sorted Collection of Data A data dictionaryMore information
Analysis of Algorithms I: Optimal Binary Search Trees
Analysis of Algorithms I: Optimal Binary Search Trees Xi Chen Columbia University Given a set of n keys K = {k 1,..., k n } in sorted order: k 1 < k 2 < < k n we wish to build an optimal binary searchMore information
Numerical Analysis Lecture Notes
Numerical Analysis Lecture Notes Peter J. Olver 5. Inner Products and Norms The norm of a vector is a measure of its size. Besides the familiar Euclidean norm based on the dot product, there are a numberMore information
In mathematics, there are four attainment targets: using and applying mathematics; number and algebra; shape, space and measures, and handling data.
MATHEMATICS: THE LEVEL DESCRIPTIONS In mathematics, there are four attainment targets: using and applying mathematics; number and algebra; shape, space and measures, and handling data. Attainment targetMore information
A 0.9 0.9. Figure A: Maximum circle of compatibility for position A, related to B and C
MEASURING IN WEIGHTED ENVIRONMENTS (Moving from Metric to Order Topology) Claudio Garuti Fulcrum Ingenieria Ltda. firstname.lastname@example.com Abstract: This article addresses the problem of measuring closenessMore information
Social Media Mining. Data Mining Essentials
Introduction Data production rate has been increased dramatically (Big Data) and we are able store much more data than before E.g., purchase data, social media data, mobile phone data Businesses and customersMore information
Sorting revisited. Build the binary search tree: O(n^2) Traverse the binary tree: O(n) Total: O(n^2) + O(n) = O(n^2)
Sorting revisited How did we use a binary search tree to sort an array of elements? Tree Sort Algorithm Given: An array of elements to sort 1. Build a binary search tree out of the elements 2. TraverseMore information
Machine Learning Final Project Spam Email Filtering
Machine Learning Final Project Spam Email Filtering March 2013 Shahar Yifrah Guy Lev Table of Content 1. OVERVIEW... 3 2. DATASET... 3 2.1 SOURCE... 3 2.2 CREATION OF TRAINING AND TEST SETS... 4 2.3 FEATUREMore information
Validity Measure of Cluster Based On the Intra-Cluster and Inter-Cluster Distance
International Journal of Electronics and Computer Science Engineering 2486 Available Online at www.ijecse.org ISSN- 2277-1956 Validity Measure of Cluster Based On the Intra-Cluster and Inter-Cluster DistanceMore information
Medical Information Management & Mining. You Chen Jan,15, 2013 firstname.lastname@example.com
Medical Information Management & Mining You Chen Jan,15, 2013 firstname.lastname@example.com 1 Trees Building Materials Trees cannot be used to build a house directly. How can we transform trees to building materials?More information
Solving Simultaneous Equations and Matrices
Solving Simultaneous Equations and Matrices The following represents a systematic investigation for the steps used to solve two simultaneous linear equations in two unknowns. The motivation for consideringMore information
This unit will lay the groundwork for later units where the students will extend this knowledge to quadratic and exponential functions.
Algebra I Overview View unit yearlong overview here Many of the concepts presented in Algebra I are progressions of concepts that were introduced in grades 6 through 8. The content presented in this courseMore information
Topological Properties
Advanced Computer Architecture Topological Properties Routing Distance: Number of links on route Node degree: Number of channels per node Network diameter: Longest minimum routing distance between anyMore information
PRE-CALCULUS GRADE 12 [C] Communication Trigonometry General Outcome: Develop trigonometric reasoning. A1. Demonstrate an understanding of angles in standard position, expressed in degrees and radians.More information
Why Taking This Course? Course Introduction, Descriptive Statistics and Data Visualization. Learning Goals. GENOME 560, Spring 2012
Why Taking This Course? Course Introduction, Descriptive Statistics and Data Visualization GENOME 560, Spring 2012 Data are interesting because they help us understand the world Genomics: Massive AmountsMore information
Solving Geometric Problems with the Rotating Calipers *
Solving Geometric Problems with the Rotating Calipers * Godfried Toussaint School of Computer Science McGill University Montreal, Quebec, Canada ABSTRACT Shamos [1] recently showed that the diameter ofMore information
Mathematical Procedures
CHAPTER 6 Mathematical Procedures 168 CHAPTER 6 Mathematical Procedures The multidisciplinary approach to medicine has incorporated a wide variety of mathematical procedures from the fields of physics,More information
Learning Big (Image) Data via Coresets for Dictionaries
Learning Big (Image) Data via Coresets for Dictionaries Dan Feldman, Micha Feigin, and Nir Sochen Abstract. Signal and image processing have seen in the last few years an explosion of interest in a newMore information
Multi-dimensional index structures Part I: motivation
Multi-dimensional index structures Part I: motivation 144 Motivation: Data Warehouse A definition A data warehouse is a repository of integrated enterprise data. A data warehouse is used specifically forMore information
Clustering. 15-381 Artificial Intelligence Henry Lin. Organizing data into clusters such that there is
Clustering 15-381 Artificial Intelligence Henry Lin Modified from excellent slides of Eamonn Keogh, Ziv Bar-Joseph, and Andrew Moore What is Clustering? Organizing data into clusters such that there isMore information
Curriculum Map Grade: _7 th Basic Math School: _ Middle Date: Oct. 31/2009
August/ September Review basic skills of add, subtract, multiply, and divide whole numbers and fractions. (skill with a # assessed locally.) Students will add, subtract, multiply, and divide positive rationalMore information


text: I Am a Sucker For Guys Who Can Make Me Laugh Me Too Personal Stories, Advice, and Support 61 People Report Group Sort popular recent Joke away I'm up for a laugh thefaultinourscars 16-17, F 1 Response 2 Aug 24, 2014 Works Everytime! My ex-husband's charming sense of humor was what won me over. Even to this day, when he knows I'm upset with him, he will try to use that charm of his to see if I will lighten up and not be so angry. His antics don't work on me anymore. deleted 26-30 0 May 12, 2010 More Stories

subset: commoncrawl


text:
Marco Brambilla: From Civilization To Power
Marco Brambilla: From Civilization To Power
CH exclusive: The making of Kanye West's newest music video "Power" with its artist/director
Kanye West has been kicking up controversy right and left recently—showing up at both the Facebook and Twitter HQs, turning his teeth to diamonds and engaging the public with his crude and prolific Tweets. After noticing Marco Brambilla's "Civilization" video installation in the elevators at The Standard New York Hotel in 2009, Kanye not only wrote about it on his blog, he commissioned the experimental filmmaker to collaborate on the video for "Power," his new single.
We're premiering the behind-the-scenes video with the artist created by The 88 (above) and directed by Jenna Elizabeth, which starts by introducing "Civilization" and then shows how "Power" was made. We've also got an exclusive interview with Brambilla below.
Cool Hunting: What is the concept and how did it come about?
Marco Brambilla: To me "Power" was about a symbol, an icon of power about to fall, like an emperor about to fall. That's when I thought I'd like to do a sort of moving portrait, a video portrait of Kanye as an authority figure in a moment when everything is about to collapse. I wanted to make it really sensual and use a lot of baroque imagery that I had used in "Civilization" and create this kind of decadent imagery around him and have all the decadence and sexuality and excess conspire against him. By the end of the video there's a change in his position. So his position is compromised at the end of the video.
CH: Are you interested in doing more collaborations in the future?
MB: Kanye is more connected to the art world than other artists, so I thought this would be an interesting opportunity to work with someone who really understands how far you can push things and how experimental you can be. A lot of people will tell you they want to do something experimental but it becomes commercial. I thought Kanye would let me be true to my vision. I've never done a music video and one of the first things I said to Kanye was that I'm not interested in making a music video, but if we want to work on something that's experimental, I can definitely do that because I really connected to that song.
CH: Is it strange that a celebrity would depict their fall from power?
MB: I think he's a true artist—he doesn't react to what people think of him. He's aware, but he's not the type of person who's going to react to things in a way that is better for marketing. He wants to push the limits. I think using part of his public image as part of the way of illustrating his new album will resonate.
CH: What was the production process like?
Once we locked in on that concept it was pretty fast; essentially a three-four week process. The post production was pretty intense because there's about 22 layers of video in the piece and each piece has to be choreographed—it's almost like a very complicated matrix. The shoot itself was shot in extreme slow motion on a Phantom camera. The characters come to life, but they're moving in a very stylized way. I knew exactly what I was going to shoot the day we went on stage. I actually shot images of the models at the casting and then I put the models together in Photoshop, so we had it pretty well figured out.
CH: Are video collages your signature now?
MB: One of the reasons I took this project is because conceptually it made sense to explore celebrity, sexuality, self-consciousness, self-destruction. This idea of being in the center of the universe becomes a little intimidating to people. I've explored it in my work before. Regardless of whether I do a video work based on sampling or based on collage, those themes come through in my work.
Marco Brambilla and the Christopher Grimes Gallery are currently working on a show called "Evolution" that will open in 2011 at the Santa Monica Museum of Art.


text:
Nick Cave Takes the Plug Awards Where the Sun Don't Shine
"I feel like my dad at a rave," said host Patton Oswalt last night at the Plug Awards.
"I feel like my dad at a rave," said host Patton Oswalt last night at the Plug Awards.
Stephen Colbert on Transgender Military Ban: Trump Went From Crazy to Cruel
Tiffany & Co. Taps Cool Young People in First Act of Rebranding
Angelina Jolie Had an … Unconventional Method for Casting Her Latest Movie
In Conversation: Trent Reznor
Former Debbie Wasserman Schultz Aide Arrested for Bank Fraud
The 'Skinny Bill' Is a Farce. Here's the Real Reason Republicans Are Doing It.
Larry David Explains Why Curb Your Enthusiasm Is Back For Another Season
Game of Thrones' Nathalie Emmanuel on Missandei and Grey Worm's Sex Scene: 'It Was So Much More Than Just Two People Making Love'
Governors Just Blasted 'Skinny Repeal.' Could That Cost the GOP a Key Senate Vote?
The Most Extravagant Real Housewife Explains What It Takes to Look Like Her


text:
HHGregg has closed after filing bankruptcy and finding no buyer.
The city is one of 50 locations to lose a Sears Auto Center. Terre Haute's center is located at the Honey Creek Mall.
The Honey Creek Mall in 2013 reported that 97 percent of the mall store space was leased. By 2016, that lease percentage dipped to 93 percent, according to Mall owner CBL & Associates annual Form 10-K report with the U.S. Securities and Exchange Commission.
And another store, Gander Mountain, has an uncertain future in Terre Haute. The company filed for bankruptcy in March, initially planning to shutter 32 stores, but that could be as many as 160 stores after Camping World won a bankruptcy auction of Gander Mountain assets for $390 million. Camping World CEO Marcus Lemonis in a statement after the auction said at least half of Gander Mountain stores will close.
"This started more than a decade ago. It is Internet retail and it will continue to grow," said John G. Ragle, president of Ragle & Company, which owns the Southland Shopping Center and Corporate Square Office Complex in Terre Haute.
"My thought is Internet retailing is now entering adolescence. It is out of its infancy, but still has a long, long way to go," Ragle said. "It has definitely had an impact," he said as several shopping areas in Terre Haute have vacancies. "It is not rocket science and it will continue."
That means nearly any merchandisable commodity can be obtained on the Internet, Ragle said.
As illustration, Amazon's market value as of Dec. 30, 2016 was $355.9 billion, more than the combined $297.8 billion market value of Walmart, Target, Best Buy, Macy's, Kohl's, Nordstrom, JC Penney and Sears, according to VisualCapitalist.com.
In 2006, Sears has a market value of $27.8 billion, but fell to $1.1 billion by 2016. Contrast Amazon's $17.5 billion in 2006, which grew to its 2016 value of more than $355 billion, the web site reports.
"What I see as surviving, so far, are small convenience strip centers, where services like hair cuts or dry cleaning or pharmacy or coffee shops are located. Drug stores are somewhat insulated," Ragle said.
"I would not want to own a lot of the big box anchor strip centers. I think the small neighborhood convenience center with a dollar store, barber shop and cell phone store will not be hit as hard. Retail has become tougher and tougher primarily from Internet retail," Ragle said.
A retail hub
Terre Haute is unique in that it is a destination retail hub, being the largest retail center between Effingham, Illinois, and Indianapolis.
Yet, don't expect the retail to be an engine of economic growth, says Kevin Christ, associate professor of economics at Rose-Hulman Institute of Technology.
"In terms of employment for the area, retail has always been important — retail and restaurants account for about a quarter of our region's employment," Christ said. "Since 2009, the region's employment in restaurants and retail has actually gone up by about 4.4 percent — but most of that has been in restaurants. Retail has been flat," Christ said.
Christ said while he is not overly optimistic about how retail trends are going to affect the regional economy, he is "not overly pessimistic either."
Christ and Robert Guell, economics professor at Indiana State University, wrote a 2017 economic outlook for the Indiana Business Review. The two point out the addition of Meijer and other retail shops along the Indiana 46 corridor on Terre Haute's east side, as well as some "new eateries" along South Third Street.
However, the stores "may represent little more than a shuffling of previous restaurant spending," the outlook report states. And the report states that the "single largest concern for regional retail centers like Terre Haute (which heavily rely on local sales) is that web retailers are not finished gobbling up market share."
Christ said the "point in our outlook is that we wouldn't look to this sector for any significant growth. New retailers might come into the market, but we suspect they will just cannibalize other retailers' sales, and thus replace other retailers' employment with their own," he said.
"As a retail hub, Terre Haute will probably stay in the game, but retail is not likely to be an engine of growth," Christ said.
Changing business models
One Terre Haute store owner is an example of a shuffling of community spending, but not for restaurants, instead in sporting goods.
Brent Compton, owner of PaceSetter Sports, has been involved with the sporting goods store, established in Terre Haute in 1982, for 26 years.
Compton said his business's biggest test came within the last year, when it was challenged from big box retailer Academy Sports.
"We had never, for 30 years, faced that kind of adversity, that kinda challenge that gobbles or takes up that kinda market share," Compton said. "The retail market now has more avenues for people to buy things, which is part of the problems for Sears and HHGregg. People can go online for items and services and more and more people, especially young people, are more comfortable doing that," he said.
That has forced PaceSetters to recreate its business model, Compton said, focusing on the grassroots investment of the community, he said.
"The biggest engine for us is probably being involved in the fabric of the community, with local soccer leagues, with little leagues and travel teams and school teams," Compton said. "That service with leagues, especially in our running community with the Wabash Valley Roadrunners and Trained in Terre Haute, is important."
"There is a value in being able to touch, see and try it and have someone who has knowledge, first-hand knowledge" of sporting equipment, Compton said. "It is people who know where Linton is at, where Casey, Illinois, is at, where North Vermillion is at and where Clay City is at and we have employees from all of those communities. We make sure we show we are really invested in the fabric of the community."
Compton said the store has held special events, such as a baseball day, offering discounts to high school, club and community teams coinciding with the first day of practice. It has also held a softball day and a track and field day "where we reach out and personally and individually invited (coaches and teams) creating a relationship with them. For stores like PaceSetter, that is the only way to survive. You have to have relationships not only with leagues but with local athletes to give them a reason to want to come inside the building," Compton said.
Last week, the Terre Haute Chamber of Commerce celebrated National Small Business Week, which Chamber President David Haynes said demonstrates how important small businesses are to the economy. Small business accounts for nearly 80 percent of the chamber's membership, Haynes said.
A coming adjustment
It's small business, Haynes said, that provides a boutique-like experience.
"I think that while many people have gone to online shopping, there are still those who go for face to face conversation, for counsel or direction on styles and utility," Haynes said.
"Service after the sale may ultimately be the difference" between small businesses and big box stores, each selling similar items such as appliances, Haynes said. "Knowing that when you walk into the store, the owner is in the back office, instead of in New York or Los Angeles, I think there is some comfort in that.
"I think there is an adjustment occurring in retail, but brick and mortar will not go away entirely," Haynes said. "It will be the survival of the fittest and communities such as ours are going to have the stores necessary to support the populous, but it may not allow for the competition like between HHGregg and Best Buy, but stores such as Central TV or Ace Washer may be what people will want," Haynes said.
Editor, John C. DePrez Jr.; Executive Editor, Carol Rogers; Publishers: IBRC and IAR


text:
Steve Weaver
Executive Director; Ex-Officio Board Member
Maryrose Pavkovic
Managing Director
Jon Pounds
Executive Director Emeritus, CPAG
Peter Landon
Board President
Landon Bone Baker Architects
Michael Patrizio
Attorney, Dowd & Dowd, Ltd.
Carl Nash
Vice President
Heather Wallack
Attorney, Kozusko Harris Duncan
Board Members
Abdi Maya
Illinois Department of Human Rights
Miranda Swanson
Division of the Physical Sciences, University of Chicago
Tracy Van Duinen
Core Artist, CPAG; Artist Educator
Bernard Williams
Core Artist,CPAG; Painter, Sculptor, and Muralist
Mary Whitman Davis
Art Historian
Sonja Henderson
Artist CPAG; Painter, Sculptor, and Muralist
Michelle Feit
Chicago Public Schools
Tulika Ladsariya
Nicole Marroquin
School of the Art Institute of Chicago
CPAG Core Artists
At the heart of Chicago Public Art Group's work are its dedicated Core Artists. The aesthetics and techniques of CPAG artworks are developed within this multi-generational, multi-racial, multi-cultural community of professional artists who are committed to creating high quality public art through collaborative processes.
After several years of working with CPAG and leading a number of major projects, an artist may be elected as a Chicago Public Art Group Core Artist in recognition of commitment to the practice of community-based artmaking; artistic and leadership skills in such areas as collaborative design, technical knowledge, project management, teaching, and community organizing; and the high aesthetic quality of completed public art projects.
For more information on the Core Artists of CPAG, including examples of important artworks, see the Artist page of the CPAG website.
Senior Artists Circle
Artists who have been identified as master community artists are invited to become members of the Senior Artist Circle of the Chicago Public Art Group. These artists have created numerous public artworks of high aesthetic quality with exemplary community engagement. CPAG Senior Artists are national leaders in the field, having developed unique artistic styles and methods for making collaborative public art.
Becoming a CPAG Artist
Interested artists should submit digital copies of their work, their artist statement, and a résumé of art experiences to Maryrose Pavkovic, Managing Director via email to firstname.lastname@example.com. New artists are then employed as assistants on a number of projects, giving them the opportunity to learn community public art techniques as apprentices to master community artists. New artists who are interested in developing a career in community public are encouraged, to participate in activities such as workshops and lectures, and to volunteer on projects.
Alphawood Foundation
Chicago Park District
Chicago Public Schools
City of Chicago Department of Cultural Affairs and Special Events (DCASE) CityArts Grant
Dennis Langley
Gaylord and Dorothy Donnelley Foundation
Illinois Arts Council Agency
Ira Brodenstein & Julia Smith, In Memory of Jim Fox
Jill & Lou Raizin
Landon Bone Baker Architects
MacArthur Funds for Arts and Culture at The Richard H. Driehaus Foundation
University of Chicago Office of Civic Engagement


text:
Ross Poldark (Paperback)
Jeremy Poldark (Paperback)
Masterpiece: Poldark (U.K. Edition) DVD
Poldark Complete Collection DVD
Demelza (Paperback)
Our Price: $16.99
Free Shipping on orders of $59 or more Details >
Item No.: DMLZ855
Softcover Book
An impoverished miner's daughter, Demelza Carne is now married to Ross Poldark. Her efforts to adapt to the ways of the gentry place her in hilarious situations, through which she becomes self-assured, mannered and lovely, and the birth of her first child brings a joy she never experienced before. Tragedy strikes where least expected and tests Ross and Demelza's marriage and their love.More >
AVAILABILITY: In Stock, leaves warehouse in 1 - 2 full bus. days Details >
Reviewed by 4 customers
Comments about PBS Demelza (Paperback):
I haven't read the books completely yet. I was woundering if you will have more to buy?
Comments about PBS Demelza (Paperback):
I have finished Book 1 of Demelza and find it just as enjoyable as Poldark. Both books, Poldark and Demelza, have answered questions I had after watching the PBS Masterpiece Theatre Poldark series. Looking forward to reading these books over and over.
Comments about PBS Demelza (Paperback):
Great way to stay in touch with the Poldark characters during the break in the video broadcasts.
Comments about PBS Demelza (Paperback):
Loved to dive into the world of Poldark!


text:
Any MTG players on Spiceworks? Or you know what, we can discuss any favorite geek game here; DnD, MTG, 40k whatever you want. I'm surprised theres not a group for this under Non-IT.
27 Replies
Jul 1, 2010 at 4:49 UTC
I'm strictly a UT2k4 player.
Jul 1, 2010 at 4:51 UTC
I was hoping we'd talk more along the lines of table top stuff
Jul 1, 2010 at 6:09 UTC
Niagara Technology Group (NTG) is an IT service provider.
DnD fo sho! I love DnD but almost never get an opportunity to play.
Jul 1, 2010 at 6:29 UTC
I haven't played since my testicles dropped.
Jul 1, 2010 at 6:36 UTC
Niagara Technology Group (NTG) is an IT service provider.
LOL, well sucks to be you then. DnD rocks.
Jul 2, 2010 at 7:14 UTC
Warhammer 40k > DnD.....oh snap I said that...
Jul 2, 2010 at 7:20 UTC
just because you like painting your little models doesn't mean i want to. DnD Pride!
Jul 2, 2010 at 7:26 UTC
You paint models in DnD too....
Jul 2, 2010 at 8:36 UTC
Niagara Technology Group (NTG) is an IT service provider.
You paint models in DnD too....
Only for fun, it's not part of the core game.
Jul 2, 2010 at 8:43 UTC
True. I like painting my models for 40k...well used to until I woke up one day and wondered why I'm buying a $50 resin tank. Its a good thing THQ came out with DoW. I think 40k gets more notoriety from those games than it does on table top. They just need to release a Space Hulk pc game and we'll be set
Jul 2, 2010 at 12:44 UTC
Bay Office Computing, LLC is an IT service provider.
And here I thought this topic was actually going to be about MTG! I've continued to play on and off for the last 15 years or so, when my work schedule and other hobbies allow time for it. Currently my buddies and I are amusing ourselves with the EDH format:
It's a highly entertaining and very inexpensive multiplayer free-for-all ruckus. Think along the lines of giant armies of dragons and 20-point fireballs. Games typically run long so high CC is irrelevant, supporting the use of all those crap rares in your collection. Since "there can only be one" of each card you're not spending bank on four copies of expensive power cards like you would in Standard. Plus, each draw is virtually unique which keeps the game interesting. Then you have the whole 'general' aspect which gives you unlimited access to the legend of your choice and you can build the entire deck around them. I highly recommend it.
Jul 2, 2010 at 12:49 UTC
I just got back into standard and built a blue and white milling/life deck. During lunch by the time the game was over I had something like 85 life. It was hilarious
Jul 2, 2010 at 1:44 UTC
Bay Office Computing, LLC is an IT service provider.
Yup, I hear U/W is killing it in the current Standard environment.
Last time I played T2 was RAV/TSP which happened to include Coldsnap randomly. I think I went 2-2-2 with Star Spangled Slaughter (URW tempo) and it was super fun, but these days I just don't have the time to commit to serious competitive play.
OTOH, EDH is completely casual and can be played in a garage with beers. With 5-6 decks the gameplay is basically WH40K minus all the painting and with the rules printed on each game piece.
Jul 2, 2010 at 1:47 UTC
Yeah I scoped out the rule page on that. It sounds a lot like Warlords, back when Warlords was popular
Right now my deck has the new Ally type creature where Allies tend to have bonus to themselves or their affects for all other allies you control Halimar Excavators is a 1U Target player mills X cards from their deck for each ally you control and then Jwari Shapeshifter 1U When enters the battlefield make it a copy of any target ally on the field. So thats my win condition Eventually it gets so big that I end up milling a guy for like 20 cards a turn until hes out or if it turns against me and I lose life too fast I have a 1W Gain life when ally comes under your control for each ally under your control. So I just generate rediculous amounts of life and I unsummon the Jwari's back into my hand if I need to and replay them to copy what I need the most of at the time.
Jul 6, 2010 at 7:34 UTC
man i tried a while back to get back into magic... and before that i tried in college... but i just don't like all the new cards. There are just alot of cheap decks out there. I am not saying they aren't good decks i just don't want to play against them. Ah i remember the alpha and the beta. back when you could just call your deck a black deck or a red deck. when it was about little creatures fighting for your amusement.
and the warhammer games are fun i just love my DnD! THAC0 4 Life!
Jul 6, 2010 at 8:08 UTC
Been playing for a few years... I got a green deck built around Riptide Replicator (favorite card) and a few nice white/blue decks. I left my best deck (ZOMBIES) in Canada of all places a year ago when i was at a hockey game for my brothers travel team.
Whats your favorite cards? Deck prefference?
I think it would be fun to play a game over spiceworks but i dont think that would work too well.. Today I'm thinking of buying another deck builder set and going all out with that. 300 cards 25$ = several decks 100 mana's 100 creatures 100 everything else = win.
Jul 6, 2010 at 8:10 UTC
Oh,... does anyone play Yo-Gi-Oh? lol I used to play ages ago and still have my deck. I built and had my deck for 2 years then entered my first turniment and won and havn't played since! ha ha i decided if i could win on my first attempt it was time to stop lolz.
Jul 6, 2010 at 8:32 UTC
Favorite deck Niv-Mizzit combo from GuildPack. I had one back in the day and now I'm looking to rebuild it
Jul 12, 2010 at 5:48 UTC
Bay Office Computing, LLC is an IT service provider.
Assuming you're referring to the Niv-Mizzet/Curiousity combo that's a great one. I'm actually in the process of building an EDH deck with Niv as my general. I'll be including other fun infinite mana/damage/draw combos to blow out my opponents and generally have a ton of fun with silly cards. For example, there's Stuffy Doll who is just a riot of a card on its own but loves Curiosity as well.
Jul 13, 2010 at 7:58 UTC
Yeah the Niv/curiosity combo is what I was talking about. Im half way there. Ive got the niv and the Vortexs and the Electrolyze i just need the curiosity and stuff it with some counter spells and the what to make stuff fizz out and it'll be good to go.
Jul 15, 2010 at 9:06 UTC
Not for years, all my firends and I just sorta stopped playing just after 6th edition came out, I gave all my cards to my wife's little brother, to which I do plan to break into his house and get them back one day. I played the 360 game but everyone just quits when their about to lose.
Warhammer looked fun then I went to the store in the mall to find out more about it and well... I had never seen such "nerdiness" in all my life I mean it was every stereotype about DnD guys played out in almost theatrical quality. Would still like to paint the little figures though.
My old school goblin deck was unstoppable.
Jul 15, 2010 at 9:23 UTC
It has been a long time since I have played...used to be really into it though.
Jul 15, 2010 at 9:56 UTC
I just got back in my self a few weeks ago and wizards just put out the new CoreSet they name them by year now apparently. They brought back Scrye in big way apparently its supposed to be a major mechanic in the new block ....though I wish they'd bring back Banding instead.
Jul 15, 2010 at 3:24 UTC
Bay Office Computing, LLC is an IT service provider.
Banding, really? Lamest mechanic ever!
...for the lose. Split second (ie the return of interrupt-speed spells) has got to be the coolest new mechanic.
This discussion has been inactive for over a year.
You may get a better answer to your question by starting a new discussion.


text:
Many of the brightest and hardest-working commercialism and exposure grouping in the rural area are obsessed near effort you to put in wealth and, if necessary, to go into financial obligation to do so. Absolutely all the media that conquer you all day are designed to get you to spend coins. In command to rescue exchange in this environment, you will condition spirit to withstand the persistent pressures to pass now.
What is it that separates those who are winning from those who are not?
Successful individuals have a well-set of your own perception of what they privation and why they poverty it. That imagination gives them the muscles to cudgel to their strategies even once doing so is embarrassed. It gives them the resolve to die hard once they are downcast. This is the same identifying of women entrepreneurs andis the cause their new, micro businesses are fortunate.
smoke pittsburgh pa
homemade smoke daddy
where to buy nicotine free electronic cigarettes
is it legal to purchase cigarettes on line
tobacco road sports cafe durham nc
government laws on tobacco
smoke shops south shore ma
can you smoke chicago midway
cheap cigarettes gastonia nc
smoke hash oil without weed
canadian tunnel duty free
cigar store indian indianapolis
marlboro cigarettes 10
duty free bermuda
duty free buffalo niagara falls
what happens when you smoke too much
tobacco shop bongs
tobacco use test
The 401k Plan
Today, the 401(k) approach has become the foremost asset transport for serviceable women to amass for status. But several don't pinch laden vantage of their plan, and this could start out them near a lot little at position. Here are whatever stairs we suppose you can nick to advance and eliminate any status worries active whether or not your status will be gratifying or laypeople charity; or whether you will have all the uncommitted incident to devote near your family unit or friends
1. Increase your contributions to the top that you can control. Many human resources add basically ample to transport lead of their employer's go well together contributions, and next they come to a close. By totting up more than to your account, over and done the equivalent contributions, you'll end up beside more in position.
nicotine content swisher sweet cigars
what's new marlboro special blend
cheap 24 hr cigarettes
cohiba cigar made
zone duty free ferry
pictures of tobacco leaves
wigwam smoke shop kelowna
marlboro lights discount
buy newport 100 cigarettes online
duty free yul
health canada tobacco ads
the facts about smoking cigarettes
duty free liquor heathrow
cheap cigarettes europe prices
thomas cook flight duty free cigarettes
cigarettes en duty free
lonsdales cigars scottsdale
pipe shop queens
2. Invest at the inauguration of each year instead of fetching a minor bit out of all cheque. Nothing in the law says you have to place in a 401(k) outline a slender at a time, from each check. By investing early, you'll put your hard cash to occupation earlier for your advantage.
3. A few years ago it was rumored that more than than 30 pct of the income in 401(k) campaign was invested with in money-market finances or analogous accounts. For investors nearing retirement, that may be proper. But record staff in their 40's and 50's have need of lump in their status nest egg. Put more of your share monetary fund in equities and smaller number in money-market finances.
4. Research indicates that concluded longstanding periods of time, small-company instrument of punishment beat large-company pillory. Since 1926, In the assets cut of your portfolio, relocation many of your ready money into funds that spend in dwarfish companies. Don't put your full assets case in small-company instrument of punishment. But reflect on investment at lowest possible 25 proportionality of your U.S. equity stash in that monetary fund.
5. Numerous studies have shown that appeal stocks outstrip biological process instrument of punishment.
According to accumulation going pay for to 1964, extensive U.S. importance companies had a dissected charge of rush back of 15.1 percent vs. individual 11.4 pct for outsized U.S. opening out companies. Among slim U.S. companies, the contrast was even more striking: a pinnated come flooding back of 17.4 percentage for the worth pillory vs. 12.1 percentage for the malignant cells pillory. Don't put your complete assets case into effectiveness instrument of punishment. But if there's a meaning monetary fund on tap to you, think about investing at lowest possible 25 percentage of your U.S. assets money in that fund.
6.Rebalance your case past a time period.Your good worth allocation conceive calls for a abiding percent to be endowed in all of respective kinds of possession. Rebalancing restores your good quality set off and allows for the probability that past year's losers may be this year's gainers. Diluting your variegation actually increases venture in your case done time, which is a result that's merely the differing of what record investors want.
7.Without conciliatory straightlaced deal portion -the most valuable set of investing choices you cause - use the assets in your scheme that have the last-place operative outlay. Choose assets next to low ratio in their portfolios
8. Don't borrow or bring in untimely withdrawals from your 401(k) unless that is the solely way to counter to a critical exigency.. Furthermore, if you issue an precipitate climb-down in the past you are 59.5 age old, your withdrawals will be thesis to a 10 per centum tax punishment (in adding together to rule-governed taxes) unless you are incapacitated This is a guileless part. Just don't do it.
9. If you vacate your job, you'll get a haphazard to ripple complete your 401(k) into an IRA. Take that unsystematic. In an IRA, you have the self tax recess as a 401(k), and you'll have the flexibleness to spend in virtually everything you can get in a 401(k), positive much much.
10. Here's the furthermost noteworthy situation you can do to increase your 401(k): Keep your contributions unconsciously payroll deducted, and make them no substance what. It's simple, but it's not unproblematic. Half of the households in the United States have net price of $20,000 or little.. In a archetypal year, in the region of common fraction of U.S. households do not set free legal tender.
Remember, to be successful, first, create in your mind your previous retirement; the Caribbean condo, the yacht, the new Lexus. Luxury and delight as far as your thought can see. Create a toughened vision, and consequently don't let go. The strength of a clear, extreme figment of the imagination applies to more than lately your position monetary fund. Let your delirium structure your life, or else of the otherwise way around, and all of the incident in the planetary can be yours.


text:
If there is anyone who deserves some meal money for showing up, it is Tiger Woods.
No golfer in history has done more for the game. And none of us are so naive as to believe that athletes are not being paid appearance fees in a lot of sports.
TIGER WOODS: Superstar golfer getting added payday
But does it make a difference to you when those fees keep athletes from playing in U.S. events?
Woods is getting from $1.7 million to $2.7 million to play in the Arab Emirates this week. That will keep him from playing in the Farmers Insurance Open at Torrey Pines, a course that Woods has owned over the years with his play.
Reid Cherner has been with USA TODAY since 1982 and written Game On! since March 2008.
He has covered everything from high schools to horse racing to the college and the pros. The only thing he likes more than his own voice is the sound of readers telling him when he's right and wrong.
Michael Hiestand has covered sports media and marketing for USA TODAY, tackling the sports biz ranging from what's behind mega-events such as the Olympics and Super Bowl to the sometimes-hidden numbers behind the sports world's bottom line.


text:
Vitello Shine Prada Satchel
Prada Saffiano Shoulder Strap Bowler Bag
Prada Bicolor Saffiano Bag Blue & Black White
Prada Saffiano Small Promenade Tote
Prada Continental Wallet Black & Blue
Prada Beige & Black Leather Pump
Prada Burgundy & Beige Leather Pumps
Prada Suede Peep Toe Platform Pumps
Prada Fluffy Pointy Toed Pumps
Prada Engraved Patent Leather Pumps
Prada Black & White Leather Sneakers
Prada White Black & Grey Leather Sneakers
Prada Black & Blue Leather Sneakers
Vitello Shine Prada Satchel
Vitello Shine Prada Satchel. Exhibits and experiences planned at the Legacy of Flight include: ' The 15-storey-tall Aerodrome is an open space focal to all of the attractions. A look at the Sunday flying programme reveals that Chambery is not the only challenging airport to which CityFlyer operates to deliver skiers to their resorts. Vitello Shine Prada Satchel. It is expected that operations will begin early in the New Year almost 12 months after the company was formed. A full description of all that is provided is not possible here, but the site provides a huge file library of all things flight simulation, chat rooms, discussion forums, daily news and reviews of new releases. Vitello Shine Prada Satchel. Prada Shoes Outlet Men. However, as the system develops and new channels are introduced, they will not match 25Khz spacings. As experience developed 1 found myself using the rudder to start the roll movement going (the secondary effect of yaw is roll) and then using the ailerons to finish the manoeuvre. Vitello Shine Prada Satchel.
Gucci Ostrich Leather Work Bag Red & Black
Gucci Leather Work Bag Black & Cognac
Gucci Bamboo Shopper Leather Tote
Gucci Aviatrix & Boston Bag Black
Gucci GG Running Medium Tote
Gucci Vintage Web Medium Boston Bag
Gucci Sukey Large Tote Black & Orange
Gucci Techno Horsbit & Heart Bit
Gucci Soho Large Hobo Black & Red
Gucci Soho Medium Shoulder Bag Tan & Black
Gucci Soho Mini Shoulder Strap Bag
Gucci Derby Canvas Small Shoulder Bag
Vitello Shine Prada Satchel
Vitello Shine Prada Satchel. This plan was confirmed in late September when it was revealed that the latest addition to the market would be known as 'buzz' when it is launched early next year. However, the doubters were proved wrong by the success of a typically elegant French design, the Sud Aviation Caravelle, which 40 years ago pioneered short and medium-haul jet airline services across the continent. Vitello Shine Prada Satchel. The detailed set-up of the Final Assembly Line between two highly qualified sites inside the Airbus system has also to be finally worked out. Luton, however, will be the first airport not operated by National Air Traffic Services to have such facilities. Vitello Shine Prada Satchel. Buy Prada Riding Boots. There is no truth in the rumour that the F-117 Stealth Fighter version is more difficult to find than others! More details are found in the 'History' page, which also covers the early Airbus designs. Vitello Shine Prada Satchel.
Louis Vuitton Neverfull MM Damier Ebene & Monogram
Louis Vuitton Speedy 30 Damier Ebene & Monogram
Louis Vuitton Galliera GM & Ascot Damier Ebene
Louis Vuitton Trevi PM & Portobello MM
Louis Vuitton Renzo MM & Bastille Damier Ebene
Louis Vuitton Keepall 55 & Speedy 35 Damier Ebene
Louis Vuitton Keepall Bandouliere & Keepall 55
Louis Vuitton Eva Clutch & Favorite PM
Louis Vuitton Eugenie Clutch & Sarah Etoile
Louis Vuitton Marco Wallet Damier Graphite & Ebene
Louis Vuitton Zippy Wallet Monogram & Damier Ebene
Louis Vuitton Samsung Galaxy Case
Vitello Shine Prada Satchel
Vitello Shine Prada Satchel. The corresponding page here contains very brief details of the Airbus aircraft family, partners in the consortium and major production locations. The team's brief is effectively to sell British excellence in aviation wherever this country's aerospace industry is on display, resulting in more performances abroad than at home by the year 2006. Vitello Shine Prada Satchel. Prada Outlets Ireland. Next, the board must make a decision on whether to launch the aircraft, and if so, to set a timetable for each variant of the superjumbo, which is planned as a 10,600km range freighter and as a 12,900kms range combi. Air Inter also bought five, bringing Caravelle production to a close in 1972 after completion of the 282nd aircraft. Vitello Shine Prada Satchel. It became clear after another 'Mr Fix-it' drove up in a battered Lada, and there was an exchange of 'paper', that this was an essential pre-requisite to getting into the 'show'. So sharp and so well honed were his responses in flight that it was easy to believe no harm could ever befall him. Vitello Shine Prada Satchel.
Hermes Birkin 35 Bag Ostrich Leather
Hermes Birkin 35 Bag Horse Embossed
Hermes Birkin 35 Bag Black & Tan
Hermes Birkin 35 Bag Orange & Black
Hermes Kelly 32 Bag Ostrich Leather
Hermes Kelly 32 Bag Ostrich Leather
Hermes Kelly 28 Bag Tan & Black
Hermes Kelly Small Bag Red & Orange
Hermes Constance Bag Black & Orange
Hermes Constance Bag Tan & Red
Hermes Jige Elan 29 Clutch Black & Red
Hermes So Kelly Bag Red & Black
Vitello Shine Prada Satchel
Vitello Shine Prada Satchel. Among the elements included in the co-operative agreements are frequent flier programme reciprocity, lounge access interchange and codesharing across a range of flights. Once the scenery is installed, the manual gives some very useful tips about how to get the best display from 'Flight Simulator'. Vitello Shine Prada Satchel. Prada Sneakers Pink. Indeed, such is its integration with the residential area that surrounds the base, that several public roads are even allowed to run between and across the two runways! It is not clear if Iranian Aviation Industries is serious about seeing the alleged F-14 Tomcat upgrade through to the end. Vitello Shine Prada Satchel. The company believes that its programme is cheaper than limited refurbishment and will result in each Lynx being out of service for a minimum time, and at the same time providing a 10,000-hour fatigue life. In-cockpit, air to air and low level footage, walkround, air to air refuelling plus crew interviews and experiences of this legendary aircraft. Vitello Shine Prada Satchel.