?:Arya, S. M. Mount, D. Netanyahu, N.S. Silverman, R. Wu, A.1994?An optimal algorithm for approximate nearest neighbor searching573-5821In Proc. 5th ACM-SIAM Sympos. Discrete Algorithms-http://citeseer.nj.nec.com/arya94optimal.html*F?Blelloch, G. Narlikar, G.1997+A Practical Comparison of N-body AlgorithmsXIn Parallel Algorithms, Series in Discrete Mathematics and Theoretical Computer Science.This work compares three algorithms for the three dimensional N-body problem, the Barnes-Hut algorithm, Greengard's Fast Multipole Method(FMM), and the Parallel Multipole Tree Algorithm (PMTA) to determine which of the algorithms performs best in practice. Although FMM has a better asymptotic running time (O(N) instead of O(N log N) for uniform distributions), the algorithm is more complicated and it is not immediately clear above what values of N it performs better in practice. We studied the dependence of accuracy on the variable parameters theta, p and alpha, and then compared the floating point operation counts of the three algorithms at similar levels of accuracy, for both charged and uncharged random distributions. At a high level of accuracy (RMS-error ~= 10^-5), the FMM did the least number of operations for N > 10^4, assuming both charged and uncharged distributions of points. At a lower level of accuracy, (RMS-error ~= 10^-3) for uncharged distributions, the FMM did not outperform Barnes-Hut even for N > 10^8. For charged distributions of particles, both the FMM and PMTA were comparable at low accuracy. The algorithms were implemented in the parallel language NESL.Vhttp://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/papers/dimacs-nbody.html compared three tree-based algorithms, the Barnes-Hut algorithm [2], Greengard's Fast Multipole algorithm [9], and the Multipole Tree algorithm [6], in terms of both the computational cost and the accuracy of the methods. http://www-2.cs.cmu.edu/~scandal/alg/nbody.html?"Bustos, B. Navarro, G. Ch'avez, E.2001CPivot selection techniques for proximity searching in metric spaces33-40^In Proc. of the XXI Conference of the Chilean Computer Science Society (SCCC'01) IEEE CS Press-http://citeseer.nj.nec.com/bustos01pivot.html*?Callahan, P.B.1993ROptimal parallel all-nearest-neighbors using the well-separated pair decomposition332-3410In Proc. 34th Annu. ACM Sympos. Found. Comp. Sci1http://citeseer.nj.nec.com/callahan93optimal.html*?$Chávez, E. Figueroa, K. Navarro, G.1983RA Fast Algorithm for the All k Nearest Neighbors Problem in General Metric Spaces.226-232;In Proc. 24th IEEE Symp. on Foundations of Computer Science'http://citeseer.ist.psu.edu/462760.html? Callahan, P. B. Kosaraju, S. Rao1995?Algorithms for Dynamic Closest Pair and n-Body Potential Fields263-272<In Proc. 6th ACM-SIAM Sympos. Discrete Algorithms (SODA '95)%http://citeseer.nj.nec.com/99546.html*D?Clarkson, K. L.19835Fast algorithms for the all nearest neighbors problem226-2323In Proc. 24th Annu. IEEE Sympos. Found. Comput. ScigSIMD architecture, k-nearest neighbor, parallel processing, data analysis, reconfigurable mesh computerGiven a set S of m points stored on a reconfigurable mesh computer of size n×n, one point per processing element (PE). In this paper we present a parallel method for solving the k-Nearest Neighbor problem (k-NN). This method permits each point of S to know its k-NN (0 0, we produce a data structure, such that given any query point, a point of S will be reported whose distance from the query point is at most a factor of (1 + E) from that of the true nearest neighbor. Our algorithm runs in O(log3 n) expected time and requires O(n log n) space. The data structure can be built in O(n’) expected time. The constant factors depend on d and 6. Because of the practical importance of nearest neighbor searching in higher dimensions, we have implemented a practical variant of this algorithm,and show empirically that for many point distributions this variant of the algorithm finds the nearest neighbor in moderately large dimension significantly faster than existing practical approaches.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=313768&coll=Portal&dl=GUIDE&CFID=20333779&CFTOKEN=92886735? 0-89871-313-7?0Chon, Hae Don Agrawal, Divyakant Abbadi, Amr El2003?Range and kNN Query Processing for Moving Objects in Grid Model401-412 Mobile Networks and Applications84With the growing popularity of mobile computing devices and wireless communications, managing dynamically changing information about moving objects is becoming feasible. In this paper, we implement a system that manages such information and propose two query algorithms: a range query algorithm and a k nearest neighbor algorithm. The range query algorithm is combined with an efficient filtering technique which determines if a polyline corresponding to the trajectory of a moving object intersects with a given range. We study the performance of the system, which shows that despite the filtering step, for moderately large ranges, the range query algorithm we propose outperforms the algorithm without filtering.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=942352&coll=Portal&dl=GUIDE&CFID=20333779&CFTOKEN=92886735 1383-469X?Yufei Tao Dimitris Papadias2003'Spatial Queries in Dynamic Environments101-139+ACM Transactions on Database Systems (TODS)282hConventional spatial queries are usually meaningless in dynamic environments since their results may be invalidated as soon as the query or data objects move. In this paper we formulate two novel query types, time parameterized and continuous queries, applicable in such environments. A time-parameterized query retrieves the actual result at the time when the query is issued, the expiry time of the result given the current motion of the query and database objects, and the change that causes the expiration. A continuous query retrieves tuples of the form , where each result is accompanied by a future interval, during which it is valid. We study time-parameterized and continuous versions of the most common spatial queries (i.e., window queries, nearest neighbors, spatial joins), proposing efficient processing algorithms and accurate cost models.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=777944&coll=Portal&dl=GUIDE&CFID=20411976&CFTOKEN=50968782 0362-5915?"Ciaccia, P. Patella, M. Zezula, P.1997IM-tree: An Efficient Access Method for Similarity Search in Metric Spaces426-435,Very Large Data Bases (VDLP) Conference 1997A new access method, called M-tree, is proposed to organize and search large data sets from a generic “metric space”, i.e. where object proximity is only defined by a distance function satisfying the positivity, symmetry, and triangle inequality postulates. We detail algorithms for insertion of objects and split management, which keep the M-tree always balanced - several heuristic split alternatives are considered and experimentally evaluated. Algorithms for similarity (range and k-nearest neighbors) queries are also described. Results from extensive experimentation with a prototype system are reported, considering as the performance criteria the number of page I/O’s and the number of distance computations. The results demonstrate that the Mtree indeed extends the domain of applicability beyond the traditional vector spaces, performs reasonably well in high-dimensional data spaces, and scales well in case of growing files./http://citeseer.ist.psu.edu/ciaccia97mtree.html 1-55860-470-7s? Yianilos, P.1993SData Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces311-321In Proc. ACM-SIAM SODA'930Metric Space, Nearest Neighbor, KD-tree, VP-treenWe consider the computational problem of finding nearest neighbors in general metric spaces. Of particular interest are spaces that may not be conveniently embedded or approximated in Euclidian space, or where the dimensionality of a Euclidian representation is very high. Also relevant are high-dimensional Euclidian settings in which the distribution of data is in some sense of lower dimension and embedded in the space. The vp-tree (vantage point tree) is introduced in several forms, together with associated algorithms, as an improved method for these difficult search problems. Tree construction executes in O(n log(n)) time, and search is under certain circumstances and in the limit, O(long(n)) expected time. The theoretical basis for this approach is developed and the results of several experiments are reported. In Euclideian cases, kd-tree performance is compared./http://citeseer.ist.psu.edu/yianilos93data.html?Bentley, J. L.1975CMultidimensional Binary Search Trees Used For Associative Searching509-517.Communications of the ACM, 18(9): September 75associative retrieval, attribute, binary search trees, binary tree insertion, information retrieval system, intersection queries, key, nearest neighbor queries, partial match queriesThis paper develops the multidimensional binary search tree (or k-d tree, where k is the dimensionality of the search space) as a data structure for storage of information to be retrieved by associative searches. The k-d tree is defined and examples are given. It is shown to be quite efficient in its storage requirements. A significant advantage of this structure is that a single data structure can handle many types of queries very efficiently. Various utility algorithms are developed; their proven average running times in an n record file are: insertion, O(log n); deletion of the root, O(n(k-1)/k); deletion of a random node, O(log n); and optimization (guarantees logarithmic performance of searches), O(n log n). Search algorithms are given for partial match queries with t keys specified [proven maximum running time of O(n(k-t)/k)] and for nearest neighbor queries [empirically observed average running time of O(log n).] These performances far surpass the best currently known algorithms for these tasks. An algorithm is presented to handle any general intersection query. The main focus of this paper is theoretical. It is felt, however, that k-d trees could be quite useful in many applications, and examples of potential uses are given.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=361007&coll=Portal&dl=GUIDE&CFID=20333779&CFTOKEN=92886735 CITINGS 147 0001-0782FF? Berchtold, S.19968The X-tree: An Index Structure for High-Dimensional Data'Proceedings of the 22nd VLDB, August 96In this paper, we propose a new method for indexing large amounts of point and spatial data in highdimensional space. An analysis shows that index structures such as the R*-tree are not adequate for indexing high-dimensional data sets. The major problem of R-tree-based index structures is the overlap of the bounding boxes in the directory, which increases with growing dimension. To avoid this problem, we introduce a new organization of the directory which uses a split algorithm minimizing overlap and additionally utilizes the concept of supernodes. The basic idea of overlap-minimizing split and supernodes is to keep the directory as hierarchical as possible, and at the same time to avoid splits in the directory that would result in high overlap. Our experiments show that for high-dimensional data, the X-tree outperforms the well-known R*-tree and the TV-tree by up to two orders of magnitude.1http://citeseer.ist.psu.edu/berchtold96xtree.html? Guttman, A.19848R-trees: A Dynamic Index Structure for Spatial Searching47-57OIn proceedings of the ACM SIGMOD International Conference on Management of DataIn order to handle spatial data efficiently, as required in computer aided design and geo-data applications, a database system needs an index mechanism that will help it retrieve data items quickly according to their spatial locations However, traditional indexing methods are not well suited to data objects of non-zero size located m multi-dimensional spaces In this paper we describe a dynamic index structure called an R-tree which meets this need, and give algorithms for searching and updating it. We present the results of a series of tests which indicate that the structure performs well, and conclude that it is useful for current database systems in spatial applications.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=602266&coll=Portal&dl=GUIDE&CFID=20333779&CFTOKEN=92886735 0-89791-128-8?,Nievergelt, J. Hinterberger, H. Sevcik, K.C.1984>The Grid File: An Adaptable, Symmetric Multikey File Structure38-71+ACM Transactions on Database Systems (TODS)91mTraditional file structures that provide multikey access to records, for example, inverted files, are extensions of file structures originally designed for single-key access. They manifest various deficiencies in particular for multikey access to highly dynamic files. We study the dynamic aspects of file structures that treat all keys symmetrically, that is, file structures which avoid the distinction between primary and secondary keys. We start from a bitmap approach and treat the problem of file design as one of data compression of a large sparse matrix. This leads to the notions of a grid partition of the search space and of a grid directory, which are the keys to a dynamic file structure called the grid file. This file system adapts gracefully to its contents under insertions and deletions, and thus achieves an upper bound of two disk accesses for single record retrieval; it also handles range queries and partially specified queries efficiently. We discuss in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=318586&coll=Portal&dl=GUIDE&CFID=20239473&CFTOKEN=33442915 0362-5915t?,Fu, A. W. Chan, P. M. Cheung, Y. Moon, Y. S.2000PDynamic VP-Tree Indexing for N-Nearest Neighbor Search Given Pair-Wise Distances154-173EThe VLDB Journal - The International Journal on Very Large Data Bases92whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=765232&coll=Portal&dl=GUIDE&CFID=20255546&CFTOKEN=38486040 1066-8888$? Robinson, J.T.1981MThe K-D-B-tree: a search structure for large multidimensional dynamic indexes10-18TIn Proceedings of the 1981 ACM SIGMOD international conference on Management of data?http://portal.acm.org/citation.cfm?id=582321&dl=ACM&coll=portal 0-89791-040-0iB?!k,Yu, B. Orlandic, R. Bailey, T. Somavaram, J.2003KKDBKD-Tree: A Compact KDB-Tree Structure for Indexing Multidimensional DatafIn Proceedings of the International Conference on Information Technology: Computers and CommunicationsThe problem of storing and retrieving high-dimensional data continues to be an important issue. Inthis paper, we propose an efficient high-dimensional pointaccess method called the KDBKD-tree.The KDBKD-treeeliminates redundant information in KDB-trees bychanging the representation of the index entries in theinterior pages. Experimental evidence shows that theKDBKD-Tree outperforms other recent variants of KDB-trees, such as KDBFD-trees and KDBHD-trees.%http://www.cs.uwyo.edu/~yu/ITCC03.pdf 0-7695-1916-4?"FBeckmann, Norbert Kriegel, Hans-Peter Schneider, Ralf Seeger, Bernhard1990LThe R*-tree: An Efficient and Robust Access Method for Points and Rectangles322-331OIn Proceedings of the ACM SIGMOD international conference on Management of data1The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R*-tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R*-tree clearly outperforms the existing R-tree variants. Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R*-tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R*-tree is very attractive because of the following two reasons 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees.vhttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=98741&coll=Portal&dl=GUIDE&CFID=20255546&CFTOKEN=38486040 0163-5808?#Theodoridis, Y Sellis, T19960A Model for the Prediction of R-tree Performance161-171dIn Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems@In this paper we present an analytical model that predicts the performance of R-trees (and its variants) when a range query needs to be answered. The cost model uses knowledge of the dataset only, i.e., the proposed formula that estimates the number of disk accesses is a hmction of data properties, namely, the amount of data and their density in the work space. In other words, the proposed model is applicable even before the construction of the R-tree index, a fact that makes it a useful tool for dynamic spatial databases. Several experiments on synthetic and real datasets show that the proposed analytical model is very accurate, the relative error being usually around 10%- 15%, for uniform and non-uniform distributions. We believe that this error is involved with the gap between efficient R-tree variants, like the R*-tree, and an optimum, not implemented yet, method. Our work extends previous research concerning R-tree analysis and constitutes a useful tool for spatial query optimizers that need to evaluate the cost of a complex spatial query and its execution procedure.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=237705&coll=Portal&dl=GUIDE&CFID=20255546&CFTOKEN=38486040 0-89791-781-2?$0Lin, King Ip Jagadish, H. V. Faloutsos, Christos19949The TV-tree: an index structure for high-dimensional data517-542EThe VLDB Journal - The International Journal on Very Large Data Bases34We propose a file structure to index high-dimensionality data, which are typically points in some feature space. The idea is to use only a few of the features, using additional features only when the additional discriminatory power is absolutely necessary. We present in detail the design of our tree structure and the associated algorithms that handle such "varying length" feature vectors. Finally, we report simulation results, comparing the proposed structure with the R*-tree, which is one of the most successful methods for low-dimensionality spaces. The results illustrate the superiority of our method, which saves up to 80% in disk accesses.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=615210&coll=Portal&dl=GUIDE&CFID=20255470&CFTOKEN=52246893 1066-8888?%White, D.A. Jain, R.1996$Similarity Indexing with the SS-tree516-523GProceedings of the Twelfth International Conference on Data EngineeringEfficient indexing of high dimensional feature vectors is important to allow visual information systems and a number other applications to scale up to large databases. In this paper, we define this problem as "similarity indexing" and describe the fundamental types of "similarity queries" that we believe should be supported. We also propose a new dynamic structure for similarity indexing called the similarity search tree or SS-tree. In nearly every test we performed on high dimensional data, we found that this structure performed better than the R*-tree. Our tests also show that the SS-tree is much better suited for approximate queries than the R*-tree.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=655573&coll=Portal&dl=GUIDE&CFID=20255470&CFTOKEN=52246893 CITINGS 14 0-8186-7240-4/?'1Saltenis, S. Jensen, C. Leutenegger, S. Lopez, M.20026Indexing of Moving Objects for Location-Based Services463DProceedings of the 18th International Conference on Data EngineeringXAccess method, Moving objects, R-tree, Location-based service, Multidimensional indexingVisionaries predict that the Internet will soon extend to billions of wireless devices, or objects, a substantial fraction of which will offer their changing positions to location-based services. This paper assumes an Internet-service scenario where objects that have not reported their position within a specified duration of time are expected to no longer be interested in, or of interest to, the service. Due to the possibility of many "expiring" objects, a highly dynamic database results.The paper presents an R-tree based technique for the indexing of the current positions of such objects. Different types of bounding regions are studied, and new algorithms are provided for maintaining the tree structure. Performance experiments indicate that, when compared to the approach where the objects are not assumed to expire, the new indexing technique can improve search performance by a factor of two or more without sacrificing update performance.>http://portal.acm.org/citation.cfm?id=878984&dl=ACM&coll=GUIDE 1063-6382?(#Agarwal, P.K. Arge, L. Erickson, J.2003Indexing Moving Points207-243'Journal of Computer and System Sciences661We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that any query of the following form can be answered quickly: Given a rectangle R and a real value t, report all K points of S that lie inside R at time t. We first present an indexing structure that, for any given constant e > 0, uses O(N/B) disk blocks and answers a query in O(N/B1/2+e + K/B)I/Os, where B is the block size. It can also report all the points of S that lie inside R during a given time interval. A point can be inserted or deleted, or the trajectory of a point can be changed, in O(log2BN) I/Os. Next, we present a general approach that improves the query time if the queries arrive in chronological order, by allowing the index to evolve over time. We obtain a tradeoff between the query time and the number of times the index needs to be updated as the points move. We also describe an indexing scheme in which the number of I/Os required to answer a query depends monotonically on the difference between the query time stamp t and the current time. Finally, we develop an efficient indexing scheme to answer approximate nearest-neighbor queries among moving points.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=846166&coll=Portal&dl=GUIDE&CFID=20411976&CFTOKEN=50968782 0022-0000P?)%Basch, J. Guibas, L.J. Hershberger J.1997Data Structures for Mobile Data747-756JProceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms-whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=314435&dl=GUIDE&coll=Portal&CFID=20411976&CFTOKEN=50968782 haven't read 0-89871-390-0:?* Basch, J. Guibas, L.J. Zhang, l.1997#Proximity problems on moving points344-351HProceedings of the thirteenth annual symposium on Computational geometryA kinetic data structure for the maintenance of a multidimensional range search tree is introduced. This structure is used as a building block to obtain kinetic data structures for two classical geometric proximity problems in arbitrary dlmensions: the first structure maintains the closest pair of a set of continuously moving points, and is provably efficient. The second structure maintains a spanning tree of the moving points whose cost remains within some prescribed factor of the minimum spanning tree.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=262998&dl=GUIDE&coll=Portal&CFID=20411976&CFTOKEN=50968782 0-89791-878-9AF?+,Tao, Yufei Papadias, Dimitris Shen, Qiongmao2002"Continuous Nearest Neighbor Search*In Proceedings of the 28th VLDB ConferencesA continuous nearest neighbor query retrieves the nearest neighbor (NN) of every point on a line segment (e.g., “find all my nearest gas stations during my route from point s to point e”). The result contains a set of tuples, such that point is the NN of all points in the corresponding interval. Existing methods for continuous nearest neighbor search are based on the repetitive application of simple NN algorithms, which incurs significant overhead. In this paper we propose techniques that solve the problem by performing a single query for the whole input segment. As a result the cost, depending on the query and dataset characteristics, may drop by orders of magnitude. In addition, we propose analytical models for the expected size of the output, as well as, the cost of query processing, and extend out techniques to several variations of the problem.(http://www.vldb.org/conf/2002/S09P02.pdf looks okay?,0Zhang, J. Zhu, M. Papadias, D. Tao, Y. Lee, D.L.2003Location-based Spatial Queries443-454TProceedings of the 2003 ACM SIGMOD international conference on on Management of data might be okay!In this paper we propose an approach that enables mobile clients to determine the validity of previous queries based on their current locations. In order to make this possible, the server returns in addition to the query result, a validity region around the client's location within which the result remains the same. We focus on two of the most common spatial query types, namely nearest neighbor and window queries, define the validity region in each case and propose the corresponding query processing algorithms. In addition, we provide analytical models for estimating the expected size of the validity region. Our techniques can significantly reduce the number of queries issued to the server, while introducing minimal computational and network overhead compared to traditional spatial queries.vhttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=872812&coll=Portal&dl=GUIDE&CFID=20303748&CFTOKEN=2062914? 1-58113-634-Xj?-:Freidman, Jerome H. Bentley, Jon Louis Finkel, Raphael Ari1977BAn Algorithm for Finding Best Matches in Logarithmic Expected Time209-2260ACM Transactions on Mathematical Software (TOMS)33best matches, nearest neighbors, file searching, computational geometry, associative searching, search trees, multidmiensional searching,An algorithm and data structure are presented for searching a file containing N records, each described by k real valued keys, for the m closest matches or nearest neighbors to a given query record. The computation required to organize the file is proportional to kN log N. The expected number of records examined in each search is independent of the file size. The expected computation to perform each search is proportional to log N. Empirical evidence suggests that, except for very small files, this algorithm is considerably faster than other methods.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=355745&coll=Portal&dl=GUIDE&CFID=20333779&CFTOKEN=92886735NMedian k-d - A refined kd-tree, using median cuts and bucketing. haven't read. 0098-3500]?.BFaloutsos, Christos Seeger, Bernhard Traina, Agma Traina, Caetano2000)Spatial Join Selectivity Using Power Laws177-188pACM SIGMOD Record , Proceedings of the 2000 ACM SIGMOD international conference on Management of data (May 2000)292We discovered a surprising law governing the spatial join selectivity across two sets of points. An example of such a spatial join is “find the libraries that are within 10 miles of schools”. Our law dictates that the number of such qualifying pairs follows a power law, whose exponent we call “pair-count exponent” (PC). We show that this law also holds for self-spatial-joins (“find schools within 5 miles of other schools”) in addition to the general case that the two point-sets are distinct. Our law holds for many real datasets, including diverse environments (geographic datasets, feature vectors from biology data, galaxy data from astronomy). In addition, we introduce the concept of the Box-Occupancy-Product-Sum (BOPS) plot, and we show that it can compute the pair-count exponent in a timely manner, reducing the run time by orders of magnitude, from quadratic to linear. Due to the pair-count exponent and our analysis (Law 1), we can achieve accurate selectivity estimates in constant time (O(1)) without the need for sampling or other expensive operations. The relative error in selectivity is about 30% with our fast BOPS method, and even better (about 10%), if we use the slower, quadratic method.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=335412&coll=Portal&dl=GUIDE&CFID=20509324&CFTOKEN=19821135 0163-5808 ?/!Hjaltason, Gísli R. Samet, Hanan1999&Distance Browsing in Spatial Databases265-318+ACM Transactions on Database Systems (TODS)242DWe compare two different techniques for browsing through a collection of spatial objects stored in an R-tree spatial data structure on the basis of their distances from an arbitrary spatial query object. The conventional approach is one that makes use of a k-nearest neighbor algorithm where k is known prior to the invocation of the algorithm. Thus if m < k neighbors are needed, the k-nearest neighbor algorithm has to be reinvoked for m neighbors, thereby possibly performing some redundant computations. The second approach is incremental in the sense that having obtained the k nearest neighbors, the k + 1st neighbor can be obtained without having to calculate the k + 1 nearest neighbors from scratch. The incremental approach is useful when processing complex queries where one of the conditions involves spatial proximity (e.g., the nearest city to Chicago with population greater than a million), in which case a query engine can make use of a pipelined strategy. We present a general incremental nearest neighbor algorithm that is applicable to a large class of hierarchical spatial data structures. This algorithm is adapted to the R-tree and its performance is compared to an existing k-nearest neighbor algorithm for R-trees [Rousseopoulos et al. 1995]. Experiments show that the incremental nearest neighbor algorithm significantly outperforms the k-nearest neighbor algorithm for distance browsing queries in a spatial database that uses the R-tree as a spatial index. Moreover, the incremental nearest neighbor algorithm usually outperforms the k-nearest neighber algorithm when applied to the k-nearest neighbor problem for the R-tree, although the improvement is not nearly as large as for distance browsing queries. In fact, we prove informally that at any step in its execution the incremental nearest neighbor algorithm is optimal with respect to the spatial data structure that is employed. Furthermore, based on some simplifying assumptions, we prove that in two dimensions the number of distance computations and leaf nodes accesses made by the algorithm for finding k neighbors is O(k + k).whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=320255&coll=Portal&dl=GUIDE&CFID=20385494&CFTOKEN=184394430BF improvement on Nearest Neighbor Queries paper 0362-5915?0Daniel A. Keim1999BEfficient geometry-based similarity search of 3D spatial databases419-430QProceedings of the 1999 ACM SIGMOD international conference on Management of data Searching a database of 3D-volume objects for objects which are similar to a given 3D search object is an important problem which arises in number of database applications - for example, in Medicine and CAD. In this paper, we present a new geometry-based solution to the problem of searching for similar 3D-volume objects. The problem is motivated from a real application in the medical domain where volume similarity is used as a basis for surgery decisions. Our solution for an efficient similarity search on large databases of 3D volume objects is based on a new geometric index structure. The basic idea of our new approach is to use the concept of hierarchical approximations of the 3D objects to speed up the search process. We formally show the correctness of our new approach and introduce two instantiations of our general idea, which are based on cuboid and octree approximations. We finally provide a performance evaluation of our new index structure revealing significant performance improvements over existing approaches.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=304219&coll=Portal&dl=GUIDE&CFID=20526069&CFTOKEN=901841176? seems okay___ MIV=approximating region to grid boxes 0163-5808?15Authors Sang-Wook Kim Charu C. Aggarwal Philip S. Yu2001=Effective Nearest Neighbor Indexing with the Euclidean Metric9-16YProceedings of the tenth international conference on Information and knowledge management\The nearest neighbor search is an important operation widely-used in multimedia databases. In higher dimensions, most of previous methods for nearest neighbor search become inefficient and require to compute nearest neighbor distances to a large fraction of points in the space. In this paper, we present a new approach for processing nearest neighbor search with the Euclidean metric, which searches over only a small subset of the original space. This approach effectively approximates clusters by encapsulating them into geometrically regular shapes and also computes better upper and lower bounds of the distances from the query point to the clusters. For showing the effectiveness of the proposed approach, we perform extensive experiments. The results reveal that the proposed approach significantly outperforms the X-tree as well as the sequential scan.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=502588&coll=Portal&dl=GUIDE&CFID=20526069&CFTOKEN=90184117'? says better than X-tree high dims.... 1-58113-436-36F?2AMihael Ankerst Gabi Kastenmüller Hans-Peter Kriegel Thomas Seidl19997Nearest Neighbor Classification in 3D Protein DatabasesgSource Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology34-43d3D Protein Databases, Nearest Neighbor Classification, Geometric Similarity Search, Machine Learning<In molecular databases, structural classification is a basic task that can be successfully approached by nearest neighbormethods. The underlying similarity models consider spatialproperties such as shape and extension as well as thematic attributes. We introduce 3D shape histograms as an intuitive and powerful approach to model similarity for solid objects such as molecules. Errors of measurement, sampling, and numerical rounding may result in small displacements of atomic coordinates. These effects may be handled by using quadratic form distance functions. An efficient processing of similarity queries based on quadratic forms is supported by a filter-refinement architecture. Experiments on our 3D protein database demonstrate the high classification accuracy of more than 90% and the good performance of the technique.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=660824&coll=Portal&dl=GUIDE&CFID=20526069&CFTOKEN=90184117? 1-57735-083-9?3Böhm, Christian2000AA Cost Model for Query Processing in High-Dimensional Data Spaces129-178?Source ACM Transactions on Database Systems (TODS) (June 2000)252gDuring the last decade, multimedia databases have become increasingly important in many application areas such as medicine, CAD, geography, and molecular biology. An important research topic in multimedia databases is similarity search in large data sets. Most current approaches that address similarity search use the feature approach, which transforms important properties of the stored objects into points of a high-dimensional space (feature vectors). Thus, similarity search is transformed into a neighborhood search in feature space. Multidimensional index structures are usually applied when managing feature vectors. Query processing can be improved substantially with optimization techniques such as blocksize optimization, data space quantization, and dimension reduction. To determine optimal parameters, an accurate estimate of index-based query processing performance is crucial. In this paper we develop a cost model for index structures for point databases such as the R*-tree and the X-tree. It provides accurate estimates of the number of data page accesses for range queries and nearest-neighbor queries under a Euclidean metric and a maximum metric and a maximum metric. The problems specific to high-dimensional data spaces, called boundary effects, are considered. The concept of the fractal dimension is used to take the effects of correlated data into account.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=357776&coll=Portal&dl=GUIDE&CFID=20385494&CFTOKEN=18439443SURVEY!!! Looks good 0362-5915'?4Warren, M. S. Salmon, J. K.1992HAstrophysical N-body Simulations using Hierarchical Tree Data Structures570-576=Proceedings of the 1992 ACM/IEEE conference on Supercomputingn-bodyWe report on recent large astrophysical N-body simulations executed on the Intel Touchstone Delta system. We review the astrophysical motivation, and the numerical techniques, and discuss steps taken to parallelize these simulations. The methods scale as O(N log N), for large values of N, and also scale linearly with the number of processors. The performance, sustained for a duration of 67 hours was between 5.1 and 5.4 Gj70p/sec on a 51,2 processor system.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=148090&coll=Portal&dl=GUIDE&CFID=20668623&CFTOKEN=51137664 0-8186-2630-5?59Papadopoulos, Apostolos Rigaux, Philippe Scholl, Michel1999>A Performance Evaluation of Spatial Join Processing Strategies286-307OProceedings of the 6th International Symposium on Advances in Spatial DatabasesoWe provide an evaluation of query execution plans (QEP) in the case of queries with one or two spatial joins. The QEPs assume R*-tree indexed relations and use a common set of spatial joins algorithms, among which one is a novel extension of a strategy based on an on-the-fly index creation prior to the join with another indexed relation. A common platform is used on which a set of spatial access methods and join algorithms are available. The QEPs are implemented with a general iterator-based spatial query processor, allowing for pipelined QEP execution, thus minimizing memory space required for intermediate results.*http://www.lri.fr/~rigaux/publis/PRS99.pdfnot read 3-540-66247-25?6Gaede, Volker Günther, Oliver1998Multidimensional Access Methods170-2317Source ACM Computing Surveys (CSUR) archive (June 1998)3020data structures, multidimensional access methodsSearch operations in databases require special support at the physical level. This is true for conventional databases as well as spatial databases, where typical search operations include the point query (find all objects that contain a given search point) and the region query (find all objects that overlap a given search region). More than ten years of spatial database research have resulted in a great variety of multidimensional access methods to support such operations. We give an overview of that work. After a brief survey of spatial data management in general, we first present the class of point access methods, which are used to search sets of points in two or more dimensions. The second part of the paper is devoted to spatial access methods to handle extended objects, such as rectangles or polyhedra. We conclude with a discussion of theoretical and experimental results concerning the relative performance of various approaches.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=280279&coll=Portal&dl=GUIDE&CFID=20544313&CFTOKEN=89100490"++ BRILLIANT, but long CITINGS 86 0360-0300'?7EFagin, Ronald Nievergelt, Jurg Pippenger, Nicholas Strong, H. Raymond1979;Extendible Hashing - A Fast Access Method for Dynamic Files315-344KSource ACM Transactions on Database Systems (TODS) archive (September 1979)43Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that grows and shrinks gracefully as the database grows and shrinks. This approach simultaneously solves the problem of making hash tables that are extendible and of making radix search trees that are balanced. We study, by analysis and simulation, the performance of extendible hashing. The results indicate that extendible hashing provides an attractive alternative to other access methods, such as balanced trees.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=320092&dl=GUIDE&coll=Portal&CFID=20544313&CFTOKEN=89100490 - not read 0362-5915?84Faloutsos, Christos Sellis, Timos Roussopoulos, Nick19872Analysis of Object Oriented Spatial Access Methods426-439QProceedings of the 1987 ACM SIGMOD international conference on Management of dataeThis paper provides an analysis of R-trees and a variation (R+-trees) that avoids overlapping rectangles in intermediate nodes of the tree. The main contributions of the paper are the following. We provide the first known analysis of R-trees. Although formulas are given for objects in one dimension (line segments), they can be generalized for objects in higher dimensions as well. We show how the the transformation of objects to higher dimenslons [HINR83] can be effectively used as a tool for the analysis of R- and R+- trees. Finally, we derive formulas for R+-trees and compare the two methods analytically. The results we obtained show that R+-trees require less than half the disk accesses required by a corresponding R-tree when searching files of real hfe sizes R+-trees are clearly superior in cases where there are few long segments and a lot of small ones.vhttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=38758&dl=GUIDE&coll=Portal&CFID=20544313&CFTOKEN=89100490-- not so great. 0163-5808q?9Tamminen, Markku Sulonen, Reijo19828The EXCELL Method for Efficient Geometric Access to Data345-351:Proceedings of the nineteenth design automation conference"The extendible cell (EXCELL) method provides a data structure for efficient geometric access. It stores geometric data into computer storage blocks corresponding to disjoint variable sized rectangular cells accessible by an address calculation type directory. We describe the method for point files and files of more complicated figures analyzing performance. We report algorithms for the nearest neighbour and point-in-polygon-network problems and describe applications to geographical data bases, hidden line elimination and geometric modeling.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=809228&coll=Portal&dl=GUIDE&CFID=20577822&CFTOKEN=14769457 Will use! 0-89791-020-6?:Freeston, Michael1987&The BANG file: A new kind of grid file260-269QProceedings of the 1987 ACM SIGMOD international conference on Management of dataA new multi-dimensional file structure has been developed in the course of a project to devise ways of improving the support for interactive queries to database and knowledge bases. Christened the 'BANG' file - a Balanced And Nested Grid - the new structure is of the 'grid file' type, but is fundamentally different from previous grid file designs in that it does not share their common underlying properties. It has a tree-structured directory which has the self-balancing property of a B-tree and which, in contrast to previous designs, always expands at the same rate as the data, whatever the form of the data distribution. Its partitioning strategy both accurately reflects the clustering of points in the data space, and is flexible enough to adapt gracefully to changes in the distribution.Bhttp://portal.acm.org/citation.cfm?id=38743&dl=ACM&coll=GUIDE#opub 0163-5808:?;$Seeger, Bernhard Kriegel, Hans-Peter1990SThe Buddy Tree: An Efficient and Robust Access Method for Spatial Data Base Systems590-601TSource Proceedings of the sixteenth international conference on Very large databasesIn this paper, we propose a new multidimensional access method, called the buddy-tree, to support point as well as spatial data in a dynamic environment. The buddy-tree can be seen as a compromise of the R-tree and the grid file, but it is fundamentally different from each of them. Because grid files loose performance for highly correlated data, the buddy-tree is designed to organize such data very efficiently, partitioning only such parts of the data space which contain data and not partitioning empty data space. The directory consists of a very flexible partitioning and reorganization scheme based on a generalization of the buddy-system. As for B-trees, the buddy-tree fulfills the property that insertions and deletions are restricted to exactly one path of the directory. Additional important properties which are not fulfilled in this combination by any other multidimensional tree-based access method are: (i) the directory grows linear in the number of records, (ii) no overflow pages are allowed, (iii) the data space is partitioned into minimum bounding rectangles of the actual data and (iv) the performance is basicly independent of the sequence of insertions. In this paper, we introduce the principles of the buddy-tree, the organization of its directory and the most important algorithms. Using our standardized testbed, we present a performance comparison of the buddy-tree with other access methods demonstrating the superiority and robustness of the buddy-tree.fhttp://portal.acm.org/citation.cfm?id=94615&dl=GUIDE&coll=GUIDE http://www.vldb.org/conf/1990/P590.PDF 0-55860-149-X?<Klaus Hinrichs1985?Implementation of the grid file: design concepts and experience569-592254= http://portal.acm.org/citation.cfm?id=5039&dl=ACM&coll=GUIDE -- CANT FIND 0006-3835?=3Hutflesz, Andreas Six, Hans-Werner Widmayer, Peter19880Twin Grid Files: Space Optimizing Access Schemes183-190QProceedings of the 1988 ACM SIGMOD international conference on Management of dataStorage access schemes for points, supporting spatial searching, usually suffer from an undesirably low storage space utilization. We show how a given set of points can be distributed among two grid files in such a way that storage space utilization is optimal. The optimal twin grid file can be built practically as fast as a standard grid file, i.e., the storage space optimality is obtained at almost no extra cost. We compare the performances of the standard grid file, the optimal static twin grid file, and an efficient dynamic twin grid file, where insertions and deletions trigger the redistribution of points among the two grid files. Twin grid files utilize storage space at roughly 90%, as compared with the 69% of the standard grid file. Typical range queries - the most important spatial search operations - can be answered in twin grid files at least as fast as in the standard grid file.=http://portal.acm.org/citation.cfm?id=50222&dl=ACM&coll=GUIDE 0-89791-268-3?>Mireille Regnier1985 Analysis of Grid File Algorithms335-358 BIT archive252uhttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=3823&coll=Portal&dl=GUIDE&CFID=20579400&CFTOKEN=32601696$-- NOT DOWNLOADED CITINGS 6 FRENCH? 0006-3835??=Kalashnikov, Dmitri V. Prabhakar, Sunil Hambrusch, Susanne E.2004@Main Memory Evaluation of Monitoring Queries Over Moving Objects117-1357Distributed and Parallel Databases archive (March 2004)152In this paper we evaluate several in-memory algorithms for efficient and scalable processing of continuous range queries over collections of moving objects. Constant updates to the index are avoided by query indexing. No constraints are imposed on the speed or path of moving objects or fraction of objects that move at any moment in time. We present a detailed analysis of a grid approach which shows the best results for both skewed and uniform data. A sorting based optimization is developed for significantly improving the cache hit-rate. Experimental evaluation establishes that indexing queries using the grid index yields orders of magnitude better performance than other index structures such as R*-trees.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=966448&coll=Portal&dl=GUIDE&CFID=20689990&CFTOKEN=77331203IAlmost 100% identical to "Efficient Evaluation of Moving Points ..." 2002 0926-8782@?@ Samet, Hanan19902The Design and Analysis of Spatial Data Structures493Boston, MA, USA*Addison-Wesley Longman Publishing Co., Inc=http://portal.acm.org/citation.cfm?id=77589&dl=ACM&coll=GUIDE)WOULD BE GOOD TO GET A COPY CITINGS 199 0-201-50255-0$Addison-Wesley Longman Publishing Co?A"Kamel, Ibrahim Faloutsos, Christos19941Hilbert R-tree: An Improved R-tree using Fractals500-509MProceedings of the Twentieth International Conference on Very Large DatabasesWe propose a new R-tree structure that outperforms all the older ones. The heart of the idea is to facilitate the deferred splitting approach in Rtrees. This is done by proposing an ordering on the Rtree nodes. This ordering has to be 'good', in the sense that it should group 'similar' data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Following [19] we have chosen the socalled '2Dc' method, which sorts rectangles according to the Hilbert value of the center of the rectangles. Given the ordering, every node has a well defined set of sibling nodes; thus, we can use deferred splitting. By adjusting the split policy, the Hilbert Rtree can achieve as high utilization as desired. To the contrary, the R \Lambda tree has no control over the space utilization, typically achieving up to 70%. We designed the manipulation algorithms in detail, and we did a full implementation of the Hilbert Rtree. Our experiments show that the '2to3' split policy provides a compromise between the insertion complexity and the search cost, giving up to 28% savings over the R \Lambda \Gamma tree [3] on real data.(citeseer.ist.psu.edu/kamel94hilbert.html?B/Christian Böhm Stefan Berchtold Daniel A. Keim2001mSearching in High-dimensional Spaces - Index Structures for Improving the Performance of Multimedia Databases322-3735ACM Computing Surveys (CSUR) archive (September 2001)333?During the last decade, multimedia databases have become increasingly important in many application areas such as medicine, CAD, geography, and molecular biology. An important research issue in the field of multimedia databases is the content-based retrieval of similar multimedia objects such as images, text, and videos. However, in contrast to searching data in a relational database, a content-based retrieval requires the search of similar objects as a basic functionality of the database system. Most of the approaches addressing similarity search use a so-called feature transformation that transforms important properties of the multimedia objects into high-dimensional points (feature vectors). Thus, the similarity search is transformed into a search of points in the feature space that are close to a given query point in the high-dimensional feature space. Query processing in high-dimensional spaces has therefore been a very active research area over the last few years. A number of new index structures and algorithms have been proposed. It has been shown that the new index structures considerably improve the performance in querying large multimedia databases. Based on recent tutorials [Berchtold and Keim 1998], in this survey we provide an overview of the current state of the art in querying multimedia databases, describing the index structures and algorithms for an efficient query processing in high-dimensional spaces. We identify the problems of processing queries in high-dimensional space, and we provide an overview of the proposed approaches to overcome these problems.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=502809&coll=Portal&dl=GUIDE&CFID=20807916&CFTOKEN=47254095?? 0360-0300e?CLawder, J. K. King, P. J. H.2001MQuerying multi-dimensional data indexed using the Hilbert space-filling curve19-24ACM SIGMOD Record (March 2001)301Mapping to one-dimensional values and then using a one-dimensional indexing method has been proposed as a way of indexing multi-dimensional data. Most previous related work uses the Z-Order Curve but more recently the Hilbert Curve has been considered since it has superior clustering properties. Any approach, however, can only be of practical value if there are effective methods for executing range and partial match queries. This paper describes such a method for the Hilbert Curve.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=373678&coll=Portal&dl=GUIDE&CFID=20699715&CFTOKEN=95585171?- Might be good to use - cool diagram - divide using quadrants. 0163-5808 ?DDBongki Moon H. v. Jagadish Christos Faloutsos Joel H. Saltz2001HAnalysis of the Clustering Properties of the Hilbert Space-Filling Curve124-1413IEEE Transactions on Knowledge and Data Engineering131locality-preserving linear mapping, range queries, multi-attribute access methods, data clustering, Hilbert curve, space-filling curves, fractals.Several schemes for the linear mapping of a multidimensional space have been proposed for various applications, such as access methods for spatio-temporal databases and image compression. In these applications, one of the most desired properties from such linear mappings is clustering, which means the locality between objects in the multidimensional space being preserved in the linear space. It is widely believed that the Hilbert space-filling curve achieves the best clustering [1], [14]. In this paper, we analyze the clustering property of the Hilbert space-filling curve by deriving closed-form formulas for the number of clusters in a given query region of an arbitrary shape (e.g., polygons and polyhedra). Both the asymptotic solution for the general case and the exact solution for a special case generalize previous work [14]. They agree with the empirical results that the number of clusters depends on the hypersurface area of the query region and not on its hypervolume. We also show that the Hilbert curve achieves better clustering than the z curve. From a practical point of view, the formulas given in this paper provide a simple measure that can be used to predict the required disk access behaviors and, hence, the total access time.http://citeseer.ist.psu.edu/cache/papers/cs/101/ftp:zSzzSzftp.cs.umd.eduzSzpubzSzhpslzSzpaperszSzhilbert-tr.pdf/moon96analysis.pdf/ CITINGS 4 1041-4347?EAbel, D.J. Mark. D. M.19908A Comparative Analysis of Some Two-Dimensional Orderings21-31Int. J. Geograph. Inf. Syst41COULD NOT FIND ANYWHERE!!!!!4?F Ercolessi, F1997A Molecular Dynamics Primer2004 01-07-2004ICTP,http://www.fisica.uniud.it/~ercolessi/md/md/G+ http://diamond.kist.re[F?GJ. A. Izaguirre T. Matthey20043Parallel multigrid summation for the N-body problemHsubmitted to Journal of Parallel and Distributed Computing (20 Feb 2004)]parallel N-body solvers, multigrid summation, fast electrostatic solvers, particle mesh-EwaldAn (n) parallel multigrid summation method for the N-body problem is presented. The method works with vacuum or periodic boundary conditions. It is based on a hierarchical decomposition of computational kernels on multiple grids. For low accuracy calculations, appropriate for molecular dynamics, a sequential implementation is faster than both Fast Multipole and Particle Mesh Ewald (PME). Its parallel implementation is more scalable than PME and comparable to the fast multipole. The method can be combined with multiple time stepping integrators to produce a powerful simulation protocol for simulation of biological molecules and other materials. The parallel implementation is based on MPI, and is tested in a variety of clusters and shared memory computers. It is available as open-source in http://protomol.sourceforge.net. An auxiliary tool allows the automatic selection of optimal parameters for given molecular systems and accuracies required, and is available in http://mdsimaid.cse.nd.edu..http://www.ii.uib.no/~matthey/text/paper12.pdf(+ Great references ect,NOT PUBLISHED!! +#?H!R. D. Skeel I. Tezcan D. J. Hardy20026Multiple Grid Methods for Classical Molecular Dynamics673-684J. Comp. Chem. 236_N-body solver; multigrid method; fast multipole method; fast electrostatics; molecular dynamicsPresented in the context of classical molecular mechanics and dynamics are multilevel summation methods for the fast calculation of energies/forces for pairwise interactions, which are based on the hierarchical interpolation of interaction potentials on multiple grids. The concepts and details underlying multigrid interpolation are described. For integration of molecular dynamics the use of different time steps for different interactions allows longer time steps for many of the interactions, and this can be combined with multiple grids in space. Comparison is made to the fast multipole method, and evidence is presented suggesting that for molecular simulations multigrid methods may be superior to the fast multipole method and other tree methods.3http://www.ks.uiuc.edu/~dhardy/preprints/SkTH02.pdf-P?IL. Greengard V. Rokhlin1987)A Fast Algorithm for Particle Simulations325-3480Journal of Computational Physics (December 1987)732San Diego, CA, USA!Academic Press Professional, Inc.>http://portal.acm.org/citation.cfm?id=36901&dl=ACM&coll=portal)- COULD NOT FIND COPY - THINK IS BOOK :( 0021-9991.?J!T. Bishop R. D. Skeel K. Schulten1997^Difficulties with Multiple Timestepping and the Fast Multipole Algorithm in Molecular Dynamics 1785-1791J. Comp. Chem.1814Vmultiple time steps; r-RESPA; Verlet method; molecular dynamics; fast multipole methodNumerical experiments are performed on a 36,000-atom protein-DNA-water simulation to ascertain the effectiveness of two devices for reducing the time spent computing long-range electrostatics interactions. It is shown for Verlet-Irr-RESPA multiple time stepping, which is based on approximating long-range forces as widely separated impulses, that a long time step of 5 fs results in a dramatic energy drift and that this is reduced by using an even larger long time step. It is also shown that the use of as many as six terms in a fast multipole algorithm approximation to long-range electrostatics still fails to prevent significant energy drift even though four digits of accuracy is obtained.Bhttp://www.ks.uiuc.edu/Publications/Papers/PDF/BISH97A/BISH97A.pdf-- not sure about it3?KE. L. Pollock Jim Glosli1996PComments on PPPM, FMM, and the Ewald Method for Large Periodic Coulombic Systems93-110"Computer Physics Communications 95Prompted by the need to simulate large molecular or gravitational systems and the availability of multiprocessor computers, alternatives to the standard Ewald calculation of Coulombic interactions have been developed. The two most popular alternatives, the fast multipole method (FMM) and the particle-particle particle-mesh (P3M) method are compared here to the Ewald method for a single processor machine. Parallel processor implementations of the P3M and Ewald methods are compared. The P3Mmethod is found to be both faster than the FMM and easier to implement efficiently as it relies on commonly available software (FFT subroutines). Both the Ewald and P3M method are easily implemented on parallel architectures with the P3M method the clear choice for large systems.7http://arxiv.org/PS_cache/cond-mat/pdf/9511/9511134.pdf?+- NOT READ Apparently says PPM = better & easier to implement!-?L'Ananth Y. Grama Vipin Kumar Ahmed Sameh1994NScalable Parallel Formulations of the Barnes-Hut Method for n-Body Simulations439-448=Proceedings of the 1994 ACM/IEEE conference on SupercomputingIn this paper, we present two new parallel formulations of the Barnes-Hut method. These parallel formulations are especially suited for simulations with irregular particle densities. We first present a parallel formulation that uses a static partitioning of the domain and assignment of subdomains to processors. We demonstrate that this scheme delivers acceptable load balance, and coupled with two collective communication operations, it yields good performance. We present a second parallel formulation which combines static decomposition of the domain with an assignment of subdomains to processors based on Morton ordering. This alleviates the load imbalance inherent in the first scheme. The second parallel formulation is inspired by two currently best known parallel algorithms for the Barnes-Hut method. We present an experimental evaluation of these schemes on a 256 processor nCUBE2 parallel computer for an astrophysical simulation.whttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=602846&coll=Portal&dl=GUIDE&CFID=21484757&CFTOKEN=13317159-- Doesn't look that great 1063-9535?NM.P. Allen D.J. Tildesley1987Computer Simulation of LiquidsNew YorkOxford University Press GREAT BOOK!!!?OJ. E. Barnes P. Hut19863A Hierarchical O(NlogN) Force Calculation Algorithm446-449Nature3244A novel code for the approximate computation of long-range forces between N mutually interacting bodies is presented. The code is based on a hierarchical tree of cubic cells and features mutual cell-cell interactions which are calculated via a Cartesian Taylor expansion in a symmetric way, such that total momentum is conserved. The code benefits from an improved and simple multipole acceptance criterion that reduces the force error and the computational effort. For N ~> 104, the computational costs are found empirically to rise sub-linear with N. For applications in stellar dynamics, this is the first competitive code with complexity O(N), it is faster than the standard tree code by a factor ten or more.7http://arxiv.org/PS_cache/astro-ph/pdf/0202/0202512.pdf<Origional fast multipole method.Voted in "best 10 algotihms"?PVinit Jain Ben Shneiderman1994NData Structures for Dynamic Queries: An Analytical and Experimental Evaluation1-119Proceedings of the workshop on Advanced visual interfacesDynamic Queries is a querying technique for doing range search on multi-key data sets. It is a direct manipulation mechanism where the query is formulated using graphical widgets and the results are displayed graphically preferably within 100 milliseconds.This paper evaluates four data structures, the multilist, the grid file, k-d tree and the quad tree used to organize data in high speed storage for dynamic queries. The effect of factors like size, distribution and dimensionality of data on the storage overhead and the speed of search is explored. Analytical models for estimating the storage and the search overheads are presented, and verified to be correct by empirical data. Results indicate that multilists are suitable for small (few thousand points) data sets irrespective of the data distribution. For large data sets the grid files are excellent for uniformly distributed data, and trees are good for skewed data distributions. There was no significant difference in performance between the tree structures.vhttp://80-portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=192313&coll=Portal&dl=GUIDE&CFID=21652029&CFTOKEN=74585814Says: grid best for uniform, trees better for skewed 0-89791-733-2?QR. W. Hockney J. W. Eastwood1988#Computer Simulation using Particles564Bristol, PA, USA Publisher Taylor & Francis, Inc.>http://portal.acm.org/citation.cfm?id=62815&dl=ACM&coll=portalVery good - copy at library 0-85274-392-0_?RDaan Frenkel Berend Smit1996CUnderstanding Molecular Simulation: From Algorithms to Applications443Academic PressLondon 0122673514DUnderstanding Molecular Simulation : From Algorithms to ApplicationsO?SBjarne Stroustrup2000.The C++ Programming Language (Special Edition) IndianapolisPearson EducationSpecial Edition 0-201-70073-5.The C++ Programming Language (Special Edition)The C++ Programming Languagec/?T Scott Meyers2003More Effective C++318035 New Ways to Improve Your PrograO?U Scott Meyers2003 Effective C++256550 Specific Ways to Improve Your Programs and Designs IndianapolisAddison-WesleySecond Edition 0201924889 ;ms and Designs IndianapolisAddison-Wesley 020163371X?VCharlotte Froese Fischer1977!The Hartree-Fock method for atoms3209The Hartree-Fock method for atoms : a numerical approach New YorkJohn Wiley & Sons Inc 047125990X!/CSD-98-1012.pdfnot published!F?W Loup Verlet1968dComputer "Experiments" on Classical Fluids. I. Thermodynamical Properties of Lennard-Jones MoleculesPhysical Review159?X Andrew Noske2004lMolecular Dynamics Simulation and Other Self-Spatial Join - an Engine Layer and Performance Testing Platform2004 26/11/2004%http://www.krimzon.net/~noske/thesis/GIncludes a "testing platform", with all code used in compiling results for this thesis, and also contains a minimal implementation of a "grid engine" layer (including only the most successful techniques in this thesis), which has how to use it to execute efficient molecular dynamic (or other) pair-wise interaction simulation.?Y Microsoft2004)C++ Language Reference - Data Type Ranges 8/11/2004Qhttp://msdn.microsoft.com/library/en-us/vclang/html/_langref_data_type_ranges.aspu.kr/SMS/papers/Ercolessi%20-%20MD%20Primer.pdfDhttp://diamond.kist.re.kr/SMS/papers/Ercolessi%20-%20MD%20Primer.pdfۿZDmitry Konovalov2004 TOMSK group20049/20045/2004'http://www.it.jcu.edu.au/~dmitry/tomsk/$Towards Molecular Structure Kinetics TOMSK group!http://www.it.jcu.edu.au/~dmitry/5/2004